FreeBSD - The Power To Serve

why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。

  1. GNU grepは入力バイトのすべてをチェックするようなことは避けている。
  2. GNU grepはバイトごとに適用する操作を極力最小限に減らしている。
  3. GNU grepはBoyer-Mooreアルゴリズムとルックアップテーブルを使って一致しない場合には処理を飛ばしている。
  4. GNU grepはBoyer-Mooreアルゴリズムの内部ループを展開するとともに、展開時にループ終了テストが必要ない場合にはBoyer-Mooreデルタテーブルエントリを活用している。
  5. GNU grepのBoyer-Mooreアルゴリズムの実装にはAndrew Hume氏およびDaniel Sunday氏の論文"Fast String Searching [PDF]"が参考になる。
  6. GNU grepは低レベルUNIX入力システムコールを使って不要なデータのコピーを避けている。
  7. GNU grepは改行コード区切りでデータを取得しないことで高速化を実現している。
  8. GNU grepは大きなバッファにまとめてデータを読み込み、その領域内でBoyer-Mooreアルゴリズムを使った検索を実施している。
  9. GNU grepではread(2)の代わりにmmap(2)を使って不要なコピーを減らす実装も提供しており(--mmap)、こちらの方がさらに高速に動作する。

こうした実装を踏まえ、BSD grep(1)を高速化するためのまとめとして次の項目を紹介している。

  • Boyer-Mooreアルゴリズムを使うとともに、内部ループは数回に渡って展開する。
  • 低レベルシステムコールで入力を実施し、検索するよりも前に入力データのコピーが発生することを避ける。
  • 一致する前の段階で改行コードを探すようなことはしない。
  • ページアラインバッファ、ページサイズ読み込み、mmap活用などカーネルレベルでもコピーが最小限になるように工夫する。

FreeBSDでは現在、GPLライセンスのツールをBSDライセンスで開発して置き換える取り組みが進められている。組み込み用途で採用するにあたってGPLを嫌う向きが多いためだ。why GNU grep is fastから続く一連のスレッドでは、memchr()がボトルネックになること、その改善版を開発していること、複数のストラテジを適用することが適切であること、固定検索文字向けのBoyer-Mooreアルゴリズムを正規表現に適用するとはどういったことかなど、興味深いやりとりが掲載されている。

BSDライセンス版のgrep(1)はGabor Kovesdan氏によって開発が進められておりFreeBSD開発版ブランチにマージされている。さまざま改善が取り組まれているがGNU grep(1)と比較してBSD grep(1)はパフォーマンスが発揮できない点が指摘されていた。Gabor Kovesdan氏は指摘を受けて改善点をまとめるとともに、より優れた正規表現ライブラリが必要だと説明。OSSとしてはGNU libregex、鬼車、PCRE 、Google RE2などいくつか候補があるが、BSDライセンスのもとで開発されwcharに対応しPOSIXにも準拠、さらに処理が高速なPlan9 TRE適切ではないかと意見がまとめられている。