結論: Rustにかんしては https://github.com/rust-lang/regex/blob/master/HACKING.md をみればええ
- lazy DFA
- literal optimization
- https://github.com/rust-lang/regex/blob/master/PERFORMANCE.md
- heavily optimized routines for string search primitives
制限付きのバックトラック法とPike VMのadaptiveな実装になっている。
想定されるメモリ使用量が少ない、かつ shortest_match_at などが使われない場合にバックトラック法が使われるらしい。
ただしregex crateは線形時間で終わるように設計されているため、このバックトラック法が制限付きの実装となっている。
fn exec_nfa(
&self,
mut ty: MatchNfaType,
matches: &mut [bool],
slots: &mut [Slot],
quit_after_match: bool,
quit_after_match_with_pos: bool,
text: &[u8],
start: usize,
end: usize,
) -> bool {
use self::MatchNfaType::*;
if let Auto = ty {
if backtrack::should_exec(self.ro.nfa.len(), text.len()) {
ty = Backtrack;
} else {
ty = PikeVM;
}
}
// The backtracker can't return the shortest match position as it is
// implemented today. So if someone calls `shortest_match` and we need
// to run an NFA, then use the PikeVM.
if quit_after_match_with_pos || ty == PikeVM {
self.exec_pikevm(
matches,
slots,
quit_after_match,
text,
start,
end,
)
} else {
self.exec_backtrack(matches, slots, text, start, end)
}
}エンジンとしてはトンプソンNFAのみの実装。
工夫として、
- match macroを使った場合の高速化
- このPRで追加されている: nitely/nim-regex#58
- match macroはRegexLitを要求する
requires a raw regex literal string as second parameter; the regex must be known at compile time, and cannot be a var/let/const- 他の場面でstatic Regexを使ってほしくないのが主な理由っぽい
- static regexを使うべきなのはここだけなので、ユーザが自分でstatic regexを作る必要はない
- literals optimization
- https://nitely.github.io/2020/11/30/regex-literals-optimization.html
- find/findAllで使われている
- このIssueで他のエンジンとの比較がある: nitely/nim-regex#57
-
Kickstart engine (Shift-Or algorithm)
- このポストにあるBit-NFAはrevertされているが、Shift-Orはずっと利用されている https://dlang.org/blog/2016/11/07/big-performance-improvement-for-std-regex/
- commits
- Bit-NFA kickstart engine: dlang/phobos#4286
- disabled in CTFE: dlang/phobos#4995
- revert Bit-NFA: dlang/phobos#5113
-
Shift-Or algorithmについての見解
- https://news.ycombinator.com/item?id=17662324
- byteseek(Javaのバイト列のマッチングライブラリ)作者はshift-orについて
- 12文字以下の短い文字列に対して非常に有用
- booyer-mooreと違い全部の文字を走査する必要があるがビット並列を利用して一致を検証するので短い文字列では他の文字列検索アルゴリズムよりも性能が出せる
- BurntSushi氏(rustのregex作者)の見解:
- 経験上、ほとんどの場面で以下のヒューリスティックな方法が性能がでる
- 文字列中で最も頻度の低いバイトを選び、それをmemchrなどのベクトル最適化されたルーチンのスキップループとして利用する
- 経験上、ほとんどの場面で以下のヒューリスティックな方法が性能がでる
- byteseek(Javaのバイト列のマッチングライブラリ)作者はshift-orについて
- BurntSushi氏はbyte stringのライブラリについてのポストでもShift-Orについて言及している
- https://blog.burntsushi.net/bstr/#motivation-based-on-performance
- やはりSIMD化されたmemchrのほうが速いだろうという見解
- https://blog.burntsushi.net/bstr/#motivation-based-on-performance
- https://news.ycombinator.com/item?id=17662324
- コンパイル時に行うメリット
- https://blog.burntsushi.net/rust-regex-syntax-extensions/ (Rustのregex!マクロについて)
- 正規表現コンパイルのランタイムがゼロコスト
- 正規表現のコンパイルのエラーがプログラムのコンパイル時にわかる
- This specialization allows us to perform optimizations such as removing heap allocation and embedding the instructions directly instead of relying on a generalized algorithm.
- VMのヒープ割り当てが避けられる
- 特殊化された最適な命令シーケンスを埋め込める
- 欠点としてはコードサイズが肥大することだが、ある程度は最適化がはたらく
- Rustはregex!マクロをやめた: https://github.com/rust-lang/regex/blob/master/HACKING.md#the-regex-macro
- コンパイラプラグインのメンテが大変で、PikeVM以外対応できていない
- コンパイラプラグイン自体がメンテされなくなった
- PikeVM以外の高速な実装やliterals optimizationによるランタイムregexのほうが現状速い
- コンパイル時に生成できたほうがいいのは間違いないが、現状はプランはないとのこと
- https://blog.burntsushi.net/rust-regex-syntax-extensions/ (Rustのregex!マクロについて)
- 他の実装
- Nim: https://nitely.github.io/nim-regex/regex.html
- matchマクロに正規表現リテラルオブジェクトを渡すとコンパイル時にregexを生成
- Nim: https://nitely.github.io/nim-regex/regex.html
新しめの正規表現ライブラリにしては珍しく後方参照をサポートしており、実行時に後方参照が正規表現パターンにあるかどうかで正規表現エンジンを切り替えてるadaptiveな仕組みになっている。
matchFirst matchAll を使った場合、後方参照がある場合はバックトラック法、ない場合はトンプソンNFAが選択される。ドキュメントには記載がないが、後方参照は \1 のような構文のものが採用されている。また match を使った場合は明示的にThompson NFAを、 bmatch を使った場合は同様にバックトラック法が利用される。
private auto defaultFactoryImpl(Char)(const ref Regex!Char re)
{
(...)
if (re.backrefed.canFind!"a != 0")
{
if (backtrackingFactory is null)
backtrackingFactory = new RuntimeFactory!(BacktrackingMatcher, Char);
return backtrackingFactory;
}
else
{
if (thompsonFactory is null)
thompsonFactory = new RuntimeFactory!(ThompsonMatcher, Char);
return thompsonFactory;
}
}また常にVMを実行するのでは遅いため、kickstart engineによる最適化(Shift-Or)も実装されている。
Pike VM(Thompson NFAにキャプチャのグルーピングをサポートしたもの。Dのregexはこれにあたる)では、複数の状態になった場合にキャプチャ位置をシャッフルする必要があったり、何度も同じイプシロン遷移をたどる必要があるために多くの時間を費やすことになるらしい。
他の実装ではRustやNimの正規表現エンジンはLiterals Optimizationを実装しているが、D言語のものはShift-Orアルゴリズムを使用している点がユニークである。
以降は注記がない場合トンプソンNFAの実装を参照する。 これは内部的にkickstart engnineによる最適化ステップ(Shift-Or)も含まれている。
matchFirst 関数はエンジンのmatch関数に対応し、 match関数ではさらに kickstart エンジンを利用するかどうかのコンパイル時分岐がある。
override int match(Group!DataIndex[] matches)
{
(...)
static if (kicked)
if (!re.kickstart.empty)
return matchImpl!(true)(matches);
return matchImpl!(false)(matches);
}kickstartエンジンを利用するかどうかはエンジンを生成する際に渡されるStreamTypeによって決まる。
static if (__traits(hasMember,Stream, "search"))
{
enum kicked = true;
}
else
enum kicked = false;RuntimeFactory関数ではInput!CharがStreamTypeとしてコンストラクタ経由で渡されている。
// A factory for run-time engines
class RuntimeFactory(alias EngineType, Char) : GenericFactory!(EngineType, Char)
{
override EngineType!Char construct(const ref Regex!Char re, in Char[] input, void[] memory) const
{
import core.lifetime : emplace;
return emplace!(EngineType!Char)(memory[0 .. classSize],
re, Input!Char(input), memory[classSize .. $]);
}
}これはsearch関数をメンバに持っているのでkickstartエンジンが使われる。
//Simple UTF-string abstraction compatible with stream interface
struct Input(Char)
if (is(Char :dchar))
{
(...)
bool search(Kickstart)(ref const Kickstart kick, ref dchar res, ref size_t pos)
{
size_t idx = kick.search(_origin, _index);
_index = idx;
return nextChar(res, pos);
}
(...)
}いったんmatchImpl関数に戻ると、まず初回は(可能な場合は)search関数を呼ぶようになっている。ThompsonMatcherのsearch関数は上記のInputのsearch関数を呼んでおり、さらにここからkickstartエンジンのsearch関数を呼ぶようになっている。
//match the input and fill matches
int matchImpl(bool withSearch)(Group!DataIndex[] matches)
{
if (!matched && clist.empty)
{
static if (withSearch)
search();
else
next();
}
else//char in question is fetched in prev call to match
{
matched = 0;
}Kickstart エンジンは Shift-Or アルゴリズムを使っており、search関数はそのアルゴリズムの実装になっている。現在の遷移状態に文字が来ている場合にhaystackとの最初のマッチングまでは memchr でスキップする高速化を行っている点と各種UTFエンコーディングに対応しているのが特徴といえる。
// lookup compatible bit pattern in haystack, return starting index
// has a useful trait: if supplied with valid UTF indexes,
// returns only valid UTF indexes
// (that given the haystack in question is valid UTF string)
@trusted size_t search(const(Char)[] haystack, size_t idx) const
{//@BUG: apparently assumes little endian machines
import core.stdc.string : memchr;
import std.conv : text;
assert(!empty);
auto p = cast(const(ubyte)*)(haystack.ptr+idx);
uint state = uint.max;
uint limit = 1u<<(n_length - 1u);
debug(std_regex_search) writefln("Limit: %32b",limit);
if (fChar != uint.max)
{
const(ubyte)* end = cast(ubyte*)(haystack.ptr + haystack.length);
const orginalAlign = cast(size_t) p & (Char.sizeof-1);
while (p != end)
{
if (!~state)
{//speed up seeking first matching place
for (;;)
{
assert(p <= end, text(p," vs ", end));
p = cast(ubyte*) memchr(p, fChar, end - p);
if (!p)
return haystack.length;
if ((cast(size_t) p & (Char.sizeof-1)) == orginalAlign)
break;
if (++p == end)
return haystack.length;
}
state = ~1u;
assert((cast(size_t) p & (Char.sizeof-1)) == orginalAlign);
static if (charSize == 3)
{
state = (state << 1) | table[p[1]];
state = (state << 1) | table[p[2]];
p += 4;
}
else
p++;
//first char is tested, see if that's all
if (!(state & limit))
return (p-cast(ubyte*) haystack.ptr)/Char.sizeof
-length;
}
else
{//have some bits/states for possible matches,
//use the usual shift-or cycle
static if (charSize == 3)
{
state = (state << 1) | table[p[0]];
state = (state << 1) | table[p[1]];
state = (state << 1) | table[p[2]];
p += 4;
}
else
{
state = (state << 1) | table[p[0]];
p++;
}
if (!(state & limit))
return (p-cast(ubyte*) haystack.ptr)/Char.sizeof
-length;
}
debug(std_regex_search) writefln("State: %32b", state);
}
}
else
{
//normal path, partially unrolled for char/wchar
static if (charSize == 3)
{
const(ubyte)* end = cast(ubyte*)(haystack.ptr + haystack.length);
while (p != end)
{
state = (state << 1) | table[p[0]];
state = (state << 1) | table[p[1]];
state = (state << 1) | table[p[2]];
p += 4;
if (!(state & limit))//division rounds down for dchar
return (p-cast(ubyte*) haystack.ptr)/Char.sizeof
-length;
}
}
else
{
auto len = cast(ubyte*)(haystack.ptr + haystack.length) - p;
size_t i = 0;
if (len & 1)
{
state = (state << 1) | table[p[i++]];
if (!(state & limit))
return idx+i/Char.sizeof-length;
}
while (i < len)
{
state = (state << 1) | table[p[i++]];
if (!(state & limit))
return idx+i/Char.sizeof
-length;
state = (state << 1) | table[p[i++]];
if (!(state & limit))
return idx+i/Char.sizeof
-length;
debug(std_regex_search) writefln("State: %32b", state);
}
}
}
return haystack.length;
}