Onigmoを最大49%高速化した話

2015-05-26

正規表現

κeenです。Rubyでも使われてる高速な正規表現エンジン、Onigmo(鬼雲)を高速化したのでその話を。

先日、正規表現技術入門を読んだというエントリの中で

ところで本に載ってた鬼雲のコードはDT(編注: Direct Threaded)にしてなかったけど簡単のためなのかな？あるいは厳格にC89に準拠するため？picrinみたくプリプロセッサで分岐すれば使えるのに。

と書いたところ、鬼雲の作者、K.Takataさんから

@k_takata 「picrinみたくプリプロセッサで分岐すれば使えるのに。」これも知らなかった。
— K.Takata (@k_takata) 2015, 5月 11

という反応を頂きました。そしてイシューにも乗ったので言い出しっぺとして実装してみました。こちらのプルリクです。

Direct Threaded VM自体の解説はRubyist Magazineに載っている笹田さんのものが詳しいようです Rubyist Magazine - YARV Maniacs 【第 3 回】命令ディスパッチの高速化

実装は少し技巧的ですがwhile, switch, case, break, continueなどをマクロでラップしつつDT VMが有効ならそれらと互換性のあるDT用のコード（gotoやラベル）に展開します。元はpicrinで使われていたテクニックです。このコードは @wasabizが書いたものなのでpicrinがどこを参考にして書かれたかは@wasabizに聞いて下さい。もしかしたらわさびずの発明かもしれませんね。

で、パフォーマンスの方ですが、最初、素直に制御命令を1つづつマクロで書き換えたのですが、こうなりました。

master

パターン	時間
Twain	47 ms
^Twain	47 ms
Twain$	47 ms
Huck[a-zA-Z]+\|Finn[a-zA-Z]+	127 ms
a[^x]{20}b	1172 ms
Tom\|Sawyer\|Huckleberry\|Finn	151 ms
.{0,3}(Tom\|Sawyer\|Huckleberry\|Finn)	497 ms
[a-zA-Z]+ing	4032 ms
^[a-zA-Z]{0,4}ing[^a-zA-Z]	96 ms
[a-zA-Z]+ing$	4175 ms
^[a-zA-Z ]{5,}$	1770 ms
^.{16,20}$	1757 ms
([a-f](.[d-m].){0,2}[h-n]){2}	1849 ms
([A-Za-z]awyer\|[A-Za-z]inn)[^a-zA-Z]	656 ms
"[^"]{0,30}[?!\.]"	115 ms
Tom.{10,25}river\|river.{10,25}Tom	260 ms

DT版

パターン	時間
Twain	100 ms
^Twain	99 ms
Twain$	100 ms
Huck[a-zA-Z]+\|Finn[a-zA-Z]+	246 ms
a[^x]{20}b	2182 ms
Tom\|Sawyer\|Huckleberry\|Finn	288 ms
.{0,3}(Tom\|Sawyer\|Huckleberry\|Finn)	847 ms
[a-zA-Z]+ing	6278 ms
^[a-zA-Z]{0,4}ing[^a-zA-Z]	203 ms
[a-zA-Z]+ing$	6430 ms
^[a-zA-Z ]{5,}$	3603 ms
^.{16,20}$	3596 ms
([a-f](.[d-m].){0,2}[h-n]){2}	3239 ms
([A-Za-z]awyer\|[A-Za-z]inn)[^a-zA-Z]	1039 ms
"[^"]{0,30}[?!\.]"	327 ms
Tom.{10,25}river\|river.{10,25}Tom	487 ms

はい。DT版の方が2倍ちょっと遅いです。そりゃないわー。最適化オプションとかも確認したのですがダメでした。

諦めて布団に入った後、ふと思い当たる節がありました。

元のコードで

case OP_XXX:
   ...
   continue;
   break;

というパターンが割と現れます。continueの後のbreakは本来なら不要ですがcaseを書く際の作法というか癖というかとにかくbreakを付けるスタイルもあります。これもそうなのでしょう。こいつらをマクロで書き換える時に愚直に

CASE(OP_XXX)
   ...
   JUMP;
   NEXT;

としてました。ここで、

#if USE_DIRECT_THREADED_VM
#define NEXT sprev = sbegin; JUMP
#define JUMP goto *oplabels[*p++]
#else
#define NEXT break
#define JUMP continue
#endif

です。これはUSE_DIRECT_THREADED_VMが定義されてる時は

L_OP_XXX:
   ...
   goto *oplabels[*p++];
   sprev = sbegin;goto *oplabels[*p++];

と展開され、gotoが2つ現れることになります。どうせ無用コードだし最適化で消えるだろと思ってたらそうでもないらしく、

CASE(OP_XXX)
   ...
   JUMP;
   NEXT;

を

CASE(OP_XXX)
   ...
   JUMP;

にし、マクロの方も

#if USE_DIRECT_THREADED_VM
#define NEXT sprev = sbegin; JUMP
#define JUMP goto *oplabels[*p++]
#else
#define NEXT break
#define JUMP continue; break
#endif

としたらようやく本領発揮してくれました。その結果がこれです。

	Master	This PR	Improve Rate
Twain	47 ms	47 ms	0%
^Twain	47 ms	47 ms	0%
Twain$	47 ms	47 ms	0%
Huck[a-zA-Z]+\|Finn[a-zA-Z]+	127 ms	127 ms	0%
a[^x]{20}b	1172 ms	889 ms	31%
Tom\|Sawyer\|Huckleberry\|Finn	151 ms	153 ms	-1%
.{0,3}(Tom\|Sawyer\|Huckleberry\|Finn)	497 ms	449 ms	10%
[a-zA-Z]+ing	4032 ms	2705 ms	49%
^[a-zA-Z]{0,4}ing[^a-zA-Z]	96 ms	98 ms	-2%
[a-zA-Z]+ing$	4175 ms	2797 ms	49%
^[a-zA-Z ]{5,}$	1770 ms	1623 ms	9%
^.{16,20}$	1757 ms	1637 ms	7%
([a-f](.[d-m].){0,2}[h-n]){2}	1849 ms	1670 ms	11%
([A-Za-z]awyer\|[A-Za-z]inn)[^a-zA-Z]	656 ms	607 ms	8%
"[^"]{0,30}[?!\.]"	115 ms	93 ms	24%
Tom.{10,25}river\|river.{10,25}Tom	260 ms	262 ms	-1%

a[^x]{20}bや[a-zA-Z]+ingのようにバックトラックが何度も起きてVMループをヘビーに回すパターンでは効果覿面のようで、最大49%の高速化です。素晴しいですね。

因みに2つめのgotoは実際には実行されないのに何故遅くなったかというとgotoはコンパイラにとってはコントロールフログラフを乱す厄介な奴なので無用コード除去に引っ掛からなかったどころか最適化ルーチンを引っ掻き回したんじゃないかと思います。

このコード、私の手元の環境でしかテストしてないのでC89なら須くサポートするOnigmoにマージされるかは分かりませんがマージされると嬉しいですね。