原文 | Stephen Toub
翻譯 | 鄭子銘
在.NET 7中，Regex得到了幾個新的方法，所有這些方法都能提高效能。新的API的簡單性可能也誤導了為實現它們所需的工作量，特別是由於新的API都支援ReadOnlySpan
dotnet/runtime#65473將Regex帶入了基於跨度的.NET時代，克服了Regex自跨度在.NET Core 2.1中引入後的一個重要限制。Regex在歷史上一直是基於處理System.String輸入的，這一事實貫穿了Regex的設計和實現，包括在.NET Framework中依賴的擴充套件性模型Regex.CompileToAssembly所暴露的API（CompileToAssembly現在已經被淘汰，在.NET Core中從未發揮作用）。依賴於字串作為輸入的性質的一個微妙之處在於如何將匹配資訊返回給呼叫者。Regex.Match返回一個Match物件，代表輸入中的第一個匹配，而這個Match物件暴露了一個NextMatch方法，可以移動到下一個匹配。這意味著Match物件需要儲存對輸入的參照，這樣它就可以作為NextMatch呼叫的一部分被反饋到匹配引擎。如果這個輸入是一個字串，很好，沒有問題。但是如果輸入的是一個ReadOnlySpan
首先，我們使FindFirstChar和Go成為虛擬的，而不是抽象的。分割這些方法的設計在很大程度上是過時的，特別是強制分離了一個處理階段，即找到匹配的下一個可能的位置，然後是在該位置實際執行匹配的階段，這與所有的引擎並不一致，比如NonBacktracking使用的引擎（它最初將FindFirstChar作為一個nop實現，並將其所有邏輯放在Go中）。然後我們新增了一個新的虛擬掃描方法，重要的是，它需要一個ReadOnlySpan
[Benchmark]
[Arguments("abc", 0, 3)]
public void Scan(string input, int beginning, int length)
{
for (int i = beginning; i < length; i++)
{
Check(input[i]);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Check(char c) { }
這將導致JIT產生類似這樣的組合程式碼。
; Program.Scan(System.String, Int32, Int32)
sub rsp,28
cmp r8d,r9d
jge short M00_L01
mov eax,[rdx+8]
M00_L00:
cmp r8d,eax
jae short M00_L02
inc r8d
cmp r8d,r9d
jl short M00_L00
M00_L01:
add rsp,28
ret
M00_L02:
call CORINFO_HELP_RNGCHKFAIL
int 3
; Total bytes of code 36
相比之下，如果我們處理的是一個跨度，它已經考慮了邊界的因素，那麼我們可以寫一個更規範的迴圈，比如這樣。
[Benchmark]
[Arguments("abc")]
public void Scan(ReadOnlySpan<char> input)
{
for (int i = 0; i < input.Length; i++)
{
Check(input[i]);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Check(char c) { }
而當涉及到編譯器時，典範形式的東西確實很好，因為程式碼的形狀越常見，越有可能被大量優化。
; Program.Scan(System.ReadOnlySpan`1<Char>)
mov rax,[rdx]
mov edx,[rdx+8]
xor ecx,ecx
test edx,edx
jle short M00_L01
M00_L00:
mov r8d,ecx
movsx r8,word ptr [rax+r8*2]
inc ecx
cmp ecx,edx
jl short M00_L00
M00_L01:
ret
; Total bytes of code 27
因此，即使不考慮以跨度為單位的操作所帶來的其他好處，我們也能從以跨度為單位執行所有的邏輯中立即獲得低階別的程式碼生成好處。雖然上面的例子是編造的（顯然匹配邏輯比一個簡單的for迴圈做得更多），但這裡有一個真實的例子。當一個regex包含一個/b，作為針對該/b評估輸入的一部分，回溯引擎呼叫一個RegexRunner.IsBoundary輔助方法，該方法檢查當前位置的字元是否是一個單詞字元，以及它之前的字元是否是一個單詞字元（也考慮到了輸入的邊界）。下面是基於字串的IsBoundary方法的樣子（它使用的runtext是RegexRunner上儲存輸入的字串欄位的名稱）。
[Benchmark]
[Arguments(0, 0, 26)]
public bool IsBoundary(int index, int startpos, int endpos)
{
return (index > startpos && IsBoundaryWordChar(runtext[index - 1])) !=
(index < endpos && IsBoundaryWordChar(runtext[index]));
}
[MethodImpl(MethodImplOptions.NoInlining)]
private bool IsBoundaryWordChar(char c) => false;
這裡是跨度版本的樣子。
[Benchmark]
[Arguments("abcdefghijklmnopqrstuvwxyz", 0)]
public bool IsBoundary(ReadOnlySpan<char> inputSpan, int index)
{
int indexM1 = index - 1;
return ((uint)indexM1 < (uint)inputSpan.Length && IsBoundaryWordChar(inputSpan[indexM1])) !=
((uint)index < (uint)inputSpan.Length && IsBoundaryWordChar(inputSpan[index]));
}
[MethodImpl(MethodImplOptions.NoInlining)]
private bool IsBoundaryWordChar(char c) => false;
這裡是所產生的結果集
; Program.IsBoundary(Int32, Int32, Int32)
push rdi
push rsi
push rbp
push rbx
sub rsp,28
mov rdi,rcx
mov esi,edx
mov ebx,r9d
cmp esi,r8d
jle short M00_L00
mov rcx,rdi
mov rcx,[rcx+8]
lea edx,[rsi-1]
cmp edx,[rcx+8]
jae short M00_L04
mov edx,edx
movzx edx,word ptr [rcx+rdx*2+0C]
mov rcx,rdi
call qword ptr [Program.IsBoundaryWordChar(Char)]
jmp short M00_L01
M00_L00:
xor eax,eax
M00_L01:
mov ebp,eax
cmp esi,ebx
jge short M00_L02
mov rcx,rdi
mov rcx,[rcx+8]
cmp esi,[rcx+8]
jae short M00_L04
mov edx,esi
movzx edx,word ptr [rcx+rdx*2+0C]
mov rcx,rdi
call qword ptr [Program.IsBoundaryWordChar(Char)]
jmp short M00_L03
M00_L02:
xor eax,eax
M00_L03:
cmp ebp,eax
setne al
movzx eax,al
add rsp,28
pop rbx
pop rbp
pop rsi
pop rdi
ret
M00_L04:
call CORINFO_HELP_RNGCHKFAIL
int 3
; Total bytes of code 117
; Program.IsBoundary(System.ReadOnlySpan`1<Char>, Int32)
push r14
push rdi
push rsi
push rbp
push rbx
sub rsp,20
mov rdi,rcx
mov esi,r8d
mov rbx,[rdx]
mov ebp,[rdx+8]
lea edx,[rsi-1]
cmp edx,ebp
jae short M00_L00
mov edx,edx
movzx edx,word ptr [rbx+rdx*2]
mov rcx,rdi
call qword ptr [Program.IsBoundaryWordChar(Char)]
jmp short M00_L01
M00_L00:
xor eax,eax
M00_L01:
mov r14d,eax
cmp esi,ebp
jae short M00_L02
mov edx,esi
movzx edx,word ptr [rbx+rdx*2]
mov rcx,rdi
call qword ptr [Program.IsBoundaryWordChar(Char)]
jmp short M00_L03
M00_L02:
xor eax,eax
M00_L03:
cmp r14d,eax
setne al
movzx eax,al
add rsp,20
pop rbx
pop rbp
pop rsi
pop rdi
pop r14
ret
; Total bytes of code 94
這裡最值得注意的是。
call CORINFO_HELP_RNGCHKFAIL
int 3
在第一個版本的結尾處有一個在第二個版本結尾處不存在的程式碼。正如我們前面看到的，當JIT發出程式碼丟擲陣列、字串或跨度的索引超出範圍的異常時，生成的程式集就是這個樣子。它在最後，因為它被認為是 "冷 "的，很少執行。它存在於第一種情況中，因為JIT無法根據對該函數的區域性分析證明runtext[index-1]和runtext[index]的存取將在字串的範圍內（它無法知道或相信startpos、endpos和runtext的邊界之間的任何隱含關係）。但是在第二種情況下，JIT可以知道並相信ReadOnlySpan
好了，現在引擎能夠被交給跨度輸入並處理它們，很好，我們能用它做什麼？好吧，Regex.IsMatch很簡單：它不需要進行多次匹配，因此不需要擔心如何儲存輸入的ReadOnlySpan
所以，IsMatch和Count可以與跨度一起工作。但是，我們仍然沒有一個方法可以讓你真正得到匹配的資訊。輸入新的EnumerateMatches方法，由dotnet/runtime#67794新增。EnumerateMatches與Match非常相似，只是它不是交回一個Match類範例，而是交回一個Ref結構的列舉元。
public ref struct ValueMatchEnumerator
{
private readonly Regex _regex;
private readonly ReadOnlySpan<char> _input;
private ValueMatch _current;
private int _startAt;
private int _prevLen;
...
}
作為一個參照結構，列舉元能夠儲存對輸入跨度的參照，因此能夠通過匹配進行迭代，這些匹配由 ValueMatch 參照結構表示。值得注意的是，今天 ValueMatch 不提供捕獲資訊，這也使它能夠參與之前提到的對 Count 的優化。即使你有一個輸入字串，EnumerateMatches也是一種對輸入的所有匹配進行無分配列舉的方法。不過，在.NET 7中，如果你還需要所有的捕獲資料，就沒有辦法實現這種無分配的列舉。如果需要的話，我們會在未來研究設計這個問題。
如前所述，所有引擎的核心是一個Scan(ReadOnlySpan
protected override void Scan(ReadOnlySpan<char> inputSpan)
{
while (!TryMatchAtCurrentPosition(inputSpan) &&
base.runtextpos != inputSpan.Length)
{
base.runtextpos++;
}
}
我們試圖匹配當前位置的輸入，如果我們成功地做到了這一點，我們就退出。然而，如果當前位置不匹配，那麼如果有任何剩餘的輸入，我們就 "撞 "一下位置，重新開始這個過程。在片語引擎術語中，這通常被稱為 "bumpalong迴圈"。然而，如果我們真的在每個輸入字元上都執行完整的匹配過程，那就會變得不必要的緩慢。對於許多模式來說，有些東西可以讓我們在進行完全匹配時考慮得更周全，快速跳過那些不可能匹配的位置，而只把時間和資源花在真正有機會匹配的位置上。為了將這一概念提升到一流水平，回溯引擎的 "bumpalong迴圈 "通常更像下面這樣（我說 "通常 "是因為在某些情況下，編譯的和原始碼生成的片語能夠生成更好的東西）。
protected override void Scan(ReadOnlySpan<char> inputSpan)
{
while (TryFindNextPossibleStartingPosition(inputSpan) &&
!TryMatchAtCurrentPosition(inputSpan) &&
base.runtextpos != inputSpan.Length)
{
base.runtextpos++;
}
}
和之前的FindFirstChar一樣，那個TryFindNextPossibleStartingPosition的責任是儘快搜尋下一個匹配的地方（或者確定沒有其他東西可能匹配，在這種情況下，它將返回false，迴圈退出）。如同FindFirstChar，而且它被嵌入了多種方式來完成其工作。在.NET 7中，TryFindNextPossibleStartingPosition學會了許多更多和改進的方法來幫助引擎快速。
在.NET 6中，直譯器引擎實際上有兩種實現TryFindNextPossibleStartingPosition的方法：如果模式以至少兩個字元的字串（可能不區分大小寫）開始，則採用Boyer-Moore子串搜尋，以及對已知是所有可能開始匹配的字元集的字元類進行線性掃描。對於後一種情況，直譯器有八種不同的匹配實現，基於RegexOptions.RightToLeft是否被設定，字元類是否需要不區分大小寫的比較，以及字元類是否只包含單個字元或多個字元的組合。其中一些比其他的更優化，例如，從左到右、大小寫敏感的單字元搜尋將使用IndexOf(char)來搜尋下一個位置，這是在.NET 5中新增的優化。然而，每次執行這個操作時，引擎都需要重新計算是哪種情況。dotnet/runtime#60822改進了這一點，引入了TryFindNextPossibleStartingPosition用來尋找下一個機會的策略的內部列舉，為TryFindNextPossibleStartingPosition增加了一個開關，以快速跳到正確的策略，並在構造直譯器時預先計算使用哪個策略。這不僅使直譯器在比賽時的實現更快，而且使其有效地免費（就比賽時的執行時間開銷而言）增加額外的策略。
dotnet/runtime#60888然後新增了第一個額外的策略。該實現已經能夠使用IndexOf(char)，但是正如之前在這篇文章中提到的，IndexOf(ReadOnlySpan
private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@"\belementary\b", RegexOptions.Compiled);
[Benchmark]
public int Count() => _regex.Matches(s_haystack).Count;
| 方法 | 執行時 | 平均值 | 比率 |
|---|---|---|---|
| Count | .NET 6.0 | 377.32 us | 1.00 |
| Count | .NET 7.0 | 55.44 us | 0.15 |
dotnet/runtime#61490然後完全刪除了Boyer-Moore。在之前提到的PR中沒有這樣做，因為缺乏處理大小寫不敏感匹配的好方法。然而，這個PR也對ASCII字母進行了特殊處理，以教導優化器如何將ASCII不區分大小寫的匹配轉化為該字母的兩種大小寫的集合（不包括少數已知的問題，如i和k，它們都可能受到所採用的文化的影響，並且可能將不區分大小寫對映為兩個以上的值）。有了足夠多的常見情況，與其使用Boyer-Moore來進行不區分大小寫的搜尋，不如直接使用IndexOfAny(char, char, ...)來搜尋起始集，而且IndexOfAny採用的向量化最終在現實世界中大大超過了老的實現。這個PR比這更進一步，它不只是發現 "起始集"，而是能夠找到所有可能與模式相匹配的字元類，這些字元類與起始集有一個固定的偏移量；然後讓分析器有能力選擇預計最不常見的集合，並對其進行搜尋，而不是恰好位於起始集的任何東西。PR也走得更遠，這在很大程度上是由非反向追蹤引擎所激發的。非反向追蹤引擎的原型實現在到達起始狀態時也使用了IndexOfAny(char, char, ...)，因此能夠快速跳過那些沒有機會將其推到下一個狀態的輸入文字。我們希望所有的引擎都能共用盡可能多的邏輯，特別是圍繞這個速度的提前，所以這個PR將直譯器和非反向追蹤引擎統一起來，讓它們共用完全相同的TryFindNextPossibleStartingPosition例程（非反向追蹤引擎只是在其圖形遍歷迴圈的適當位置呼叫）。由於非反向追蹤引擎已經在以這種方式使用IndexOfAny，最初不這樣做會對我們測量的各種模式產生明顯的倒退，這導致我們投資在所有地方使用它。這個PR還在編譯引擎中引入了第一個不區分大小寫的比較的特殊情況，例如，如果我們發現一個集合是[Ee]，而不是發出類似於c == 'E' || c == 'e'的檢查，我們會發出類似於(c | 0x20) == 'e' 的檢查（前面討論的那些有趣的ASCII技巧又開始發揮作用了）。
private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@"\belementary\b", RegexOptions.Compiled | RegexOptions.IgnoreCase);
[Benchmark]
public int Count() => _regex.Matches(s_haystack).Count;
| 方法 | 執行時 | 平均值 | 比率 |
|---|---|---|---|
| Count | .NET 6.0 | 499.3 us | 1.00 |
| Count | .NET 7.0 | 177.7 us | 0.35 |
以前的PR開始把IgnoreCase模式的文字變成集合，特別是ASCII，例如(?i)a會變成[Aa]。那個PR在知道會有更完整的東西出現的情況下，黑進了對ASCII的支援，正如它在dotnet/runtime#67184中所做的那樣。與其寫死只有ASCII字元對映到的不區分大小寫的集合，這個PR本質上是寫死每個可能的字元的集合。一旦這樣做了，我們就不再需要在匹配時知道大小寫不敏感的問題，而是可以在有效的匹配集上加倍努力，我們已經需要能夠很好地做到這一點。現在，我說它對每個可能的字元都進行了編碼；這並不完全正確。如果是真的，那就會佔用大量的記憶體，事實上，大部分的記憶體都會被浪費掉，因為絕大多數的字元都不參與大小寫轉換......我們需要處理的字元只有大約2000個。因此，該實現採用了一個三層表方案。第一個表有64個元素，將全部字元分為64個組；在這64個組中，有54個沒有參與大小寫轉換的字元，所以如果我們遇到這些條目，我們可以立即停止搜尋。對於剩下的10個在其範圍內至少有一個字元參與的條目，第一個表中的字元和值被用來計算第二個表中的索引；在那裡，大多數條目都說沒有任何字元參與大小寫轉換。只有當我們在第二張表中得到一個合法條目時，才會給我們一個進入第三張表的索引，在這個位置我們可以找到所有被認為與第一張表大小寫相等的字元。
dotnet/runtime#63477（後來又在dotnet/runtime#66572中進行了改進），繼續增加了另一種搜尋策略，這個策略的靈感來自於nim-regex的字面優化。我們從效能的角度跟蹤了大量的片語，以確保我們在常見的情況下沒有倒退，並幫助指導投資。其中一個是mariomka/regex-benchmark語言的regex基準的模式集。其中一個是針對URI的：（@"[\w]+://[/\s?#]+[\s?#]+(?:?[\s#]*)?(?:#[\s]*)?" 。這個模式違背了迄今為止所啟用的尋找下一個好位置的策略，因為它保證以 "單詞字元"（\w）開始，其中包括65,000個可能的字元中的50,000個；我們沒有一個好的方法來對這樣一個字元類進行向量搜尋。然而，這個模式很有趣，它以一個迴圈開始，不僅如此，它是一個上界迴圈，我們的分析將確定它是原子性的，因為保證緊隨迴圈的字元是一個':'，它本身不是一個單詞字元，因此，沒有什麼迴圈可以匹配並放棄作為回溯的一部分，可以匹配':'。這一切使我們有了一種不同的向量化方法：與其試圖搜尋\w字元類，不如搜尋子串"