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

κeenです。Rubyでも使われてる高速な正規表現エンジン、Onigmo(鬼雲)を高速化したのでその話を。 先日、正規表現技術入門を読んだというエントリの中で

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

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

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

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

パターン時間
Twain47 ms
^Twain47 ms
Twain$47 ms
Huck[a-zA-Z]+|Finn[a-zA-Z]+127 ms
a[^x]{20}b1172 ms
Tom|Sawyer|Huckleberry|Finn151 ms
.{0,3}(Tom|Sawyer|Huckleberry|Finn)497 ms
[a-zA-Z]+ing4032 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}Tom260 ms

DT版

パターン時間
Twain100 ms
^Twain99 ms
Twain$100 ms
Huck[a-zA-Z]+|Finn[a-zA-Z]+246 ms
a[^x]{20}b2182 ms
Tom|Sawyer|Huckleberry|Finn288 ms
.{0,3}(Tom|Sawyer|Huckleberry|Finn)847 ms
[a-zA-Z]+ing6278 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}Tom487 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

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

MasterThis PRImprove Rate
Twain47 ms47 ms0%
^Twain47 ms47 ms0%
Twain$47 ms47 ms0%
Huck[a-zA-Z]+|Finn[a-zA-Z]+127 ms127 ms0%
a[^x]{20}b1172 ms889 ms31%
Tom|Sawyer|Huckleberry|Finn151 ms153 ms-1%
.{0,3}(Tom|Sawyer|Huckleberry|Finn)497 ms449 ms10%
[a-zA-Z]+ing4032 ms2705 ms49%
^[a-zA-Z]{0,4}ing[^a-zA-Z]96 ms98 ms-2%
[a-zA-Z]+ing$4175 ms2797 ms49%
^[a-zA-Z ]{5,}$1770 ms1623 ms9%
^.{16,20}$1757 ms1637 ms7%
([a-f](.[d-m].){0,2}[h-n]){2}1849 ms1670 ms11%
([A-Za-z]awyer|[A-Za-z]inn)[^a-zA-Z]656 ms607 ms8%
"[^"]{0,30}[?!\.]"115 ms93 ms24%
Tom.{10,25}river|river.{10,25}Tom260 ms262 ms-1%

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

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

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

Written by κeen
Older article
幽霊型を知った