问grep是如何运行得这么快的？

EN

假设你的问题是关于GNU grep的。这是作者Mike Haertel的笔记：

GNU grep速度很快，因为它避免了查看每个输入字节。

GNU grep很快，因为它对所查看的每个字节执行很少的指令。

GNU grep使用著名的Boyer-Moore算法，该算法首先查找目标字符串的最后一个字母，并使用查找表告诉它，只要找到不匹配的字符，就可以在输入中跳过多远。

GNU grep还展开Boyer-Moore的内部循环，并以这样的方式设置Boyer-Moore增量表条目，这样它就不需要在每个展开的步骤都执行循环退出测试。其结果是，在限制中，GNU grep对于它实际查看的每个输入字节平均执行的x86指令少于3条(并且它完全跳过了许多字节)。

GNU grep使用原始Unix输入系统调用，并避免在读取数据后复制数据。此外，GNU grep避免将输入拆分成行。查找换行符将使grep减慢数倍，因为要找到换行符，它必须查看每个字节！

因此，GNU grep不使用面向行的输入，而是将原始数据读入大型缓冲区，使用Boyer-Moore搜索缓冲区，只有在找到匹配项时，它才会继续查找边界换行符(某些命令行选项，如-n，将禁用此优化)。

这个答案是取自here的信息的一个子集。

为史蒂夫的精彩回答再添一笔。

这可能不是广为人知的，但grep几乎总是更快的时，更长的模式串比短的，因为在更长的模式中，Boyer-Moore可以以更大的步幅向前跳跃，以获得更好的次线性速度：

示例：

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

较长的表单快35%！

怎么会这样?Boyer-Moore从pattern-string构造一个跳转表，当出现不匹配时，它会在将输入中的单个字符与跳过表中的字符进行比较之前，选择可能的最长跳过(从最后一个字符到第一个字符)。

这是a video explaining Boyer Moore (归功于kommradHomer)

另一个常见的误解(对于GNU grep)是认为fgrep比grep更快。fgrep中的f不代表'fast'，它代表'fixed‘(参见手册页)，而且由于这两个程序都是同一个程序，并且都使用Boyer-Moore，所以在搜索没有regexp特殊字符的固定字符串时，它们之间的速度没有差别。我使用fgrep的唯一原因是，当有一个regexp特殊字符(如.、[]或*)时，我不希望它被解释为这样。而且，与fgrep相比，更易移植/更标准的grep -F形式更受欢迎。