為什么 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仍然要快一些：