为什么 GNU grep 如此之快?

oschina
 oschina
发布于 2013年12月05日
收藏 185

编注:这是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

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

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处,尊重他人劳动共创开源社区。
转载请注明:文章转载自 OSCHINA 社区 [http://www.oschina.net]
本文标题:为什么 GNU grep 如此之快?
加载中

最新评论(31

大哥哥
大哥哥
专注,专业,科学这种态度值得尊敬
燃灯
燃灯

引用来自“emacsen”的评论

引用来自“燃灯”的评论

引用来自“木有文化”的评论

引用来自“YiseNet”的评论

我也想知道mac os的spotlight是怎么实现的,对整个硬盘文件的搜索也就瞬间

预先建立了索引。。。

linux 也可以建立索引数据库实现瞬间搜索

为毛Linux不能实时updatedb,但是 Windows下的小软件everything却可以

可能出于性能考虑吧,everything硬盘读写很频繁的。
emacsen
emacsen

引用来自“燃灯”的评论

引用来自“木有文化”的评论

引用来自“YiseNet”的评论

我也想知道mac os的spotlight是怎么实现的,对整个硬盘文件的搜索也就瞬间

预先建立了索引。。。

linux 也可以建立索引数据库实现瞬间搜索

为毛Linux不能实时updatedb,但是 Windows下的小软件everything却可以
NickWilde
NickWilde
让程序变得更快的关键就是让它们做更少的事情。;-)
工程师爸爸
工程师爸爸
文章作者态度非常值得尊敬 赞1
社会你大哥
社会你大哥
高大上
lingxi27
lingxi27
译者是个小菇凉
haitaosoft
haitaosoft
刚刚看到:http://blog.jobbole.com/52669/
【注意:由于Boyer-Moore(BM)自右向左做匹配,有一种可能性是一个匹配分布在不同的块中,这种情况下是不能找到任何匹配的。

如果你想确保这样的事情不会发生,使用Knuth-Pratt-Morris(KMP)算法来替代】
nirvanawgw
nirvanawgw
locate 也很快呀
高跟男爵
高跟男爵
上午在右边模块,中午跑到左边了。
说明osc的左边比右边更有关注度。
返回顶部
顶部