Onigmoのインタプリタをdirect threaded codeに置き換えてCRubyを8%高速化した話

Ruby言語の正規表現エンジンとしても使われているOnigmo(鬼雲)を高速化したのでその話をします。

Onigmoでは、正規表現のマッチにはバイトコードインタプリタを用いてNFAの実行をしています。バイトコードインタプリタの高速化には古くから知られている技法として、direct threaded codeがあり、この技法を用いればswitch-caseを用いて実装されたインタプリタと比べると間接jumpの除去が行えるなど高速化が期待できます。実際、Onigmoでもswitch-case によるdispatchからこのdirect threaded codeに変えることで高速化しています。

keens.github.io

github.com

... と思ったらdirect threaded codeではなく、token threaded codeという実装になっておりました。(ref: Rename USE_DIRECT_THREADED_VM to USE_TOKEN_THREADED_VM · k-takata/Onigmo@be63582 · GitHub)

token threaded codeはswitch caseに比べれば十分に速いのですが、バイトコード命令のdispatch部分(バイトコードを読み込んで、対応する命令の実装部分のアドレスを引いて、jumpする)にまだ高速化の余地があります。direct threaded codeでは命令dispatchには、バイトコード上に事前に書き込んで置いたアドレスにjumpする方式を取っているので、load 1個分速い訳ですね。

// Token threaded code
void **labels = {};
uint8_t *opcode = ...;

goto labels[*opcode];

// Direct threaded code
void **labels = {};
uint8_t *opcode = ...;

goto *(void **)opcode; 

ということでtoken threaded codeをdirect threaded codeに更に置き換えることで更なる高速化を実現しました。

github.com

と言うのは簡単なのですが、実はdirect threaded codeに変更する際に少し困った問題がありました。switch-case dispatchやtoken threaded codeとは異なり、direct threaded codeではバイトコード上にopcodeではなくアドレスを書き込む必要があります。opcodを保持していた領域にアドレスを書き込めばいいかと思うかもしれませんが、Onigmoのopcodeは1byte、対してアドレスはLinux 64bit環境なら8byteなのでとても足りないです。(switch-caseやtoken threaded codeも省メモリを目的にするならば利点があったのです。) 組み込みシステムなどメモリ使用量の制約が強いような環境では適応は難しいかもしれませんが、いくらでもメモリが使える環境だったら特に問題ないかもしれませんね。

Performance comparison of regular expression engines を使ってbefore/afterを手元のM1 macbookで計測した結果が以下の通りとなります。

Pattern	Current	Proposal	Improve Rate
Twain	15 ms	15 ms	0%
(?i)Twain	60 ms	18 ms	233%
[a-z]shing	14 ms	13 ms	7.6%
Huck[a-zA-Z]+|Saw[a-zA-Z]+	20 ms	16 ms	25%
\b\w+nn\b	394 ms	414 ms	-5.1%
[a-q][^u-z]{13}x	20 ms	7 ms	185%
Tom|Sawyer|Huckleberry|Finn	25 ms	19 ms	31%
(?i)Tom|Sawyer|Huckleberry|Finn	236 ms	179 ms	34%
.{0,2}(Tom|Sawyer|Huckleberry|Finn)	48 ms	38 ms	26%
.{2,4}(Tom|Sawyer|Huckleberry|Finn)	46 ms	44 ms	4.5%
Tom.{10,25}river|river.{10,25}Tom	42 ms	41 ms	2.4%
[a-zA-Z]+ing	509 ms	410 ms	24%
\s[a-zA-Z]{0,12}ing\s	48 ms	44 ms	9%
([A-Za-z]awyer|[A-Za-z]inn)\s	101 ms	99 ms	2%
["'][^"']{0,30}[?!.]["']	44 ms	39 ms	12%

せっかくなので、CRubyに適応したらどのくらい速くなるかも確認しておきましょう。 お手軽なbenchmarkアプリケーションがなかったので、Computer Language Benchmarks Gameのregex-reduxを使いました。 benchmarksgame-team.pages.debian.net

github.com

Before:

$ time time ./ruby -W0 regex-redux.rb 0 < a.txt
agggtaaa|tttaccct 356
[cgt]gggtaaa|tttaccc[acg] 1250
a[act]ggtaaa|tttacc[agt]t 4252
ag[act]gtaaa|tttac[agt]ct 2894
agg[act]taaa|ttta[agt]cct 5435
aggg[acg]aaa|ttt[cgt]ccct 1537
agggt[cgt]aa|tt[acg]accct 1431
agggta[cgt]a|t[acg]taccct 1608
agggtaa[cgt]|[acg]ttaccct 2178

50833411
50000000
27388361
        4.47 real        13.75 user         0.51 sys

time ./ruby -W0 regex-redux.rb 0 < a.txt  13.76s user 0.52s system 318% cpu 4.475 total

After:

$ time time ./ruby -W0 regex-redux.rb 0 < a.txt
agggtaaa|tttaccct 356
[cgt]gggtaaa|tttaccc[acg] 1250
a[act]ggtaaa|tttacc[agt]t 4252
ag[act]gtaaa|tttac[agt]ct 2894
agg[act]taaa|ttta[agt]cct 5435
aggg[acg]aaa|ttt[cgt]ccct 1537
agggt[cgt]aa|tt[acg]accct 1431
agggta[cgt]a|t[acg]taccct 1608
agggtaa[cgt]|[acg]ttaccct 2178

50833411
50000000
27388361
        4.26 real        12.62 user         0.48 sys
time ./ruby -W0 regex-redux.rb 0 < a.txt  12.62s user 0.48s system 306% cpu 4.270 total

実行環境は同じくM1 macです。user の時間が13.75sec -> 12.62secと8.9%くらいの高速化が達成できるようです。悪くはなさそうです。 Onigmoのpull request、まだ手持ちのmacで限られたパターンの正規表現しかテストしていないのでマージされるかは分かりませんが、近いうちにマージされると嬉しいですね。