为什么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),这样可以使内核避免拷贝字节。

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

原文发布时间为:2013-12-05

本文来自合作伙伴“Linux中国”

时间: 2024-09-27 02:59:12

为什么GNU grep如此之快?的相关文章

grep为何如此之快

下面是GNU grep的原作者MikeHaertel 在FreeBSD邮件列表中对 "GNU grep为什么比BSD grep要快" 这个问题所做的回答,解释了grep是如何进行快速搜索的,下面是邮件正文内容: why GNU grep is fast Mike Haertel mike at ducky.net Sat Aug 21 03:00:30 UTC 2010 •     Previous message: Latest intr problems •     Next me

运维中搜索工具Grep, Ack, Ag的效率比较【附图】

前言 我经常看到很多程序员, 运维在代码搜索上使用ack, 甚至ag(the_silver_searcher ), 而我工作中95%都是用grep,剩下的是ag. 我觉得很有必要聊一聊这个话题. 我以前也是一个运维, 我当时也希望找到最好的最快的工具用在工作的方方面面. 但是我很好奇为什么ag和ack没有作为linux发行版的内置部分. 内置的一直是grep. 我当初的理解是受各种开源协议的限制, 或者发行版的boss个人喜好. 后来我就做了实验, 研究了下他们到底谁快. 当时的做法也无非跑几个

何不 Ack?Grep, Ack, Ag的搜索效率对比

何不 Ack?Grep, Ack, Ag的搜索效率对比 前言 我(@董伟明9 )经常看到很多程序员, 运维在代码搜索上使用ack, 甚至ag(the_silver_searcher ), 而我工作中95%都是用grep,剩下的是ag. 我觉得很有必要聊一聊这个话题. 我以前也是一个运维, 我当时也希望找到最好的最快的工具用在工作的方方面面. 但是我很好奇为什么ag和ack没有作为linux发行版的内置部分. 内置的一直是grep. 我当初的理解是受各种开源协议的限制, 或者发行版的boss个人喜

全面解析Linux的grep命令中正则表达式的用法

  Linux 附带有 GNU grep 命令工具,它支持扩展正则表达式extended regular expressions,而且 GNU grep 在所有的 Linux 系统中都是默认有的.Grep 命令被用于搜索定位存储在您服务器或工作站上的任何信息. 正则表达式 正则表达式就是用于匹配每行输入的一种模式,模式是指一串字符序列.下面是范例: 代码如下: ^w1 w1|w2 [^ ] grep 正则表达式示例 在 /etc/passswd 目录中搜索 'vivek' 代码如下: grep

快速掌握grep命令及正则表达式

Linux系统自带了支持拓展正则表达式的 GNU 版本 grep 工具,所有的Linux发行版中均默认安装grep ,grep 命令被用来检索一台服务器或工作站上任何位置的文本信息,如何在 Linux 系统和类 Unix 的操作系统中使用带正则表达式的 grep 命令呢? 快速了解正则表达式 1.如何匹配你要查找的内容? 正则表达式只不过是每个输入行匹配的模式. 在 '/etc/passswd' 中检索 'vivek' . grep vivek /etc/passwd  输出结果案例: vive

grep 命令系列:grep 中的正则表达式

grep 命令系列:grep 中的正则表达式 在 Linux .类 Unix 系统中我该如何使用 Grep 命令的正则表达式呢? Linux 附带有 GNU grep 命令工具,它支持扩展正则表达式extended regular expressions,而且 GNU grep 在所有的 Linux 系统中都是默认有的.Grep 命令被用于搜索定位存储在您服务器或工作站上的任何信息. 正则表达式 正则表达式就是用于匹配每行输入的一种模式,模式是指一串字符序列.下面是范例: ^w1 w1|w2 [

删除一个目录下的所有文件但保留一个指定文件

原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 .作者信息和本声明.否则将追究法律责任.http://dgd2010.blog.51cto.com/1539422/1735050 之前看过oldboy(老男孩)前辈的一篇文章<linux面试题:删除一个目录下的所有文件,但保留一个指定文件>,近日终于有机会得以验证,但与老男孩前辈的文章中具体讲的有些不太一样,故而专门写一篇文章重新整理这个问题.虽然是同一个话题,和同一种思路,但细节上有一定的差别. 需求: 删除一个目录下的所有文

无需Ptrace就能实现Linux进程间代码注入

本文讲的是无需Ptrace就能实现Linux进程间代码注入, ptrace系统调用 ptrace系统调从名字上看是用于进程跟踪的,它提供了父进程可以观察和控制其子进程执行的能力,并允许父进程检查和替换子进程的内核镜像(包括寄存器)的值.其基本原理是: 当使用了ptrace跟踪后,所有发送给被跟踪的子进程的信号(除了SIGKILL),都会被转发给父进程,而子进程则会被阻塞,这时子进程的状态就会被系统标注为TASK_TRACED.而父进程收到信号后,就可以对停止下来的子进程进行检查和修改,然后让子进

Linux Shell脚本之远程自动化部署java maven项目

原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 .作者信息和本声明.否则将追究法律责任.http://dgd2010.blog.51cto.com/1539422/1771555 脚本功能: 检查运行环境(包括运行权限.网络.DNS解析等),自动从git上获取java maven项目工程源码,在机器A上build,build完成后,备份机器B上原有的配置文件(如果存在),将Class.Lib文件和备份的配置文件等上传到机器B,重新启动机器B上的服务以便变更生效. 脚本特点: 1.