為什麼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），這樣可以使核心避免拷貝位元組。

讓程式變得更快的關鍵就是讓它們做更少的事情。;-)

緻禮

Mike