独立开发者@董川民

Just So So ...

.NET 7 中的性能改进（十二）

原文 | Stephen Toub

翻译 | 郑子铭

New APIs

在.NET 7中，Regex得到了几个新的方法，所有这些方法都能提高性能。新的API的简单性可能也误导了为实现它们所需的工作量，特别是由于新的API都支持ReadOnlySpan输入到regex引擎。.

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，这个跨度作为一个引用结构就不能存储在Match类对象上，因为引用结构只能在堆栈而不是堆上。仅仅这一点就使支持跨度成为一个挑战，但问题甚至更加根深蒂固。所有的 regex 引擎都依赖于 RegexRunner，它是一个基类，上面存储了所有必要的状态，以反馈给构成正则表达式实际匹配逻辑的 FindFirstChar 和 Go 方法（这些方法包含执行匹配的所有核心代码，其中 FindFirstChar 是一种优化，用于跳过不可能开始匹配的输入位置，然后 Go 执行实际匹配逻辑）。如果你看一下内部的RegexInterpreter类型，也就是当你构造一个新的Regex(...)而不使用RegexOptions.Compiled或RegexOptions.NonBacktracking标志时得到的引擎，它来源于RegexRunner。同样，当你使用RegexOptions.Compiled时，它把它反射的动态方法交给了一个从RegexRunner派生的类型，RegexOptions.NonBacktracking有一个SymbolicRegexRunnerFactory，产生从RegexRunner派生的类型，以此类推。这里最相关的是，RegexRunner是公共的，因为由Regex.CompileToAssembly类型（以及现在的regex源代码生成器）生成的类型包括从这个RegexRunner派生的类型。因此，那些FindFirstChar和Go方法是抽象的、受保护的、无参数的，因为它们从基类上受保护的成员中获取它们需要的所有状态。这包括要处理的字符串输入。那么，跨度呢？我们当然可以对一个输入的ReadOnlySpan调用ToString()。这在功能上是正确的，但却完全违背了接受跨度的目的，更糟糕的是，这可能会导致消费应用程序的性能比没有API时更差。相反，我们需要一种新的方法和新的API。

首先，我们使FindFirstChar和Go成为虚拟的，而不是抽象的。分割这些方法的设计在很大程度上是过时的，特别是强制分离了一个处理阶段，即找到匹配的下一个可能的位置，然后是在该位置实际执行匹配的阶段，这与所有的引擎并不一致，比如NonBacktracking使用的引擎（它最初将FindFirstChar作为一个nop实现，并将其所有逻辑放在Go中）。然后我们添加了一个新的虚拟扫描方法，重要的是，它需要一个ReadOnlySpan作为参数；这个span不能从基本的RegexRunner中暴露出来，必须被传递进去。然后，我们在Scan方面实现了FindFirstChar和Go，并使它们 "只是工作"。然后，所有的引擎都是以这个跨度来实现的；它们不再需要访问受保护的RegexRunner.runtext、RegexRunner.runtextbeg和RegexRunner.runtextend成员，它们只是被交给跨度，已经切成了输入区域，并进行处理。从性能的角度来看，这样做的一个好处是使JIT能够更好地消除各种开销，特别是围绕边界检查。当逻辑以字符串的形式实现时，除了输入字符串本身之外，引擎还被告知要处理的输入区域的开头和结尾（因为开发者可以调用类似Regex.Match(string input, int beginning, int length)的方法，以便只处理一个子串）。显然，引擎的匹配逻辑比这要复杂得多，但简化一下，想象一下整个引擎只是在输入上的一个循环。有了输入、开头和长度，看起来就像。

[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的下限是0，上限（独占）是span的Length，并且通过该方法的构造，它可以证明span的访问总是在边界内。因此，它不需要在方法中发出任何边界检查，而且该方法也没有索引超出范围抛出的提示性签名。你可以在dotnet/runtime#66129、dotnet/runtime#66178和dotnet/runtime#72728中看到更多利用跨度作为所有引擎核心的例子，所有这些例子都清理了不必要的边界检查，然后总是0和跨度.长度。

好了，现在引擎能够被交给跨度输入并处理它们，很好，我们能用它做什么？好吧，Regex.IsMatch很简单：它不需要进行多次匹配，因此不需要担心如何存储输入的ReadOnlySpan以备下次匹配。同样地，新的Regex.Count提供了一个优化的实现来计算输入中有多少个匹配，它可以绕过使用Match或MatchCollection，因此也可以轻松地在跨度上操作；dotnet/runtime#64289添加了基于字符串的重载，dotnet/runtime#66026添加了基于跨度的重载。我们可以通过向引擎传递额外的信息来进一步优化Count，让它们知道它们实际上需要计算多少信息。例如，我之前指出，NonBacktracking在相对于它需要收集的信息而言，需要做多少工作，是相当有代价的。最便宜的做法是只确定是否有一个匹配，因为它可以在一次向前通过输入的过程中做到这一点。如果它还需要计算实际的起点和终点界限，这就需要再反向通过一些输入。如果它还需要计算捕获信息，这就需要在NFA的基础上再进行一次正向传递（即使其他两次是基于DFA的）。Count需要边界信息，因为它需要知道从哪里开始寻找下一个匹配，但它不需要捕获信息，因为这些捕获信息都不会交还给调用者。dotnet/runtime#68242更新了引擎以接收这些额外的信息，从而使Count等方法变得更有效率。

所以，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中，如果你还需要所有的捕获数据，就没有办法实现这种无分配的枚举。如果需要的话，我们会在未来研究设计这个问题。

TryFindNextPossibleStartingPosition

如前所述，所有引擎的核心是一个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)的实现在很多情况下在.NET 7中得到了很大的改善，以至于除了最角落的情况，它最终都比Boyer-Moore好很多。因此，这个PR使一个新的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字符类，不如搜索子串"

本文作者：郑子铭信息来源：公众号 DotNet NB所属分类：.NET

董川民

Life is like a box of chocolates,you never know what you're going to get.
ChongQing Movie Motorcycle Website