いまや grep、ack、ag、pt、sift など様々な grep ツールが存在し、高速 grep ツール戦線が激化している昨今ですが、いかがお過ごしでしょう。私は普段から検索ツールには pt を使っていますが、ふとしたことから文字列探索アルゴリズムに興味がわいてきて highway という高速パターンマッチングツールを開発しました。pt や sift が流行りの Go 言語で実装されている中、我が道を行く highway は C 言語での実装にしました (単に Go 言語を知らないだけとも言う＼(^o^)／)。

highway (github)

highway とは

マルチスレッドで動作する高速パターンマッチングツールです。速そうな名前をつけたくて「高速」でググったら「高速道路」がたくさん出てきたのでこの名前になりました。そりゃそうだ。

機能

基本的な機能としては pt とほぼ同じです。しかし速度については pt 以上かな、と。

• ag / pt / sift 相当(もしくはそれ以上) の速度でのパターンマッチング。
• 正規表現での検索。
• UTF-8 以外に EUC-JP と Shift_JIS のサポート(だって日本人だもん)。
• デフォルトで .gitignore 内のパターンを検索対象から除外。

インストール

Mac OS X

homebrew で一発です。

$ brew tap tkengo/highway
$ brew install highway

Fedora Core

yum でインストールできます。その際にリポジトリを追加する必要があります。

$ sudo vi /etc/yum.repos.d/highway.repo
[repos.highway]
name=highway
baseurl=http://tkengo.github.io/highway/fedora
enabled=0
gpgcheck=0

$ sudo yum install highway --enablerepo="repos.highway"

CentOS 6 系

同じく yum でインストールできます。こちらもリポジトリの追加は必要ですが、加えて EPEL も追加します。

$ wget http://ftp-srv2.kddilabs.jp/Linux/distributions/fedora/epel/6/x86_64/epel-release-6-8.noarch.rpm
$ rpm -ivh epel-release-6-8.noarch.rpm
$ sudo vi /etc/yum.repos.d/highway.repo
[repos.highway]
name=highway
baseurl=http://tkengo.github.io/highway/centos/6
enabled=0
gpgcheck=0

$ sudo yum install highway --enablerepo="repos.highway"

上記以外の環境またはソースからビルド

ビルドには autoconf automake gperftools が必要なので適宜インストールしておいてください。どれも OS のパッケージ管理ツールからインストールできると思います。(CentOS で yum を使う場合は EPEL リポジトリを追加しないと gperftools がインストールできない)

$ git clone https://github.com/tkengo/highway.git
$ cd highway
$ ./tools/build.sh

これでディレクトリ直下に hw というバイナリができます。

Windows

ごめんなさい。現時点では Windows には対応していません。

使い方

ほぼ pt と同じ。コマンド名は hw です。

コマンド名 + 検索パターン文字列とするだけでカレントディレクトリ以下を再帰的に検索してくれます。

$ hw PATTERN

指定したファイルやディレクトリ以下の検索もできます。ファイルやディレクトリは複数指定することができます。以下の例では src ディレクトリと include ディレクトリ以下を再帰的に検索します。

$ hw PATTERN src include

オプションがいくつかあるので、ヘルプを見てみてください。

$ hw -h

開発動機

私は普段から pt を使っていますが、別に pt が使いにくかったとかそういうのではなくて。

高速な文字列探索のアルゴリズムと言えば grep でも使われている Boyer-Moore のアルゴリズムが有名です。その亜種としてさらに高速な Quick-Search というアルゴリズムも存在します。そして 2007 年に、より高速であるとして以下の論文がインターネットに公開されました。

A simple fast hybrid pattern-matching algorithm

元々は全然関係のない論文を探してたんですがたまたまこの論文を見つけて、前からアルゴリズムとか好きな方だったのでちょっと実装してみようと思って作り始めたのが highway でした。最初は試験的に作ってみて ag と pt と速度比べをして遊んでいたのですが、意外と感触がよかったので体裁を整えて公開してみようと思い、本格的に開発に取り掛かったのが 9 月中旬。sift というベンチマーク結果だけ見ると超神速なツールがでてきたのが 9 月下旬でタイミング的に「うっ」となりつつも、約 1 ヶ月の開発期間を経てとりあえず公開に至りました。

ただ、文字列探索アルゴリズムにおいては元々 Quick-Search でも十分な速度を出すことができます。上記論文の実験結果を見ても通常の検索は Quick-Search より少し速いだけでほとんど変わらない。例えば a が 10 万個続くテキストに対して aaa とか aaaaaaa とかで検索する (これを論文中では Pathological cases “異常なケース” と表現) という場合においては結構優位に立っていますが、そもそもそういう文字列って日常的には扱わない。

なので highway の速さの秘密の全てがここに詰まっているわけでもなく、実装に当たり工夫している箇所はこのアルゴリズム以外にもいくつかあるため、速くできたのはそういうことの積み重ねかなと思っています。これは人類を救うスーパー万能アルゴリズムなんだ、という誤解がされないように補足しておきます。

パフォーマンス計測

せっかく作ったのであれば既存のツールと速度的にどのくらい差があるか気になるところ。ということでいくつかのパターンでベンチマークを取ってみました。なお、計測には OS のキャッシュが効いた状態の数値を利用しました。

ベンチマーク環境

ベンチマーク条件

sift には .gitignore 内のパターンを除外する機能がなく、pt には逆に全ファイルを検索対象にする機能がないため ag と hw においては .gitignore 内のパターンを無視するデフォルト検索、及び全ファイル対象での検索の 2 パターンを計測します。また各ツールでなるべく同じような条件でベンチマークをとれるように、以下のような条件を基本とします。

• 大文字小文字は区別する
• 行番号は表示する
• 表示はグルーピングする

ベンチマーク方法

zsh のビルトインコマンドの time を使いました。出力結果がこういうやつですね。

hw include 0.02s user 0.02s system 160% cpu 0.021 total

この time コマンドを使って、各ツール毎に同じ条件で 10 回ずつ繰り返し実行して total の部分の値の平均値をとって、それをグラフにしました。

ベンチマーク結果

highway のソースコード

まずは highway のソースコード (https://github.com/tkengo/highway) を include という文字列で検索しました。なお clone 後に autoconf や automake、configure、 make などを実行して、一時ファイルなどがたくさんできた状態での検索です。

Linux カーネルのソースコード

次に Linux カーネルのソースコード (https://github.com/torvalds/linux) (全体で約 1.8GB) を EXPORT_SYMBOL_GPL という文字列で検索しました。こちらは clone 後のソースをそのまま検索しています。

巨大ファイル

次に 3.2G の 1 つの巨大ファイルを include という文字列で検索しました。この巨大ファイルは適当なソースコードを集めてきて全部 cat コマンドで 1 ファイルに結合したものです。1 ファイルなので hw と ag の全ファイル検索の結果は除外しています。

巨大ファイルツリー

さらにベンチマーク環境に使用した Mac のホームディレクトリ以下を include という文字列で検索してみます。普通こんな検索はしないと思いますが、ホームディレクトリ以下にはファイルとディレクトリを合わせて 100 万個以上のエントリーが存在していました。なお、検索結果の数があまりにも多すぎて画面に出力していたらかなり時間がかかるので、このベンチマークに限っては標準出力はすべて /dev/null へ捨てます。

ag (全ファイル) と sift のグラフがないのは 120 秒以上ターミナルに戻ってこなかったからです。

正規表現

最後に Linux カーネルのソースコード (https://github.com/torvalds/linux) を今度は正規表現 .*SYMBOL.* で検索してみます。行のどこかに SYMBOL という文字列があればマッチします。

sift のグラフがないのは前と同じく 120 秒以上ターミナルに戻ってこなかったからです。検索結果は随時ターミナルに出力されていたのですが、何度やっても最後の結果を出力した後に止まってしまいます。top コマンドで確認すると CPU を使ってるようなので動いてはいると思うのですが、なんでしょうね。後処理が重いのかな？

※正規表現に関してはいろいろなパターンが考えられますし、各ツールで使用している正規表現エンジンも違いますので、他のパターンだとまた速度も変わってくると思います。ちなみに highway では Onigmo を使わせて頂いております。

まとめ

ベンチマークについてはあくまで個人の端末での検証となりますので、参考程度に留めておいてもらうのが良いと思います。背後で動いている他のプロセスの影響、実行環境の違い、また検索ワードや正規表現のパターン、検索対象ファイルの総数など、実行時間は様々な要因によって結果が変わってくるので、気になる方は実際にインストールして体感してみるのが一番です。

また、このベンチマークでは実行時間に焦点をあてて比較しましたが、プロセスのメモリ使用量に目を向けるとまた結果は変わってくるかと思います（やってないけど）。 この辺に関してはまだ改善の余地がありそうですが、最近のパソコンは潤沢なメモリを積んでいることが多いし、常駐するプロセスなわけでもないので、とりあえずは後回しです。

もちろんバグもあると思いますし、落ちたりとか、マッチするはずのものにマッチしなかったとか、こういう場合におせーよハゲ、とかあったら、遠慮無くイシュー作ったりして声かけてください。

ということで highway の紹介でした。暇な人がいたら是非使ってみてくださいね。