【譯】.NET 7 中的效能改進（十一）
原文 | Stephen Toub
翻譯 | 鄭子銘
同樣，為了不做不必要的工作，有一個相當常見的模式出現在string.Substring和span.Slice等方法中。
span = span.Slice(offset, str.Length - offset);
這裡需要注意的是，這些方法都有過載，只取起始偏移量。由於指定的長度是指定偏移量後的剩餘部分，所以呼叫可以簡化為。
span = span.Slice(offset);
這不僅可讀性和可維護性更強，而且還有一些小的效率優勢，例如，在64位元上，Slice(int, int)建構函式比Slice(int)有一個額外的加法，而對於32位元，Slice(int, int)建構函式會產生一個額外的比較和分支。因此，簡化這些呼叫對程式碼維護和效能都是有益的，dotnet/runtime#68937對所有發現的該模式的出現都進行了簡化。dotnet/runtime#73882使其更具影響力，它簡化了string.Substring，以消除不必要的開銷，例如，它將四個引數驗證檢查濃縮為一個快速路徑比較（在64位元程序中）。
好了，關於弦的問題就到此為止。那跨度呢？C# 11中最酷的功能之一是對Ref欄位的新支援。什麼是參照欄位？你對C#中的參照很熟悉，我們已經討論過它們本質上是可管理的指標，也就是說，由於它參照的物件在堆上被移動，執行時可以隨時更新的指標。這些參照可以指向物件的開頭，也可以指向物件內部的某個地方，在這種情況下，它們被稱為 "內部指標"。Ref從1.0開始就存在於C#中，但那時它主要是通過參照傳遞給方法呼叫，例如
class Data
{
public int Value;
}
...
void Add(ref int i)
{
i++;
}
...
var d = new Data { Value = 42 };
Add(ref d.Value);
Debug.Assert(d.Value == 43);
後來的C#版本增加了擁有本地參考文獻的能力，例如。
void Add(ref int i)
{
ref j = ref i;
j++;
}
甚至是要有 ref 的返回，例如
ref int Add(ref int i)
{
ref j = ref i;
j++;
return ref j;
}
這些設施更為先進，但它們在整個更高效能的程式碼庫中被廣泛使用，近年來.NET中的許多優化在很大程度上是由於這些與ref相關的能力而實現的。
Span
private T[] _items;
...
public T this[int i]
{
get => _items[i];
set => _items[i] = value;
}
但不是 span。Span
public ref T this[int index]
{
get
{
if ((uint)index >= (uint)_length)
ThrowHelper.ThrowIndexOutOfRangeException();
return ref Unsafe.Add(ref _reference, index);
}
}
注意這裡只有一個getter，沒有setter；這是因為它返回一個指向實際儲存位置的ref T。它是一個可寫的參照，所以你可以對它進行賦值，例如，你可以寫。
span[i] = value;
但這並不等同於呼叫一些設定器。
span.set_Item(i, value);
它實際上等同於使用getter來檢索參照，然後通過該參照寫入一個值，比如說
ref T item = ref span.get_Item(i);
item = value;
這一切都很好，但是getter定義中的_reference是什麼？好吧，Span
public readonly ref struct Span<T>
{
internal readonly ref T _reference;
private readonly int _length;
...
}
ref欄位在整個dotnet/runtime中的推廣是在dotnet/runtime#71498中完成的，此前C#語言主要是在dotnet/roslyn#62155中獲得了這種支援，這本身就是許多PR的高潮，首先是一個特性分支。Ref欄位本身不會自動提高效能，但它確實大大簡化了程式碼，它允許使用ref欄位的新自定義程式碼，以及利用它們的新API，這兩者都可以幫助提高效能（特別是在不犧牲潛在安全的情況下的效能）。新API的一個例子是ReadOnlySpan
public Span(ref T reference);
public ReadOnlySpan(in T reference);
在dotnet/runtime#67447中新增的（然後在dotnet/runtime#71589中公開並更廣泛地使用）。這可能會引出一個問題：考慮到跨度已經能夠儲存一個參照，為什麼對參照欄位的支援能夠使兩個新的建構函式接受參照？畢竟，MemoryMarshal.CreateSpan(ref T reference, int length)和相應的CreateReadOnlySpan方法已經存在了很長時間，而這些新的建構函式相當於呼叫那些長度為1的方法。 答案是：安全。
想象一下，如果你可以隨意地呼叫這個建構函式。你就可以寫出這樣的程式碼了。
public Span<int> RuhRoh()
{
int i = 42;
return new Span<int>(ref i);
}
在這一點上，這個方法的呼叫者得到了一個指向垃圾的跨度；這在本應是安全的程式碼中是很糟糕的。你已經可以通過使用指標來完成同樣的事情。
public Span<int> RuhRoh()
{
unsafe
{
int i = 42;
return new Span<int>(&i, 1);
}
}
但在這一點上，你已經承擔了使用不安全程式碼和指標的風險，任何由此產生的問題都在你身上。在C# 11中，如果你現在試圖使用基於Ref的建構函式來編寫上述程式碼，你會遇到這樣的錯誤。
error CS8347: Cannot use a result of 'Span<int>.Span(ref int)' in this context because it may expose variables referenced by parameter 'reference' outside of their declaration scope
換句話說，編譯器現在理解Span
通常情況下，解決了一個問題，就會把罐子踢到路上，並暴露出另一個問題。編譯器現在認為，傳遞給 ref 結構上的方法的 ref 可以使該 ref 結構範例儲存該 ref（注意，傳遞給 ref 結構上的方法的 ref 結構已經是這種情況），但是如果我們不希望這樣呢？如果我們想說 "這個 ref 是不可儲存的，並且不應該逃出呼叫範圍 "呢？從呼叫者的角度來看，我們希望編譯器能夠允許傳入這樣的 ref，而不抱怨潛在的壽命延長；從呼叫者的角度來看，我們希望編譯器能夠阻止方法做它不應該做的事情。進入作用域。這個新的C#關鍵字所做的正是我們所希望的：把它放在一個Ref或Ref結構引數上，編譯器將保證（不使用不安全的程式碼）該方法不能把引數藏起來，然後使呼叫者能夠編寫依賴該保證的程式碼。例如，考慮這個程式。
var writer = new SpanWriter(stackalloc char[128]);
Append(ref writer, 123);
writer.Write(".");
Append(ref writer, 45);
Console.WriteLine(writer.AsSpan().ToString());
static void Append(ref SpanWriter builder, byte value)
{
Span<char> tmp = stackalloc char[3];
value.TryFormat(tmp, out int charsWritten);
builder.Write(tmp.Slice(0, charsWritten));
}
ref struct SpanWriter
{
private readonly Span<char> _chars;
private int _length;
public SpanWriter(Span<char> destination) => _chars = destination;
public Span<char> AsSpan() => _chars.Slice(0, _length);
public void Write(ReadOnlySpan<char> value)
{
if (_length > _chars.Length - value.Length)
{
throw new InvalidOperationException("Not enough remaining space");
}
value.CopyTo(_chars.Slice(_length));
_length += value.Length;
}
}
我們有一個Ref結構SpanWriter，它的建構函式接受一個Span
error CS8350: This combination of arguments to 'SpanWriter.Write(ReadOnlySpan<char>)' is disallowed because it may expose variables referenced by parameter 'value' outside of their declaration scope
我們該怎麼做呢？Write方法實際上並沒有儲存引數值，而且也不需要，所以我們可以改變方法的簽名，將其註釋為範圍。
public void Write(scoped ReadOnlySpan<char> value)
如果Write試圖儲存值，編譯器會拒絕。
error CS8352: Cannot use variable 'ReadOnlySpan<char>' in this context because it may expose referenced variables outside of their declaration scope
但由於它沒有嘗試這樣做，現在一切都編譯成功了。你可以在前面提到的dotnet/runtime#71589中看到關於如何利用這個的例子。
還有另一個方向：有些東西是隱式範圍的，比如結構上的this參照。考慮一下這段程式碼。
public struct SingleItemList
{
private int _value;
public ref int this[int i]
{
get
{
if (i != 0) throw new IndexOutOfRangeException();
return ref _value;
}
}
}
這將產生一個編譯器錯誤。
error CS8170: Struct members cannot return 'this' or other instance members by reference
有效地，這是因為這是隱含的範圍（儘管這個關鍵詞以前並不存在）。如果我們想讓這樣的專案能夠被返回呢？輸入[UnscopedRef]。這在需求中是很罕見的，以至於它沒有得到自己的C#語言關鍵字，但C#編譯器確實識別了新的[UnscopedRef]屬性。它可以被放到相關的引數上，也可以放到方法和屬性上，在這種情況下，它適用於該成員的這個參照。因此，我們可以將之前的程式碼例子修改為：。
[UnscopedRef]
public ref int this[int i]
而現在程式碼將被成功編譯。當然，這也對這個方法的呼叫者提出了要求。對於一個呼叫站點來說，編譯器看到了被呼叫成員上的[UnscopedRef]，然後知道返回的ref可能會參照該結構中的一些東西，因此給返回的ref分配了與該結構相同的生命週期。因此，如果該結構是一個生活在堆疊上的區域性，那麼該參照也將被限制在同一方法上。
另一個有影響的跨度相關的變化來自於dotnet/runtime#70095，來自@teo-tsirpanis。System.HashCode的目標是為產生高質量的雜湊碼提供一個快速、易於使用的實現。在其目前的版本中，它包含了一個隨機的全程序種子，並且是xxHash32非加密雜湊演演算法的實現。在之前的版本中，HashCode增加了一個AddBytes方法，該方法接受一個ReadOnlySpan
private byte[] _data = Enumerable.Range(0, 256).Select(i => (byte)i).ToArray();
[Benchmark]
public int AddBytes()
{
HashCode hc = default;
hc.AddBytes(_data);
return hc.ToHashCode();
}
| 方法 | 執行時 | 平均值 | 比率 |
|---|---|---|---|
| AddBytes | .NET 6.0 | 159.11 ns | 1.00 |
| AddBytes | .NET 7.0 | 42.11 ns | 0.26 |
另一個與跨度有關的變化，dotnet/runtime#72727重構了一堆程式碼路徑，以消除一些快取的陣列。為什麼要避免快取陣列？畢竟，快取一次陣列並反覆使用它不是可取的嗎？是的，如果那是最好的選擇，但有時有更好的選擇。例如，其中一個變化採取了這樣的程式碼。
private static readonly char[] s_pathDelims = { ':', '\\', '/', '?', '#' };
...
int index = value.IndexOfAny(s_pathDelims);
並將其替換為以下程式碼。
int index = value.AsSpan().IndexOfAny(@":\/?#");
這有很多好處。在可用性方面的好處是使被搜尋的令牌靠近使用地點，在可用性方面的好處是列表是不可改變的，這樣某些地方的程式碼就不會意外地替換陣列中的一個值。但也有效能方面的好處。我們不需要一個額外的欄位來儲存陣列。我們不需要作為這個型別的靜態建構函式的一部分來分配陣列。而且，載入/使用字串的速度也稍微快一些。
private static readonly char[] s_pathDelims = { ':', '\\', '/', '?', '#' };
private static readonly string s_value = "abcdefghijklmnopqrstuvwxyz";
[Benchmark]
public int WithArray() => s_value.IndexOfAny(s_pathDelims);
[Benchmark]
public int WithString() => s_value.AsSpan().IndexOfAny(@":\/?#");
| 方法 | 平均值 | 比率 |
|---|---|---|
| WithArray | 8.601 ns | 1.00 |
| WithString | 6.949 ns | 0.81 |
另一個例子來自該PR，其程式碼大致如下。
private static readonly char[] s_whitespaces = new char[] { ' ', '\t', '\n', '\r' };
...
switch (attr.Value.Trim(s_whitespaces))
{
case "preserve": return Preserve;
case "default": return Default;
}
並將其替換為以下程式碼。
switch (attr.Value.AsSpan().Trim(" \t\n\r"))
{
case "preserve": return Preserve;
case "default": return Default;
}
在這種情況下，我們不僅避免了char[]，而且如果文字確實需要修剪空白處，新版本（修剪一個跨度而不是原始字串）將為修剪後的字串儲存一個分配。這是在利用C#11的新特性，即支援在ReadOnlySpan
當然，在某些情況下，陣列是完全不必要的。在那份PR中，有幾個這樣的案例。
private static readonly char[] WhiteSpaceChecks = new char[] { ' ', '\u00A0' };
...
int wsIndex = target.IndexOfAny(WhiteSpaceChecks, targetPosition);
if (wsIndex < 0)
{
return false;
}
通過改用跨度，我們也可以這樣寫。
int wsIndex = target.AsSpan(targetPosition).IndexOfAny(' ', '\u00A0');
if (wsIndex < 0)
{
return false;
}
wsIndex += targetPosition;
MemoryExtensions.IndexOfAny對兩個和三個引數有專門的過載，這時我們根本不需要陣列（這些過載也恰好更快；當傳遞一個兩個字元的陣列時，實現會從陣列中提取兩個字元並傳遞給同一個雙引數的實現）。dotnet/runtime#60409刪除了一個單字元陣列，該陣列被快取以傳遞給string.Split，取而代之的是使用直接接受單字元的Split過載。
最後，來自@NewellClark的 dotnet/runtime#59670 擺脫了更多的陣列。我們在前面看到了C#編譯器是如何對用恆定長度和恆定元素構造的byte[]進行特殊處理的，並立即將其轉換為ReadOnlySpan
正則 (Regex)
早在5月份，我就分享了一篇關於.NET 7中正規表示式改進的詳細文章。回顧一下，在.NET 5之前，Regex的實現已經有相當長的時間沒有被觸動過了。在.NET 5中，我們從效能的角度出發，將其恢復到與其他多個行業的實現相一致或更好。.NET 7在此基礎上進行了一些重大的飛躍。如果你還沒有讀過這篇文章，請你現在就去讀，我等著你......
歡迎回來。有了這個背景，我將避免在這裡重複內容，而是專注於這些改進到底是如何產生的，以及這樣做的PR。
RegexOptions.NonBacktracking
讓我們從Regex中較大的新功能之一開始，即新的RegexOptions.NonBacktracking實現。正如在上一篇文章中所討論的，RegexOptions.NonBacktracking將Regex的處理轉為使用基於有限自動機的新引擎。它有兩種主要的執行模式，一種是依靠DFA (deterministic finite automata)（確定的有限自動機），一種是依靠NFA (non-deterministic finite automata)（非確定的有限自動機）。這兩種實現方式都提供了一個非常有價值的保證：處理時間與輸入的長度成線性關係。而反追蹤引擎 (backtracking engine)（如果沒有指定NonBacktracking，Regex就會使用這種引擎）可能會遇到被稱為 "災難性反追蹤 (catastrophic backtracking)"的情況，即有問題的表示式與有問題的輸入相結合會導致輸入長度的指數級處理，NonBacktracking保證它只會對輸入中的每個字元做一個攤薄的恆定量。在DFA的情況下，這個常數是非常小的。對於NFA，這個常數可以大得多，基於模式的複雜性，但對於任何給定的模式，工作仍然是與輸入的長度成線性關係。
NonBacktracking的實現經歷了大量的開發工作，它最初是在dotnet/runtime#60607中被加入到dotnet/runtime中。然而，它的原始研究和實現實際上來自微軟研究院(MSR)，並以MSR釋出的Symbolic Regex Matcher (SRM)庫的形式作為一個實驗包提供。在現在的.NET 7的程式碼中，你仍然可以看到它的痕跡，但它已經有了很大的發展，在.NET團隊的開發人員和MSR的研究人員之間進行了緊密的合作（在被整合到dotnet/runtime之前，它在dotnet/runtimelab孵化了一年多，原始的SRM程式碼是通過dotnet/runtimelab#588從@veanes那裡拿來的）。
這個實現是基於正規表示式導數的概念，這個概念已經存在了幾十年（這個術語最初是由Janusz Brzozowski在20世紀60年代的一篇論文中提出的），並且在這個實現中得到了很大的改進。Regex衍生物構成了用於處理輸入的自動機（考慮 "圖"）的基礎。其核心思想是相當簡單的：取一個片語並處理一個字元......你得到的描述處理這一個字元后剩下的新片語是什麼？這就是導數。例如，給定一個匹配三個字的片語 w{3}，如果你把這個片語應用於下一個輸入字元'a'，那麼，這將剝去第一個 w，留給我們的是衍生詞 `w{2}。很簡單，對嗎？那麼更復雜的東西呢，比如表示式.(the|he)。如果下一個字元是t會怎樣？那麼，t有可能被模式開頭的.所吞噬，在這種情況下，剩下的重組詞將與開頭的重組詞（.(the|he)）完全相同，因為在匹配t之後，我們仍然可以匹配與沒有t時完全相同的輸入。但是，t也可能是匹配the的一部分，並且應用於the，我們將剝離t並留下he，所以現在我們的導數是.（the|he）|he。那麼原始交替中的 "他 "呢？t不匹配h，所以導數將是空的，我們在這裡表示為一個空的字元類，得到.(the|he)|he|[]。當然，作為交替的一部分，最後的 "無 "是一個nop，所以我們可以將整個派生簡化為.(the|he)|he...完成。這只是針對下一個t的原始模式的應用，如果是針對h呢？按照與t相同的邏輯，這次我們的結果是.(the|he)|e。以此類推。如果我們從h的導數開始，下一個字元是e呢？在交替的左邊，它可以被.消耗掉（但不匹配t或h），所以我們最後得到的是同樣的子表示式。但是在交替關係的右側，e與e匹配，剩下的就是空字串（）。.*（the|he）|（）。在一個模式是 "nullable"（它可以匹配空字串）的地方，可以認為是一個匹配。我們可以把這整個事情看成是一個圖，每個輸入字元都有一個過渡到應用它所產生的衍生物的過程。
看起來非常像DFA，不是嗎？它應該是這樣的。而這正是NonBacktracking處理輸入的DFA的構造方式。對於每一個楔形結構（連線、交替、迴圈等），引擎都知道如何根據正在評估的字元來推匯出下一個楔形。這個應用是懶惰地完成的，所以我們有一個初始的起始狀態（原始模式），然後當我們評估輸入中的下一個字元時，它尋找是否已經有一個可用於該過渡的衍生工具：如果有，它就跟隨它，如果沒有，它就動態/懶惰地匯出圖中的下一個節點。在其核心，這就是它的工作方式。
當然，魔鬼在細節中，有大量的複雜情況和工程智慧用於使引擎高效。其中一個例子是記憶體消耗和吞吐量之間的權衡。考慮到能夠有任何字元作為輸入，你可以有效地從每個節點中獲得65K的轉換（例如，每個節點可能需要一個65K的元素表）；這將大大增加記憶體消耗。然而，如果你真的有那麼多的轉換，很有可能其中大部分都會指向同一個目標節點。因此，NonBacktracking保持了自己對字元的分組，稱之為 "minterms"。如果兩個字元有完全相同的過渡，它們就屬於同一個minterm。然後，過渡是以minterms為單位構建的，每個minterm從一個給定的節點中最多有一個過渡。當下一個輸入字元被讀取時，它將其對映到一個minterm ID上，然後為該ID找到合適的過渡；為了節省潛在的大量記憶體，增加了一層間接性。這種對映是通過一個陣列點陣圖來處理ASCII的，而一個高效的資料結構被稱為二進位制決策圖（BDD），用於處理0x7F以上的一切。
如前所述，非反向追蹤引擎在輸入長度上是線性的。但這並不意味著它總是精確地檢視每個輸入字元一次。如果你呼叫Regex.IsMatch，它就會這樣做；畢竟，IsMatch只需要確定是否存在匹配，而不需要計算任何額外的資訊，比如匹配的實際開始或結束位置，任何關於捕獲的資訊等等。因此，引擎可以簡單地使用它的自動機沿著輸入行走，在圖中從一個節點過渡到另一個節點，直到它達到最終狀態或耗盡輸入。然而，其他操作確實需要它收集更多的資訊。Regex.Match需要計算一切，這實際上需要在輸入上進行多次行走。在最初的實現中，Match的等價物總是需要三遍：向前匹配以找到匹配的終點，然後從終點位置反向匹配模式，以找到匹配的實際起始位置，然後再從已知的起始位置向前走一次，以找到實際的終點位置。然而，有了@olsaarik的dotnet/runtime#68199，除非需要捕獲，否則現在只需兩遍就能完成：一遍向前走以找到匹配的保證結束位置，然後一遍反向走以找到其開始位置。而來自@olsaarik的dotnet/runtime#65129增加了對捕獲的支援，原來的實現也沒有。這種捕獲支援增加了第三道程式，一旦知道匹配的邊界，引擎就會再執行一次正向程式，但這次是基於NFA的 "模擬"，能夠記錄轉換中的 "捕獲效果"。所有這些都使得非反向追蹤的實現具有與反向追蹤引擎完全相同的語意，總是以相同的順序和相同的捕獲資訊產生相同的匹配。這方面唯一的區別是，在逆向追蹤引擎中，迴圈內的捕獲組將儲存在迴圈的每個迭代中捕獲的所有值，而在非逆向追蹤的實現中，只有最後一個迭代被儲存。除此之外，還有一些非反追蹤實現根本不支援的結構，因此在試圖構建Regex時，嘗試使用任何這些結構都會失敗，例如反向參照和回看。
即使在它作為MSR的一個獨立庫取得進展之後，仍有100多個PR用於使RegexOptions.NonBacktracking成為現在的.NET 7，包括像@olsaarik的dotnet/runtime#70217這樣的優化，它試圖簡化DFA核心的緊密內部匹配迴圈（如 讀取下一個輸入字元，找到適當的過渡，移動到下一個節點，並檢查節點的資訊，如它是否是最終狀態），以及像@veanes的dotnet/runtime#65637這樣的優化，它優化了NFA模式以避免多餘的分配，快取和重複使用列表和集合物件，使處理狀態列表的過程中不需要分配。
對於NonBacktracking來說，還有一組效能方面的PR。無論使用的是哪種多重引擎，Regex的實現都是將模式轉化為可處理的東西，它本質上是一個編譯器，和許多編譯器一樣，它自然會傾向於遞迴演演算法。在Regex的情況下，這些演演算法涉及到正規表示式結構樹的行走。遞迴最終成為表達這些演演算法的一種非常方便的方式，但是遞迴也存在堆疊溢位的可能性；本質上，它是將堆疊空間作為抓取空間，如果最終使用了太多，事情就會變得很糟糕。處理這個問題的一個常見方法是把遞迴演演算法變成一個迭代演演算法，這通常涉及到使用顯式的狀態堆疊而不是隱式的。這樣做的好處是，你可以儲存的狀態量只受限於你有多少記憶體，而不是受限於你執行緒的堆疊空間。然而，缺點是，以這種方式編寫演演算法通常不那麼自然，而且它通常需要為堆疊分配堆空間，如果你想避免這種分配，就會導致額外的複雜情況，例如各種池。dotnet/runtime#60385為Regex引入了一種不同的方法，然後被@olsaarik的dotnet/runtime#60786專門用於NonBacktracking的實現。它仍然使用遞迴，因此受益於遞迴演演算法的表現力，以及能夠使用堆疊空間，從而在最常見的情況下避免額外的分配，但隨後為了避免堆疊溢位，它發出明確的檢查以確保我們在堆疊上沒有太深（.NET早已為此目的提供了幫助器RuntimeHelpers.EnsureSufficientExecutionStack和RuntimeHelpers.TryEnsureSufficientExecutionStack）。如果它檢測到它在堆疊上的位置太深，它就會分叉到另一個執行緒繼續執行。觸發這個條件是很昂貴的，但在實踐中很少會被觸發（例如，在我們龐大的功能測試中，只有在明確寫成的測試中才會被觸發），它使程式碼保持簡單，並保持典型案例的快速。類似的方法也用於dotnet/runtime的其他領域，如System.Linq.Expressions。
正如我在上一篇關於正規表示式的博文中提到的，回溯實現和非回溯實現都有其存在的意義。非回溯實現的主要好處是可預測性：由於線性處理的保證，一旦你構建了regex，你就不需要擔心惡意輸入會在你的潛在易受影響的表示式的處理過程中造成最壞情況的行為。這並不意味著RegexOptions.NonBacktracking總是最快的；事實上，它經常不是。作為對降低最佳效能的交換，它提供了最佳的最壞情況下的效能，對於某些型別的應用，這是一個真正值得和有價值的權衡。
原文連結
Performance Improvements in .NET 7
本作品採用知識共用署名-非商業性使用-相同方式共用 4.0 國際許可協定進行許可。
歡迎轉載、使用、重新發布，但務必保留文章署名 鄭子銘 （包含連結： http://www.cnblogs.com/MingsonZheng/ ），不得用於商業目的，基於本文修改後的作品務必以相同的許可釋出。
如有任何疑問，請與我聯絡 ([email protected])