logo标签列表

strstr比算法更快吗？

cperformancealgorithmstring-matchingstrstr
20

我有一个大小为21056字节的文件。

我用C语言编写了一个程序，将整个文件读入缓冲区，然后使用多个搜索算法在文件中搜索长度为82个字符的标记。

我使用了“Exact String Matching Algorithms”页面上所有算法的实现。我使用了：KMP、BM、TBM和Horspool算法。然后我使用了strstr函数并对每个算法进行了基准测试。

我的疑问是，每次strstr函数都比其他算法表现更好。唯一比它更快的是BM算法。

难道strstr函数不应该是最慢的吗？

这是我的基准测试代码，并且有一个BM算法的基准测试示例：

double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}


before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);

有人能解释一下为什么strstr比其他搜索算法表现更好吗？如果需要，我可以在请求时发布更多代码。

2
错误在你的代码中。至少Horspool算法应该始终优于strstr函数 - KMP算法实际上可能会更慢。但由于你没有发布你的代码，我们无法帮助你。话虽如此，你可以有意选择数据使得朴素搜索算法获胜，因此输入数据的选择也很重要。 - Konrad Rudolph
你是认真在对一个20k字符串进行搜索，以找到一个80字节的字符串吗？你的样本大小如此之小，你甚至可以用手做！ - Blindy
4个回答
32
为什么你认为strstr应该比其他函数慢？你知道strstr使用的是哪种算法吗？我认为很可能strstr使用了经过精细调整、特定于处理器、用汇编编写的KMP类型或更好的算法。如果是这种情况，在这样小的基准测试中，你无法在C中超越它。
（我认为这很可能是因为程序员喜欢实现这些东西。）
2
@Josh，它确实有用，不要被误导。 - Konrad Rudolph
7
glibc的实现。虽然不是汇编语言，但我相信它经过了大量的优化。 - Piotr Praszmo
4
@Josh: 这并不是这样的，不要被误导了！ - TonyK
2
@Banthar 令我惊讶的是，我确实看过多个 strstr 实现（在过去几年里，我也曾广泛地研究字符串搜索实现），而我看到的每个实现都是朴素搜索-顺便说一句，这是一个好选择（参见上文）。我也很惊讶他们用 BM 而不是 Horspool 进行长指针的搜索，因为后者在典型情况下平均表现更好（同样，请参见上文）。 - Konrad Rudolph
4
@Konrad：啊，我看到我链接的页面上的算法描述有点令人困惑。但它确实是一个无弱点的算法：时间复杂度为常数，空间复杂度为线性。它的存在应该得到更好的认识和赞赏！ :) 而且，它就在它应该在的地方：在strstr()库实现中。 :) - j_random_hacker
显示剩余17条评论
20
Horspool、KMP等算法在最小化字节比较数量方面是最优的。但是，在现代处理器上，这不是瓶颈。在x86/64处理器上，您的字符串以缓存行宽度块（通常为64个字节）的形式加载到L1高速缓存中。无论您的算法有多聪明，除非它给您比这更大的步幅，否则您将一无所获；而更复杂的Horspool代码（至少需要一个表查找）无法竞争。此外，您被限制为C字符串约束：代码必须检查每个字节。strstr()预计在广泛范围的情况下是最佳的；例如，在短字符串中搜索像"\r\n"这样的小字符串，以及在一些更智能的算法可能有希望的更长字符串中进行搜索。基本的strchr/memcmp循环在整个可能输入的范围内都很难被击败。自2003年以来，几乎所有兼容x86的处理器都支持SSE2。如果您反汇编了glibc的strlen()/x86，您可能已经注意到它使用一些SSE2 PCMPEQ和MOVMASK操作以每次16个字节地搜索空终止符。该解决方案非常有效，对于任何长于空字符串的内容都能超过明显的超级简单循环。我采用了这个想法，并提出了一个strstr()，它在所有大于1个字节的情况下都能击败glibc的strstr()，其中相对差异几乎无关紧要。如果您有兴趣，请查看：

顺便说一句，您可能已经发现x86 REP SCASB/REP CMPSB操作在超过32字节的情况下效果很差，对于较短的字符串也没有太大改善。希望英特尔能花更多精力去解决这个问题，而不是添加SSE4.2“字符串”操作。

对于足够重要的字符串，我的性能测试表明BNDM在全面上优于Horspool。BNDM对“病态”情况更加容忍，例如目标频繁重复模式的最后一个字节。BNDM还可以以与32位寄存器相当的效率和启动成本使用SSE2（128位寄存器）。源代码 此处。

2
你尝试过向glibc提交补丁吗？当然，这需要对各种不同输入进行仔细的基准测试，但你上面的解释似乎是合理的。 - Konrad Rudolph
鉴于缓存优化，尝试使用Horspool超越朴素搜索是否浪费时间？ - mikew
@Mischa，有什么建议可以告诉我如何在Windows上编译这段代码吗？我不知道ffs是什么以及在哪里获取它。 - user626528
哇，非常抱歉我没有回答那个问题。记录一下，MSVC的等效函数是_BitScanForward()，但它有点笨重。我将其包装为以下形式（请原谅注释中的代码，O编辑器）：static inline uint32_t intlowz(uint32_t x) { uint32_t pos; return x ? (_BitScanForward(&pos, x), pos) : 32; } - Mischa
3
没有看到您的代码，很难准确地说。 strstr 是经过大量优化的，通常是用汇编语言编写的。它会读取4个字节的数据并进行比较(如果对齐不正确，则可能进行位操作以使其对齐)，以最小化内存延迟。 它还可以利用SSE等技术一次加载16个字节。 如果您的代码一次只加载一个字节，那么它可能会被内存延迟击败。
请使用调试器并逐步浏览 strstr 的反汇编结果--您可能会发现一些有趣的东西。
1
非常遗憾，4字节比较和SSE对字符串搜索的影响相当有限，因为元素之间存在线性依赖关系。特别是，您不能只在非重叠的4字节块中进行比较：即使您一次比较4个字节，仍然需要比较重叠的块，而不会获得太多优势。 - Konrad Rudolph
@Konrad：strstr基本上可以实现为围绕strchr和strcmp/memcmp的循环（其中memcmp需要一个初始的strlen）。strchr可以通过一些位操作技巧和进行4字节加载来实现。memcmp可以从两个比较对象中每次加载4个字节并比较这些单词。如果两个操作数没有相同的对齐方式，您需要同时跟踪两个单词并进行位操作以获取要与另一个字符串进行比较的不对齐单词。例如，请参见glibc中的sysdeps/x86_64/memcmp.S。 - Adam Rosenfield
@Konrad：通过将模式的前4个字节与一个4字节滑动窗口进行比较，将下一个目标字符串字节插入到32位字的底部并进行移位，您可以获得一些东西。这不是您所希望的那么多，因为在同一寄存器上混合8位和32位指令会使指令流水线停顿。SSE则完全不同：您可以将目标字符串的16个字节与模式的第一个字节进行比较，并复制16次。这真的很棒。请参见我下面的文章，了解更多详细信息。 - Mischa
2
想象一下你想要清洁某个东西。你可以自己清洁它，或者你可以雇用十名专业清洁工人来清洁它。如果清洁的工作是一个办公楼，后者更可取。如果清洁工作只涉及一个窗户，前者更可取。
因为这项工作不需要花费太长时间，所以你从未因为花费时间高效地完成工作而得到任何回报。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接