Onigmoのインタプリタをdirect threaded codeに置き換えてCRubyを8%高速化した話
Ruby言語の正規表現エンジンとしても使われているOnigmo(鬼雲)を高速化したのでその話をします。
Onigmoでは、正規表現のマッチにはバイトコードインタプリタを用いてNFAの実行をしています。バイトコードインタプリタの高速化には古くから知られている技法として、direct threaded codeがあり、この技法を用いればswitch-caseを用いて実装されたインタプリタと比べると間接jumpの除去が行えるなど高速化が期待できます。実際、Onigmoでもswitch-case によるdispatchからこのdirect threaded codeに変えることで高速化しています。
... と思ったら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に更に置き換えることで更なる高速化を実現しました。
と言うのは簡単なのですが、実は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
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で限られたパターンの正規表現しかテストしていないのでマージされるかは分かりませんが、近いうちにマージされると嬉しいですね。
