最適化中

SkRegExpの改訂版は一応完成しています。

ただ、あまりにも遅いので少し最適化を施しているところです。

今作業しているのは2つ。繰り返しとリテラル文字の最適化です。

リテラル文字の最適化は既に終わっています。

どういう最適化かというと、「abc」という正規表現があったとき、今のバージョンでは、最初に「a」とマッチするか、次に「b」とマッチするか、最後に「c」とマッチするか、と言う具合に1文字ごとに照合していました。

これをまとめて照合するように最適化しました。

「abc」という正規表現なら「abc」とまとめて照合するようにしました。

この最適化、カンタンなようで結構大変でした。

たとえば、「abc*」という正規表現の場合、連続するリテラルは「ab」だけで、「c」は「*」の影響下にあります。

つまり、パーサーで次のような処理をする必要があります。

「a」を読み出す。
次の文字を読む。
「b」を読み出す。
次の文字を読む。
「c」を読み出す。
次の文字を読む
「?」を読み出す。
「c」は「?」の支配下なので連続するリテラルではない。
「ab」が連続するリテラルなので構文木に追加。

つまり、連続するリテラルを判断するには、字句解析で2つ先読みする必要があるわけです。

もちろん、読み出すだけではダメで元に戻せないとダメです。

そこで行った作業は以下の通り。

TREParserから文字を切り出す部分をTRELexとして分離。TREParserだと、何を保存すれば元に戻れるのか見通しが悪かったためです。

そして、TRELexの中に、リングバッファもどきを設けて2つ分の字句解析の結果を残して置くようにしました。

この最適化、正規表現にリテラル文字を多く含む場合は劇的なスピードアップが見込めますし、事実しています。

1文字単位で処理すると、「1文字比較、次のNFAに遷移、1文字比較」と言う具合に、余計なステップが入っているので、まとめて処理すれば速くなるのは当然です。

今は繰り返しの最適化を行っています。正規表現で多く使われるのはこっちなのでこの方が最適化の効果は大きいでしょう。

改訂版の公開まで、もうしばらくお待ちください。

待っている人がいるかどうかわかりませんが。

コメントを残す

メールアドレスが公開されることはありません。