为什么GNU grep如此之快？

winston

本文由 伯乐在线 - 敏敏 翻译自 FreeBSD Mailing Lists。欢迎加入技术翻译小组。转载请参见文章末尾处的要求。

编注：这是GNU grep的原作者Mike Haertel 在FreeBSD邮件列表中对 “GNU grep为什么比BSD grep要快” 所做的回答，下面是邮件正文内容：

Gabor 您好，

我是GNU grep的原作者，同时也是一名FreeBSD用户，不过我一直使用的是-stable版本（也就是更老的版本），而没怎么关注-current版本。

但是，当我无意间翻阅-current版的邮件列表时，偶然发现了一些关于BSD grep与GNU grep性能的讨论，你可能也注意到了那些讨论。

不管怎么说，仅供参考吧，下面是一些简单的总结，关于为什么GNU grep如此之快。或许你能借鉴其中的一些思想运用到BSD grep中去。

#技巧1：GNU grep之所以快是因为它并不会去检查输入中的每一个字节。

#技巧2：GNU grep之所以快是因为它对那些的确需要检查的每个字节都执行非常少的指令（操作）。

GNU grep使用了非常著名的Boyer-Moore算法（译者注：BM算法，是一种非常高效的字符串搜索算法，一般情况下，比KMP算法快3-5倍，具体可查看这篇讲解非常详细的文章：grep之字符串搜索算法Boyer-Moore由浅入深（比KMP快3-5倍）），该算法首先从目标字符串的最后一个字符开始查找，并且使用一个查找表，它可以在发现一个不匹配字符之后，计算出可以跳过多少个输入字符并继续查找。

GNU grep还展开了Boyer-Moore算法的内部循环，并建立了一个Boyer-Moore的delta表，这样它就不需要在每一个展开的步骤进行循环退出判断了。这样的结果就是，在极限情况下（in the limit），GNU grep在需要检查的每一个输入字节上所执行的x86指令不会超过3条（并且还跳过了许多字节）。

你可以看看由Andrew Hume和Daniel Sunday 1991年11月在“Software Practice & Experience”上发表的论文“Fast String Searching”，该文很好的讨论了Boyer-Moore算法的实现技巧，该文有免费的PDF在线版（译者注：点这里查看或下载）。

一旦有了快速搜索，这时你会发现也需要同样快速的输入。

GNU grep使用了原生Unix输入系统调用并避免了在读取后对数据进行拷贝。

而且，GNU grep还避免了对输入进行分行，查找换行符会让grep减慢好几倍，因为要找换行符你就必须查看每个字节！

所以GNU grep没有使用基于行的输入，而是将原数据读入到一个大的缓冲区buffer，用Boyer-Moore算法对这个缓冲区进行搜索，只有在发现一个匹配之后才会去查找最近的换行符（某些命令参数，比如-n会禁止这种优化）。

最后，当我还在维护GNU grep的时候（15+年前……），GNU grep也尝试做一些非常困难的事情使内核也能避免处理输入的每个字节，比如使用mmap()而不是read()来进行文件输入。当时，用read()会使大部分Unix版本造成一些额外的拷贝。因为我已经不再GNU grep了，所以似乎mmap已经不再默认使用了，但是你仍然可以通过参数–mmap来启用它，至少在文件系统的buffer已经缓存了你的数据的情况下，mmap仍然要快一些：

1. $ time sh -c 'find . -type f -print | xargs grep -l 123456789abcdef'
2.   real  0m1.530s
3.   user  0m0.230s
4.   sys   0m1.357s
5. $ time sh -c 'find . -type f -print | xargs grep --mmap -l 123456789abcdef'
6.   real  0m1.201s
7.   user  0m0.330s
8.   sys   0m0.929s

复制代码

[这里使用的输入是一个648M的MH邮件文件夹，包含大约41000条信息]

所以即使在今天，使用–mmap仍然可以提速20%以上。

总结：

- 使用Boyer-Moore算法（并且展开它的内层循环）。

- 使用原生系统调用来建立你的缓冲输入，避免在搜索之前拷贝输入字节。（无论如何，最好使用缓冲输出，因为在grep的常用场景中，输出的要比输入的少，所以输出缓冲拷贝的开销要小，并且可以节省许多这样小的无缓冲写操作。）

- 在找到一个匹配之前，不要查找换行符。

- 尝试做一些设置（比如页面对齐缓冲区，按页大小来读取块，选择性的使用mmap），这样可以使内核避免拷贝字节。

让程序变得更快的关键就是让它们做更少的事情。;-)

致礼

Mike

原文链接： FreeBSD Mailing Lists   翻译： 伯乐在线- 敏敏
译文链接： http://blog.jobbole.com/52313/

minchieh

字符流运算    ace中有