先日、社内で highway のアーキテクチャの話をする機会があったので、スライドを作って話しました。秘密情報というわけでもないので、せっかくなので公開したいと思います。ということで、この記事では highway のアーキテクチャを簡単に紹介します。C で実装されており、実装にあたっては既存のツールよりも高速に動作させるためにいくつもの工夫をしたので highway の内部がどうなっているのか興味がある方は読んでみると面白いかもしれません。
highway についての詳細はこちら。
資料
以下、補足や簡単な説明などをつらつらと。
文字列探索アルゴリズム
highway ではリテラルによる検索は、以下の論文を参考に実装しています。
A simple fast hybrid pattern-matching algorithm
通称 FJS 法と呼ばれるこのアルゴリズムは Boyer-Moore と Knuth–Morris–Pratt をベースにしています。Boyer-Moore と Knuth-Morris-Pratt についてはスライド内で解説していますが、FJS についてはアルゴリズム開発者の一人である Jennings さんの Web サイトで Java アプレットを使ったデモを公開しており、実際にどのように検索が進んでいくのかがとてもわかりやすく可視化されていますので、動作の解説はそちらにおまかせしました。是非以下の URL から覗いてみてください。
また、スライドには書いてありませんが highway は正規表現による検索もサポートしており、その部分には OSS の正規表現ライブラリである Onigmo(鬼雲) を利用しています。
マルチスレッド
highway はマルチスレッドで動作し、内部は以下の要素で構成されます。
メインスレッド
検索対象ファイルを再帰的に探索し、
.gitignoreの無視パターンを加味しつつ、対象ファイルをキューに追加していくのが仕事です。ファイルキュー
検索対象ファイルが溜まっていくキューです。他の全てのスレッドからアクセスされるため、キューへのアクセスは排他制御されています。
検索スレッド
1 ファイルの検索処理が 1 スレッドに割り当てられます。スレッドはキューの先頭にあるファイルを取り出して検索し、処理がが完了するとキューのアイテムに対して探索済みのフラグを付与します。
出力スレッド
キューの先頭からアイテムを取り出し、そのアイテムが探索済みであれば結果を出力します。キューの先頭のアイテムに探索済みフラグがついていなければ、そのアイテムにフラグがつくまで待ち状態となります。
また highway では探索済みフラグによって、マルチスレッドでありながら検索結果の出力順が実行毎に変わらないように制御されています。
ファイルのスキップ
ファイルの先頭から 512 バイトを見て、ヌルバイトがあったり存在しない文字コードが 1 割以上あるとバイナリと判定します。各文字エンコーディングでは、それぞれ以下のようなテーブルを持っているのでそれを元に判定します。
また .gitignore の無視パターンは検索対象に含めないようになっています。この辺りはハッシュテーブルと単方向リストを使った実装になっており、なるべく高速に処理できるよう工夫しています。ちなみに、git 自体はどうやって .gitignore をチェックしているんだろうと思ってソースを読んでみたのですが、たぶん普通にリストに保持して全パターンチェックしてます。
ディスク I/O
通常、ファイル中のパターン検索といえば行毎に結果を出力するので、ファイルから 1 行ずつ読み込んでその中にパターンがあるかどうかを調べてあれば出力、という風に作るのが最も簡単です。ただ 1 行毎にファイルから読み込むのは都度 IO が発生してしまうのでそれなりに遅くなってしまいます。改行は気にせずに大きなバッファを用意してそのバッファのサイズ分ずつ読み込んで検索処理を進めていき、改行の検索や行番号の計算はメモリ上でやるようにすれば IO が減ってより高速になります。実装レベルの話だと fgets(3) などは使わずにシステムコールの open(2) と read(2) を使ってファイル内容を読み込んでいきます。
その他
スライドには書いていませんが、他に細かい工夫をいくつかやっています。
まず、検索結果を出力する際にはマッチ位置がわかりやすいようにエスケープシーケンスによるカラーリングを行いますが、背景色をつける場合はつけない場合に比べて出力が遅くなるので hw では背景色を使わないようにしました。
また highway では出力に printf(3) を使いますが、その都度出力するよりもある程度バッファに溜め込んでおき、一気に出力するようにした方が速くなります。ご存知の通り printf(3) はデフォルトでバッファリングをやってくれますがそのサイズが 1KB と少し小さいのでこれを setvbuf(3) を使ってもっと大きなバッファを設定してあげます。検索結果の量が多い場合などはより速くなります。
それともうひとつ、メモリ確保には通常 glibc の malloc(3) や calloc(3) を利用しますが、より高速でマルチスレッドフレンドリーな tcmalloc というライブラリが Google によって開発されています。highway ではメモリ確保に tcmalloc を利用することで高速化を図っています。ただし、標準ではないのでコンパイル時に tcmalloc のライブラリが必要になります。
まとめ
スライドでは文字列探索アルゴリズムを一番最初に紹介して、それが highway を開発するきっかけになったと説明していますが、実際には文字列探索は複雑なアルゴリズムを使わない力技でも十分に高速です。なので文字列探索アルゴリズムが全体的なスピードアップに寄与している割合は実はそんなに高くなかったりします。高速化は地道な努力の積み重ねで実現されています。
いかがでしたでしょうか。特別に変なことはやってないので、そんなに難しくはなく、誰もが実装できるような内容だと思います。OSS が活発な現在、公開されているソースコードから色々なノウハウを自分のために取り込むことが当たり前のようにできます。実際に highway も ag や pt、sift、ack などのコードを参考にしました。
活発に OSS 活動していこう。
