资讯专栏INFORMATION COLUMN

为什么GNU grep如此之快?

Joyven / 2842人阅读

摘要:不管怎么说,仅供参考吧,下面是一些简单的总结,关于为什么如此之快。技巧之所以快是因为它并不会去检查输入中的每一个字节。使用了原生输入系统调用并避免了在读取后对数据进行拷贝。在找到一个匹配之前,不要查找换行符。

编注:这是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 翻译: 伯乐在线 - 敏敏

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/7429.html

相关文章

  • 轻量级 memcached缓存代理 twemproxy实践

    摘要:本文内容脑图如下文章共字,阅读大约需要分钟概述是开源的轻量级代理服务器,本质就是一个集群管理工具,主要用来弥补和对集群管理的不足,其完成的最大功劳就是通过在后端减少同缓存服务器的连接数从而增加吞吐量。本文先实践一波让来一群小弟时的工作情况。 showImg(https://segmentfault.com/img/remote/1460000017056459); 本文内容脑图如下: ...

    ninefive 评论0 收藏0
  • 轻量级 memcached缓存代理 twemproxy实践

    摘要:本文内容脑图如下文章共字,阅读大约需要分钟概述是开源的轻量级代理服务器,本质就是一个集群管理工具,主要用来弥补和对集群管理的不足,其完成的最大功劳就是通过在后端减少同缓存服务器的连接数从而增加吞吐量。本文先实践一波让来一群小弟时的工作情况。 showImg(https://segmentfault.com/img/remote/1460000017056459); 本文内容脑图如下: ...

    Dogee 评论0 收藏0
  • 关于Python的未来

    摘要:社区的需求将影响语言未来的发展方向,基金会前任主任,核心开发人员,研究软件工程师我想我们将继续看到的科学编程部分的增长。作为一种语言的另一个惊人的优势在于,新的开发人员可以轻松地进入,轻松的学习并快速提高工作效率。 showImg(https://segmentfault.com/img/remote/1460000018949569); 来源 | 愿码(ChainDesk.CN)内...

    Apollo 评论0 收藏0
  • Bash Cookbook 学习笔记 【中级】

    摘要:本文是以英文版为基础整理的笔记,力求脱水更新完中级。空格被默认作各列的分隔符,也可以通过开关进行自定义。这样的数组也叫作关联数组,或称为映射,或者是哈希表。空行表示段落的结束会匹配空行。 showImg(https://segmentfault.com/img/bVZARf?w=314&h=413); Read Me 本文是以英文版 为基础整理的笔记,力求脱水 2018.01.21 ...

    frank_fun 评论0 收藏0
  • Bash Cookbook 学习笔记 【中级】

    摘要:本文是以英文版为基础整理的笔记,力求脱水更新完中级。空格被默认作各列的分隔符,也可以通过开关进行自定义。这样的数组也叫作关联数组,或称为映射,或者是哈希表。空行表示段落的结束会匹配空行。 showImg(https://segmentfault.com/img/bVZARf?w=314&h=413); Read Me 本文是以英文版 为基础整理的笔记,力求脱水 2018.01.21 ...

    ckllj 评论0 收藏0

发表评论

0条评论

Joyven

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<