strstr比算法快？

我有一个21056字节的文件。

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

我已经使用了“精确字符串匹配算法”页面中所有算法的实现。我用过：KMP，BM，TBM和Horspool。然后我使用strstr并对每个人进行基准测试。

我想知道的是，每次strstr优于所有其他算法。有时候唯一更快的是BM。

不应该是最慢的吗？

这是我的基准代码，其中包含基准测试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优于其他搜索算法吗？如果需要，我会根据请求发布更多代码。

为什么你认为strstr应该比其他所有人慢？你知道strstr使用什么算法吗？我认为strstr很可能使用KMP类型或更好的微调，处理器特定的汇编编码算法。在这种情况下，对于如此小的基准测试，你没有机会在C表现出色。

（我认为这很可能是因为程序员喜欢实现这样的东西。）

Horspool，KMP等人在最小化字节比较次数方面是最佳的。

但是，这不是现代处理器的瓶颈。在x86 / 64处理器上，您的字符串将以高速缓存行宽度块（通常为64字节）加载到L1高速缓存中。无论你的算法多么聪明，除非它给你的步幅大于那个，你什么都得不到; 而更复杂的Horspool代码（至少有一个表查找）无法竞争。

此外，你仍然坚持使用null-termination的“C”字符串约束：SOMEWHERE代码必须检查每个字节。

strstr()预计将适用于各种情况; 例如，在短字符串中搜索像"\r\n"的小字符串，以及在某些更智能的算法可能有希望的情况下搜索更长的字符串。基本的strchr / memcmp循环很难在整个可能的输入范围内击败。

几乎所有x86兼容处理器自2003年以来都支持SSE2。如果你为glibc反汇编strlen() / x86，你可能已经注意到它使用一些SSE2 PCMPEQ和MOVMASK操作来一次搜索16个字节的空终止符。该解决方案非常有效，它可以胜过明显的超简单循环，比空字符串更长。

我接受了这个想法并提出了一个strstr() ，它可以胜过glibc的strstr()适用于大于1个字节的所有情况—相对差异几乎没有实际意义。如果您有兴趣，请查看：

收敛SSE2和strstr()
没有ASM代码的更好的strstr()

如果您想看到一个超过15个字节的目标字符串支配strstr()的非SSE2解决方案，请查看：

它使用多字节比较而不是strchr()来找到执行memcmp的点。

顺便说一句，你现在可能已经想到x86 REP SCASB / REP CMPSB操作对于长度超过32字节的任何操作都会出现问题，并且对于较短的字符串没有太大的改进。希望英特尔更多关注这一点，而不是添加SSE4.2“字符串”操作。

对于足够重要的字符串，我的性能测试显示BNDM全面胜过Horspool。 BNDM更能容忍“病态”情况，例如重复重复模式的最后一个字节的目标。 BNDM还可以以与32位寄存器竞争效率和启动成本的方式使用SSE2（128位寄存器）。源代码在这里。

没有看到你的代码，很难说清楚。 strstr经过大量优化，通常用汇编语言编写。它执行的操作包括一次读取4个字节的数据并比较它们（如果对齐不正确，必要时进行比特）以最小化内存延迟。它也可以利用像SSE这样的东西一次加载16个字节。如果您的代码一次只加载一个字节，它可能会被内存延迟所杀死。

使用你的调试器并逐步完成strstr的反汇编 – 你可能会在那里找到一些有趣的东西。

想象一下，你想要清理一些东西。你可以自己清理它，或者你可以聘请十个专业清洁工来清理它。如果清洁工作是办公楼，则后一种解决方案更可取。如果清洁工作是一个窗口，前者将是更可取的。

由于工作不需要很长时间，因此您在设置高效工作所花费的时间上永远无法获得任何回报。