strstr比算法快？

Question

我有一个21056字节的文件.

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

我已经使用了"精确字符串匹配算法"页面中所有算法的实现.我用过: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表现优于其他搜索算法吗？如果需要,我会根据请求发布更多代码.

Answer 1

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

(我认为这很可能是因为程序员喜欢实现这样的东西.)

Answer 2

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

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

此外,你仍然坚持使用null-termination的"C"字符串约束:SOMEWHERE代码必须检查每个字节.

strstr()预计对于各种病例都是最佳的; 例如,搜索"\r\n"短字符串中的小字符串,以及更长的字符串,其中一些更智能的算法可能有希望.基本的strchr/memcmp循环很难在整个可能的输入范围内击败.

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

我接受了这个想法并提出了一个比所有大于1字节的情况更好的strstr()glibc's strstr()---其中相对差异几乎没有实际意义.如果您有兴趣,请查看:

• 融合SSE2和 strstr()

• strstr()没有ASM代码更好

  如果您想看到一个strstr()超过15字节的目标字符串占主导地位的非SSE2解决方案,请查看:

  它使用多字节比较而不是strchr()找到做memcmp的点.

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

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