为什么 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 算法（译者注：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 仍然要快一些：

$ 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 的常用场景中，输出的要比输入的少，所以输出缓冲拷贝的开销要小，并且可以节省许多这样小的无缓冲写操作。）

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

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

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

致礼

Mike