为什么GNU grep这样快？

这是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算法，它会从目标字符串的最后一个字符开始查找，并且配合一个查找表，它可以在发现一个不匹配字符之后，计算出应该跳过后续输入中的多少个字符并继续查找。

GNU grep还展开了Boyer-Moore算法的内层循环，并设置了一个Boyer-Moore的delta表，这样它就不需要在每一个展开后的步骤进行循环退出判断了，这样的效果就是，在极限情况下，GNU grep针对每一个输入字节所执行的x86指令不会超过3条（并且它还跳过了好多字节）。

你可以看看Andrew Hume和Daniel Sunday在1991年11月的“软件实践与经验”杂志发表的“快速字符串查找”，这篇文章很好的讨论了关于Boyer-Moore算法的实现技巧，你可以在网上找到免费的PDF。

一旦你的搜索足够快了，这时你就会发现你需要同样快的输入。

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

此外，GNU grep还避免了对输入进行分行，查找换行符会让grep慢上好几倍，因为要查找换行符，你就需要去查看每一个字节。

所以取而代之，GNU grep没有使用基于行的输入，而是直接将输入读入一个大的buffer，然后使用Boyer-Moore对这个buffer进行搜索，并且只有在它发现一个匹配之后，它才会去查找最近的换行符（如果你使用了-n选项，则这个优化就没有效果了）。

最后，当我还在维护GNU grep的时候（那已经是15年前了），GNU grep还尝试了一些非常困难的事情，比如使用mmap()来取代read()从文件读取输入，从而避免内核去处理输入中的所有字节。在那时，在几乎所有的Unix版本上使用read()都会造成额外的拷贝，因为我已经不再维护GNU grep了，所以似乎现在GNU grep默认已经不使用mmap了，但是你仍然可以使用–mmap来启用它，并且在文件系统的buffer已经缓存了你要查找的数据的情况下，mmap仍然要更快一些：

$ time sh -c ‘find . -type f -print | xargs grep -l 123456789abcdef’
real 0m1.530s
user 0m0.230s
sys 0m1.357s
$ time sh -c ‘find . -type f -print | xargs grep –mmap -l 123456789abcdef’
real 0m1.201s
user 0m0.330s
sys 0m0.929s

[这里使用的输入数据是648M的MH邮件目录，包含大约41000条消息]

所以即便在今日，使用–mmap仍然可以得到20%以上的速度提升。

总结：

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

- 使用原生系统调用来建立你的输入缓冲区，避免在搜索之前进行拷贝（当然，你可以缓冲输出，因为相比输入，在grep的常用场景中，输出都要少很多，所以对输出进行拷贝还算可以接受，并且这可以避免很多小且昂贵的没有缓冲的写操作）。

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

- 做好细节（比如按页对齐缓冲区，page-aligned buffer，按页大小来读取块，也可以考虑使用mmap），这样可以帮助内核避免拷贝数据。

让程序变得更快的关键就是让它们做更少的事情，：)

致礼

Mike