SkRegExp version 3.1.0 release

マイナーバージョンアップは2年ぶりです。

とは言っても、バグ修正は行なっていましたが。

今回のマイナーバージョンアップは、今まで放置していた危ないバグの修正と高速化がテーマです。

危ないバグとは?

次の正規表現でマッチさせると無限ループ?と思われるくらい処理に時間が掛かります。

[\x{0}-\x{ffff}]

正規表現を知っている人がこのような正規表現を書くことはないと思います。

たとえばUnicodeの漢字の範囲が必要なら\p{Han}と書きますからね。

そんなわけでずっと放置してきました。

ところが先日、某海外製アプリでこの症状に遭遇しました。

まさかと思ってバイナリを覗くとSkRegExpWの文字が!

SkRegExpが使われていることに驚いたと同時に冷や汗が。

せっかく使ってもらっているのだからそれなりの責任を果たさなければと考えを改めました。

というわけでこのバージョンで修正しました。

もう一つのテーマの高速化については、地味な作業なのでこちらも放置してきたことを改善しました。

まだやらなければならないこともあるんですが、取り敢えず、モチベーションを維持しているうちにできることは片付けました。

SkRegExp version 3.1 はこちらからダウンロードできます。

20%速くなりました

TREMatchEngine.MatchPrim を TREMatchEngine.MatchCore に統合する作業を完了しました。

現在のバージョンでは要素ごとに MacthcPrim メソッドを呼び出しています。

ココが SkRegExp のボトルネックでは?

と言うわけで、 MatchPrim を MatchCore の中に押し込んだバージョンを作りました。

その結果は?

この変更だけで20%速くなりました。

やっぱり、ループ中のメソッド呼び出しは重いんですね。

近いうちに version 3.1 として公開します。

SkRegExp version 3.0.3 公開

SkRegExp version 3.0.3 を公開しました。

次のバグを修正しました。

  • 修正)戻り読みの中で選択(|)を使った正規表現パターンで Access violation が出るバグを修正。
    TRETrieList.Add 内のハッシュテーブルでキーが重複したときの処理が間違っていた。
  • 修正)戻り読みの中で選択(|)を使った正規表現パターンでマッチしないことがあるバグを修正。

    最適化すべきでない部分を最適化していたため。

  • 修正)選択(|)の際、最適化が効かなくなるバグを修正。
    TRENFA.GenerateStaeteList メソッドでリテラル文字の開始位置を正しく計算していなかった。

SkRegExp version 3.0.3 はこちらからダウンロードできます。

SkRegExp のボトルネック

前回、 ExecNext が遅いと書いたことに関連します。

「 ExecNext が遅い」ことに関しては環境の問題だったようです。

ただ、その時調べたことから SkRegExp のボトルネックに気が付きました。

その記事のコメントで、 benok さんに Sampling Profiler と言うソフトを教えていただきました。

それを使って調べたところ、 TREMacthEngine.MatchPrim で多くの時間を費やしていることがわかりました。

マッチエンジンの中心なので当然です。

これは AQTime でわかっていました。

Sampling Profiler でわかったのは「 MatchPrim 内のどこで時間を費やしているか?」でした。

スタートアップとクリーンアップで70%を占めていました。

アセンブラで見てみると実にたくさんの仕事をしていました。

MatchPrim は1文字ごとに最低1回は呼び出されています。

コレは重いです。

SkRegExp は PCRE に比べると単純なパターンと単純な検索文字列の組み合わせが遅いです。

今まではその種の最適化をしていないせいだと考えていました。

しかし、 MatchPrim が重いためかもしれないと考えを改めました。

単純なパターンはエンジンの素の性能を表しているのかも、ですね。

そんなわけで、 MatchPrim メソッドを MatchCore 内に展開することにしました。

が、 MatchPrim を呼び出しているメソッドは5つあります。

5つ全部に MatchPrim を展開したらメンテナンスが大変です。

コードも大きくなりますし。

前段階として、今、 MatchCore を1つにまとめる作業をしています。

これが意外に大変でして…。

次のバージョンアップは地味なものになりそうです。

ExecNext が遅い…

SkRegExp の TSkRegExp.ExecNext が遅いことに気づいた。

TSkRegExp の ExecPos と Exec を1回実行するだけなら TRegEx より速い。

これは Google で “Regular expression bench mark” で検索して出てくる正規表現のベンチマークプログラムで検証している。

しかし、同じパターンで同じテキストを繰り返し検索すると遅くなる。

困ったことに遅くなる原因がよくわからない…。

TREMatchEngine.MatchEntry か、TMatchEngine.MatchPrim が遅いのだとは思う。

でも、どちらもこれ以上速くする余地があるとは思えないのだが。

大文字小文字を区別しない検索も Unicode 標準フルセットへ対応【SkRegExp ver. 3.0 の目玉】

SkRegExp version 3.0 は大文字小文字を区別しない検索も Unicode 標準に対応しました。

従来、大文字小文字を区別しない検索は、小文字を大文字に変換して比較していました。

小文字を大文字に変換する方法は、UnicodeData.txt の大文字の情報を使っていました。

しかし、この方法には問題があります。

ヨーロッパの言語では一つの大文字が複数の小文字に対応したり、またその逆だったりします。

UnicodeData.txt の情報ではこうした文字を取りこぼしてしまいます。

もっとも、日本人は別に困りませんけどね。

とは言っても SkRegExp の野望は世界進出です。

世界に出るためにはヨーロッパを無視できません。

というわけで重い腰を上げました。

このような用途のためには CaseFolding.txt を使えばいいのだそうです。

CaseFolding.txt とは、こんなのが書かれているテキストファイルです。


1E9E; F; 0073 0073; # LATIN CAPITAL LETTER SHARP S
1E9E; S; 00DF; # LATIN CAPITAL LETTER SHARP S
1EA0; C; 1EA1; # LATIN CAPITAL LETTER A WITH DOT BELOW

CaseFolding.txt を読むと、シンプルセットなら C と S を、フルセットなら C と F をサポートすればいいとのこと。

TRegEx はシンプルセットのようなので SkRegExp はフルセットをサポートしました。

同じだったら SkRegExp を使う意味はないですからね。

ちなみに「速度が落ちるかな?」と思ったらそうでもありませんでした。

まあ、落ちたことは落ちたんですが最適化の見直しもあって影響はゼロでした。

ヨーロッパの言語を使う機会がある方は SkRegExp がお勧めです。

大文字小文字を区別しない検索も Unicode 標準フルセットへ対応した SkRegExp version 3.0 はこちらからダウンロードできます。

SkRegExp version 3.0 公開

SkRegExp version 3.0 を公開しました。

主な変更点は次の通りです。

Perl 5.14 互換の構文をサポートしました。

  • メタ文字 o{NNNNNN} と N
  • 修飾子 a, d, l, u
  • 拡張構文 (?^…)
  • POSIX文字クラスに IsSpacePerl、UnicodeProperty に SpacePerl を追加

大文字小文字を区別しないマッチで Unicode 標準に対応しました。

ヨーロッパの言語では、1文字の大文字が2つの小文字に対応したり、その逆があったりします。

version 3.0 ではそのような文字にもマッチするようになりました。

UnicodeProp.pas の切り離しが可能になりました。

条件定義 USE_UNICODE_PROPERTY を無効にすると UnicodeProp.pas を切り離すことができます。

Unicode Property が必要ないプログラムの場合、サイズを節約できます。

UnicodeProp.pas に依存するメタ文字 p, P, X が普通の文字になり、名前付きグループに [_A-Za-z0-9] 以外の文字が使えなくなります。

ただし、テストが不十分です。その点ご了承ください。

改行文字を指定できるようになりました。

従来は Unicode の改行すべてを「改行」として扱っていました。

version 3.0 からは TSkRegExp.LineBreakKind で次の5つを選択できるようになりました。

  1. CR
  2. LF
  3. CRLF
  4. CR/LF/CRLF
  5. すべての改行文字

標準では CR/LF/CRLF の3つを改行として扱います。

他に、最適化に関わるクラスと内容を見直し、処理を軽くしました。

また、私が使っているテストプログラム3本を今回のバージョンから同梱しています。

SkRegExp 本体と違って人様に見せることをまったく考えていない汚いソースです。

それでも「ないよりはマシだろう」と思って同梱することにしました。

コレでいつ私が SkRegExp を諦めても大丈夫ですな。

ま、まだそのつもりはありませんが。

SkRegExp version 3.0 はこちらからダウンロードできます。

UnicodeProp.pas を切り離す【SkRegExp version 3.0 の目玉】

SkRegExp version 3.0 のテストも大詰めです。

そこで、公開までの間、version 3.0 の目玉について紹介します。

第1回目は「UnicodeProp.pas を切り離す」についてです。

SkRegExp は Unicode 対応の正規表現ライブラリです。

Unicode サポートのため、UnicodeProp.pas と言う巨大なテーブルを保持しています。

しかし、正規表現の Unicode サポートが必要ない場面もあります。

たとえば、MIME 解析などは Unicode サポートは一切不要です。

そこで、そのような用途に対応するため、USE_UNICODE_PROPERTY と言う条件定義を追加しました。

USE_UNICODE_PROPERTY を有効にすると Unicode サポートが組み込まれます。これが標準の動作です。

一方、USE_UNICODE_PROPERTY を無効にすると 次の Unicode サポートが組み込まれなくなります。

  • Unicode プロパティを指定するメタ文字 p, P
  • Unicode対応の ドット ( . ) のメタ文字 X
    これらのメタ文字は普通の文字として扱われます。
  • 名前付きグループに使える文字が [_A-Za-z0-9] の文字に制限されます。
    たとえば漢字のグループ名を指定すると例外が発生します。

実は USE_UNICODE_PROPERTY についてはテストしていません。

理由はカンタン、テストが面倒だから。

そのためドキュメントには掲載しません。

アンドキュメンテッドな機能とお考え下さい。

ただし、USE_UNICODE_PROPERTY を無効にしたとき、新たなコードが走ることはありません。

既にテストを通ったコードのうち、Unicode サポートのコードだけが無効になっています。

したがって、信頼性は Unicode サポート有りの SKRegExp と代わらないと思います。