正規表現エンジンのチューニング

SagittariusではRE2(Pike VM?)ベースの正規表現エンジンを積んでいて(実際にはハイブリッドなのだが、今回はこっちのエンジンが対象)、基本的な正規表現ならO(n)で走る。実際にはO(n+α)だったりするが、O(n)でいいだろう。リニアに走るなら速度はそんなに気にしなくてもいいんじゃないかと思うのだが、以下のようなコードを走らせると不満が出るほど遅い。

#< (sagittarius regex) >
(import (time) (srfi :1)
 (text tree)
 (sagittarius control)
 (sagittarius regex)
 (only (sagittarius regex impl) dump-regex))

(define s
  (tree->string `(,(make-list 1000 `(,(make-string 1000 #\a) "01:23")) ":45")))

(define (time-this count thunk)
  (time (dotimes (i count) (thunk))))

(print (time-this 10 (^[] (#/\d\d:\d\d:\d\d/ s))))

以下が実行結果(Cygwin on Windows XP CoreDuo 1.6GHz)

$ sash reg.scm

;;  (dotimes (i count) (thunk))
;;  2.921875 real    2.969000 user    0.000000 sys
#t

ちょっとねぇ・・・とりあえず、本質的な問題を脇に置いておいて、不必要な計算を減らして400ms程度速くしたのだが、やはり枝葉の最適かなので2割程度にしかならない。

何が問題か？エンジンの走り方以外の何者でもないのだが・・・
 PikeVMはバックトラックをしないNFAなエンジンである。っで、バックトラックさせない為に、内部で仮想スレッドとスレッドキューを持っていて、一文字チェックする毎にスレッドキューに次に実行させるインストラクションとマッチした状態を保存したスレッドを溜め込む。文字がマッチしなければキューにあるスレッドは1個なんだけど、例えば4文字までマッチしたスレッドがあるとすると、他にも3スレッド脇で走っていたりする。
以上を踏まえて、上記のコードを見ると、途中で「01:23」と4文字マッチして、捨てられるという処理が1000回ほど必要になる。そのため、内部で回すスレッドの関係でガッツリ遅くなる。のではないかと結論付けている。
現実的にこれほどベンチマークに特化したかのような入力文字列の処理が必要になるかどうかは別にしても、遅いというのは悪であるのでなんとかしたい。しかし、問題の幹の部分はそれこそ正規表現エンジン自体を改善(可能ならDFAにするとか)しないと無理なので、そこまで大掛かりにしたくない(ものぐさ)。
とりあえず、やってみて効果のあったもの。

• 不要コードの削除
• キューをクリアするに最小限の要素のみクリア

無駄だったもの

• 急場のダイレクトスレッドコード

枝葉のチューニングではこの程度が限界だろうか？せめて倍速まで持っていきたいのだが、う～ん。