いまさらgrepが10倍高速化したのはなぜか

最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。
ニュース記事：grepコマンド最新版、”-i”で10倍の高速化
本家のリリースノート：grep – News: grep-2.17 released [stable]

今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。

なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？

そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものくらいしか思いつかないのかもしれないが、世の中にはもっと複雑なものがあるのが原因のようだ。

対応するgitのコミットはこれらしい：
grep: make –ignore-case (-i) faster (sometimes 10x) in multibyte locales

ここのソースコード内のコメントに詳しい解説が書いてあった。なぜ今まで遅かったのかが書いてある。

引用：
+ /* As currently implemented, case-insensitive matching is expensive in
+ multi-byte locales because of a few outlier locales in which some
+ characters change size when converted to upper or lower case. To
+ accommodate those, we revert to searching the input one line at a
+ time, rather than using the much more efficient buffer search.
+ However, if we have a regular expression, /foo/i, we can convert
+ it to an equivalent case-insensitive /[fF][oO][oO]/, and thus
+ avoid the expensive read-and-process-a-line-at-a-time requirement.
+ Optimize-away the “-i” option, when possible, converting each
+ candidate alpha, C, in the regexp to [Cc]. */

これはつまりこういうことだ。

• マルチバイトロケールによっては、「大文字→小文字」または「小文字→大文字」の変換をすると文字のバイト数が変わってしまうことがある（！）
• そのため、バッファを使った効率の良い検索が使えず、1行読み込んで変換して検索するという効率の悪い実装が行われていた
• そこで発想を変えて、検索される文字列を同値な正規表現にあらかじめ変換すると速くなった。つまり「foo」という文字列を検索するときは「[fF][oO][oO]」という正規表現に変換してから検索する。

大文字と小文字でバイト数が違うことがあるというのは知らなかったし驚いた。なんか具体例を示せないかなと思ったのだが、このgrepのコミットにはトルコ語でテストしたと書いてある。トルコ語関係で検索したら、マイクロソフトの次のようなサイトが見つかった。

カスタムの大文字と小文字の対応規則および並べ替え規則

引用：
トルコ語のアルファベットに固有の大文字と小文字の対応規則は、言語によっては大文字と小文字の対応が一部異なる例を示しています。 ほとんどのラテン語アルファベットでは、文字 “I” (Unicode 0069) は文字 “I” (Unicode 0049) の小文字です。 それに対し、トルコ語のアルファベットでは文字 “I” に 2 つのバージョンがあります。1 つはドット付きで、もう 1 つはドットなしです。 トルコ語では、文字 “I” (Unicode 0049) は別の文字 “I” (Unicode 0131) の大文字と見なされます。 文字 “I” (Unicode 0069) は、さらに別の文字 “İ” (Unicode 0130) の小文字と見なされます。 このため、大文字と小文字を区別せずに、文字 “I” (Unicode 0069) と “I” (Unicode 0049) の文字列比較を行った場合、ほとんどのカルチャでは成功しますが、トルコ語 (トルコ) のカルチャ “tr-TR” では失敗します。

これ、ざっと読んだだけでは、何を言っているのかわからなかったのだが、改めてまとめると以下のようになる。

• 英語を含む多くの言語では”i”は”I”の小文字だとみなされる
• トルコ語では”i”と”I”、両方の文字とも使われている
• しかしトルコ語では”i”は”I”の小文字ではない
• トルコ語では、”i”はある他の文字の小文字で、”I”はある他の文字の大文字である

そこで、このサイトを使って調べてみたところ、トルコ語でIの小文字はı(UTF-8でc4 b1)、iの大文字はİ(UTF-8でc4 b0)となっている。Iとiは1バイトなので、それらをトルコ語でそれぞれ小文字と大文字に変換すると2バイトになってサイズが変わることになる。

まとめ

• 世界には、大文字／小文字の変換を行うとUTF-8で表現した時のサイズが変わる言語がある
• そのせいで、従来のGNU grepは1行ずつ読み込んで変換するという効率の悪い実装をしていたが、検索文字列を同値な正規表現に変換することで高速化を実現した
• 文字列の検索は枯れた技術に思われているかもしれないが、UTF-8周りだといろいろ気持ち悪いことがあるようだ(枯れているのは「バイト列」の検索？)

P.S. 英語、トルコ語混じりファイルの検索で、トルコ人が苦労することはないんだろうかと思った。

追記：
（2014/2/27 11:37 加筆）
その後、バージョン2.18についての解説も書いたので、ここにリンクを貼っておく。
GNU grep 2.18リリース: 10倍速くなったと思ったら今度は200倍遅くなっていた