Let's start Scheme

2012-08-22

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

とりあえず、昨日のコードがGauche(0.9.3)と同程度の速度が出るように改善できた。

やったこと
  1. 疎な配列をエミュレートしていたのだけれど、それに付随していたイテレータの削除
    • 10%程度
  2. 地味にコードのリファクタリング
    • 10%程度
  3. インストラクションコードの2番目がアトムチェックのコードならマッチする場所までチェックする
    • これが効いた、900% 
もともと昨日のコードでは、1000個の'a'と'01:23'という文字列が1000回繰り返して最後に':45'とつくのだけれど、途中の'a'の部分は絶対にマッチしないくせにわざわざキュー操作していたのがまずかったのだ。なら、最初にマッチする場所まで先読みしてやれよかったという話。

現状ではものすごく手抜きな先読みなので、#/(\d\d):\d\d:\d\d/と変更されるだけで遅くなるんだけど。また気になったら直すことにしよう。

さすがにグルーピングしただけでパフォーマンスが落ちるのはあんまりなので直した。あと(aa|bb)形式もいけるようにした。
とりあえずのところは満足ということにしよう。

追記。ベンチマークの結果をつけるの忘れてた。
以下は前回と同じ環境での結果(上が改善後)
$ ./build/sash.exe reg.scm

;;  (dotimes (i count) (thunk))
;;  0.328125 real    0.375000 user    0.000000 sys
#t

$ sash reg.scm

;;  (dotimes (i count) (thunk))
;;  2.921875 real    2.985000 user    0.000000 sys
#t
ほぼ10倍?このパターンがどれほど実際のプログラムで出てくるかは分からないけど・・・

No comments:

Post a Comment