Performance Improvements in .NET 8 & 7 & 6 -- String【翻译】

原文:https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/#strings-arrays-and-spans

.Net 8

.NET 8在数据处理领域有了巨大的改进,特别是在有效操作字符串,数组和Span方面。既然我们刚刚谈到了UTF8和IUtf8SpanFormattable,那就从这里开始。

UTF8

如前所述,现在有很多类型实现了IUtf8SpanFormattable。我注意到所有的数值原始类型,DateTime{Offset},和Guid,以及dotnet/runtime#84556,System.Version类型也实现了它,同样,由于dotnet/runtime#84487,IPAddress和新的IPNetwork类型也实现了它。然而,.NET 8不仅在所有这些类型上提供了这个接口的实现,而且还在一个关键的地方使用了这个接口。

如果你还记得,C# 10和.NET 6的字符串插值完全被改造了。这不仅使字符串插值变得更加高效,而且还提供了一种模式,类型可以实现这种模式,以便有效地使用字符串插值语法来做除创建新字符串之外的事情。例如,为Span添加了一个新的TryWrite扩展方法,使得可以直接将格式化的插值字符串格式化到目标char缓冲区中:

public bool Format(Span<char> span, DateTime dt, out int charsWritten) =>
    span.TryWrite($"Date: {dt:R}", out charsWritten);

上述内容由编译器转换为以下等效内容:

public bool Format(Span<char> span, DateTime dt, out int charsWritten)
{
    var handler = new MemoryExtensions.TryWriteInterpolatedStringHandler(6, 1, span, out bool shouldAppend);
    _ = shouldAppend &&
        handler.AppendLiteral("Date: ") &&
        handler.AppendFormatted<DateTime>(dt, "R");
    return MemoryExtensions.TryWrite(span, ref handler, out charsWritten);
}

该通用的 AppendFormatted 调用的实现会检查 T 并尝试做最优的事情。在这种情况下,它会看到 T 实现了 ISpanFormattable,并最终使用其 TryFormat 直接格式化到目标 span 中。

这是针对 UTF16 的。现在有了 IUtf8SpanFormattable,我们有机会做同样的事情,但是针对 UTF8。这正是 dotnet/runtime#83852 所做的。它引入了新的 Utf8.TryWrite 方法,该方法的行为与前述的 TryWrite 完全相同,只是以 UTF8 的形式写入目标 Span,而不是以 UTF16 的形式写入目标 Span。实现也对 IUtf8SpanFormattable 进行了特殊处理,使用其 TryFormat 直接写入目标缓冲区。

有了这个,我们可以编写与我们之前编写的方法等效的方法:

public bool Format(Span<byte> span, DateTime dt, out int bytesWritten) =>
    Utf8.TryWrite(span, $"Date: {dt:R}", out bytesWritten);

并且这会按照你现在预期的方式进行降低处理:

public bool Format(Span<byte> span, DateTime dt, out int bytesWritten)
{
    var handler = new Utf8.TryWriteInterpolatedStringHandler(6, 1, span, out bool shouldAppend);
    _ = shouldAppend &&
        handler.AppendLiteral("Date: ") &&
        handler.AppendFormatted<DateTime>(dt, "R");
    return Utf8.TryWrite(span, ref handler, out bytesWritten);
}

因此,除了你期望改变的部分之外,它们是相同的。但从某些方面来说,这也是一个问题。看看那个 AppendLiteral("Date: ") 调用。在处理目标为 Span 的 UTF16 情况下,AppendLiteral 的实现只需要将该字符串复制到目标中;不仅如此,JIT 还会内联调用,看到正在复制一个字符串字面量,并展开复制操作,使其非常高效。但在处理 UTF8 的情况下,我们不能只是将 UTF16 字符串字符复制到目标的 UTF8 Span 缓冲区中;我们需要对字符串进行 UTF8 编码。虽然我们当然可以做到这一点(通过引入新的 Encoding.TryGetBytes 方法,dotnet/runtime#84609 和 dotnet/runtime#85120 使得这变得简单),但需要在运行时反复花费时间来执行可以在编译时完成的工作,这是非常低效的。毕竟,我们处理的是在 JIT 时间已知的字符串字面量;如果 JIT 能够执行 UTF8 编码,然后像在 UTF16 情况下已经执行的那样进行展开复制,那将非常好。通过 dotnet/runtime#85328 和 dotnet/runtime#89376,这正是发生的情况,因此性能在它们之间实际上是相同的。

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.Unicode;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly char[] _chars = new char[100];
    private readonly byte[] _bytes = new byte[100];
    private readonly int _major = 1, _minor = 2, _build = 3, _revision = 4;

    [Benchmark] public bool FormatUTF16() => _chars.AsSpan().TryWrite($"{_major}.{_minor}.{_build}.{_revision}", out int charsWritten);
    [Benchmark] public bool FormatUTF8() => Utf8.TryWrite(_bytes, $"{_major}.{_minor}.{_build}.{_revision}", out int bytesWritten);
}
方法 平均值
FormatUTF16 19.07 ns
FormatUTF8 19.33 ns

ASCII

UTF8 是互联网上和在端点之间传输文本的主要编码方式。然而,这些数据中的大部分实际上是 ASCII 的子集,即范围在 [0, 127] 的 128 个值。当你知道你正在处理的数据是 ASCII 时,你可以通过使用针对子集优化的例程来获得更好的性能。.NET 8 中的新 Ascii 类,由 dotnet/runtime#75012 和 dotnet/runtime#84886 引入,然后在 dotnet/runtime#85926(来自 @gfoidl),dotnet/runtime#85266(来自 @Daniel-Svensson),dotnet/runtime#84881,和 dotnet/runtime#87141 中进一步优化,提供了这个功能:

namespace System.Text;

public static class Ascii
{
    public static bool Equals(ReadOnlySpan<byte> left, ReadOnlySpan<byte> right);
    public static bool Equals(ReadOnlySpan<byte> left, ReadOnlySpan<char> right);
    public static bool Equals(ReadOnlySpan<char> left, ReadOnlySpan<byte> right);
    public static bool Equals(ReadOnlySpan<char> left, ReadOnlySpan<char> right);

    public static bool EqualsIgnoreCase(ReadOnlySpan<byte> left, ReadOnlySpan<byte> right);
    public static bool EqualsIgnoreCase(ReadOnlySpan<byte> left, ReadOnlySpan<char> right);
    public static bool EqualsIgnoreCase(ReadOnlySpan<char> left, ReadOnlySpan<byte> right);
    public static bool EqualsIgnoreCase(ReadOnlySpan<char> left, ReadOnlySpan<char> right);

    public static bool IsValid(byte value);
    public static bool IsValid(char value);
    public static bool IsValid(ReadOnlySpan<byte> value);
    public static bool IsValid(ReadOnlySpan<char> value);

    public static OperationStatus ToLower(ReadOnlySpan<byte> source, Span<byte> destination, out int bytesWritten);
    public static OperationStatus ToLower(ReadOnlySpan<char> source, Span<char> destination, out int charsWritten);
    public static OperationStatus ToLower(ReadOnlySpan<byte> source, Span<char> destination, out int charsWritten);
    public static OperationStatus ToLower(ReadOnlySpan<char> source, Span<byte> destination, out int bytesWritten);

    public static OperationStatus ToUpper(ReadOnlySpan<byte> source, Span<byte> destination, out int bytesWritten);
    public static OperationStatus ToUpper(ReadOnlySpan<char> source, Span<char> destination, out int charsWritten);
    public static OperationStatus ToUpper(ReadOnlySpan<byte> source, Span<char> destination, out int charsWritten);
    public static OperationStatus ToUpper(ReadOnlySpan<char> source, Span<byte> destination, out int bytesWritten);

    public static OperationStatus ToLowerInPlace(Span<byte> value, out int bytesWritten);
    public static OperationStatus ToLowerInPlace(Span<char> value, out int charsWritten);
    public static OperationStatus ToUpperInPlace(Span<byte> value, out int bytesWritten);
    public static OperationStatus ToUpperInPlace(Span<char> value, out int charsWritten);

    public static OperationStatus FromUtf16(ReadOnlySpan<char> source, Span<byte> destination, out int bytesWritten);
    public static OperationStatus ToUtf16(ReadOnlySpan<byte> source, Span<char> destination, out int charsWritten);

    public static Range Trim(ReadOnlySpan<byte> value);
    public static Range Trim(ReadOnlySpan<char> value);

    public static Range TrimEnd(ReadOnlySpan<byte> value);
    public static Range TrimEnd(ReadOnlySpan<char> value);

    public static Range TrimStart(ReadOnlySpan<byte> value);
    public static Range TrimStart(ReadOnlySpan<char> value);
}

注意,它提供了操作 UTF16 (char) 和 UTF8 (byte) 的重载,并且在许多情况下,它们是混合的,这样你可以比如说,比较一个 UTF8 ReadOnlySpan 和一个 UTF16 ReadOnlySpan,或者将一个 UTF16 ReadOnlySpan 转码为一个 UTF8 ReadOnlySpan(当处理 ASCII 时,这纯粹是一个缩小操作,去掉每个 char 中的前导 0 字节)。例如,添加这些方法的 PR 也在各种地方使用了它们(我强烈主张这一点,以确保所设计的实际上是满足需求的,或者确保其他核心库代码从新的 API 中受益,这反过来使这些 API 更有价值,因为它们的好处积累到更多的间接消费者),包括在 SocketsHttpHandler 的多个地方。以前,SocketsHttpHandler 有自己的助手来完成这个目的,我在这个基准测试中复制了一个例子:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly byte[] _bytes = "Strict-Transport-Security"u8.ToArray();
    private readonly string _chars = "Strict-Transport-Security";

    [Benchmark(Baseline = true)]
    public bool Equals_OpenCoded() => EqualsOrdinalAsciiIgnoreCase(_chars, _bytes);

    [Benchmark]
    public bool Equals_Ascii() => Ascii.EqualsIgnoreCase(_chars, _bytes);

    internal static bool EqualsOrdinalAsciiIgnoreCase(string left, ReadOnlySpan<byte> right)
    {
        if (left.Length != right.Length)
            return false;

        for (int i = 0; i < left.Length; i++)
        {
            uint charA = left[i], charB = right[i];

            if ((charA - 'a') <= ('z' - 'a')) charA -= ('a' - 'A');
            if ((charB - 'a') <= ('z' - 'a')) charB -= ('a' - 'A');

            if (charA != charB)
                return false;
        }

        return true;
    }
}
方法 平均值 比率
Equals_OpenCoded 31.159 ns 1.00
Equals_Ascii 3.985 ns 0.13

许多这些新的 Ascii API 也得到了 Vector512 的处理,这样当当前机器支持 AVX512 时,它们就会亮起,感谢 @anthonycanino 在 dotnet/runtime#88532 和 @khushal1996 在 dotnet/runtime#88650 的贡献。

Base64

一个更进一步限制的文本子集是 Base64 编码的数据。当需要将任意字节作为文本传输时,就会使用这种方法,结果是只使用 64 个字符(小写 ASCII 字母,大写 ASCII 字母,ASCII 数字,'+',和 '/')的文本。.NET 一直有在 System.Convert 上用于编码和解码 Base64 的方法,使用 UTF16 (char),并且在 .NET Core 2.1 中引入 Span 时,它得到了一组基于 span 的方法。在那个时候,System.Text.Buffers.Base64 类也被引入,专门用于编码和解码 UTF8 (byte) 的 Base64。这在 .NET 8 中得到了进一步的改进。

dotnet/runtime#85938 来自 @heathbm 和 dotnet/runtime#86396 在这里做出了两个贡献。首先,他们使 Base64.Decode 方法的 UTF8 行为与 Convert 类的对应方法一致,特别是在处理空白字符方面。由于 Base64 编码数据中经常有换行符,所以 Convert 类的 Base64 解码方法允许有空白字符;相比之下,Base64 类的解码方法如果遇到空白字符就会失败。现在这些解码方法允许的空白字符与 Convert 完全相同。这部分是因为这些 PR 的第二个贡献,即一组新的 Base64.IsValid 静态方法。与 Ascii.IsValid 和 Utf8.IsValid 一样,这些方法简单地声明提供的 UTF8 或 UTF16 输入是否代表有效的 Base64 输入,以便 Convert 和 Base64 的解码方法都能成功解码。与我们看到的所有此类 .NET 中引入的处理一样,我们努力使新功能尽可能高效,以便它可以在其他地方最大限度地受益。例如,dotnet/runtime#86221 来自 @WeihanLi 更新了新的 Base64Attribute 来使用它,dotnet/runtime#86002 更新了 PemEncoding.TryCountBase64 来使用它。在这里,我们可以看到一个基准测试,比较了旧的非向量化的 TryCountBase64 和使用向量化的 Base64.IsValid 的新版本:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Buffers.Text;
using System.Runtime.CompilerServices;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly string _exampleFromPemEncodingTests =
        "MHQCAQEEICBZ7/8T1JL2amvNB/QShghtgZPtnPD4W+sAcHxA+hJsoAcGBSuBBAAK\n" +
        "oUQDQgAE3yNC5as8JVN5MjF95ofNSgRBVXjf0CKtYESWfPnmvT3n+cMMJUB9lUJf\n" +
        "dkFNgaSB7JlB+krZVVV8T7HZQXVDRA==\n";

    [Benchmark(Baseline = true)]
    public bool Count_Old() => TryCountBase64_Old(_exampleFromPemEncodingTests, out _, out _, out _);

    [Benchmark] 
    public bool Count_New() => TryCountBase64_New(_exampleFromPemEncodingTests, out _, out _, out _);

    private static bool TryCountBase64_New(ReadOnlySpan<char> str, out int base64Start, out int base64End, out int base64DecodedSize)
    {
        int start = 0, end = str.Length - 1;
        for (; start < str.Length && IsWhiteSpaceCharacter(str[start]); start++) ;
        for (; end > start && IsWhiteSpaceCharacter(str[end]); end--) ;

        if (Base64.IsValid(str.Slice(start, end + 1 - start), out base64DecodedSize))
        {
            base64Start = start;
            base64End = end + 1;
            return true;
        }

        base64Start = 0;
        base64End = 0;
        return false;
    }

    private static bool TryCountBase64_Old(ReadOnlySpan<char> str, out int base64Start, out int base64End, out int base64DecodedSize)
    {
        base64Start = 0;
        base64End = str.Length;

        if (str.IsEmpty)
        {
            base64DecodedSize = 0;
            return true;
        }

        int significantCharacters = 0;
        int paddingCharacters = 0;

        for (int i = 0; i < str.Length; i++)
        {
            char ch = str[i];

            if (IsWhiteSpaceCharacter(ch))
            {
                if (significantCharacters == 0) base64Start++;
                else base64End--;
                continue;
            }

            base64End = str.Length;

            if (ch == '=') paddingCharacters++;
            else if (paddingCharacters == 0 && IsBase64Character(ch)) significantCharacters++;
            else
            {
                base64DecodedSize = 0;
                return false;
            }
        }

        int totalChars = paddingCharacters + significantCharacters;

        if (paddingCharacters > 2 || (totalChars & 0b11) != 0)
        {
            base64DecodedSize = 0;
            return false;
        }

        base64DecodedSize = (totalChars >> 2) * 3 - paddingCharacters;
        return true;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static bool IsBase64Character(char ch) => char.IsAsciiLetterOrDigit(ch) || ch is '+' or '/';

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static bool IsWhiteSpaceCharacter(char ch) => ch is ' ' or '\t' or '\n' or '\r';
}

方法 平均值 比率
Count_Old 356.37 ns 1.00
Count_New 33.72 ns 0.09

Hex

ASCII 的另一个相关子集是十六进制,.NET 8 在字节与其十六进制表示之间的转换方面做出了改进。特别是,dotnet/runtime#82521 使用 Langdale 和 Mula 描述的算法向量化了 Convert.FromHexString 方法。即使在适度长度的输入上,这对吞吐量也有非常明显的影响:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Security.Cryptography;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private string _hex;

    [Params(4, 16, 128)]
    public int Length { get; set; }

    [GlobalSetup]
    public void Setup() => _hex = Convert.ToHexString(RandomNumberGenerator.GetBytes(Length));

    [Benchmark]
    public byte[] ConvertFromHex() => Convert.FromHexString(_hex);
}
方法 运行时 长度 平均值 比率
ConvertFromHex .NET 7.0 4 24.94 ns 1.00
ConvertFromHex .NET 8.0 4 20.71 ns 0.83
ConvertFromHex .NET 7.0 16 57.66 ns 1.00
ConvertFromHex .NET 8.0 16 17.29 ns 0.30
ConvertFromHex .NET 7.0 128 337.41 ns 1.00
ConvertFromHex .NET 8.0 128 56.72 ns 0.17

当然,.NET 8 的改进远不止于对某些已知字符集的操作;还有许多其他的改进值得探索。让我们从 System.Text.CompositeFormat 开始,它在 dotnet/runtime#80753 中被引入。

String Formatting

自 .NET 开始以来,string 及其相关类就提供了处理复合格式字符串的 API,这些字符串中的文本与格式项占位符交错,例如 "The current time is {0:t}"。然后,这些字符串可以传递给各种 API,如 string.Format,这些 API 既提供复合格式字符串,也提供应替换占位符的参数,例如 string.Format("The current time is {0:t}", DateTime.Now) 将返回一个类似于 "The current time is 3:44 PM" 的字符串(占位符中的 0 表示要替换的参数的基于 0 的编号,t 是应使用的格式,在这种情况下是标准的短时间模式)。这样的方法调用需要在每次调用时解析复合格式字符串,尽管对于给定的调用站点,复合格式字符串通常不会从调用到调用改变。这些 API 也通常是非泛型的,这意味着如果参数是值类型(如我的示例中的 DateTime),它将产生一个装箱分配。为了简化这些操作的语法,C# 6 增加了对字符串插值的支持,这样你可以写 $"The current time is {DateTime.Now:t}",而不是写 string.Format(null, "The current time is {0:t}", DateTime.Now),然后由编译器来实现与使用 string.Format 相同的行为(编译器通常只是通过将插值降低为对 string.Format 的调用来实现)。

在 .NET 6 和 C# 10 中,字符串插值得到了显著的改进,无论是在支持的场景还是在效率上。效率的一个关键方面是它使解析可以一次性完成(在编译时)。它还避免了与提供参数相关的所有分配。这些改进有助于所有使用字符串插值的场景,以及实际应用和服务中大部分使用 string.Format 的场景。然而,编译器支持的工作方式是能够在编译时看到字符串。如果格式字符串直到运行时才知道,比如说它是从 .resx 资源文件或其他配置源中提取的,那该怎么办?在这个时候,string.Format 仍然是答案。

现在在 .NET 8 中,有了一个新的答案:CompositeFormat。就像插值字符串允许编译器一次性做重复使用的优化工作,CompositeFormat 也允许这种可重用的工作一次性完成,以优化重复使用。由于它在运行时进行解析,所以它能够处理字符串插值无法达到的剩余情况。要创建一个实例,只需调用其 Parse 方法,该方法接受一个复合格式字符串,解析它,并返回一个 CompositeFormat 实例:

private static readonly CompositeFormat s_currentTimeFormat = CompositeFormat.Parse(SR.CurrentTime);

然后,像 string.Format 这样的现有方法现在有了新的重载,与现有的完全相同,但是它们接受的是 CompositeFormat 格式,而不是字符串格式。然后可以像这样完成之前的格式化:

string result = string.Format(null, s_currentTimeFormat, DateTime.Now);

这个重载(以及像 StringBuilder.AppendFormat 和 MemoryExtensions.TryWrite 这样的方法的其他新重载)接受泛型参数,避免了装箱。

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[MemoryDiagnoser(displayGenColumns: false)]
public class Tests
{
    private static readonly CompositeFormat s_format = CompositeFormat.Parse(SR.CurrentTime);

    [Benchmark(Baseline = true)]
    public string FormatString() => string.Format(null, SR.CurrentTime, DateTime.Now);

    [Benchmark]
    public string FormatComposite() => string.Format(null, s_format, DateTime.Now);
}

internal static class SR
{
    public static string CurrentTime => /*load from resource file*/"The current time is {0:t}";
}
方法 平均值 比率 分配 分配比率
FormatString 163.6 ns 1.00 96 B 1.00
FormatComposite 146.5 ns 0.90 72 B 0.75

如果你在编译时知道复合格式字符串,那么插值字符串就是答案。否则,CompositeFormat 可以以一些启动成本为代价,提供在同一球场的吞吐量。使用 CompositeFormat 进行格式化实际上是使用与字符串插值相同的插值字符串处理器实现的,例如,string.Format(..., compositeFormat, ...) 最终会调用 DefaultInterpolatedStringHandler 上的方法来完成实际的格式化工作。

还有一个新的分析器可以帮助这个。CA1863 "Use 'CompositeFormat'" 在 dotnet/roslyn-analyzers#6675 中被引入,用于识别可能从使用 CompositeFormat 参数中受益的 string.Format 和 StringBuilder.AppendFormat 调用。CA1863

Span

从格式化转向,让我们将注意力转向人们经常想要对数据序列执行的所有其他类型的操作,无论是数组、字符串,还是通过跨度统一的所有这些的操作。System.MemoryExtensions 类型是许多用于操作所有这些的例程的家,通过跨度,它在 .NET 8 中收到了许多新的 API。

一个非常常见的操作是计算有多少个东西。例如,为了支持多行注释,System.Text.Json 需要计算给定的 JSON 片段中有多少个换行符。这当然可以写成一个循环,无论是字符-by-字符还是使用 IndexOf 和切片。现在在 .NET 8 中,你也可以只调用 Count 扩展方法,感谢 @bollhals 的 dotnet/runtime#80662 和 @gfoidl 的 dotnet/runtime#82687。在这里,我们正在计算 Project Gutenberg 的 "The Adventures of Sherlock Holmes" 中的换行符数量:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly byte[] s_utf8 = new HttpClient().GetByteArrayAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    [Benchmark(Baseline = true)]
    public int Count_ForeachLoop()
    {
        int count = 0;
        foreach (byte c in s_utf8)
        {
            if (c == '\n') count++;
        }
        return count;
    }

    [Benchmark]
    public int Count_IndexOf()
    {
        ReadOnlySpan<byte> remaining = s_utf8;
        int count = 0;

        int pos;
        while ((pos = remaining.IndexOf((byte)'\n')) >= 0)
        {
            count++;
            remaining = remaining.Slice(pos + 1);
        }

        return count;
    }

    [Benchmark]
    public int Count_Count() => s_utf8.AsSpan().Count((byte)'\n');
}
方法 平均值 比率
Count_ForeachLoop 314.23 us 1.00
Count_IndexOf 95.39 us 0.30
Count_Count 13.68 us 0.04

使 MemoryExtensions.Count 如此快速的实现的核心,特别是在搜索单个值时,基于两个关键原语:PopCount 和 ExtractMostSignificantBits。这是构成 Count 实现的大部分的 Vector128 循环(实现还有类似的 Vector256 和 Vector512 循环):

Vector128<T> targetVector = Vector128.Create(value);
ref T oneVectorAwayFromEnd = ref Unsafe.Subtract(ref end, Vector128<T>.Count);
do
{
    count += BitOperations.PopCount(Vector128.Equals(Vector128.LoadUnsafe(ref current), targetVector).ExtractMostSignificantBits());
    current = ref Unsafe.Add(ref current, Vector128<T>.Count);
}
while (!Unsafe.IsAddressGreaterThan(ref current, ref oneVectorAwayFromEnd));

这是创建一个向量,其中向量的每个元素都是目标(在这种情况下,'\n')。然后,只要还有至少一个向量的数据剩余,它就加载下一个向量(Vector128.LoadUnsafe)并将其与目标向量(Vector128.Equals)进行比较。这产生了一个新的 Vector128,其中每个 T 元素在值相等时都是全 1,而在值不相等时都是全 0。然后我们提取出每个元素的最高有效位(ExtractMostSignificantBits),所以在值相等的地方得到值为 1 的位,否则为 0。然后我们在结果 uint 上使用 BitOperations.PopCount 来获取“人口计数”,即值为 1 的位的数量,并将其添加到我们的运行总数。通过这种方式,计数操作的内部循环保持无分支,实现可以非常快速地处理数据。你可以在 dotnet/runtime#81325 中找到使用 Count 的几个例子,它在核心库的几个地方使用了它。

一个类似的新的 MemoryExtensions 方法是 Replace,它在 .NET 8 中有两种形式。dotnet/runtime#76337 来自 @gfoidl 添加了一个就地变体:

public static unsafe void Replace<T>(this Span<T> span, T oldValue, T newValue) where T : IEquatable<T>?;

dotnet/runtime#83120 添加了一个复制变体:

public static unsafe void Replace<T>(this ReadOnlySpan<T> source, Span<T> destination, T oldValue, T newValue) where T : IEquatable<T>?;

这个方法在哪里会派上用场呢?例如,Uri 有一些代码路径需要将目录分隔符标准化为 '/',这样任何 '\' 字符都需要被替换。这之前使用了一个 IndexOf 循环,如前面的 Count 基准测试所示,现在它可以直接使用 Replace。以下是一个比较(纯粹为了基准测试,它来回标准化,以便每次运行基准测试时都能找到原始状态):

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly char[] _uri = "server/somekindofpathneeding/normalizationofitsslashes".ToCharArray();

    [Benchmark(Baseline = true)]
    public void Replace_ForLoop()
    {
        Replace(_uri, '/', '\\');
        Replace(_uri, '\\', '/');

        static void Replace(char[] chars, char from, char to)
        {
            for (int i = 0; i < chars.Length; i++)
            {
                if (chars[i] == from)
                {
                    chars[i] = to;
                }
            }
        }
    }

    [Benchmark]
    public void Replace_IndexOf()
    {
        Replace(_uri, '/', '\\');
        Replace(_uri, '\\', '/');

        static void Replace(char[] chars, char from, char to)
        {
            Span<char> remaining = chars;
            int pos;
            while ((pos = remaining.IndexOf(from)) >= 0)
            {
                remaining[pos] = to;
                remaining = remaining.Slice(pos + 1);
            }
        }
    }

    [Benchmark]
    public void Replace_Replace()
    {
        _uri.AsSpan().Replace('/', '\\');
        _uri.AsSpan().Replace('\\', '/');
    }
}
方法 平均值 比率
Replace_ForLoop 40.28 ns 1.00
Replace_IndexOf 29.26 ns 0.73
Replace_Replace 18.88 ns 0.47

新的 Replace 方法比手动循环和 IndexOf 循环都要好。和 Count 一样,Replace 有一个相当简单和紧凑的内部循环;再次,这里是该循环的 Vector128 变体:

do
{
    original = Vector128.LoadUnsafe(ref src, idx);
    mask = Vector128.Equals(oldValues, original);
    result = Vector128.ConditionalSelect(mask, newValues, original);
    result.StoreUnsafe(ref dst, idx);

    idx += (uint)Vector128<T>.Count;
}
while (idx < lastVectorIndex);

这是加载下一个向量的数据(Vector128.LoadUnsafe)并将其与填充了 oldValue 的向量进行比较,这会产生一个新的掩码向量,对于相等的情况为 1,对于不等的情况为 0。然后它调用超级方便的 Vector128.ConditionalSelect。这是一个无分支的 SIMD 条件操作:它产生一个新的向量,如果掩码的位是 1,则从一个向量中取出元素,如果掩码的位是 0,则从另一个向量中取出元素(想象一下三元运算符)。然后将结果向量保存为结果。以这种方式,它会覆盖整个跨度,在某些情况下,只是写回之前的值,在原始值是目标 oldValue 的情况下,写出 newValue。这个循环体是无分支的,不会根据需要替换的元素数量改变成本。在极端的情况下,如果没有任何东西需要被替换,基于 IndexOf 的循环可能会稍微快一点,因为 IndexOf 的内部循环的主体有更少的指令,但是这样的 IndexOf 循环对于每个需要做的替换都要付出相对较高的成本。

StringBuilder 也有这样一个基于 IndexOf 的实现,用于其 Replace(char oldChar, char newChar) 和 Replace(char oldChar, char newChar, int startIndex, int count) 方法,现在它们基于 MemoryExtensions.Replace,所以改进也会积累在这里。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly StringBuilder _sb = new StringBuilder("http://server\\this\\is\\a\\test\\of\\needing\\to\\normalize\\directory\\separators\\");

    [Benchmark]
    public void Replace()
    {
        _sb.Replace('\\', '/');
        _sb.Replace('/', '\\');
    }
}
方法 运行时 平均值 比率
Replace .NET 7.0 150.47 ns 1.00
Replace .NET 8.0 24.79 ns 0.16

有趣的是,尽管 StringBuilder.Replace(char, char) 使用了 IndexOf 并切换到使用 Replace,但 StringBuilder.Replace(string, string) 根本没有使用 IndexOf,这个问题在 dotnet/runtime#81098 中得到了修复。在处理字符串时,StringBuilder 中的 IndexOf 更复杂,因为它的分段特性。StringBuilder 不仅仅是由一个数组支持:它实际上是一个分段的链表,每个分段都存储一个数组。对于基于字符的 Replace,它可以简单地在每个分段上单独操作,但对于基于字符串的 Replace,它需要处理被搜索的值可能跨越分段边界的可能性。因此,StringBuilder.Replace(string, string) 是在每个分段上逐字符地进行遍历,每个位置都进行等值检查。现在有了这个 PR,它使用 IndexOf,只有在足够接近分段边界可能会被跨越时,才会回退到逐字符检查。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly StringBuilder _sb = new StringBuilder()
        .Append("Shall I compare thee to a summer's day? ")
        .Append("Thou art more lovely and more temperate: ")
        .Append("Rough winds do shake the darling buds of May, ")
        .Append("And summer's lease hath all too short a date; ")
        .Append("Sometime too hot the eye of heaven shines, ")
        .Append("And often is his gold complexion dimm'd; ")
        .Append("And every fair from fair sometime declines, ")
        .Append("By chance or nature's changing course untrimm'd; ")
        .Append("But thy eternal summer shall not fade, ")
        .Append("Nor lose possession of that fair thou ow'st; ")
        .Append("Nor shall death brag thou wander'st in his shade, ")
        .Append("When in eternal lines to time thou grow'st: ")
        .Append("So long as men can breathe or eyes can see, ")
        .Append("So long lives this, and this gives life to thee.");

    [Benchmark]
    public void Replace()
    {
        _sb.Replace("summer", "winter");
        _sb.Replace("winter", "summer");
    }
}
方法 运行时 平均值 比率
Replace .NET 7.0 5,158.0 ns 1.00
Replace .NET 8.0 476.4 ns 0.09

只要我们在讨论 StringBuilder,那么在 .NET 8 中,它也有一些很好的改进。@yesmey 在 dotnet/runtime#85894 中调整了 StringBuilder.Append(string value) 和 JIT,使 JIT 能够展开作为附加常量字符串一部分的内存复制。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly StringBuilder _sb = new();

    [Benchmark]
    public void Append()
    {
        _sb.Clear();
        _sb.Append("This is a test of appending a string to StringBuilder");
    }
}
方法 运行时 平均值 比率
Append .NET 7.0 7.597 ns 1.00
Append .NET 8.0 3.756 ns 0.49

@yesmey 在 dotnet/runtime#86287 中改变了 StringBuilder.Append(char value, int repeatCount) 的实现,使用 Span.Fill 替代手动循环,利用了 Fill 实现的优化,即使对于相对较小的计数也是如此。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly StringBuilder _sb = new();

    [Benchmark]
    public void Append()
    {
        _sb.Clear();
        _sb.Append('x', 8);
    }
}
方法 运行时 平均值 比率
Append .NET 7.0 11.520 ns 1.00
Append .NET 8.0 5.292 ns 0.46

回到 MemoryExtensions,另一个新的有用的方法是 MemoryExtensions.Split(和 MemoryExtensions.SplitAny)。这是 string.Split 的一些用法的基于 span 的对应方法。我说“一些”,是因为实际上有两种主要的使用 string.Split 的模式:当你期望有一定数量的部分,和当有未知数量的部分。例如,如果你想解析一个由 System.Version 使用的版本字符串,最多有四个部分(“主版本号.次版本号.构建号.修订号”)。但是,如果你想将一个文件的内容分割成文件中的所有行(由 \n 分隔),那就是未知的(并且可能相当大的)数量的部分。新的 MemoryExtensions.Split 方法专注于预期有已知的(并且相当小的)最大数量的部分的情况。在这种情况下,它可以比 string.Split 更有效,特别是从分配的角度来看。

string.Split 有接受 int count 的重载,MemoryExtensions.Split 的行为与这些重载完全相同;然而,你给它的不是 int count,而是一个 Span 目标,其长度是你本来会用于 count 的值。例如,假设你想分割一个由 '=' 分隔的键/值对。如果这是 string.Split,你可以这样写:

string[] parts = keyValuePair.Split('=');

当然,如果输入实际上对你的期望是错误的,并且有100个等号,你将最终创建一个包含101个字符串的数组。所以,你可能会这样写:

string[] parts = keyValuePair.Split('=', 3);

等等,“3”?不是只有两部分吗,如果是,为什么不传递“2”?这是因为最后一部分发生的行为。最后一部分包含分隔符前的字符串的剩余部分,所以例如调用:

"shall=i=compare=thee".Split(new[] { '=' }, 2)

会产生数组:

string[2] { "shall", "i=compare=thee" }

如果你想知道是否有超过两部分,你需要请求至少一个更多,然后如果最后一个被产生,你知道输入是错误的。例如,这个:

"shall=i=compare=thee".Split(new[] { '=' }, 3)

产生这个:

string[3] { "shall", "i", "compare-thee" }

和这个:

"shall=i".Split(new[] { '=' }, 3)

产生这个:

string[2] { "shall", "i" }

我们可以用新的重载做同样的事情,除了 a) 调用者提供目标 span 来写入结果,和 b) 结果被存储为 System.Range 而不是 string。这意味着整个操作是无分配的。并且,由于 Span 上的索引器允许你传入一个 Range 并切片 span,你可以轻松地使用写入的范围来访问输入的相关部分。

Span<Range> parts = stackalloc Range[3];
int count = keyValuePairSpan.Split(parts, '=');
if (count == 2)
{
    Console.WriteLine($"key={keyValuePairSpan[parts[0]]}, value={keyValuePairSpan[parts[1]]}");
}

这是一个来自 dotnet/runtime#80211 的例子,它使用 SplitAny 来降低 MimeBasePart.DecodeEncoding 的成本:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[MemoryDiagnoser(displayGenColumns: false)]
public class Tests
{
    private readonly string _input = "=?utf-8?B?RmlsZU5hbWVf55CG0Y3Qq9C60I5jw4TRicKq0YIM0Y1hSsSeTNCy0Klh?=";
    private static readonly char[] s_decodeEncodingSplitChars = new char[] { '?', '\r', '\n' };

    [Benchmark(Baseline = true)]
    public Encoding Old()
    {
        if (string.IsNullOrEmpty(_input))
        {
            return null;
        }

        string[] subStrings = _input.Split(s_decodeEncodingSplitChars);
        if (subStrings.Length < 5 || 
            subStrings[0] != "=" || 
            subStrings[4] != "=")
        {
            return null;
        }

        string charSet = subStrings[1];
        return Encoding.GetEncoding(charSet);
    }

    [Benchmark]
    public Encoding New()
    {
        if (string.IsNullOrEmpty(_input))
        {
            return null;
        }

        ReadOnlySpan<char> valueSpan = _input;
        Span<Range> subStrings = stackalloc Range[6];
        if (valueSpan.SplitAny(subStrings, "?\r\n") < 5 ||
            valueSpan[subStrings[0]] is not "=" ||
            valueSpan[subStrings[4]] is not "=")
        {
            return null;
        }

        return Encoding.GetEncoding(_input[subStrings[1]]);
    }
}
方法 平均值 比率 分配 分配比率
旧的 143.80 ns 1.00 304 B 1.00
新的 94.52 ns 0.66 32 B 0.11

MemoryExtensions.Split 和 MemoryExtensions.SplitAny 的更多示例可以在 dotnet/runtime#80471 和 dotnet/runtime#82007 中找到。这两个都从之前使用 string.Split 的各种 System.Net 类型中移除了分配。

感谢 dotnet/runtime#76803,MemoryExtensions 还包括了一组新的针对范围的 IndexOf 方法:

public static int IndexOfAnyInRange<T>(this ReadOnlySpan<T> span, T lowInclusive, T highInclusive) where T : IComparable<T>;
public static int IndexOfAnyExceptInRange<T>(this ReadOnlySpan<T> span, T lowInclusive, T highInclusive) where T : IComparable<T>;
public static int LastIndexOfAnyInRange<T>(this ReadOnlySpan<T> span, T lowInclusive, T highInclusive) where T : IComparable<T>;
public static int LastIndexOfAnyExceptInRange<T>(this ReadOnlySpan<T> span, T lowInclusive, T highInclusive) where T : IComparable<T>;

想要找到下一个 ASCII 数字的索引?没问题:

int pos = text.IndexOfAnyInRange('0', '9');

想要确定一些输入是否包含任何非 ASCII 或控制字符?你得到了:

bool nonAsciiOrControlCharacters = text.IndexOfAnyExceptInRange((char)0x20, (char)0x7e) >= 0;

例如,dotnet/runtime#78658 使用 IndexOfAnyInRange 快速确定 Uri 的部分是否可能包含双向控制字符,搜索范围
[\u200E, \u202E] 中的任何内容,然后只有在找到该范围内的任何内容时才进一步检查。而 dotnet/runtime#79357 使用 IndexOfAnyExceptInRange 来确定是否使用 Encoding.UTF8 或 Encoding.ASCII。它之前是用一个简单的 foreach 循环实现的,现在是用一个更简单的调用 IndexOfAnyExceptInRange:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly string _text =
        "Shall I compare thee to a summer's day? " +
        "Thou art more lovely and more temperate: " +
        "Rough winds do shake the darling buds of May, " +
        "And summer's lease hath all too short a date; " +
        "Sometime too hot the eye of heaven shines, " +
        "And often is his gold complexion dimm'd; " +
        "And every fair from fair sometime declines, " +
        "By chance or nature's changing course untrimm'd; " +
        "But thy eternal summer shall not fade, " +
        "Nor lose possession of that fair thou ow'st; " +
        "Nor shall death brag thou wander'st in his shade, " +
        "When in eternal lines to time thou grow'st: " +
        "So long as men can breathe or eyes can see, " +
        "So long lives this, and this gives life to thee.";

    [Benchmark(Baseline = true)]
    public Encoding Old()
    {
        foreach (char c in _text)
            if (c > 126 || c < 32)
                return Encoding.UTF8;

        return Encoding.ASCII;
    }

    [Benchmark]
    public Encoding New() =>
        _text.AsSpan().IndexOfAnyExceptInRange((char)32, (char)126) >= 0 ?
            Encoding.UTF8 :
            Encoding.ASCII;
}
方法 平均值 比率
旧的 297.56 ns 1.00
新的 20.69 ns 0.07

这更多的是一个生产力的事情,而不是性能(至少是今天),但是 .NET 8 也包括了新的 ContainsAny 方法(dotnet/runtime#87621),它允许以稍微清洁的方式编写这些然后与 0 进行比较的 IndexOf 调用,例如,前面的例子可以稍微简化为:

public Encoding New() =>
    _text.AsSpan().ContainsAnyExceptInRange((char)32, (char)126) ?
        Encoding.UTF8 :
        Encoding.ASCII;

我喜欢这种帮助器的一件事是,代码可以简化为使用它们,然后随着帮助器的改进,依赖它们的代码也会改进。在 .NET 8 中,有很多“帮助器改进”。

dotnet/runtime#86655 来自 @DeepakRajendrakumaran,为 MemoryExtensions 中的大多数基于 span 的帮助器添加了对 Vector512 的支持。这意味着当在支持 AVX512 的硬件上运行时,许多这些操作简单地变得更快。这个基准测试使用环境变量来显式禁用对各种指令集的支持,这样我们可以比较给定操作在没有向量化时的性能,当 Vector128 被使用并硬件加速时,当 Vector256 被使用并硬件加速时,以及当 Vector512 被使用并硬件加速时的性能。我在支持 AVX512 的开发机上运行了这个:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using BenchmarkDotNet.Toolchains.CoreRun;

var config = DefaultConfig.Instance
    .AddJob(Job.Default.WithId("Scalar").WithEnvironmentVariable("DOTNET_EnableHWIntrinsic", "0").AsBaseline())
    .AddJob(Job.Default.WithId("Vector128").WithEnvironmentVariable("DOTNET_EnableAVX512F", "0").WithEnvironmentVariable("DOTNET_EnableAVX2", "0"))
    .AddJob(Job.Default.WithId("Vector256").WithEnvironmentVariable("DOTNET_EnableAVX512F", "0"))
    .AddJob(Job.Default.WithId("Vector512"));
BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args, config);

[HideColumns("Error", "StdDev", "Median", "RatioSD", "EnvironmentVariables")]
public class Tests
{
    private readonly char[] _sourceChars = Enumerable.Repeat('a', 1024).ToArray();

    [Benchmark]
    public bool Contains() => _sourceChars.AsSpan().IndexOfAny('b', 'c') >= 0;
}
方法 任务 平均值 比率
Contains Scalar 491.50 ns 1.00
Contains Vector128 53.77 ns 0.11
Contains Vector256 34.75 ns 0.07
Contains Vector512 21.12 ns 0.04

所以,从 128 位到 256 位并不完全是减半,从 256 位到 512 位也不完全是减半,但是非常接近。

dotnet/runtime#77947 为足够大的输入向量化了 Equals(..., StringComparison.OrdinalIgnoreCase)(string 和 ReadOnlySpan 都使用相同的底层实现)。在循环中,它加载下两个向量。然后检查这些向量中是否有任何非 ASCII 字符;通过将它们合并(vec1 | vec2)然后查看任何元素的高位是否设置,它可以有效地做到这一点...如果没有,那么输入向量中的所有元素都是 ASCII (((vec1 | vec2) & Vector128.Create(unchecked((ushort)~0x007F))) == Vector128.Zero)。如果它找到任何非 ASCII 字符,它就会继续使用旧的比较模式。但只要所有内容都是 ASCII,那么它就可以以向量化的方式进行比较。对于每个向量,它使用一些位黑客技巧来创建向量的小写版本,然后比较小写版本的相等性。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly string _a = "shall i compare thee to a summer's day? thou art more lovely and more temperate";
    private readonly string _b = "SHALL I COMPARE THEE TO A SUMMER'S DAY? THOU ART MORE LOVELY AND MORE TEMPERATE";

    [Benchmark]
    public bool Equals() => _a.AsSpan().Equals(_b, StringComparison.OrdinalIgnoreCase);
}
方法 运行时 平均值 比率
Equals .NET 7.0 47.97 ns 1.00
Equals .NET 8.0 18.93 ns 0.39

dotnet/runtime#78262 使用相同的技巧来向量化 ToLowerInvariant 和 ToUpperInvariant:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly string _a = "shall i compare thee to a summer's day? thou art more lovely and more temperate";
    private readonly char[] _b = new char[100];

    [Benchmark]
    public int ToUpperInvariant() => _a.AsSpan().ToUpperInvariant(_b);
}
方法 运行时 平均值 比率
ToUpperInvariant .NET 7.0 33.22 ns 1.00
ToUpperInvariant .NET 8.0 16.16 ns 0.49

dotnet/runtime#78650 来自 @yesmey 还优化了 MemoryExtensions.Reverse:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly byte[] _bytes = Enumerable.Range(0, 32).Select(i => (byte)i).ToArray();

    [Benchmark]
    public void Reverse() => _bytes.AsSpan().Reverse();
}
方法 运行时 平均值 比率
Reverse .NET 7.0 3.801 ns 1.00
Reverse .NET 8.0 2.052 ns 0.54

dotnet/runtime#75640 改进了内部的 RuntimeHelpers.IsBitwiseEquatable 方法,这个方法被绝大多数的 MemoryExtensions 使用。如果你查看 MemoryExtensions 的源代码,你会发现一个相当常见的模式:对 byte、ushort、uint 和 ulong 进行特殊处理,使用向量化实现,然后对其他所有内容回退到一般的非向量化实现。但它并不完全是“特殊处理 byte、ushort、uint 和 ulong”,而是“特殊处理与 byte、ushort、uint 或 ulong 大小相同的位可等类型”。如果某个东西是“位可等的”,那就意味着我们不需要担心它可能提供的任何 IEquatable 实现或它可能有的任何 Equals 重写,我们可以简单地依赖于值的位与另一个值相同或不同来确定值是否相同或不同。如果这样的位等价语义适用于某种类型,那么确定 byte、ushort、uint 和 ulong 的等价性的内联函数可以用于任何 1、2、4 或 8 字节的类型。在 .NET 7 中,RuntimeHelpers.IsBitwiseEquatable 只对运行时中的有限和硬编码的列表为真:bool、byte、sbyte、char、short、ushort、int、uint、long、ulong、nint、nuint、Rune 和枚举。现在在 .NET 8 中,该列表扩展到了一个动态可发现的集合,其中运行时可以轻松地看到该类型本身并未提供任何等价性实现。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[MemoryDiagnoser(displayGenColumns: false)]
public class Tests
{
    private MyColor[] _values1, _values2;

    [GlobalSetup]
    public void Setup()
    {
        _values1 = Enumerable.Range(0, 1_000).Select(i => new MyColor { R = (byte)i, G = (byte)i, B = (byte)i, A = (byte)i }).ToArray();
        _values2 = (MyColor[])_values1.Clone();
    }

    [Benchmark] public int IndexOf() => Array.IndexOf(_values1, new MyColor { R = 1, G = 2, B = 3, A = 4 });

    [Benchmark] public bool SequenceEquals() => _values1.AsSpan().SequenceEqual(_values2);

    struct MyColor { public byte R, G, B, A; }
}
方法 运行时 平均值 比率 分配的内存 分配比率
IndexOf .NET 7.0 24,912.42 ns 1.000 48000 B 1.00
IndexOf .NET 8.0 70.44 ns 0.003 - 0.00
SequenceEquals .NET 7.0 25,041.00 ns 1.000 48000 B 1.00
SequenceEquals .NET 8.0 68.40 ns 0.003 - 0.00

注意,这不仅意味着结果得到了向量化,而且还避免了过度的装箱(因此所有的分配),因为它不再对每个值类型实例调用 Equals(object)。

dotnet/runtime#85437 改进了 IndexOf(string/span, StringComparison.OrdinalIgnoreCase) 的向量化。想象一下,我们正在搜索一些文本中的“elementary”一词。在 .NET 7 中,它会执行 IndexOfAny('E', 'e') 来找到“elementary”可能匹配的第一个位置,然后执行类似于 Equals("elementary", textAtFoundPosition, StringComparison.OrdinalIgnoreCase) 的操作。如果 Equals 失败,那么它就会循环到下一个可能的起始位置进行搜索。如果要搜索的字符很少见,这是可以的,但在这个例子中,'e' 是英语字母表中最常见的字母,所以 IndexOfAny('E', 'e') 经常停止,跳出向量化的内循环,以进行完全的 Equals 比较。相比之下,在 .NET 7 中,使用 Mula 描述的算法改进了 IndexOf(string/span, StringComparison.Ordinal):这里的想法是,你不仅仅是搜索一个字符(例如第一个),你还有一个向量用于另一个字符(例如最后一个),你适当地偏移它们,并且你将它们的比较结果一起作为内循环的一部分。即使 'e' 非常常见,'e' 然后九个字符后的 'y' 就少得多,因此它可以在紧密的内循环中停留更长时间。现在在 .NET 8 中,当我们在输入中找到两个 ASCII 字符时,我们将同样的技巧应用于 OrdinalIgnoreCase,例如,它会同时搜索 'E' 或 'e' 后面跟着九个字符后的 'Y' 或 'y'。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    private readonly string _needle = "elementary";

    [Benchmark]
    public int Count()
    {
        ReadOnlySpan<char> haystack = s_haystack;
        ReadOnlySpan<char> needle = _needle;
        int count = 0;

        int pos;
        while ((pos = haystack.IndexOf(needle, StringComparison.OrdinalIgnoreCase)) >= 0)
        {
            count++;
            haystack = haystack.Slice(pos + needle.Length);
        }

        return count;
    }
}
方法 运行时 平均值 比率
Count .NET 7.0 676.91 us 1.00
Count .NET 8.0 62.04 us 0.09

即使是简单的 IndexOf(char) 在 .NET 8 中也有显著的改进。在这里,我在搜索 "The Adventures of Sherlock Holmes" 中的 '@',我恰好知道它并未出现,因此整个搜索将在 IndexOf(char) 的紧密内循环中进行。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    [Benchmark]
    public int IndexOfAt() => s_haystack.AsSpan().IndexOf('@');
}
方法 运行时 平均值 比率
IndexOfAt .NET 7.0 32.17 us 1.00
IndexOfAt .NET 8.0 20.84 us 0.64

这个改进要归功于 dotnet/runtime#78861。SIMD 和向量化的目标是用相同的资源做更多的事情;而不是一次处理一件事,而是一次处理 2 或 4 或 8 或 16 或 32 或 64 件事。对于大小为 16 位的字符,在 128 位向量中,你可以一次处理 8 个字符;对于 256 位,这个数字翻倍,对于 512 位,再翻倍。但这不仅仅关于向量的大小;你还可以找到创新的方法,使用向量处理比你原本能处理的更多的事情。例如,在 128 位向量中,你可以一次处理 8 个字符...但你可以一次处理 16 个字节。如果你可以将字符作为字节来处理呢?你当然可以将 8 个字符重新解释为 16 个字节,但对于大多数算法,你会得到错误的答案(因为字符的每个字节将被独立处理)。如果你可以将两个向量的字符压缩到一个字节向量,然后在这个字节向量上进行后续处理呢?只要你在字节向量上做几个指令的处理,并且压缩的成本足够低,你就可以接近将算法的性能提高一倍。这就是这个 PR 所做的,至少对于非常常见的针,以及支持 SSE2 的硬件。SSE2 有专门的指令,用于将两个向量缩小到一个向量,例如,取一个 Vector128 a 和一个 Vector128 b,并将它们组合成一个 Vector c,通过取输入中每个 short 的低字节。然而,这些特定的指令并不完全忽略每个 short 中的另一个字节;相反,它们“饱和”。这意味着,如果将 short 值转换为 byte 会溢出,它会产生 255,如果会下溢,它会产生 0。这意味着我们可以取两个 16 位值的向量,将它们打包成一个 8 位值的向量,然后只要我们搜索的东西在范围 [1, 254] 内,我们就可以确保对向量的等式检查是准确的(对 0 或 255 的比较可能会导致假阳性)。注意,虽然 Arm 支持类似的“饱和缩窄”,但这些特定指令的成本被测量为足够高,以至于在这里使用它们是不可行的(它们在其他地方被使用)。这个改进也适用于其他几个基于字符的方法,包括 IndexOfAny(char, char) 和 IndexOfAny(char, char, char)。

最后要强调的是以 Span 为中心的改进。Memory 和 ReadOnlyMemory 类型并未实现 IEnumerable,但 MemoryMarshal.ToEnumerable 方法确实存在,可以从它们中获取可枚举的对象。它主要隐藏在 MemoryMarshal 中,以引导开发者不直接遍历 Memory,而是遍历其 Span,例如:

foreach (T value in memory.Span) { ... }

这背后的推动力是 Memory.Span 属性有一些开销,因为 Memory 可以由多种不同的对象类型支持(即 T[],如果是 ReadOnlyMemory 则为字符串,或 MemoryManager),Span 需要获取正确对象的 Span。即便如此,有时你确实需要从 {ReadOnly}Memory 获取 IEnumerable,ToEnumerable 提供了这个功能。在这种情况下,从性能的角度来看,不仅仅将 {ReadOnly}Memory 作为 IEnumerable 传递实际上是有益的,因为这样做会对值进行装箱,然后枚举该可枚举对象将需要为 IEnumerator 进行第二次分配。相比之下,MemoryMarshal.ToEnumerable 可以返回一个既是 IEnumerable 又是 IEnumerator 的 IEnumerable 实例。实际上,自从它被添加以来,它就是这样做的,整个实现如下:

public static IEnumerable<T> ToEnumerable<T>(ReadOnlyMemory<T> memory)
{
    for (int i = 0; i < memory.Length; i++)
        yield return memory.Span[i];
}

C# 编译器为这样的迭代器生成一个实际上也实现了 IEnumerator 并从 GetEnumerator 返回自身以避免额外分配的 IEnumerable,所以这是好的。然而,如前所述,Memory.Span 有一些开销,而这是每个元素都访问 .Span 一次...并不理想。dotnet/runtime#89274 以多种方式解决了这个问题。首先,ToEnumerable 本身可以检查 Memory 背后的底层对象的类型,对于 T[] 或字符串,可以返回一个不同的迭代器,该迭代器直接索引数组或字符串,而不是每次访问都通过 .Span。此外,ToEnumerable 可以检查 Memory 表示的边界是否为数组或字符串的全长...如果是,那么 ToEnumerable 可以直接返回原始对象,无需任何额外的分配。结果是,对于除 MemoryManager 之外的任何东西,都有一个更有效的枚举方案,这是非常罕见的(但也不会受到其他类型改进的负面影响)。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Buffers;
using System.Runtime.InteropServices;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly Memory<char> _array = Enumerable.Repeat('a', 1000).ToArray();

    [Benchmark]
    public int Count() => Count(MemoryMarshal.ToEnumerable<char>(_array));

    [Benchmark]
    public int CountLINQ() => Enumerable.Count(MemoryMarshal.ToEnumerable<char>(_array));

    private static int Count<T>(IEnumerable<T> source)
    {
        int count = 0;
        foreach (T item in source) count++;
        return count;
    }

    private sealed class WrapperMemoryManager<T>(Memory<T> memory) : MemoryManager<T>
    {
        public override Span<T> GetSpan() => memory.Span;
        public override MemoryHandle Pin(int elementIndex = 0) => throw new NotSupportedException();
        public override void Unpin() => throw new NotSupportedException();
        protected override void Dispose(bool disposing) { }
    }
}
方法 运行时 平均值 比率
Count .NET 7.0 6,336.147 ns 1.00
Count .NET 8.0 1,323.376 ns 0.21
CountLINQ .NET 7.0 4,972.580 ns 1.000
CountLINQ .NET 8.0 9.200 ns 0.002

SearchValues

从这篇文档的长度就可以看出,.NET 8 中有大量的性能改进。正如我之前提到的,我认为 .NET 8 中最有价值的新增功能是默认启用动态 PGO。在此之后,我认为最令人兴奋的新增功能是新的 System.Buffers.SearchValues 类型。在我看来,它简直太棒了。

从功能上讲,SearchValues 并没有做任何你不能已经做的事情。例如,假设你想在文本中搜索下一个 ASCII 字母或数字。你已经可以通过 IndexOfAny 来实现:

ReadOnlySpan<char> text = ...;
int pos = text.IndexOfAny("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");

这是可以工作的,但它并不特别快。在 .NET 7 中,IndexOfAny(ReadOnlySpan) 是针对搜索最多 5 个目标字符进行优化的,例如,它可以有效地向量化搜索英文元音(IndexOfAny("aeiou"))。但是,对于像前面的例子中的 62 个字符的目标集,它将不再向量化,而是试图看看每个字符可以使用多少指令,而不是试图看看每个指令可以处理多少字符(这意味着我们不再谈论在 haystack 中每个字符的指令的分数,而是谈论在 haystack 中每个字符的多个指令)。它通过一个布隆过滤器来实现,这在实现中被称为“概率映射”。其思想是维护一个 256 位的位图。对于每个 needle 字符,它在该位图中设置 2 位。然后在搜索 haystack 时,对于每个字符,它查看位图中是否设置了两个位;如果至少有一个没有设置,那么这个字符就不可能在 needle 中,搜索可以继续,但如果两个位都在位图中,那么 haystack 字符可能在 needle 中,但不能确定,然后搜索 needle 中的字符,看看我们是否找到了匹配。

实际上,已经有已知的算法可以更有效地进行这些搜索。例如,Mula 描述的“通用”算法在搜索任意集合的 ASCII 字符时是一个很好的选择,使我们能够有效地向量化搜索由 ASCII 的任何子集组成的 needle。这样做需要一些计算来分析 needle 并构建执行搜索所需的相关位图和向量,就像我们必须为布隆过滤器这样做一样(尽管生成的是不同的工件)。dotnet/runtime#76740 在 {Last}IndexOfAny{Except} 中实现了这些技术。而不是总是构建一个概率映射,它首先检查 needle,看看所有的值是否都是 ASCII,如果是,那么它切换到这个优化的基于 ASCII 的搜索;如果不是,它回退到之前使用的相同的概率映射方法。PR 还认识到,只有在正确的条件下,尝试任何优化才是值得的;例如,如果 haystack 真的很短,我们最好只是做简单的 O(M*N) 搜索,对于 haystack 中的每个字符,我们搜索 needle,看看 char 是否是目标。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    [Benchmark]
    public int CountEnglishVowelsAndSometimeVowels()
    {
        ReadOnlySpan<char> remaining = s_haystack;
        int count = 0, pos;
        while ((pos = remaining.IndexOfAny("aeiouyAEIOUY")) >= 0)
        {
            count++;
            remaining = remaining.Slice(pos + 1);
        }

        return count;
    }
}
方法 运行时 平均值 比率
CountEnglishVowelsAndSometimeVowels .NET 7.0 6.823 ms 1.00
CountEnglishVowelsAndSometimeVowels .NET 8.0 3.735 ms 0.55

即使有了这些改进,构建这些向量的工作还是相当重复的,而且并不是免费的。如果你在循环中有这样的 IndexOfAny,你就需要反复地支付构建这些向量的成本。我们还可以做更多的工作来进一步检查数据,选择一个更优的方法,但是每进行一次额外的检查,都会增加 IndexOfAny 调用的开销。这就是 SearchValues 的用武之地。SearchValues 的想法是一次性完成所有这些工作,然后将其缓存。几乎总是,使用 SearchValues 的模式是创建一个,将其存储在一个静态的只读字段中,然后使用该 SearchValues 进行所有针对该目标集的搜索操作。现在有一些像 IndexOfAny 这样的方法的重载,它们接受一个 SearchValues 或 SearchValues,例如,而不是一个 ReadOnlySpan 或 ReadOnlySpan。因此,我之前的 ASCII 字母或数字的例子现在看起来是这样的:

private static readonly SearchValues<char> s_asciiLettersOrDigits = SearchValues.Create("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
...
int pos = text.IndexOfAny(s_asciiLettersOrDigits);

dotnet/runtime#78093 提供了 SearchValues 的初始实现(它最初被命名为 IndexOfAnyValues,但我们随后将其重命名为更通用的 SearchValues,以便我们现在和将来可以与其他方法一起使用,如 Count 或 Replace)。如果你浏览实现,你会看到 Create 工厂方法不仅仅返回一个具体的 SearchValues 类型;相反,SearchValues 提供了一个内部抽象,然后由十五个以上的派生实现实现,每个都专门用于不同的场景。你可以通过运行以下程序很容易地在代码中看到这一点:

// dotnet run -f net8.0

using System.Buffers;

Console.WriteLine(SearchValues.Create(""));
Console.WriteLine(SearchValues.Create("a"));
Console.WriteLine(SearchValues.Create("ac"));
Console.WriteLine(SearchValues.Create("ace"));
Console.WriteLine(SearchValues.Create("ab\u05D0\u05D1"));
Console.WriteLine(SearchValues.Create("abc\u05D0\u05D1"));
Console.WriteLine(SearchValues.Create("abcdefghijklmnopqrstuvwxyz"));
Console.WriteLine(SearchValues.Create("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"));
Console.WriteLine(SearchValues.Create("\u00A3\u00A5\u00A7\u00A9\u00AB\u00AD"));
Console.WriteLine(SearchValues.Create("abc\u05D0\u05D1\u05D2"));
and you’ll see output like the following:

System.Buffers.EmptySearchValues`1[System.Char]
System.Buffers.SingleCharSearchValues`1[System.Buffers.SearchValues+TrueConst]
System.Buffers.Any2CharSearchValues`1[System.Buffers.SearchValues+TrueConst]
System.Buffers.Any3CharSearchValues`1[System.Buffers.SearchValues+TrueConst]
System.Buffers.Any4SearchValues`2[System.Char,System.Int16]
System.Buffers.Any5SearchValues`2[System.Char,System.Int16]
System.Buffers.RangeCharSearchValues`1[System.Buffers.SearchValues+TrueConst]
System.Buffers.AsciiCharSearchValues`1[System.Buffers.IndexOfAnyAsciiSearcher+Default]
System.Buffers.ProbabilisticCharSearchValues
System.Buffers.ProbabilisticWithAsciiCharSearchValues`1[System.Buffers.IndexOfAnyAsciiSearcher+Default]

每个不同的输入都会被映射到一个不同的 SearchValues 派生类型。

在初始的 PR 之后,SearchValues 一直在不断地改进和完善。例如,dotnet/runtime#78863 添加了 AVX2 支持,这样,当使用 256 位向量(如果可用)而不是 128 位向量时,一些基准测试的吞吐量几乎翻了一倍,而 dotnet/runtime#83122 则启用了 WASM 支持。dotnet/runtime#78996 添加了一个 Contains 方法,用于实现标量回退路径。而 dotnet/runtime#86046 通过调整如何在内部传递相关的位图和向量,减少了使用 SearchValues 调用 IndexOfAny 的开销。但我最喜欢的两个调整是 dotnet/runtime#82866 和 dotnet/runtime#84184,它们在 '\0'(空)是 needle 中的字符之一时,改进了开销。为什么这会有关系呢?搜索 '\0' 看起来并不常见吧?有趣的是,在各种情况下,它可能会很常见。假设你有一个非常擅长搜索 ASCII 的任何子集的算法,但你想用它来搜索特定的 ASCII 子集或非 ASCII 的东西。如果你只搜索子集,你就不会了解到非 ASCII 的命中。如果你搜索除子集之外的所有东西,你会了解到非 ASCII 的命中,但也会了解到所有错误的 ASCII 字符。相反,你想做的是反转 ASCII 子集,例如,如果你的目标字符是 'A' 到 'Z' 和 'a' 到 'z',你反而创建包括 '\u0000' 到 '\u0040','\u005B' 到 '\u0060',和 '\u007B' 到 '\u007F' 的子集。然后,你不是用那个反转的子集做 IndexOfAny,而是用那个反转的子集做 IndexOfAnyExcept;这是一个真正的“两个错误造就一个正确”的情况,因为我们最终会得到我们想要的行为,即搜索原始的 ASCII 字母子集加上任何非 ASCII 的东西。你会注意到,'\0' 在我们的反转子集中,这使得 '\0' 在其中时的性能比其他情况更重要。

有趣的是,.NET 8 中的概率映射代码路径实际上也享受到了一定程度的向量化,即使没有 SearchValues,也要感谢 dotnet/runtime#80963(它在 dotnet/runtime#85189 中得到了进一步的改进,该改进在 Arm 上使用了更好的指令,在 dotnet/runtime#85203 中避免了一些无用的工作)。这意味着,无论是否使用 SearchValues,涉及概率映射的搜索都会比在 .NET 7 中快得多。例如,这里有一个基准测试,再次搜索 “The Adventures of Sherlock Holmes”,并计算其中的行结束符数量,使用的是 string.ReplaceLineEndings 使用的相同的 needle:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    [Benchmark]
    public int CountLineEndings()
    {
        int count = 0;
        ReadOnlySpan<char> haystack = s_haystack;

        int pos;
        while ((pos = haystack.IndexOfAny("\n\r\f\u0085\u2028\u2029")) >= 0)
        {
            count++;
            haystack = haystack.Slice(pos + 1);
        }

        return count;
    }
}
方法 运行时 平均值 比率
CountLineEndings .NET 7.0 2.155 ms 1.00
CountLineEndings .NET 8.0 1.323 ms 0.61

然后,可以使用 SearchValues 来进一步改进。它不仅通过缓存每次调用 IndexOfAny 都需要重新计算的概率映射来实现,而且还通过识别当 needle 包含 ASCII 时,这是一个好的指示(启发式)ASCII haystacks 将会突出。因此,dotnet/runtime#89155 添加了一个快速路径,该路径执行对任何 ASCII needle 值或任何非 ASCII 值的搜索,如果它找到一个非 ASCII 值,那么它就回退到执行向量化概率映射搜索。

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Buffers;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
    private static readonly SearchValues<char> s_lineEndings = SearchValues.Create("\n\r\f\u0085\u2028\u2029");

    [Benchmark]
    public int CountLineEndings_Chars()
    {
        int count = 0;
        ReadOnlySpan<char> haystack = s_haystack;

        int pos;
        while ((pos = haystack.IndexOfAny("\n\r\f\u0085\u2028\u2029")) >= 0)
        {
            count++;
            haystack = haystack.Slice(pos + 1);
        }

        return count;
    }

    [Benchmark]
    public int CountLineEndings_SearchValues()
    {
        int count = 0;
        ReadOnlySpan<char> haystack = s_haystack;

        int pos;
        while ((pos = haystack.IndexOfAny(s_lineEndings)) >= 0)
        {
            count++;
            haystack = haystack.Slice(pos + 1);
        }

        return count;
    }
}
方法 平均值
CountLineEndings_Chars 1,300.3 us
CountLineEndings_SearchValues 430.9 us

dotnet/runtime#89224 进一步增强了这种启发式方法,通过快速检查下一个字符是否为非 ASCII 来保护 ASCII 快速路径,如果是,则跳过基于 ASCII 的搜索,从而避免处理全非 ASCII 输入时的开销。例如,这是运行前一个基准测试的结果,代码完全相同,只是将 URL 改为 https://www.gutenberg.org/files/39963/39963-0.txt,这是一份几乎完全由希腊文组成的文档,包含了亚里士多德的《雅典人的宪法》:

方法 平均值
CountLineEndings_Chars 542.6 us
CountLineEndings_SearchValues 283.6 us

有了 SearchValues 的所有优点,现在在 dotnet/runtime 中得到了广泛的应用。例如,System.Text.Json 之前有自己专用的实现函数 IndexOfQuoteOrAnyControlOrBackSlash,用于搜索任何序数值小于 32 的字符,或引号,或反斜杠。在 .NET 7 中,该实现是大约 200 行的复杂 Vector 基础代码。现在在 .NET 8 中,感谢 dotnet/runtime#82789,它只是这样:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int IndexOfQuoteOrAnyControlOrBackSlash(this ReadOnlySpan<byte> span) =>
    span.IndexOfAny(s_controlQuoteBackslash);

private static readonly SearchValues<byte> s_controlQuoteBackslash = SearchValues.Create(
    "\u0000\u0001\u0002\u0003\u0004\u0005\u0006\u0007\u0008\u0009\u000A\u000B\u000C\u000D\u000E\u000F\u0010\u0011\u0012\u0013\u0014\u0015\u0016\u0017\u0018\u0019\u001A\u001B\u001C\u001D\u001E\u001F"u8 + // Any Control, < 32 (' ')
    "\""u8 + // Quote
    "\\"u8); // Backslash

这种使用方式在一系列的 PR 中得到了推广,例如 dotnet/runtime#78664 在 System.Private.Xml 中使用了 SearchValues,dotnet/runtime#81976 在 JsonSerializer 中使用,dotnet/runtime#78676 在 X500NameEncoder 中使用,dotnet/runtime#78667 在 Regex.Escape 中使用,dotnet/runtime#79025 在 ZipFile 和 TarFile 中使用,dotnet/runtime#79974 在 WebSocket 中使用,dotnet/runtime#81486 在 System.Net.Mail 中使用,以及 dotnet/runtime#78896 在 Cookie 中使用。dotnet/runtime#78666 和 dotnet/runtime#79024 在 Uri 中的使用特别好,包括使用 SearchValues 优化了常用的 Uri.EscapeDataString 助手;这显示出了显著的改进,特别是当没有需要转义的内容时。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private string _value = Convert.ToBase64String("How did I escape? With difficulty. How did I plan this moment? With pleasure. "u8);

    [Benchmark]
    public string EscapeDataString() => Uri.EscapeDataString(_value);
}
方法 运行时 平均值 比率
EscapeDataString .NET 7.0 85.468 ns 1.00
EscapeDataString .NET 8.0 8.443 ns 0.10

总的来说,仅在 dotnet/runtime 中,SearchValues.Create 现在已经在 40 多个地方被使用,这还不包括作为 Regex 的一部分生成的所有使用(稍后会有更多介绍)。dotnet/roslyn-analyzers#6898 对此起到了推动作用,它添加了一个新的分析器,该分析器将标记 SearchValues 的使用机会并更新代码以使用它:CA1870。

在整个讨论中,我多次提到了 ReplaceLineEndings,将其作为一个想要有效搜索多个字符的例子。在 dotnet/runtime#78678 和 dotnet/runtime#81630 之后,它现在也使用了 SearchValues,并且还增加了其他优化。鉴于对 SearchValues 的讨论,它在这里的使用方式将是显而易见的,至少基本的使用方式是这样的。以前,ReplaceLineEndings 依赖于一个内部助手 IndexOfNewlineChar 来实现这个功能:

internal static int IndexOfNewlineChar(ReadOnlySpan<char> text, out int stride)
{
    const string Needles = "\r\n\f\u0085\u2028\u2029";
    int idx = text.IndexOfAny(needles);
    ...
}

现在,它这样做:

int idx = text.IndexOfAny(SearchValuesStorage.NewLineChars);

其中,NewLineChars 只是:

internal static class SearchValuesStorage
{
    public static readonly SearchValues<char> NewLineChars = SearchValues.Create("\r\n\f\u0085\u2028\u2029");
}

这很直接。然而,它进一步推进了事情。注意,这个列表中有 6 个字符,其中一些是 ASCII,一些不是。了解 SearchValues 目前采用的算法,我们知道这将使它偏离只做 ASCII 搜索的路径,而是使用一种搜索 3 个 ASCII 字符加上任何非 ASCII 的算法,如果找到任何非 ASCII,那么将回退到执行概率映射搜索。如果我们能去掉其中一个字符,我们就能回到只使用可以处理任何 5 个字符的 IndexOfAny 实现的范围。在非 Windows 系统上,我们很幸运。ReplaceLineEndings 默认用 Environment.NewLine 替换行结束符;在 Windows 上,这是 "\r\n",但在 Linux 和 macOS 上,这是 "\n"。如果替换文本是 "\n"(在 Windows 上也可以通过使用 ReplaceLineEndings(string replacementText) 重载选择),那么搜索 '\n' 只是为了用 '\n' 替换它,这是一个无操作,这意味着我们可以在替换文本是 "\n" 时从搜索列表中删除 '\n',这使我们只有 5 个目标字符,给我们带来了一点优势。虽然这是一个很好的小收获,但更大的收获是我们不会频繁地跳出向量化循环,或者如果所有的行结束符都是替换文本,我们根本不会跳出。此外,.NET 7 的实现总是创建一个新的字符串来返回,但如果我们实际上没有用任何新的东西替换任何东西,我们可以避免分配它。所有这些的结果是对 ReplaceLineEndings 的巨大改进,一部分是由于 SearchValues,一部分是超出了 SearchValues。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[MemoryDiagnoser(displayGenColumns: false)]
public class Tests
{
    // NOTE: This text uses \r\n as its line endings
    private static readonly string s_text = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    [Benchmark]
    [Arguments("\r\n")]
    [Arguments("\n")]
    public string ReplaceLineEndings(string replacement) => s_text.ReplaceLineEndings(replacement);
}
方法 运行时 替换 平均值 比率 分配 分配比率
ReplaceLineEndings .NET 7.0 \n 2,746.3 us 1.00 1163121 B 1.00
ReplaceLineEndings .NET 8.0 \n 995.9 us 0.36 1163121 B 1.00
ReplaceLineEndings .NET 7.0 \r\n 2,920.1 us 1.00 1187729 B 1.00
ReplaceLineEndings .NET 8.0 \r\n 356.5 us 0.12 0.00

SearchValue 的变化也积累到了基于 span 的非分配的 EnumerateLines 中:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_text = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    [Benchmark]
    public int CountLines()
    {
        int count = 0;
        foreach (ReadOnlySpan<char> _ in s_text.AsSpan().EnumerateLines()) count++;
        return count;
    }
}
方法 运行时 平均值 比率
CountLines .NET 7.0 2,029.9 us 1.00
CountLines .NET 8.0 353.2 us 0.17

Regex

刚刚研究了 SearchValues,现在是谈论正则表达式的好时机,因为前者现在在后者中起着重要的作用。.NET 5 中显著改进了正则表达式,然后在 .NET 7 中再次进行了全面改革,引入了正则表达式源代码生成器。现在在 .NET 8 中,正则表达式继续得到重大投资,特别是在这个版本中,利用了在堆栈较低处引入的许多已经讨论过的工作,以实现更有效的搜索。

作为提醒,System.Text.RegularExpressions 中有效地有三种不同的“引擎”,这意味着实际上有三种不同的组件用于处理正则表达式。最简单的引擎是“解释器”;正则表达式构造函数将正则表达式转换为一系列正则表达式操作码,然后 RegexInterpreter 针对传入的文本评估这些操作码。这是在一个“扫描”循环中完成的,(简化后)看起来像这样:

while (TryFindNextStartingPosition(text))
{
    if (TryMatchAtCurrentPosition(text) || _currentPosition == text.Length) break;
    _currentPosition++;
}

TryFindNextStartingPosition 尝试尽可能多地移动输入文本,直到找到输入中可能开始匹配的位置,然后 TryMatchAtCurrentPosition 在该位置对输入评估模式。在解释器中,该评估涉及到像这样的循环,处理从模式产生的操作码:

while (true)
{
    switch (_opcode)
    {
        case RegexOpcode.Stop:
            return match.FoundMatch;
        case RegexOpcode.Goto:
            Goto(Operand(0));
            continue;
        ... // cases for ~50 other opcodes
    }
}

然后是非回溯引擎,当你选择在 .NET 7 中引入的 RegexOptions.NonBacktracking 选项时,你会得到这个引擎。这个引擎与解释器共享相同的 TryFindNextStartingPosition 实现,这样所有涉及尽可能多地跳过文本(理想情况下通过向量化的 IndexOf 操作)的优化都会累积到解释器和非回溯引擎中。然而,相似之处就到此为止。非回溯引擎不是处理正则表达式操作码,而是通过将正则表达式模式转换为懒构造的确定性有限自动机(DFA)或非确定性有限自动机(NFA),然后使用它来评估输入文本。非回溯引擎的关键优点是它在输入长度上提供线性时间执行保证。更多详细信息,请阅读 .NET 7 中的正则表达式改进。

第三种引擎实际上有两种形式:RegexOptions.Compiled 和正则表达式源代码生成器(在 .NET 7 中引入)。除了一些边角案例,这两者在工作方式上实际上是相同的。它们都生成针对提供的输入模式的特定代码,前者在运行时生成 IL,后者在构建时生成 C#(然后由 C# 编译器编译为 IL)。生成的代码的结构,以及应用的 99% 的优化,在它们之间是相同的;事实上,在 .NET 7 中,RegexCompiler 完全被重写为 C# 代码的块对块翻译,这些代码是正则表达式源代码生成器发出的。对于两者,实际发出的代码都完全定制为提供的确切模式,两者都试图生成尽可能有效地处理正则表达式的代码,源代码生成器试图通过生成尽可能接近专家 .NET 开发人员可能编写的代码来实现这一点。这在很大程度上是因为它生成的源代码是可见的,甚至在 Visual Studio 中编辑模式时也是实时的:在 Visual Studio 中生成的正则表达式。

我提到所有这些,是因为在整个正则表达式中,无论是解释器和非回溯引擎使用的 TryFindNextStartingPosition,还是 RegexCompiler 和正则表达式源代码生成器生成的代码中,都有大量的机会使用新引入的 API 来加速搜索。我在看你,IndexOf 和朋友们。

如前所述,.NET 8 中引入了新的 IndexOf 变体,用于搜索范围,而且从 dotnet/runtime#76859 开始,正则表达式现在将在生成的代码中充分利用它们。例如,考虑 [GeneratedRegex(@"[0-9]{5}")], 它可能被用来在美国搜索邮政编码。.NET 7 中的正则表达式源代码生成器会为 TryFindNextStartingPosition 生成包含以下内容的代码:

// The pattern begins with '0' through '9'.
// Find the next occurrence. If it can't be found, there's no match.
ReadOnlySpan<char> span = inputSpan.Slice(pos);
for (int i = 0; i < span.Length - 4; i++)
{
    if (char.IsAsciiDigit(span[i]))
    ...
}

现在在 .NET 8 中,同样的属性会生成这样的代码:

// 模式以集合 [0-9] 中的字符开始。
// 找到下一个出现的位置。如果找不到,那就没有匹配。
ReadOnlySpan<char> span = inputSpan.Slice(pos);
for (int i = 0; i < span.Length - 4; i++)
{
    int indexOfPos = span.Slice(i).IndexOfAnyInRange('0', '9');
    ...
}

.NET 7 的实现一次检查一个字符,而 .NET 8 的代码通过 IndexOfAnyInRange 向量化搜索,一次检查多个字符。这可以显著提高速度。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.RegularExpressions;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    private readonly Regex _regex = new Regex("[0-9]{5}", RegexOptions.Compiled);

    [Benchmark]
    public int Count() => _regex.Count(s_haystack);
}
方法 运行时 平均值 比率
Count .NET 7.0 423.88 us 1.00
Count .NET 8.0 29.91 us 0.07

生成的代码也可以在其他地方使用这些 API,甚至作为验证匹配本身的一部分。假设你的模式是 [GeneratedRegex(@"(\w{3,})[0-9]")], 它将寻找并捕获至少三个单词字符的序列,然后跟着一个 ASCII 数字。这是一个标准的贪婪循环,所以它会消耗尽可能多的单词字符(包括 ASCII 数字),然后回溯,退回一些消耗的单词字符,直到找到一个数字。以前,这是通过退回一个字符,看看它是否是一个数字,退回一个字符,看看它是否是一个数字,等等来实现的。现在呢?源代码生成器发出包含以下内容的代码:

charloop_ending_pos = inputSpan.Slice(charloop_starting_pos, charloop_ending_pos - charloop_starting_pos).LastIndexOfAnyInRange('0', '9')

换句话说,它使用 LastIndexOfAnyInRange 来优化向后搜索下一个可行回溯位置的操作。

另一个显著的改进是建立在堆栈较低处的改进之上的 dotnet/runtime#85438。如前所述,.NET 8 中 span.IndexOf("...", StringComparison.OrdinalIgnoreCase) 的向量化已经得到改进。以前,Regex 没有使用这个 API,因为它通常可以用自己的自定义生成的代码做得更好。但现在这个 API 已经被优化,这个 PR 改变了 Regex 使用它,使生成的代码更简单,更快。这里我正在不区分大小写地搜索整个单词“year”:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.RegularExpressions;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    private readonly Regex _regex = new Regex(@"\byear\b", RegexOptions.Compiled | RegexOptions.IgnoreCase);

    [Benchmark]
    public int Count() => _regex.Count(s_haystack);
}
| 方法 | 运行时 | 平均值 | 比率 |
| --- | --- | --- | --- |
| Count | .NET 7.0 | 181.80 us | 1.00 |
| Count | .NET 8.0 | 63.10 us | 0.35 |

除了学习如何使用现有的 IndexOf(..., StringComparison.OrdinalIgnoreCase) 和新的 IndexOfAnyInRange 和 IndexOfAnyExceptInRange,.NET 8 中的 Regex 还学习如何使用新的 SearchValues。这对于 Regex 来说是一个巨大的提升,因为它现在意味着它可以向量化搜索比以前更多的集合。例如,假设你想搜索所有的十六进制数字。你可能会使用像 [0123456789ABCDEFabcdef]+ 这样的模式。如果你将它插入到 .NET 7 中的 regex 源代码生成器,你会得到一个发出包含如下代码的 TryFindNextPossibleStartingPosition:

// 模式以集合 [0-9A-Fa-f] 中的字符开始。
// 找到下一个出现的位置。如果找不到,那就没有匹配。
ReadOnlySpan<char> span = inputSpan.Slice(pos);
for (int i = 0; i < span.Length; i++)
{
    if (char.IsAsciiHexDigit(span[i]))
    {
        base.runtextpos = pos + i;
        return true;
    }
}

现在在 .NET 8 中,主要归功于 dotnet/runtime#78927,你会得到像这样的代码:

// 模式以集合 [0-9A-Fa-f] 中的字符开始。
// 找到下一个出现的位置。如果找不到,那就没有匹配。
int i = inputSpan.Slice(pos).IndexOfAny(Utilities.s_asciiHexDigits);
if (i >= 0)
{
    base.runtextpos = pos + i;
    return true;
}

那么 Utilities.s_asciiHexDigits 是什么呢?它是一个 SearchValues,被输出到文件的 Utilities 类中:

/// <summary>支持搜索在 "0123456789ABCDEFabcdef" 中或不在其中的字符。</summary>
internal static readonly SearchValues<char> s_asciiHexDigits = SearchValues.Create("0123456789ABCDEFabcdef");

源代码生成器明确识别了这个集合,因此为它创建了一个好的名字,但这纯粹是为了可读性;即使它不识别集合为某种众所周知且易于命名的东西,它仍然可以使用 SearchValues。例如,如果我将集合扩充为所有有效的十六进制数字和下划线,我会得到这样的结果:

/// <summary>支持搜索在 "0123456789ABCDEF_abcdef" 中或不在其中的字符。</summary>
internal static readonly SearchValues<char> s_ascii_FF037E0000807E000000 = SearchValues.Create("0123456789ABCDEF_abcdef");

当最初添加到 Regex 中时,SearchValues 只在输入集全为 ASCII 时使用。但随着 .NET 8 的开发,SearchValues 的改进,Regex 对它的使用也随之改进。有了 dotnet/runtime#89205,Regex 现在依赖于 SearchValues 的能力,有效地搜索 ASCII 和非 ASCII,并且如果它能有效地枚举集合的内容,且该集合包含相当少的字符(今天,这意味着不超过 128 个),它也会发出一个 SearchValues。有趣的是,SearchValues 的优化,首先搜索目标的 ASCII 子集,然后回退到向量化的概率映射搜索,最初是在 Regex 中原型化的(dotnet/runtime#89140),之后我们决定将优化推向 SearchValues,这样 Regex 可以生成更简单的代码,其他非 Regex 消费者也会受益。
然而,这仍然留下了我们无法有效地枚举集合以确定它包含的每个字符的情况,也不希望将大量的字符传递给 SearchValues。考虑集合 \w,即“单词字符”。在 65,536 个 char 值中,有 50,409 个匹配集合 \w。为了尝试为它们创建一个 SearchValues,枚举所有这些字符将是低效的,Regex 也不会尝试。相反,从 dotnet/runtime#83992 开始,Regex 采用了上面提到的类似方法,但是有一个标量回退。例如,对于模式 \w+,它将以下助手发射到 Utilities:

internal static int IndexOfAnyWordChar(this ReadOnlySpan<char> span)
{
    int i = span.IndexOfAnyExcept(Utilities.s_asciiExceptWordChars);
    if ((uint)i < (uint)span.Length)
    {
        if (char.IsAscii(span[i]))
        {
            return i;
        }

        do
        {
            if (Utilities.IsWordChar(span[i]))
            {
                return i;
            }
            i++;
        }
        while ((uint)i < (uint)span.Length);
    }

    return -1;
}

/// <summary>支持搜索在"\0\u0001\u0002\u0003\u0004\u0005\u0006\a\b\t\n\v\f\r\u000e\u000f\u0010\u0011\u0012\u0013\u0014\u0015\u0016\u0017\u0018\u0019\u001a\u001b\u001c\u001d\u001e\u001f !\"#$%&'()*+,-./:;<=>?@[\\]^`{|}~\u007f" 中或不在其中的字符。</summary>
internal static readonly SearchValues<char> s_asciiExceptWordChars = SearchValues.Create("\0\u0001\u0002\u0003\u0004\u0005\u0006\a\b\t\n\v\f\r\u000e\u000f\u0010\u0011\u0012\u0013\u0014\u0015\u0016\u0017\u0018\u0019\u001a\u001b\u001c\u001d\u001e\u001f !\"#$%&'()*+,-./:;<=>?@[\\]^`{|}~\u007f");

它将助手命名为“IndexOfAnyWordChar”是一回事,再次,这与它能够生成这个助手是分开的;它只是在这里识别集合作为确定名称的一部分,并能够提出一个更好的名称,但如果它没有识别它,方法的主体将是相同的,名称只是不太可读,因为它会提出相当混乱但唯一的东西。

有趣的是,我注意到源代码生成器和 RegexCompiler 实际上是相同的,只是一个生成 C#,一个生成 IL。这有 99% 是正确的。然而,他们使用 SearchValues 的方式有一个有趣的区别,这使得源代码生成器在如何利用这种类型方面更有效率。每当源代码生成器需要一个新的字符组合的 SearchValues 实例时,它可以只发出另一个静态只读字段,因为它是静态只读的,JIT 的去虚拟化和内联优化可以启动,使用这个看到实例的实际类型并基于此进行优化。好极了。RegexCompiler 是另一回事。RegexCompiler 为给定的 Regex 发出 IL,并使用 DynamicMethod 这提供了反射发射最轻量级的解决方案,也允许当它们不再被引用时,生成的方法被垃圾收集。然而,DynamicMethods 就是方法。没有支持创建额外的静态字段的需求,没有进入更昂贵的 TypeBuilder-based 解决方案。那么 RegexCompiler 如何创建和存储任意数量的 SearchValue 实例,以及如何以类似地启用去虚拟化的方式来做呢?它采用了一些技巧。首先,向内部的 CompiledRegexRunner 类型添加了一个字段,该字段存储生成方法的委托:private readonly SearchValues[]? _searchValues; 作为数组,这使得可以存储任意数量的 SearchValues;发出的 IL 可以访问字段,获取数组,并索引到它以获取相关的 SearchValues 实例。当然,只做这个,不允许去虚拟化,甚至动态 PGO 在这里也没有帮助,因为目前 DynamicMethods 不参与分层;编译直接进入 tier 1,所以没有机会进行仪器化以查看实际使用的 SearchValues-derived 类型。幸运的是,有可用的解决方案。JIT 可以从存储它的本地类型中了解实例的类型,所以一个解决方案是创建一个具体的和密封的 SearchValues 派生类型的本地(我们在这一点上正在写 IL,所以我们可以做这样的事情,而不实际访问问题中的类型),从数组中读取 SearchValues,将其存储到本地,然后使用本地进行后续访问。实际上,我们在 .NET 8 的开发过程中这样做了一段时间。然而,这确实需要一个本地,并需要额外的读/写本地。相反,dotnet/runtime#85954 中的一个调整允许 JIT 使用 Unsafe.As(object o) 中的 T 来了解 T 的实际类型,所以 RegexCompiler 只需要使用 Unsafe.As 来通知 JIT 实例的实际类型,然后它就被去虚拟化了。RegexCompiler 用来发出 IL 加载 SearchValues 的代码是这样的:

// from RegexCompiler.cs, tweaked for readability in this post
private void LoadSearchValues(ReadOnlySpan<char> chars)
{
    List<SearchValues<char>> list = _searchValues ??= new();
    int index = list.Count;
    list.Add(SearchValues.Create(chars));

    // Unsafe.As<DerivedSearchValues>(Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(this._searchValues), index));
    _ilg.Emit(OpCodes.Ldarg_0);
    _ilg.Emit(OpCodes.Ldfld, s_searchValuesArrayField);
    _ilg.Emit(OpCodes.Call, s_memoryMarshalGetArrayDataReferenceSearchValues);
    _ilg.Emit(OpCodes.Ldc_I4, index * IntPtr.Size);
    _ilg.Emit(OpCodes.Add);
    _ilg.Emit(OpCodes.Ldind_Ref);
    _ilg.Emit(OpCodes.Call, typeof(Unsafe).GetMethod("As", new[] { typeof(object) })!.MakeGenericMethod(list[index].GetType()));
}

我们可以通过如下的基准测试来看到所有这些操作:

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.RegularExpressions;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public partial class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    private static readonly Regex s_names = new Regex("Holmes|Watson|Lestrade|Hudson|Moriarty|Adler|Moran|Morstan|Gregson", RegexOptions.Compiled);

    [Benchmark]
    public int Count() => s_names.Count(s_haystack);
}

在这里,我们在同一份夏洛克·福尔摩斯的文本中搜索侦探故事中最常见的一些角色的名字。正则表达式模式分析器会尝试找到可以向量化搜索的东西,它会查看每个匹配位置可以有效存在的所有字符,例如,所有匹配都以 'H'、'W'、'L'、'M'、'A' 或 'G' 开始。而且,由于最短的匹配是五个字母(“Adler”),它最终会查看前五个位置,得出以下集合:

0: [AGHLMW]
1: [adeoru]
2: [delrst]
3: [aegimst]
4: [aenorst]

所有这些集合中的字符都超过了五个,这是一个重要的区分,因为在 .NET 7 中,这是 IndexOfAny 会向量化搜索的字符的最大数量。因此,在 .NET 7 中,Regex 最终会生成遍历输入并逐个检查字符的代码(尽管它确实使用了快速的无分支位图机制来匹配集合):

ReadOnlySpan<char> span = inputSpan.Slice(pos);
for (int i = 0; i < span.Length - 4; i++)
{
    if (((long)((0x8318020000000000UL << (int)(charMinusLow = (uint)span[i] - 'A')) & (charMinusLow - 64)) < 0) &&
    ...
}

现在在 .NET 8 中,有了 SearchValues,我们可以有效地搜索这些集合中的任何一个,实现最终会选择它认为统计上最不可能匹配的一个:

int indexOfPos = span.Slice(i).IndexOfAny(Utilities.s_ascii_8231800000000000);

其中,s_ascii_8231800000000000 定义为:

/// <summary>支持搜索 "AGHLMW" 中的字符或不在其中的字符。</summary>
internal static readonly SearchValues<char> s_ascii_8231800000000000 = SearchValues.Create("AGHLMW");

这使得整个搜索过程更加高效。

方法 运行时 平均值 比率
Count .NET 7.0 630.5 us 1.00
Count .NET 8.0 142.3 us 0.23

像 dotnet/runtime#84370, dotnet/runtime#89099, 和 dotnet/runtime#77925 这样的其他 PR 也对 IndexOf 和朋友们的使用做出了贡献,调整了涉及的各种启发式方法。但是,除此之外,Regex 的改进也有所提高。例如,dotnet/runtime#84003 通过使用位扭转技巧,优化了在非 ASCII 字符上匹配 \w 的性能。而 dotnet/runtime#84843 改变了内部枚举的底层类型,从 int 变为 byte,这样做可以缩小包含此枚举值的对象的大小 8 字节(在 64 位进程中)。更有影响力的是 dotnet/runtime#85564,它对 Regex.Replace 做出了可衡量的改进。Replace 保持了一个 ReadOnlyMemory 段的列表,这些段将被组合回最终的字符串;一些段来自原始字符串,而一些则是替换字符串。然而,事实证明,该 ReadOnlyMemory 中包含的字符串引用是不必要的。我们可以只维护一个 int 列表,每次我们添加一个段时,我们向列表中添加 int 偏移量和 int 计数,由于替换的性质,我们可以简单地依赖于我们需要在每对值之间插入替换文本的事实。

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.RegularExpressions;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

    private static readonly Regex s_vowels = new Regex("[aeiou]", RegexOptions.Compiled);

    [Benchmark]
    public string RemoveVowels() => s_vowels.Replace(s_haystack, "");
}
方法 运行时 平均值 比率
RemoveVowels .NET 7.0 8.763 ms 1.00
RemoveVowels .NET 8.0 7.084 ms 0.81

最后要强调的 Regex 改进实际上并不是由于 Regex 本身的任何内容,而是由于 Regex 在每个操作中都使用的一个基元:Interlocked.Exchange。考虑以下基准测试:

// dotnet run -c Release -f net7.0 --filter "*" --runtimes net7.0 net8.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.RegularExpressions;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private static readonly Regex s_r = new Regex("", RegexOptions.Compiled);

    [Benchmark]
    public bool Overhead() => s_r.IsMatch("");
}

这纯粹是测量调用 Regex 实例的开销;匹配程序将立即完成,因为模式匹配任何输入。由于我们只讨论几十纳秒,你的数字可能会有所不同,但我经常得到这样的结果:

方法 运行时 平均值 比率
Overhead .NET 7.0 32.01 ns 1.00
Overhead .NET 8.0 28.81 ns 0.90

这几纳秒的改进主要归功于 dotnet/runtime#79181,该改进将 Interlocked.CompareExchange 和 Interlocked.Exchange 对于引用类型变为内联,特别是当 JIT 可以看到要写入的新值是 null 时。这些 API 需要在将对象引用写入共享位置的过程中使用 GC 写入屏障,原因与本文前面讨论的相同,但是在写入 null 时,不需要这样的屏障。这对 Regex 有利,Regex 在租用 RegexRunner 来实际处理匹配时使用 Interlocked.Exchange:

RegexRunner runner = Interlocked.Exchange(ref _runner, null) ?? CreateRunner();
try { ... }
finally { _runner = runner; }

许多对象池实现都使用了类似的 Interlocked.Exchange,并将同样受益。

Hashing

在 .NET 6 中引入的 System.IO.Hashing 库提供了非加密哈希算法的实现;最初,它附带了四种类型:Crc32、Crc64、XxHash32 和 XxHash64。在 .NET 8 中,它得到了重大投资,增加了新的优化算法,提高了现有实现的性能,并在所有算法中增加了新的表面区域。

由于其在大型和小型输入上的高性能以及其整体质量水平(例如,产生的冲突少,输入分散良好等),xxHash 系列哈希算法近来已经变得非常流行。System.IO.Hashing 之前包含了旧的 XXH32 和 XXH64 算法的实现(分别作为 XxHash32 和 XxHash64)。现在在 .NET 8 中,感谢 dotnet/runtime#76641,它包括了 XXH3 算法(作为 XxHash3),并且感谢来自 @xoofx 的 dotnet/runtime#77944,它包括了 XXH128 算法(作为 XxHash128)。XxHash3 算法在 @xoofx 的 dotnet/runtime#77756 中通过分摊一些加载和存储的成本进一步优化,在 @xoofx 的 dotnet/runtime#77881 中,通过更好地利用 AdvSimd 硬件内在功能,提高了在 Arm 上的吞吐量。

为了看到这些哈希函数的整体性能,这里有一个微基准测试,比较了加密的 SHA256 与每一个非加密哈希函数的吞吐量。我还包括了 FNV-1a 的实现,这是 C# 编译器可能用于 switch 语句的哈希算法(当它需要切换一个字符串,例如,它不能想出一个更好的方案,它哈希输入,然后在每个 case 的预生成哈希中进行二分搜索),以及基于 System.HashCode 的实现(注意 HashCode 与其他的不同,它专注于启用对任意 .NET 类型的哈希,包括每个进程的随机化,而这些其他哈希函数的目标是在进程边界上 100% 确定)。

// For this test, you'll also need to add:
//     <PackageReference Include="System.IO.Hashing" Version="8.0.0-rc.1.23419.4" />
// to the benchmarks.csproj's <ItemGroup>.
// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Buffers.Binary;
using System.IO.Hashing;
using System.Security.Cryptography;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly byte[] _result = new byte[100];
    private byte[] _source;

    [Params(3, 33_333)]
    public int Length { get; set; }

    [GlobalSetup]
    public void Setup() => _source = Enumerable.Range(0, Length).Select(i => (byte)i).ToArray();

    // Cryptographic
    [Benchmark(Baseline = true)] public void TestSHA256() => SHA256.HashData(_source, _result);

    // Non-cryptographic
    [Benchmark] public void TestCrc32() => Crc32.Hash(_source, _result);
    [Benchmark] public void TestCrc64() => Crc64.Hash(_source, _result);
    [Benchmark] public void TestXxHash32() => XxHash32.Hash(_source, _result);
    [Benchmark] public void TestXxHash64() => XxHash64.Hash(_source, _result);
    [Benchmark] public void TestXxHash3() => XxHash3.Hash(_source, _result);
    [Benchmark] public void TestXxHash128() => XxHash128.Hash(_source, _result);

    // Algorithm used by the C# compiler for switch statements
    [Benchmark]
    public void TestFnv1a()
    {
        int hash = unchecked((int)2166136261);
        foreach (byte b in _source) hash = (hash ^ b) * 16777619;
        BinaryPrimitives.WriteInt32LittleEndian(_result, hash);
    }

    // Randomized with a custom seed per process
    [Benchmark]
    public void TestHashCode()
    {
        HashCode hc = default;
        hc.AddBytes(_source);
        BinaryPrimitives.WriteInt32LittleEndian(_result, hc.ToHashCode());
    }
}
方法 长度 平均值 比率
TestSHA256 3 856.168 ns 1.000
TestHashCode 3 9.933 ns 0.012
TestXxHash64 3 7.724 ns 0.009
TestXxHash128 3 5.522 ns 0.006
TestXxHash32 3 5.457 ns 0.006
TestCrc32 3 3.954 ns 0.005
TestCrc64 3 3.405 ns 0.004
TestXxHash3 3 3.343 ns 0.004
TestFnv1a 3 1.617 ns 0.002
TestSHA256 33333 60,407.625 ns 1.00
TestFnv1a 33333 31,027.249 ns 0.51
TestHashCode 33333 4,879.262 ns 0.08
TestXxHash32 33333 4,444.116 ns 0.07
TestXxHash64 33333 3,636.989 ns 0.06
TestCrc64 33333 1,571.445 ns 0.03
TestXxHash3 33333 1,491.740 ns 0.03
TestXxHash128 33333 1,474.551 ns 0.02
TestCrc32 33333 1,295.663 ns 0.02

XxHash3 和 XxHash128 比 XxHash32 和 XxHash64 表现得更好的主要原因是它们的设计主要是为了向量化。因此,.NET 实现使用 System.Runtime.Intrinsics 中的支持,充分利用底层硬件。这些数据也暗示了为什么 C# 编译器使用 FNV-1a:它非常简单,对于小输入的开销也非常小,这是 switch 语句中最常用的输入形式,但如果你主要预期的是较长的输入,那么它将是一个糟糕的选择。

你会注意到,在上一个例子中,Crc32 和 Crc64 在吞吐量方面都与 XxHash3 处于同一水平(XXH3 通常在质量方面比 CRC32/64 排名更高)。在这个比较中,Crc32 得益于来自 @brantburnett 的 dotnet/runtime#83321,dotnet/runtime#86539 和 dotnet/runtime#85221。这些基于 Intel 十年前的一篇名为 "Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction" 的论文,对 Crc32 和 Crc64 的实现进行了向量化。所引用的 PCLMULQDQ 指令是 SSE2 的一部分,然而 PR 也能够通过利用 Arm 的 PMULL 指令在 Arm 上进行向量化。结果是,与 .NET 7 相比,对于需要哈希的较大输入,有了巨大的提升。

// For this test, you'll also need to add:
//     <PackageReference Include="System.IO.Hashing" Version="7.0.0" />
// to the benchmarks.csproj's <ItemGroup>.
// dotnet run -c Release -f net7.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Environments;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using System.IO.Hashing;

var config = DefaultConfig.Instance
    .AddJob(Job.Default.WithRuntime(CoreRuntime.Core70).WithNuGet("System.IO.Hashing", "7.0.0").AsBaseline())
    .AddJob(Job.Default.WithRuntime(CoreRuntime.Core80).WithNuGet("System.IO.Hashing", "8.0.0-rc.1.23419.4"));
BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args, config);

[HideColumns("Error", "StdDev", "Median", "RatioSD", "NuGetReferences")]
public class Tests
{
    private readonly byte[] _source = Enumerable.Range(0, 1024).Select(i => (byte)i).ToArray();
    private readonly byte[] _destination = new byte[4];

    [Benchmark]
    public void Hash() => Crc32.Hash(_source, _destination);
}
方法 运行时 平均值 比率
Hash .NET 7.0 2,416.24 ns 1.00
Hash .NET 8.0 39.01 ns 0.02

另一个改变也进一步提高了这些算法的性能,但其主要目的实际上是使它们在各种场景中更易于使用。NonCryptographicHashAlgorithm 的原始设计是专注于创建现有加密算法的非加密替代品,因此所有的 API 都专注于输出结果摘要,这些摘要是不透明的字节,例如,CRC32 生成一个 4 字节的哈希。然而,特别是对于这些非加密算法,许多开发者更熟悉返回数值结果,例如,CRC32 生成一个 uint。同样的数据,只是表示方式不同。有趣的是,这些算法中的一些以这样的整数为操作对象,所以获取字节实际上需要一个单独的步骤,既要确保有某种存储位置可用于写入结果字节,然后再将结果提取到该位置。为了解决所有这些问题,dotnet/runtime#78075 在 System.IO.Hashing 的所有类型中添加了新的实用方法来生成这样的数字。例如,Crc32 添加了两个新方法:

public static uint HashToUInt32(ReadOnlySpan<byte> source);
public uint GetCurrentHashAsUInt32();

如果你只想要某些输入字节的基于 uint 的 CRC32 哈希,你可以简单地调用这个一次性静态方法 HashToUInt32。或者,如果你正在逐步构建哈希,已经创建了 Crc32 类型的实例并向其追加了数据,你可以通过 GetCurrentHashAsUInt32 获取当前的 uint 哈希。对于像 XxHash3 这样的算法,这也省去了几条指令,因为它实际上需要做更多的工作来将结果作为字节产生,只是然后需要将这些字节作为 ulong 获取回来:

// For this test, you'll also need to add:
//     <PackageReference Include="System.IO.Hashing" Version="8.0.0-rc.1.23419.4" />
// to the benchmarks.csproj's <ItemGroup>.
// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.IO.Hashing;
using System.Runtime.InteropServices;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly byte[] _source = new byte[] { 1, 2, 3 };

    [Benchmark(Baseline = true)]
    public ulong HashToBytesThenGetUInt64()
    {
        ulong hash = 0;
        XxHash3.Hash(_source, MemoryMarshal.AsBytes(new Span<ulong>(ref hash)));
        return hash;
    }

    [Benchmark]
    public ulong HashToUInt64() => XxHash3.HashToUInt64(_source);
}
方法 平均值 比率
HashToBytesThenGetUInt64 3.686 ns 1.00
HashToUInt64 3.095 ns 0.84

在哈希方面,@deeprobin 的 dotnet/runtime#61558 添加了新的 BitOperations.Crc32C 方法,允许进行迭代的 crc32c 哈希计算。crc32c 的一个好处是多个平台提供了这个操作的指令,包括 SSE 4.2 和 Arm,.NET 方法将使用任何可用的硬件支持,通过委托到 System.Runtime.Intrinsics 中的相关硬件内在功能,例如:

if (Sse42.X64.IsSupported) return (uint)Sse42.X64.Crc32(crc, data);
if (Sse42.IsSupported) return Sse42.Crc32(Sse42.Crc32(crc, (uint)(data)), (uint)(data >> 32));
if (Crc32.Arm64.IsSupported) return Crc32.Arm64.ComputeCrc32C(crc, data);

我们可以通过比较 crc32c 算法的手动实现和现在的内置实现,看到这些内在功能的影响:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Numerics;
using System.Security.Cryptography;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly byte[] _data = RandomNumberGenerator.GetBytes(1024 * 1024);

    [Benchmark(Baseline = true)]
    public uint Crc32c_Manual()
    {
        uint c = 0;
        foreach (byte b in _data) c = Tests.Crc32C(c, b);
        return c;
    }

    [Benchmark]
    public uint Crc32c_BitOperations()
    {
        uint c = 0;
        foreach (byte b in _data) c = BitOperations.Crc32C(c, b);
        return c;
    }

    private static readonly uint[] s_crcTable = Generate(0x82F63B78u);

    internal static uint Crc32C(uint crc, byte data) =>
        s_crcTable[(byte)(crc ^ data)] ^ (crc >> 8);

    internal static uint[] Generate(uint reflectedPolynomial)
    {
        var table = new uint[256];

        for (int i = 0; i < 256; i++)
        {
            uint val = (uint)i;
            for (int j = 0; j < 8; j++)
            {
                if ((val & 0b0000_0001) == 0)
                {
                    val >>= 1;
                }
                else
                {
                    val = (val >> 1) ^ reflectedPolynomial;
                }
            }

            table[i] = val;
        }

        return table;
    }
}
方法 平均值 比率
Crc32c_Manual 1,977.9 us 1.00
Crc32c_BitOperations 739.9 us 0.37

Initialization

几个版本前,C# 编译器添加了一个非常有价值的优化,现在在核心库中被大量使用,新的 C# 构造(如 u8)也严重依赖它。在代码中存储和访问序列或数据表是非常常见的。例如,假设我想快速查找公历中一个月有多少天,基于该月的 0-based 索引。我可以使用这样的查找表(为了解释的目的,忽略闰年):

byte[] daysInMonth = new byte[] { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

当然,现在我正在分配一个 byte[],所以我应该将它移动到一个静态只读字段。即使这样,数组仍然需要被分配,数据加载到它,第一次使用时会产生一些启动开销。相反,我可以这样写:

ReadOnlySpan<byte> daysInMonth = new byte[] { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

虽然这看起来像是在分配,但实际上并没有。C# 编译器认识到用来初始化 byte[] 的所有数据都是常量,而且数组被直接存储到 ReadOnlySpan 中,它不提供任何提取数组的方法。因此,编译器将其降低为实际上做这个的代码(我们不能确切地用 C# 表达生成的 IL,所以这是伪代码):

ReadOnlySpan<byte> daysInMonth = new ReadOnlySpan<byte>(
    &<PrivateImplementationDetails>.9D61D7D7A1AA7E8ED5214C2F39E0C55230433C7BA728C92913CA4E1967FAF8EA,
    12);

它将数组的数据复制到程序集中,然后构造 span 不是通过数组分配,而是直接将 span 包装到程序集数据的指针中。这不仅避免了启动开销和堆上的额外对象,而且更好地启用了各种 JIT 优化,特别是当 JIT 能够看到正在访问的偏移量时。如果我运行这个基准测试:

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[DisassemblyDiagnoser]
public class Tests
{
    private static readonly byte[] s_daysInMonthArray = new byte[] { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    private static ReadOnlySpan<byte> DaysInMonthSpan => new byte[] { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

    [Benchmark] public int ViaArray() => s_daysInMonthArray[0];

    [Benchmark] public int ViaSpan() => DaysInMonthSpan[0];
}

它生成了这样的汇编代码:

; Tests.ViaArray()
       mov       rax,1B860002028
       mov       rax,[rax]
       movzx     eax,byte ptr [rax+10]
       ret
; Total bytes of code 18

; Tests.ViaSpan()
       mov       eax,1F
       ret
; Total bytes of code 6

换句话说,对于数组,它正在读取数组的地址,然后读取偏移量为0x10,或者十进制16的元素,这是数组数据开始的地方。对于 span,它只是加载值0x1F,或者十进制31,因为它直接从程序集数据中读取数据。(这不是 JIT 对数组示例中缺失的优化...数组是可变的,所以 JIT 不能基于数组中存储的当前值进行常量折叠,因为从技术上讲,它可能会改变。)

然而,这个编译器优化只适用于 byte,sbyte 和 bool。任何其他原始类型,编译器只会简单地做你要求它做的事情:分配数组。这远非理想。限制的原因是字节顺序。编译器需要生成在小端和大端系统上都能工作的二进制文件;对于单字节类型,没有字节顺序问题(因为字节顺序是关于字节的排序,如果只有一个字节,那么只有一种排序),但对于多字节类型,生成的代码不能再直接指向数据,因为在某些系统上,数据的字节会被反转。

.NET 7 添加了一个新的 API 来帮助解决这个问题,即 RuntimeHelpers.CreateSpan。这个 API 的设计思路是,编译器会发出对 CreateSpan 的调用,传入包含数据的字段的引用,而不是仅仅发出 new ReadOnlySpan(ptrIntoData, dataLength)。然后,JIT 和 VM 会共同确保数据被正确且高效地加载;在小端系统上,代码会被发出,就好像调用不存在一样(被替换为围绕指针和长度包装 span 的等价物),而在大端系统上,数据会被加载、反转和缓存到数组中,然后代码生成会创建一个包装该数组的 span。不幸的是,尽管这个 API 在 .NET 7 中发布,但编译器对它的支持并没有发布,而且因为没有人实际使用它,所以在工具链中存在各种问题,这些问题都没有被注意到。

值得庆幸的是,所有这些问题现在在 .NET 8 和 C# 编译器中都得到了解决(并且也回溯到了 .NET 7)。dotnet/roslyn#61414 为 C# 编译器添加了对 short、ushort、char、int、uint、long、ulong、double、float 以及基于这些的枚举的支持。在目标框架中,如果 CreateSpan 可用(.NET 7+),编译器生成使用它的代码。在函数不可用的框架上,编译器回退到发出静态只读数组以缓存数据,并围绕它包装一个 span。这对于构建多目标框架的库来说是一个重要的考虑因素,这样在向“下层”构建时,实现不会因为依赖这个优化而从 proverbial 性能悬崖上掉下来(这个优化有点奇怪,因为你实际上需要以一种方式编写你的代码,没有优化,性能会比你原本应该得到的更差)。有了编译器实现,以及对 Mono 运行时的修复 dotnet/runtime#82093 和 dotnet/runtime#81695,以及对修剪器的修复(需要保留编译器发出的数据的对齐) dotnet/cecil#60,运行时的其余部分就能够使用这个特性,它在 dotnet/runtime#79461 中这样做了。所以现在,例如,System.Text.Json 可以使用这个来存储一个(非闰年)年有多少天,但也可以存储在给定月份之前有多少天,这是之前由于存在大于字节可以存储的值而无法以这种形式有效地实现的。

// dotnet run -c Release -f net8.0 --filter **

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD", "i")]
[MemoryDiagnoser(displayGenColumns: false)]
[DisassemblyDiagnoser]
public class Tests
{
    private static ReadOnlySpan<int> DaysToMonth365 => new int[] { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 };

    [Benchmark]
    [Arguments(1)]
    public int DaysToMonth(int i) => DaysToMonth365[i];
}
方法 平均值 代码大小 分配
DaysToMonth 0.0469 ns 35 B
; Tests.DaysToMonth(Int32)
       sub       rsp,28
       cmp       edx,0D
       jae       short M00_L00
       mov       eax,edx
       mov       rcx,12B39072DD0
       mov       eax,[rcx+rax*4]
       add       rsp,28
       ret
M00_L00:
       call      CORINFO_HELP_RNGCHKFAIL
       int       3
; Total bytes of code 35

dotnet/roslyn#69820(尚未合并,但应该很快就会)通过确保初始化 ReadOnlySpan 到新的 T[] { const of T, const of T, ... /* all const values */ } 的模式将始终避免数组分配,无论使用的 T 的类型如何。T 只需要能够在 C# 中表示为常量。这意味着这个优化现在也适用于 string,decimal,nint 和 nuint。对于这些,编译器将回退到使用缓存的数组单例。有了这个,这段代码:

// dotnet build -c Release -f net8.0

internal static class Program
{
    private static void Main() { }

    private static ReadOnlySpan<bool> Booleans => new bool[] { false, true };
    private static ReadOnlySpan<sbyte> SBytes => new sbyte[] { 0, 1, 2 };
    private static ReadOnlySpan<byte> Bytes => new byte[] { 0, 1, 2 };

    private static ReadOnlySpan<short> Shorts => new short[] { 0, 1, 2 };
    private static ReadOnlySpan<ushort> UShorts => new ushort[] { 0, 1, 2 };
    private static ReadOnlySpan<char> Chars => new char[] { '0', '1', '2' };
    private static ReadOnlySpan<int> Ints => new int[] { 0, 1, 2 };
    private static ReadOnlySpan<uint> UInts => new uint[] { 0, 1, 2 };
    private static ReadOnlySpan<long> Longs => new long[] { 0, 1, 2 };
    private static ReadOnlySpan<ulong> ULongs => new ulong[] { 0, 1, 2 };
    private static ReadOnlySpan<float> Floats => new float[] { 0, 1, 2 };
    private static ReadOnlySpan<double> Doubles => new double[] { 0, 1, 2 };

    private static ReadOnlySpan<nint> NInts => new nint[] { 0, 1, 2 };
    private static ReadOnlySpan<nuint> NUInts => new nuint[] { 0, 1, 2 };
    private static ReadOnlySpan<decimal> Decimals => new decimal[] { 0, 1, 2 };
    private static ReadOnlySpan<string> Strings => new string[] { "0", "1", "2" };
}

现在编译成类似这样的代码(再次强调,这是伪代码,因为我们无法用 C# 精确表示 IL 中发出的内容):

internal static class Program
{
    private static void Main() { }

    //
    // No endianness concerns. Create a span that points directly into the assembly data,
    // using the `ReadOnlySpan<T>(void*, int)` constructor.
    //

    private static ReadOnlySpan<bool> Booleans => new ReadOnlySpan<bool>(
        &<PrivateImplementationDetails>.B413F47D13EE2FE6C845B2EE141AF81DE858DF4EC549A58B7970BB96645BC8D2, 2);

    private static ReadOnlySpan<sbyte> SBytes => new ReadOnlySpan<sbyte>(
        &<PrivateImplementationDetails>.AE4B3280E56E2FAF83F414A6E3DABE9D5FBE18976544C05FED121ACCB85B53FC, 3);

    private static ReadOnlySpan<byte> Bytes => new ReadOnlySpan<byte>(
        &<PrivateImplementationDetails>.AE4B3280E56E2FAF83F414A6E3DABE9D5FBE18976544C05FED121ACCB85B53FC, 3);

    //
    // Endianness concerns but with data that a span could point to directly if
    // of the correct byte ordering. Go through the RuntimeHelpers.CreateSpan intrinsic.
    //

    private static ReadOnlySpan<short> Shorts => RuntimeHelpers.CreateSpan<short>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.90C2698921CA9FD02950BE353F721888760E33AB5095A21E50F1E4360B6DE1A02);

    private static ReadOnlySpan<ushort> UShorts => RuntimeHelpers.CreateSpan<ushort>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.90C2698921CA9FD02950BE353F721888760E33AB5095A21E50F1E4360B6DE1A02);

    private static ReadOnlySpan<char> Chars => RuntimeHelpers.CreateSpan<char>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.9B9A3CBF2B718A8F94CE348CB95246738A3A9871C6236F4DA0A7CC126F03A8B42);

    private static ReadOnlySpan<int> Ints => RuntimeHelpers.CreateSpan<int>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.AD5DC1478DE06A4C2728EA528BD9361A4B945E92A414BF4D180CEDAAEAA5F4CC4);

    private static ReadOnlySpan<uint> UInts => RuntimeHelpers.CreateSpan<uint>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.AD5DC1478DE06A4C2728EA528BD9361A4B945E92A414BF4D180CEDAAEAA5F4CC4);

    private static ReadOnlySpan<long> Longs => RuntimeHelpers.CreateSpan<long>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.AB25350E3E65EFEBE24584461683ECDA68725576E825E550038B90E7B14799468);

    private static ReadOnlySpan<ulong> ULongs => RuntimeHelpers.CreateSpan<ulong>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.AB25350E3E65EFEBE24584461683ECDA68725576E825E550038B90E7B14799468);

    private static ReadOnlySpan<float> Floats => RuntimeHelpers.CreateSpan<float>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.75664B4DA1C08DE9E8FAD52303CC458B3E420EDDE6591E58761E138CC5E3F1634);

    private static ReadOnlySpan<double> Doubles => RuntimeHelpers.CreateSpan<double>((RuntimeFieldHandle)
        &<PrivateImplementationDetails>.B0C45303F7F11848CB5E6E5B2AF2FB2AECD0B72C28748B88B583AB6BB76DF1748);

    //
    // Create a span around a cached array.
    //

    private unsafe static ReadOnlySpan<nuint> NUInts => new ReadOnlySpan<nuint>(
        <PrivateImplementationDetails>.AD5DC1478DE06A4C2728EA528BD9361A4B945E92A414BF4D180CEDAAEAA5F4CC_B16
            ??= new nuint[] { 0, 1, 2 });

    private static ReadOnlySpan<nint> NInts => new ReadOnlySpan<nint>(
        <PrivateImplementationDetails>.AD5DC1478DE06A4C2728EA528BD9361A4B945E92A414BF4D180CEDAAEAA5F4CC_B8
            ??= new nint[] { 0, 1, 2 });

    private static ReadOnlySpan<decimal> Decimals => new ReadOnlySpan<decimal>(
        <PrivateImplementationDetails>.93AF9093EDC211A9A941BDE5EF5640FD395604257F3D945F93C11BA9E918CC74_B18
            ??= new decimal[] { 0, 1, 2 });

    private static ReadOnlySpan<string> Strings => new ReadOnlySpan<string>(
        <PrivateImplementationDetails>.9B9A3CBF2B718A8F94CE348CB95246738A3A9871C6236F4DA0A7CC126F03A8B4_B11
            ??= new string[] { "0", "1", "2" });
}

另一个与 C# 编译器密切相关的改进来自 @alrz 的 dotnet/runtime#66251。前面提到的关于单字节类型的优化也适用于 stackalloc 初始化。如果我写:

Span<int> span = stackalloc int[] { 1, 2, 3 };

C# 编译器发出的代码类似于我写的以下内容:

byte* ptr = stackalloc byte[12];
*(int*)ptr = 1;
*(int*)(ptr) = 2;
*(int*)(ptr + (nint)2 * (nint)4) = 3;
Span<int> span = new Span<int>(ptr);

然而,如果我从多字节的 int 切换到单字节的 byte:

Span<byte> span = stackalloc byte[] { 1, 2, 3 };

那么我得到的内容更接近这样:

byte* ptr = stackalloc byte[3];
Unsafe.CopyBlock(ptr, ref <PrivateImplementationDetails>.039058C6F2C0CB492C533B0A4D14EF77CC0F78ABCCCED5287D84A1A2011CFB81, 3); // 实际上是 cpblk 指令
Span<byte> span = new Span<byte>(ptr, 3);

然而,与 new[] 情况不同,后者不仅优化了 byte、sbyte 和 bool,还优化了以 byte 和 sbyte 为基础类型的枚举,而 stackalloc 优化并没有。多亏了这个 PR,现在它也可以了。

C# 12 和 .NET 8 中有一个半相关的新特性:InlineArrayAttribute。stackalloc 一直提供了一种使用栈空间作为缓冲区的方法,而不需要在堆上分配内存;然而,在 .NET 的大部分历史中,这是“不安全的”,因为它产生了一个指针:

byte* buffer = stackalloc byte[8];

C# 7.2 引入了一个极其有用的改进,可以直接在栈上分配到一个 span,此时它变成了“安全的”,不需要在不安全的上下文中,并且像对任何其他 span 一样,对 span 的所有访问都会适当地进行边界检查:

Span<byte> buffer = stackalloc byte[8];

C# 编译器会将其降低到类似以下的内容:

Span<byte> buffer;
unsafe
{
    byte* tmp = stackalloc byte[8];
    buffer = new Span<byte>(tmp, 8);
}

然而,这仍然限制了可以被 stackalloc 的东西,即不包含任何托管引用的非托管类型,而且它的使用也受到限制。这不仅是因为 stackalloc 不能在 catch 和 finally 块等地方使用,而且还因为你希望能够在其他类型内部拥有这样的缓冲区,而不仅仅限于栈:C# 一直支持“固定大小缓冲区”的概念,例如:

struct C
{
    internal unsafe fixed char name[30];
}

但这些需要在不安全的上下文中,因为它们向消费者展示为一个指针(在上述示例中,C.name 的类型是 char*),并且它们不进行边界检查,而且它们支持的元素类型有限(只能是 bool、sbyte、byte、short、ushort、char、int、uint、long、ulong、double 或 float)。

.NET 8 和 C# 12 为此提供了一个答案:[InlineArray]。这个新的属性可以放在包含单个字段的结构体上,如下所示:

[InlineArray(8)]
internal struct EightStrings
{
    private string _field;
}

然后,运行时将该结构体扩展为逻辑上等同于你写的:

internal struct EightStrings
{
    private string _field0;
    private string _field1;
    private string _field2;
    private string _field3;
    private string _field4;
    private string _field5;
    private string _field6;
    private string _field7;
}

确保所有的存储都适当地连续和对齐。为什么这很重要?因为 C# 12 然后使得从这些实例中获取一个 span 变得容易,例如:

EightStrings strings = default;
Span<string> span = strings;

这都是“安全的”,并且字段的类型可以是任何有效的泛型类型参数。这意味着几乎可以是除了 refs、ref 结构体和指针之外的任何东西。这是 C# 语言强加的一个约束,因为如果字段类型是 T,你将无法构造一个 Span,但是可以抑制警告,因为运行时本身确实支持任何字段类型。获取 span 的编译器生成的代码等同于你写的:

EightStrings strings = default;
Span<string> span = MemoryMarshal.CreateSpan(ref Unsafe.As<EightStrings, string>(ref strings), 8);

这显然很复杂,不是你经常想要写的东西。实际上,编译器也不想经常发出这样的代码,所以它将其放入程序集中的一个助手中,以便重用。

[CompilerGenerated]
internal sealed class <PrivateImplementationDetails>
{
    internal static Span<TElement> InlineArrayAsSpan<TBuffer, TElement>(ref TBuffer buffer, int length) =>
        MemoryMarshal.CreateSpan(ref Unsafe.As<TBuffer, TElement>(ref buffer), length);
    ...
}

是 C# 编译器发出的一个类,用于包含由它在程序的其他地方发出的代码使用的助手和其他编译器生成的工件。你在前面的讨论中也看到了它,因为它是它发出支持从常量初始化数组和 span 的数据的地方。)

带有 [InlineArray] 属性的类型也是一个普通的结构体,可以在任何其他结构体可以使用的地方使用;它使用 [InlineArray] 实际上是一个实现细节。所以,例如,你可以将它嵌入到另一个类型中,以下代码将按你期望的方式打印出 "0" 到 "7":

// dotnet run -c Release -f net8.0

using System.Runtime.CompilerServices;

MyData data = new();
Span<string> span = data.Strings;

for (int i = 0; i < span.Length; i++) span[i] = i.ToString();

foreach (string s in data.Strings) Console.WriteLine(s);

public class MyData
{
    private EightStrings _strings;

    public Span<string> Strings => _strings;

    [InlineArray(8)]
    private unsafe struct EightStrings { private string _field; }
}

dotnet/runtime#82744 为 CoreCLR 运行时提供了 InlineArray 的支持,dotnet/runtime#83776 和 dotnet/runtime#84097 为 Mono 运行时提供了支持,dotnet/roslyn#68783 合并了 C# 编译器的支持。

这个特性并不仅仅是关于你直接使用它。编译器本身也使用 [InlineArray] 作为其他新的和计划中的特性的实现细节...我们在讨论集合时会更多地讨论这个问题。

Analyzers

最后,尽管运行时和核心库在提高现有功能的性能和添加新的性能相关支持方面取得了长足的进步,但有时最好的修复实际上是在消费代码中。这就是分析器的作用。在 .NET 8 中添加了几个新的分析器,以帮助找到特定类别的字符串相关性能问题。

CA1858,由 @Youssef1313 在 dotnet/roslyn-analyzers#6295 中添加,寻找对 IndexOf 的调用,其中结果然后被检查是否等于 0。这在功能上与调用 StartsWith 相同,但是它的代价要高得多,因为它可能最终会检查整个源字符串,而不仅仅是开始位置(dotnet/runtime#79896 在 dotnet/runtime 中修复了一些这样的用法)。CA1858

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly string _haystack = """
        It was the best of times, it was the worst of times,
        it was the age of wisdom, it was the age of foolishness,
        it was the epoch of belief, it was the epoch of incredulity,
        it was the season of light, it was the season of darkness,
        it was the spring of hope, it was the winter of despair.
        """;
    private readonly string _needle = "hello";

    [Benchmark(Baseline = true)]
    public bool StartsWith_IndexOf0() =>
        _haystack.IndexOf(_needle, StringComparison.OrdinalIgnoreCase) == 0;

    [Benchmark]
    public bool StartsWith_StartsWith() =>
        _haystack.StartsWith(_needle, StringComparison.OrdinalIgnoreCase);
}
方法 平均值 比率
StartsWith_IndexOf0 31.327 ns 1.00
StartsWith_StartsWith 4.501 ns 0.14

CA1865、CA1866 和 CA1867 都是相互关联的。这些都是在 dotnet/roslyn-analyzers#6799 中由 @mrahhal 添加的,用于寻找对字符串方法(如 StartsWith)的调用,搜索传入单字符字符串参数的调用,例如 str.StartsWith("@"),并建议将参数转换为字符。分析器引发的诊断 ID 取决于转换是否100%等效,或者是否可能导致行为改变,例如,从语言比较切换到序数比较。CA1865

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private readonly string _haystack = "All we have to decide is what to do with the time that is given us.";

    [Benchmark(Baseline = true)]
    public int IndexOfString() => _haystack.IndexOf("v");

    [Benchmark]
    public int IndexOfChar() => _haystack.IndexOf('v');
}
方法 平均值 比率
IndexOfString 37.634 ns 1.00
IndexOfChar 1.979 ns 0.05

CA1862,添加在 dotnet/roslyn-analyzers#6662 中,寻找代码中执行不区分大小写的比较的地方(这是可以的),但是通过首先将输入字符串转换为小写/大写,然后进行比较(这远非理想)。直接使用 StringComparison 要有效得多。dotnet/runtime#89539 修复了一些这样的情况。CA1862

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[MemoryDiagnoser(displayGenColumns: false)]
public class Tests
{
    private readonly string _input = "https://dot.net";

    [Benchmark(Baseline = true)]
    public bool IsHttps_ToUpper() => _input.ToUpperInvariant().StartsWith("HTTPS://");

    [Benchmark]
    public bool IsHttps_StringComparison() => _input.StartsWith("HTTPS://", StringComparison.OrdinalIgnoreCase);
}
方法 平均值 比率 分配 分配比率
IsHttps_ToUpper 46.3702 ns 1.00 56 B 1.00
IsHttps_StringComparison 0.4781 ns 0.01 - 0.00

而 CA1861,由 @steveberdy 在 dotnet/roslyn-analyzers#5383 中添加,寻找提升和缓存作为参数传递的数组的机会。dotnet/runtime#86229 解决了在 dotnet/runtime 中由分析器发现的问题。CA1861

// dotnet run -c Release -f net8.0 --filter "*"

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[MemoryDiagnoser(displayGenColumns: false)]
public class Tests
{
    private static readonly char[] s_separator = new[] { ',', ':' };
    private readonly string _value = "1,2,3:4,5,6";

    [Benchmark(Baseline = true)]
    public string[] Split_Original() => _value.Split(new[] { ',', ':' });

    [Benchmark]
    public string[] Split_Refactored() => _value.Split(s_separator);
}
方法 平均值 比率 分配 分配比率
Split_Original 108.6 ns 1.00 248 B 1.00
Split_Refactored 104.0 ns 0.96 216 B 0.87

.Net 7

Arrays, Strings, and Spans

在应用程序中,可以消耗资源的计算形式有很多,其中最常见的包括处理存储在数组、字符串和现在的跨度中的数据。因此,你会看到每个 .NET 发布版都专注于从这些场景中移除尽可能多的开销,同时也寻找进一步优化开发人员常用操作的方法。

让我们从一些新的 API 开始,这些 API 可以帮助更容易地编写更高效的代码。当检查字符串解析/处理代码时,常常会看到字符被检查是否包含在各种集合中。例如,你可能会看到一个循环寻找 ASCII 数字字符:

while (i < str.Length)
{
    if (str[i] >= '0' && str[i] <= '9')
    {
        break;
    }
    i++;
}

或者是 ASCII 字母字符:

while (i < str.Length)
{
    if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
    {
        break;
    }
    i++;
}

或者其他类似的组。有趣的是,这样的检查代码有广泛的变化,通常取决于开发人员为优化它们付出了多少努力,或者在某些情况下可能甚至没有意识到一些性能被忽视了。例如,同样的 ASCII 字母检查可以被写成:

while (i < str.Length)
{
    if ((uint)((c | 0x20) - 'a') <= 'z' - 'a')
    {
        break;
    }
    i++;
}

虽然这更“激进”,但也更简洁,更有效。它利用了一些技巧。首先,它不是通过两次比较来确定字符是否大于或等于下界并且小于或等于上界,而是基于字符和下界之间的距离进行单次比较 ((uint)(c - 'a'))。如果 'c' 超过 'z',那么 'c' - 'a' 将大于25,比较将失败。如果 'c' 早于 'a',那么 'c' - 'a' 将为负,将其转换为 uint 将导致它环绕到一个巨大的数字,也大于25,再次导致比较失败。因此,我们能够通过额外的一次减法来避免整个额外的比较和分支,这几乎总是一个好交易。第二个技巧是 | 0x20。ASCII 表有一些深思熟虑的关系,包括大写 'A' 和小写 'a' 只相差一个位 ('A' 是 0b1000001 和 'a' 是 0b1100001)。要从任何小写 ASCII 字母转换为其大写 ASCII 等价物,我们只需要 & ~0x20(关闭该位),要从任何大写 ASCII 字母转换为其小写 ASCII 等价物,我们只需要 | 0x20(打开该位)。我们可以在我们的范围检查中利用这一点,通过将我们的字符 c 规范化为小写,以便以一点位扭曲的低成本,我们可以实现小写和大写的范围检查。当然,我们不希望每个开发者都必须知道并在每次使用时编写这些技巧。相反,.NET 7 在 System.Char 上公开了一堆新的帮助器,以封装这些常见的检查,以有效的方式完成。char 已经有了像 IsDigit 和 IsLetter 这样的方法,它们提供了这些名称的更全面的 Unicode 含义(例如,有大约320个 Unicode 字符被分类为“数字”)。现在在 .NET 7 中,也有这些帮助器:

IsAsciiDigit
IsAsciiHexDigit
IsAsciiHexDigitLower
IsAsciiHexDigitUpper
IsAsciiLetter
IsAsciiLetterLower
IsAsciiLetterUpper
IsAsciiLetterOrDigit

这些方法由 dotnet/runtime#69318 添加,该方法还在 dotnet/runtime 中的许多位置使用它们,这些位置正在执行此类检查(其中许多使用的方法效率较低)。

另一个专注于封装常见模式的新 API 是新的 MemoryExtensions.CommonPrefixLength 方法,由 dotnet/runtime#67929 引入。这个方法接受两个 ReadOnlySpan 实例或一个 Span 和一个 ReadOnlySpan,以及一个可选的 IEqualityComparer,并返回在每个输入跨度开始处相同的元素数量。当你想知道两个输入的第一个不同点时,这个方法非常有用。dotnet/runtime#68210 由 @gfoidl 提供,然后利用新的 Vector128 功能提供了实现的基本向量化。由于它正在比较两个序列并寻找它们的第一个不同点,这个实现使用了一个巧妙的技巧,即有一个单独的方法实现来比较序列作为字节。如果正在比较的 T 是位等价的,并且没有提供自定义的等价比较器,那么它将重新解释跨度的引用作为字节引用,并使用单个共享的实现。

另一组新的 API 是 IndexOfAnyExcept 和 LastIndexOfAnyExcept 方法,由 dotnet/runtime#67941 引入,并在 dotnet/runtime#71146 和 dotnet/runtime#71278 的多个其他调用站点中使用。虽然这些方法有点复杂,但它们非常方便。它们做的就是它们的名字所暗示的:而 IndexOf(T value) 在输入中搜索 value 的第一个出现,而 IndexOfAny(T value0, T value1, ...) 在输入中搜索 value0, value1 等的第一个出现,IndexOfAnyExcept(T value) 搜索的是第一个不等于 value 的出现,同样,IndexOfAnyExcept(T value0, T value1, ...) 搜索的是第一个不等于 value0, value1 等的出现。例如,假设你想知道一个整数数组是否完全为 0。你现在可以这样写:

bool allZero = array.AsSpan().IndexOfAnyExcept(0) < 0;

dotnet/runtime#73488 也向量化了这个重载。

private byte[] _zeros = new byte[1024];

[Benchmark(Baseline = true)]
public bool OpenCoded()
{
    foreach (byte b in _zeros)
    {
        if (b != 0)
        {
            return false;
        }
    }

    return true;
}

[Benchmark]
public bool IndexOfAnyExcept() => _zeros.AsSpan().IndexOfAnyExcept((byte)0) < 0;
方法 平均值 比率
OpenCoded 370.47 ns 1.00
IndexOfAnyExcept 23.84 ns 0.06

当然,虽然新的“索引”变体很有帮助,但我们已经有了一堆这样的方法,重要的是它们要尽可能高效。这些核心的 IndexOf{Any} 方法在大量的地方被使用,其中许多地方对性能敏感,所以每个版本都会得到额外的关怀。虽然像 dotnet/runtime#67811 这样的 PR 通过非常仔细地关注生成的汇编代码(在这种情况下,调整了 Arm64 上 IndexOf 和 IndexOfAny 中使用的一些检查,以实现更好的利用率)来获得收益,但最大的改进来自于添加了向量化而之前没有使用,或者重做了向量化方案以获得显著的收益的地方。让我们从 dotnet/runtime#63285 开始,这为字节和字符的“子字符串”的 IndexOf 和 LastIndexOf 的许多使用带来了巨大的改进。以前,给定一个像 str.IndexOf("hello") 这样的调用,实现基本上会做的相当于反复搜索 'h',当找到一个 'h' 时,然后执行一个 SequenceEqual 来匹配剩余的部分。然而,你可以想象,很容易遇到第一个字符被搜索的情况非常常见,以至于你经常需要跳出向量化循环,以便进行完整的字符串比较。相反,PR 实现了一个基于 SIMD 友好的算法进行子字符串搜索的算法。它不仅仅是搜索第一个字符,而是可以向量化搜索第一个和最后一个字符,它们之间的距离适当。在我们的“hello”例子中,在任何给定的输入中,找到一个 'h' 的可能性比找到一个 'h' 后面四个字符后的 'o' 的可能性要大得多,因此这个实现能够在向量化循环中停留更长的时间,产生更少的假阳性,迫使它走 SequenceEqual 的路线。实现还处理了两个字符选择相等的情况,在这种情况下,它会快速寻找另一个不等的字符,以最大化搜索的效率。我们可以通过一些例子看到所有这些的影响:


private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

[Benchmark]
[Arguments("Sherlock")]
[Arguments("elementary")]
public int Count(string needle)
{
    ReadOnlySpan<char> haystack = s_haystack;
    int count = 0, pos;
    while ((pos = haystack.IndexOf(needle)) >= 0)
    {
        haystack = haystack.Slice(pos + needle.Length);
        count++;
    }

    return count;
}

这是从Project Gutenberg下载《福尔摩斯探案集》的文本,然后使用IndexOf来计算文本中“Sherlock”和“elementary”出现的次数。在我的机器上,我得到了这样的结果:

方法 运行时 平均值 比率
Count .NET 6.0 Sherlock 43.68 us 1.00
Count .NET 7.0 Sherlock 48.33 us 1.11
Count .NET 6.0 elementary 1,063.67 us 1.00
Count .NET 7.0 elementary 56.04 us 0.05

对于“Sherlock”,.NET 7的性能实际上比.NET 6稍差一点;不多,但可测量的10%。这是因为在源文本中大写'S'字符非常少,确切地说是841个,文档中的字符总数为593,836个。在只有0.1%的起始字符密度的情况下,新算法并没有带来太多的好处,因为现有的只搜索第一个字符的算法基本上捕获了所有可能的向量化收益,我们确实在搜索'S'和'k'时付出了一些开销,而以前我们只搜索'S'。相比之下,文档中有54,614个'e'字符,所以源的近10%。在这种情况下,.NET 7比.NET 6快20倍,用.NET 7计算所有'e'需要53微秒,而.NET 6需要1084微秒。在这种情况下,新方案带来了巨大的收益,通过向量化搜索'e'和特定距离的'y',这种组合的频率要少得多。这是那些总体上观察到的平均收益巨大,尽管我们可以看到一些特定输入的小回归的情况。

另一个显著改变使用算法的例子是dotnet/runtime#67758,它使一些向量化可以应用于IndexOf("...", StringComparison.OrdinalIgnoreCase)。以前,这个操作是用一个相当典型的子字符串搜索实现的,遍历输入字符串,在每个位置做一个内循环来比较目标字符串,除了对每个字符进行ToUpper以便以不区分大小写的方式进行。现在有了这个PR,它基于之前由Regex使用的方法,如果目标字符串以ASCII字符开始,实现可以使用IndexOf(如果字符不是ASCII字母)或IndexOfAny(如果字符是ASCII字母)来快速跳到可能匹配的第一个位置。让我们看看刚才看过的完全相同的基准测试,但是调整为使用OrdinalIgnoreCase:

private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;

[Benchmark]
[Arguments("Sherlock")]
[Arguments("elementary")]
public int Count(string needle)
{
    ReadOnlySpan<char> haystack = s_haystack;
    int count = 0, pos;
    while ((pos = haystack.IndexOf(needle, StringComparison.OrdinalIgnoreCase)) >= 0)
    {
        haystack = haystack.Slice(pos + needle.Length);
        count++;
    }

    return count;
}

在这里,两个单词在 .NET 7 上的速度比在 .NET 6 上快了大约4倍:

方法 运行时 平均值 比率
Count .NET 6.0 Sherlock 2,113.1 us 1.00
Count .NET 7.0 Sherlock 467.3 us 0.22
Count .NET 6.0 elementary 2,325.6 us 1.00
Count .NET 7.0 elementary 638.8 us 0.27

我们现在正在执行向量化的 IndexOfAny('S', 's') 或 IndexOfAny('E', 'e'),而不是手动遍历每个字符并进行比较。 (dotnet/runtime#73533 现在也使用相同的方法来处理 IndexOf(char, StringComparison.OrdinalIgnoreCase)。)

另一个例子来自 @gfoidl 的 dotnet/runtime#67492。它使用我们之前讨论过的方法更新了 MemoryExtensions.Contains,用于处理向量化操作结束时剩余的元素:处理最后一个向量的数据,即使这意味着重复已经完成的一些工作。这对于处理时间可能被那些剩余部分的串行处理所主导的较小输入特别有帮助。

private byte[] _data = new byte[95];

[Benchmark]
public bool Contains() => _data.AsSpan().Contains((byte)1);
方法 运行时 平均值 比率
Contains .NET 6.0 15.115 ns 1.00
Contains .NET 7.0 2.557 ns 0.17

@alexcovington 的 dotnet/runtime#60974 扩大了 IndexOf 的影响范围。在此 PR 之前,IndexOf 为一字节和两字节大小的基本类型进行了向量化,但此 PR 也将其扩展到四字节和八字节大小的基本类型。与大多数其他向量化实现一样,它检查 T 是否可以进行位等价,这对于向量化很重要,因为它只查看内存中的位,而不关注可能在类型上定义的任何 Equals 实现。在实践中,这意味着这仅限于运行时对其有深入了解的少数几种类型(Boolean,Byte,SByte,UInt16,Int16,Char,UInt32,Int32,UInt64,Int64,UIntPtr,IntPtr,Rune 和枚举),但理论上它可以在未来被扩展。

private int[] _data = new int[1000];

[Benchmark]
public int IndexOf() => _data.AsSpan().IndexOf(42);
方法 运行时 平均值 比率
IndexOf .NET 6.0 252.17 ns 1.00
IndexOf .NET 7.0 78.82 ns 0.31

最后一个有趣的与 IndexOf 相关的优化。字符串长期以来都有 IndexOf/IndexOfAny/LastIndexOf/LastIndexOfAny,显然对于字符串,这都是关于处理字符的。当 ReadOnlySpan 和 Span 出现时,MemoryExtensions 被添加以为 spans 和朋友提供扩展方法,包括这样的 IndexOf/IndexOfAny/LastIndexOf/LastIndexOfAny 方法。但对于 spans,这不仅仅是关于 char,因此 MemoryExtensions 增长了其大部分与字符串分开的实现集。多年来,MemoryExtensions 的实现已经专门化了越来越多的类型,但特别是 byte 和 char,因此随着时间的推移,字符串的实现大部分已被替换为委托到 MemoryExtensions 使用的相同实现。然而,IndexOfAny 和 LastIndexOfAny 一直是统一的阻力,每个都有自己的方向。string.IndexOfAny 确实委托给了与 MemoryExtensions.IndexOfAny 相同的实现,用于搜索1-5个值,但对于超过5个值,string.IndexOfAny 使用了一个“概率映射”,基本上是一个布隆过滤器。它创建一个256位表,并根据要搜索的值快速设置该表中的位(基本上是对它们进行哈希,但使用了一个简单的哈希函数)。然后它遍历输入,而不是将每个输入字符与每个目标值进行比较,而是首先在表中查找输入字符。如果相应的位没有设置,它知道输入字符与任何目标值都不匹配。如果设置了相应的位,那么它将继续将输入字符与每个目标值进行比较,有很高的可能性是其中之一。MemoryExtensions.IndexOfAny 对于超过5个值缺少这样的过滤器。相反,string.LastIndexOfAny 没有为多个目标值提供任何向量化,而 MemoryExtensions.LastIndexOfAny 向量化了两个和三个目标值。从 dotnet/runtime#63817 开始,所有这些现在都已统一,这样字符串和 MemoryExtensions 都可以得到对方的最好部分。

private readonly char[] s_target = new[] { 'z', 'q' };
const string Sonnet = """
    Shall I compare thee to a summer's day?
    Thou art more lovely and more temperate:
    Rough winds do shake the darling buds of May,
    And summer's lease hath all too short a date;
    Sometime too hot the eye of heaven shines,
    And often is his gold complexion dimm'd;
    And every fair from fair sometime declines,
    By chance or nature's changing course untrimm'd;
    But thy eternal summer shall not fade,
    Nor lose possession of that fair thou ow'st;
    Nor shall death brag thou wander'st in his shade,
    When in eternal lines to time thou grow'st:
    So long as men can breathe or eyes can see,
    So long lives this, and this gives life to thee.
    """;

[Benchmark]
public int LastIndexOfAny() => Sonnet.LastIndexOfAny(s_target);

[Benchmark]
public int CountLines()
{
    int count = 0;
    foreach (ReadOnlySpan<char> _ in Sonnet.AsSpan().EnumerateLines())
    {
        count++;
    }

    return count;
}
方法 运行时 平均值 比率
LastIndexOfAny .NET 6.0 443.29 ns 1.00
LastIndexOfAny .NET 7.0 31.79 ns 0.07
CountLines .NET 6.0 1,689.66 ns 1.00
CountLines .NET 7.0 1,461.64 ns 0.86

该 PR 还清理了使用 IndexOf 系列的用法,特别是在检查包含而不是实际结果的索引的用法。IndexOf 系列的方法在找到元素时返回非负值,否则返回 -1。这意味着在检查是否找到元素时,代码可以使用 >= 0 或 != -1,当检查元素是否未找到时,代码可以使用 < 0 或 == -1。事实证明,与 -1 生成的比较相比,对 0 生成的代码的效率略高,而这不是 JIT 可以自己替换的,除非 IndexOf 方法是内置的,这样 JIT 可以理解返回值的语义。因此,为了保持一致性和小的性能提升,所有相关的调用站点都被切换为与 0 比较,而不是与 -1 比较。

说到调用站点,拥有高度优化的 IndexOf 方法的一大好处是可以在所有可以受益的地方使用它们,消除了开放编码替换的维护影响,同时也获得了性能提升。dotnet/runtime#63913 在 StringBuilder.Replace 内部使用了 IndexOf,以加速对下一个要替换的字符的搜索:

private StringBuilder _builder = new StringBuilder(Sonnet);

[Benchmark]
public void Replace()
{
    _builder.Replace('?', '!');
    _builder.Replace('!', '?');
}
方法 运行时 平均值 比率
Replace .NET 6.0 1,563.69 ns 1.00
Replace .NET 7.0 70.84 ns 0.04

dotnet/runtime#60463 来自 @nietras 在 StringReader.ReadLine 中使用了 IndexOfAny 来搜索 '\r' 和 '\n' 行结束字符,即使在分配和方法设计固有的情况下,也可以获得一些实质性的吞吐量增益:

[Benchmark]
public void ReadAllLines()
{
    var reader = new StringReader(Sonnet);
    while (reader.ReadLine() != null) ;
}
方法 运行时 平均值 比率
ReadAllLines .NET 6.0 947.8 ns 1.00
ReadAllLines .NET 7.0 385.7 ns 0.41

dotnet/runtime#70176 清理了大量其他用法。

最后在 IndexOf 方面,正如所述,多年来我们在优化这些方法上投入了大量的时间和精力。在以前的版本中,一部分精力是直接使用硬件内置函数,例如,有一个 SSE2 代码路径,一个 AVX2 代码路径和一个 AdvSimd 代码路径。现在我们有了 Vector128 和 Vector256,许多这样的用法可以被简化(例如,避免在 SSE2 实现和 AdvSimd 实现之间的重复),同时仍然保持良好甚至更好的性能,同时自动支持在其他具有自己内置函数的平台上的向量化,如 WebAssembly。dotnet/runtime#73481, dotnet/runtime#73556, dotnet/runtime#73368, dotnet/runtime#73364, dotnet/runtime#73064, 和 dotnet/runtime#73469 都在这里做出了贡献,在某些情况下带来了有意义的吞吐量增益:

[Benchmark]
public int IndexOfAny() => Sonnet.AsSpan().IndexOfAny("!.<>");
方法 运行时 平均值 比率
IndexOfAny .NET 6.0 52.29 ns 1.00
IndexOfAny .NET 7.0 40.17 ns 0.77

IndexOf 系列只是 string/MemoryExtensions 上许多得到显著改进的方法之一。另一个是 SequenceEquals 系列,包括 Equals, StartsWith, 和 EndsWith。我在整个版本中最喜欢的改变之一是 dotnet/runtime#65288,它正好在这个领域。调用 StartsWith 这样的方法并使用常量字符串参数是非常常见的,例如 value.StartsWith("https://"), value.SequenceEquals("Key") 等。这些方法现在被 JIT 识别,JIT 现在可以自动展开比较并一次比较多个字符,例如,一次读取四个字符作为一个长整数,并对该长整数与这四个字符的预期组合进行一次比较。结果是美妙的。使其更好的是 dotnet/runtime#66095,它为 OrdinalIgnoreCase 添加了这种支持。还记得那些稍早前讨论的与 char.IsAsciiLetter 和朋友们有关的 ASCII 位操作技巧吗?JIT 现在采用了同样的技巧作为这种展开的一部分,所以如果你做同样的 value.StartsWith("https://") 但是作为 value.StartsWith("https://", StringComparison.OrdinalIgnoreCase),它会识别到整个比较字符串是 ASCII,并且会在比较常量和从输入中读取的数据上 OR 入适当的掩码,以便以不区分大小写的方式进行比较。

private string _value = "https://dot.net";

[Benchmark]
public bool IsHttps_Ordinal() => _value.StartsWith("https://", StringComparison.Ordinal);

[Benchmark]
public bool IsHttps_OrdinalIgnoreCase() => _value.StartsWith("https://", StringComparison.OrdinalIgnoreCase);

方法 运行时 平均值 比率
IsHttps_Ordinal .NET 6.0 4.5634 ns 1.00
IsHttps_Ordinal .NET 7.0 0.4873 ns 0.11
IsHttps_OrdinalIgnoreCase .NET 6.0 6.5654 ns 1.00
IsHttps_OrdinalIgnoreCase .NET 7.0 0.5577 ns 0.08

有趣的是,自 .NET 5 以来,由 RegexOptions.Compiled 生成的代码在比较多个字符的序列时会执行类似的展开,当在 .NET 7 中添加了源生成器时,它也学会了如何做这个。然而,源生成器在这种优化上有问题,因为字节顺序问题。被比较的常量受到字节排序问题的影响,因此源生成器需要生成可以在小端或大端机器上运行的代码。JIT 没有这个问题,因为它在生成代码的机器上执行代码(在它被用来提前生成代码的场景中,整个代码已经绑定到特定的架构)。通过将这个优化移动到 JIT,可以从 RegexOptions.Compiled 和正则表达式源生成器中删除相应的代码,这样也可以从生成使用 StartsWith 的更易读的代码中获益,速度也一样快(dotnet/runtime#65222 和 dotnet/runtime#66339)。这是全面的胜利。(只有在 dotnet/runtime#68055 之后,才能从 RegexOptions.Compiled 中删除这个,该修复了 JIT 识别这些字符串字面量在 DynamicMethods 中的能力,RegexOptions.Compiled 使用反射发出来吐出正在编译的正则表达式的 IL。)

StartsWith 和 EndsWith 在其他方面也有所改进。dotnet/runtime#63734(由 dotnet/runtime#64530 进一步改进)添加了另一个非常有趣的基于 JIT 的优化,但要理解它,我们需要理解 string 的内部布局。string 在内存中基本上是表示为一个 int 长度,后面跟着那么多的 chars 加上一个 null 终止符 char。实际的 System.String 类在 C# 中将这个表示为一个 int _stringLength 字段,后面跟着一个 char _firstChar 字段,这样 _firstChar 确实与字符串的第一个字符对齐,或者如果字符串为空,则与 null 终止符对齐。在 System.Private.CoreLib 内部,特别是在 string 本身的方法中,代码通常会在需要查阅第一个字符时直接引用 _firstChar,因为这通常比使用 str[0] 更快,特别是因为没有边界检查涉及到,通常不需要查阅字符串的长度。现在,考虑一下 string 上的这样一个方法,比如 public bool StartsWith(char value)。在 .NET 6 中,实现是:

return Length != 0 && _firstChar == value;

根据我刚才的描述,这是有道理的:如果 Length 是 0,那么字符串就不会以指定的字符开始,如果 Length 不是 0,那么我们就可以直接将 value 与 _firstChar 进行比较。但是,为什么需要这个 Length 检查呢?我们不能只做 return _firstChar == value; 吗?这将避免额外的比较和分支,而且它将工作得很好……除非目标字符本身就是 '\0',在这种情况下,我们可能会在结果上得到假阳性。现在来看这个 PR。PR 引入了一个内部的 JIT intrinsinc RuntimeHelpers.IsKnownConstant,如果包含方法被内联,然后传递给 IsKnownConstant 的参数被看到是一个常量,那么 JIT 将用 true 替换它。在这种情况下,实现可以依赖其他 JIT 优化踢入并优化方法中的各种代码,有效地使开发者能够写出两种不同的实现,一种是当参数被知道是常量时,另一种是当不是时。有了这个,PR 能够优化 StartsWith 如下:

public bool StartsWith(char value)
{
    if (RuntimeHelpers.IsKnownConstant(value) && value != '\0')
        return _firstChar == value;

    return Length != 0 && _firstChar == value;
}

如果 value 参数不是一个常量,那么 IsKnownConstant 将被替换为 false,整个开始的 if 块将被消除,方法将被留下来就像之前一样。但是,如果这个方法被内联并且 value 实际上是一个常量,那么 value != '\0' 的条件也将在 JIT 编译时被评估。如果 value 实际上是 '\0',那么,再次,整个 if 块将被消除,我们并没有更糟。但在常见的情况下,value 不是 null,整个方法将最终被编译,就好像它是:

return _firstChar == ConstantValue;

我们为自己节省了读取字符串长度的时间,一个比较和一个分支。dotnet/runtime#69038 然后采用了类似的技术来处理 EndsWith。

private string _value = "https://dot.net";

[Benchmark]
public bool StartsWith() =>
    _value.StartsWith('a') ||
    _value.StartsWith('b') ||
    _value.StartsWith('c') ||
    _value.StartsWith('d') ||
    _value.StartsWith('e') ||
    _value.StartsWith('f') ||
    _value.StartsWith('g') ||
    _value.StartsWith('i') ||
    _value.StartsWith('j') ||
    _value.StartsWith('k') ||
    _value.StartsWith('l') ||
    _value.StartsWith('m') ||
    _value.StartsWith('n') ||
    _value.StartsWith('o') ||
    _value.StartsWith('p');
方法 运行时 平均值 比率
StartsWith .NET 6.0 8.130 ns 1.00
StartsWith .NET 7.0 1.653 ns 0.20

IsKnownConstant 的另一个使用示例来自 dotnet/runtime#64016,它用它来改进当指定 MidpointRounding 模式时的 Math.Round。对此的调用几乎总是明确地将枚举值指定为常量,这就允许 JIT 为方法专门生成特定模式的代码;这反过来,例如,使得在 Arm64 上的 Math.Round(..., MidpointRounding.AwayFromZero) 调用被降低为单个 frinta 指令。

EndsWith 在 dotnet/runtime#72750 中也得到了改进,特别是当指定 StringComparison.OrdinalIgnoreCase 时。这个简单的 PR 只是切换了用来实现这个方法的内部辅助方法,利用了一个对这个方法的需求足够且开销较低的方法。

[Benchmark]
[Arguments("System.Private.CoreLib.dll", ".DLL")]
public bool EndsWith(string haystack, string needle) =>
haystack.EndsWith(needle, StringComparison.OrdinalIgnoreCase);

方法 运行时 平均值 比率
EndsWith .NET 6.0 10.861 ns 1.00
EndsWith .NET 7.0 5.385 ns 0.50

最后,dotnet/runtime#67202 和 dotnet/runtime#73475 使用 Vector128 和 Vector256 替换了直接硬件内在使用,就像之前为各种 IndexOf 方法所示,但这里是为 SequenceEqual 和 SequenceCompareTo。

在 .NET 7 中受到一些关注的另一个方法是 MemoryExtensions.Reverse(以及 Array.Reverse,因为它共享相同的实现),它执行目标跨度的就地反转。dotnet/runtime#64412 来自 @alexcovington 提供了通过直接使用 AVX2 和 SSSE3 硬件内在的向量化实现,dotnet/runtime#72780 来自 @SwapnilGaikwad 跟进添加了一个 AdvSimd 内在实现用于 Arm64。(原始向量化更改引入了一个意外的回归,但那是由 dotnet/runtime#70650 修复的。)

private char[] text = "Free. Cross-platform. Open source.\r\nA developer platform for building all your apps.".ToCharArray();

[Benchmark]
public void Reverse() => Array.Reverse(text);
方法 运行时 平均值 比率
Reverse .NET 6.0 21.352 ns 1.00
Reverse .NET 7.0 9.536 ns 0.45

String.Split 也在 dotnet/runtime#64899 中看到了向量化的改进,这是由 @yesmey 提供的。就像之前讨论的一些 PR 一样,它将现有的 SSE2 和 SSSE3 硬件内在的使用切换到新的 Vector128 帮助器,这改进了现有的实现,同时也隐式地为 Arm64 添加了向量化支持。

许多应用程序和服务都需要转换各种格式的字符串,无论是从 UTF8 字节到字符串和反向转换,还是格式化和解析十六进制值。在 .NET 7 中,这些操作也以各种方式得到了改进。例如,Base64 编码是一种将任意二进制数据(想想 byte[])表示在只支持文本的媒介上的方式,将字节编码为 64 种不同的 ASCII 字符中的一种。.NET 中有多个 API 实现了这种编码。对于将以 ReadOnlySpan 表示的二进制数据和以 ReadOnlySpan 表示的 UTF8(实际上是 ASCII)编码数据之间进行转换,System.Buffers.Text.Base64 类型提供了 EncodeToUtf8 和 DecodeFromUtf8 方法。这些在几个版本前就已经向量化了,但在 .NET 7 中,它们通过 dotnet/runtime#70654 从 @a74nh 进一步改进,将基于 SSSE3 的实现转换为使用 Vector128(这反过来隐式地在 Arm64 上启用了向量化)。然而,对于将以 ReadOnlySpan/byte[] 表示的任意二进制数据和以 ReadOnlySpan/char[]/string 表示的数据之间进行转换,System.Convert 类型公开了多个方法,例如 Convert.ToBase64String,这些方法历史上并未向量化。这在 .NET 7 中发生了变化,其中 dotnet/runtime#71795 和 dotnet/runtime#73320 向量化了 ToBase64String、ToBase64CharArray 和 TryToBase64Chars 方法。他们这样做的方式很有趣。而不是有效地复制来自 Base64.EncodeToUtf8 的向量化实现,他们反而在 EncodeToUtf8 上层进行操作,调用它将输入字节数据编码到输出 Span。然后,他们将这些字节“扩宽”为字符(记住,Base64 编码数据是一组 ASCII 字符,所以从这些字节到字符只需要在每个元素上添加一个 0 字节)。这种扩宽本身可以很容易地以向量化的方式完成。这种层叠的另一个有趣之处是它实际上并不需要为编码的字节提供单独的中间存储。实现可以完美地计算将 X 字节编码为 Y Base64 字符的结果字符数(有一个公式),并且实现可以分配最终的空间(例如,在 ToBase64CharArray 的情况下)或确保提供的空间足够(例如,在 TryToBase64Chars 的情况下)。既然我们知道初始编码将需要恰好一半的字节数,我们就可以在同一空间内进行编码(目标 span 被重新解释为字节 span 而不是字符 span),然后“就地”扩宽:从字节的末尾和字符空间的末尾开始走,将字节复制到目标中。

private byte[] _data = Encoding.UTF8.GetBytes("""
    Shall I compare thee to a summer's day?
    Thou art more lovely and more temperate:
    Rough winds do shake the darling buds of May,
    And summer's lease hath all too short a date;
    Sometime too hot the eye of heaven shines,
    And often is his gold complexion dimm'd;
    And every fair from fair sometime declines,
    By chance or nature's changing course untrimm'd;
    But thy eternal summer shall not fade,
    Nor lose possession of that fair thou ow'st;
    Nor shall death brag thou wander'st in his shade,
    When in eternal lines to time thou grow'st:
    So long as men can breathe or eyes can see,
    So long lives this, and this gives life to thee.
    """);
private char[] _encoded = new char[1000];

[Benchmark]
public bool TryToBase64Chars() => Convert.TryToBase64Chars(_data, _encoded, out _);
方法 运行时 平均值 比率
TryToBase64Chars .NET 6.0 623.25 ns 1.00
TryToBase64Chars .NET 7.0 81.82 ns 0.13

就像可以使用扩宽从字节转换为字符一样,也可以使用缩小从字符转换为字节,特别是如果字符实际上是 ASCII,因此上字节为 0。这种缩小可以向量化,内部的 NarrowUtf16ToAscii 实用程序助手就是这样做的,作为 Encoding.ASCII.GetBytes 等方法的一部分。虽然此方法以前已经向量化,但其主要快速路径使用了 SSE2,因此不适用于 Arm64;感谢 @SwapnilGaikwad 的 dotnet/runtime#70080,该路径被改为基于跨平台的 Vector128,在支持的平台上实现了相同级别的优化。同样,@SwapnilGaikwad 的 dotnet/runtime#71637 为 Encoding.UTF8.GetByteCount 等方法使用的 GetIndexOfFirstNonAsciiChar 内部助手添加了 Arm64 向量化。(同样,dotnet/runtime#67192 将内部的 HexConverter.EncodeToUtf16 方法从使用 SSSE3 内在函数改为使用 Vector128,自动提供了 Arm64 实现。)

Encoding.UTF8 也有所改进。特别是,dotnet/runtime#69910 简化了 GetMaxByteCount 和 GetMaxCharCount 的实现,使它们足够小,常常在直接从 Encoding.UTF8 使用时内联,使 JIT 能够去虚拟化调用。

[Benchmark]
public int GetMaxByteCount() => Encoding.UTF8.GetMaxByteCount(Sonnet.Length);
方法 运行时 平均值 比率
GetMaxByteCount .NET 6.0 1.7442 ns 1.00
GetMaxByteCount .NET 7.0 0.4746 ns 0.27

可以说,.NET 7 中关于 UTF8 的最大改进是新的 C# 11 对 UTF8 字面量的支持。最初在 C# 编译器中实现,在 dotnet/roslyn#58991,随后在 dotnet/roslyn#59390,dotnet/roslyn#61532,和 dotnet/roslyn#62044 中进行了后续工作,UTF8 字面量使编译器能够在编译时将 UTF8 编码为字节。而不是写一个普通的字符串,例如 "hello",开发者只需在字符串字面量后面添加新的 u8 后缀,例如 "hello"u8。此时,这不再是一个字符串。相反,这个表达式的自然类型是 ReadOnlySpan。如果你写:

public static ReadOnlySpan<byte> Text => "hello"u8;

C# 编译器将编译等效于你写的:

public static ReadOnlySpan<byte> Text =>
    new ReadOnlySpan<byte>(new byte[] { (byte)'h', (byte)'e', (byte)'l', (byte)'l', (byte)'o', (byte)'\0' }, 0, 5);    

换句话说,编译器在编译时执行了等同于 Encoding.UTF8.GetBytes 的操作,并硬编码了结果字节,节省了在运行时执行该编码的成本。当然,乍一看,这种数组分配可能看起来效率极低。然而,外表可能会欺骗人,这种情况也不例外。在过去的几个版本中,当 C# 编译器看到一个 byte[](或 sbyte[] 或 bool[])用常量长度和常量值初始化,并立即转换为或用于构造 ReadOnlySpan 时,它会优化掉 byte[] 分配。相反,它将该 span 的数据复制到程序集的数据部分,然后构造一个直接指向加载的程序集中的数据的 span。这是上述属性的实际生成的 IL:

IL_0000: ldsflda valuetype '<PrivateImplementationDetails>'/'__StaticArrayInitTypeSize=6' '<PrivateImplementationDetails>'::F3AEFE62965A91903610F0E23CC8A69D5B87CEA6D28E75489B0D2CA02ED7993C
IL_0005: ldc.i4.5
IL_0006: newobj instance void valuetype [System.Runtime]System.ReadOnlySpan`1<uint8>::.ctor(void*, int32)
IL_000b: ret

这意味着我们不仅在运行时节省了编码成本,而且我们避免了可能需要存储结果数据的任何托管分配,我们还从 JIT 能够看到关于编码数据的信息(如它的长度)中受益,从而实现了连锁优化。你可以通过检查像这样的方法生成的汇编清楚地看到这一点:

public static int M() => Text.Length;

对于这段代码,JIT生成的代码如下:

; Program.M()
       mov       eax,5
       ret
; Total bytes of code 6

JIT内联了属性访问,看到span是用长度5构造的,所以它并没有发出任何数组分配或span构造,甚至没有任何类似的操作,它只是输出 mov eax, 5 来返回span的已知长度。

主要归功于 @am11 的 dotnet/runtime#70568, dotnet/runtime#69995, dotnet/runtime#70894, dotnet/runtime#71417,以及 dotnet/runtime#71292, dotnet/runtime#70513, 和 dotnet/runtime#71992,现在在整个 dotnet/runtime 中使用了超过2100次 u8。虽然这并不是一个公平的比较,但以下的基准测试展示了在执行时实际上对 u8 执行的工作有多少:

[Benchmark(Baseline = true)]
public ReadOnlySpan<byte> WithEncoding() => Encoding.UTF8.GetBytes("test");

[Benchmark] 
public ReadOnlySpan<byte> Withu8() => "test"u8;
方法 平均值 比率 分配 分配比率
WithEncoding 17.3347 ns 1.000 32 B 1.00
Withu8 0.0060 ns 0.000 0.00

就像我说的,这并不公平,但它证明了这一点 🙂

编码当然只是创建字符串实例的一种机制。在 .NET 7 中,其他方法也有所改进。以超常见的 long.ToString 为例。以前的版本改进了 int.ToString,但是 32 位和 64 位算法之间有足够的差异,因此 long 并没有看到所有相同的增益。现在,感谢 dotnet/runtime#68795,64 位格式化代码路径变得更像 32 位,从而提高了性能。

你还可以看到 string.Format 和 StringBuilder.AppendFormat 的改进,以及其他在这些之上的助手(如 TextWriter.AppendFormat)。dotnet/runtime#69757 彻底改造了 Format 内部的核心例程,以避免不必要的边界检查,偏向预期的情况,并一般清理实现。然而,它也使用 IndexOfAny 来搜索需要填充的下一个插值孔,如果非孔字符到孔的比率高(例如,具有少数孔的长格式字符串),那么它可能比以前快得多。

private StringBuilder _sb = new StringBuilder();

[Benchmark]
public void AppendFormat()
{
    _sb.Clear();
    _sb.AppendFormat("There is already one outstanding '{0}' call for this WebSocket instance." +
                     "ReceiveAsync and SendAsync can be called simultaneously, but at most one " +
                     "outstanding operation for each of them is allowed at the same time.",
                     "ReceiveAsync");
}
方法 运行时 平均值 比率
AppendFormat .NET 6.0 338.23 ns 1.00
AppendFormat .NET 7.0 49.15 ns 0.15

说到 StringBuilder,除了对 AppendFormat 的上述改变之外,它还有其他改进。一个有趣的变化是 dotnet/runtime#64405,它实现了两个相关的事情。第一个是去除格式化操作中的固定。例如,StringBuilder 有一个 Append(char* value, int valueCount) 重载,它将指定数量的字符从指定的指针复制到 StringBuilder,其他 API 是根据这个方法实现的;例如,Append(string? value, int startIndex, int count) 方法基本上是这样实现的:

fixed (char* ptr = value)
{
    Append(ptr + startIndex, count);
}

这个 fixed 语句被翻译成一个“固定指针”。通常,GC 可以自由地在堆上移动托管对象,它可能会这样做以压缩堆(例如,避免对象之间的小的、不可用的内存碎片)。但是,如果 GC 可以移动对象,那么一个普通的本地指针指向那个内存将是非常不安全和不可靠的,因为没有通知,被指向的数据可能会移动,你的指针现在可能指向垃圾或者被移动到这个位置的其他对象。有两种方法可以处理这个问题。第一种是“托管指针”,也被称为“引用”或“ref”,这就是你在 C# 中使用“ref”关键字时得到的;它是一个运行时会用被指向的对象移动时的正确值更新的指针。第二种是阻止被指向的对象被移动,将其“固定”在原地。这就是“fixed”关键字所做的,它在 fixed 块的持续时间内固定引用的对象,这段时间内使用提供的指针是安全的。幸运的是,当没有 GC 发生时,固定是便宜的;然而,当 GC 发生时,固定的对象不能被移动,因此固定可能对应用程序的性能(以及 GC 本身)产生全局影响。固定也会阻止各种优化。随着 C# 在许多地方能够使用 ref 的新特性(例如,ref 局部变量,ref 返回,现在在 C# 11 中,ref 字段),以及 .NET 中用于操作 ref 的新 API(例如,Unsafe.Add,Unsafe.AreSame),现在可以将使用固定指针的代码重写为使用托管指针,从而避免固定带来的问题。这就是这个 PR 所做的。所有的 Append 方法不再以 Append(char*, int) 辅助函数为基础实现,而是以 Append(ref char, int) 辅助函数为基础实现。所以,例如,之前显示的 Append(string? value, int startIndex, int count) 实现现在类似于

Append(ref Unsafe.Add(ref value.GetRawStringData(), startIndex), count);

其中,string.GetRawStringData 方法只是公共的 string.GetPinnableReference 方法的内部版本,返回的是 ref 而不是 ref readonly。这意味着 StringBuilder 内部所有的高性能代码都可以继续使用指针来避免边界检查等,但现在也可以在不固定所有输入的情况下这样做。

这个 StringBuilder 的改变做的第二件事是统一了对 string 输入的优化,也适用于 char[] 输入和 ReadOnlySpan 输入。具体来说,因为将 string 实例追加到 StringBuilder 是非常常见的,所以很久以前就加入了一个特殊的代码路径来优化这个输入,特别是在 StringBuilder 已经有足够的空间来容纳整个输入的情况下,此时可以使用高效的复制。但是,有了共享的 Append(ref char, int) 辅助函数,这个优化可以被移动到那个辅助函数中,这样不仅可以帮助 string,还可以帮助任何其他也调用同一个辅助函数的类型。这个效果在一个简单的微基准测试中是可见的:

private StringBuilder _sb = new StringBuilder();

[Benchmark]
public void AppendSpan()
{
    _sb.Clear();
    _sb.Append("this".AsSpan());
    _sb.Append("is".AsSpan());
    _sb.Append("a".AsSpan());
    _sb.Append("test".AsSpan());
    _sb.Append(".".AsSpan());
}
方法 运行时 平均值 比率
AppendSpan .NET 6.0 35.98 ns 1.00
AppendSpan .NET 7.0 17.59 ns 0.49

改进底层堆栈中的事物的一大优点是它们具有乘法效应;它们不仅有助于提高直接依赖于改进功能的用户代码的性能,还可以帮助提高核心库中其他代码的性能,进一步帮助依赖的应用程序和服务。例如,你可以看到 DateTimeOffset.ToString,它依赖于 StringBuilder:

private DateTimeOffset _dto = DateTimeOffset.UtcNow;

[Benchmark]
public string DateTimeOffsetToString() => _dto.ToString();
方法 运行时 平均值 比率
DateTimeOffsetToString .NET 6.0 340.4 ns 1.00
DateTimeOffsetToString .NET 7.0 289.4 ns 0.85

StringBuilder 本身随后由 @teo-tsirpanis 的 dotnet/runtime#64922 进一步更新,该更新改进了 Insert 方法。过去,StringBuilder 上的 Append(primitive) 方法(例如 Append(int))会对值调用 ToString,然后追加生成的字符串。随着 ISpanFormattable 的出现,作为一种快速路径,这些方法现在尝试直接格式化到 StringBuilder 的内部缓冲区中的值,只有当剩余空间不足时,它们才会作为后备采取旧路径。当时,Insert 没有以这种方式进行改进,因为它不能只是格式化到构建器末尾的空间;插入位置可能在构建器的任何地方。这个 PR 解决了这个问题,通过格式化到一些临时的堆栈空间,然后委托给之前讨论的 PR 中现有的内部基于 ref 的辅助函数,将生成的字符插入到正确的位置(当 ISpanFormattable.TryFormat 的堆栈空间不足时,它也会回退到 ToString,但这只会在极其角落的情况下发生,比如格式化为数百位的浮点值)。

private StringBuilder _sb = new StringBuilder();

[Benchmark]
public void Insert()
{
    _sb.Clear();
    _sb.Insert(0, 12345);
}
方法 运行时 平均值 比率 分配 分配比率
Insert .NET 6.0 30.02 ns 1.00 32 B 1.00
Insert .NET 7.0 25.53 ns 0.85 - 0.00

StringBuilder 也有其他一些小的改进,比如 dotnet/runtime#60406,它从 Replace 方法中移除了一个小的 int[] 分配。然而,即使有了所有这些改进,StringBuilder 的最快使用方式也没有使用;dotnet/runtime#68768 移除了一堆最好用其他字符串创建机制的 StringBuilder 的使用。例如,旧的 DataView 类型有一些代码,用于创建排序规范作为字符串:

private static string CreateSortString(PropertyDescriptor property, ListSortDirection direction)
{
    var resultString = new StringBuilder();
    resultString.Append('[');
    resultString.Append(property.Name);
    resultString.Append(']');
    if (ListSortDirection.Descending == direction)
    {
        resultString.Append(" DESC");
    }
    return resultString.ToString();
}

我们实际上并不需要这里的 StringBuilder,因为在最坏的情况下,我们只是连接三个字符串,而 string.Concat 有一个专门的重载用于这个精确的操作,它具有该操作的最佳可能的实现(如果我们找到了更好的方法,那么该方法将会相应地得到改进)。所以我们可以直接使用它:

private static string CreateSortString(PropertyDescriptor property, ListSortDirection direction) =>
    direction == ListSortDirection.Descending ?
        $"[{property.Name}] DESC" :
        $"[{property.Name}]";

注意,我通过插值字符串来表达这个连接,但是C#编译器会将这个插值字符串“降级”为对string.Concat的调用,所以这个的IL与我写的几乎无法区分:

private static string CreateSortString(PropertyDescriptor property, ListSortDirection direction) =>
    direction == ListSortDirection.Descending ?
        string.Concat("[", property.Name, "] DESC") :
        string.Concat("[", property.Name, "]");

顺便说一下,扩展的 string.Concat 版本强调了,如果这个方法被写成以下形式,那么生成的 IL 会少一些:

private static string CreateSortString(PropertyDescriptor property, ListSortDirection direction) =>
    string.Concat("[", property.Name, direction == ListSortDirection.Descending ? "] DESC" : "]"); 

但这并不会对性能产生实质性影响,在这里,清晰性和可维护性比节省几个字节更重要。

[Benchmark(Baseline = true)]
[Arguments("SomeProperty", ListSortDirection.Descending)]
public string WithStringBuilder(string name, ListSortDirection direction)
{
    var resultString = new StringBuilder();
    resultString.Append('[');
    resultString.Append(name);
    resultString.Append(']');
    if (ListSortDirection.Descending == direction)
    {
        resultString.Append(" DESC");
    }
    return resultString.ToString();
}

[Benchmark]
[Arguments("SomeProperty", ListSortDirection.Descending)]
public string WithConcat(string name, ListSortDirection direction) =>
    direction == ListSortDirection.Descending?
        $"[{name}] DESC" :
方法 平均值 比率 分配 分配比率
WithStringBuilder 68.34 ns 1.00 272 B 1.00
WithConcat 20.78 ns 0.31 64 B 0.24

还有一些地方,StringBuilder 仍然适用,但它被用在足够热的路径上,以至于.NET的早期版本看到StringBuilder实例被缓存。包括 System.Private.CoreLib 在内的几个核心库,都有一个内部的 StringBuilderCache 类型,它在 [ThreadStatic] 中缓存一个 StringBuilder 实例,这意味着每个线程都可能最终拥有这样一个实例。这里有几个问题,包括 StringBuilder 使用的缓冲区在 StringBuilder 未被使用时无法用于其他任何事情,因此,StringBuilderCache 对可以被缓存的 StringBuilder 实例的容量设置了限制;试图缓存超过该长度的实例会导致它们被丢弃。相反,最好使用缓存的数组,这些数组没有长度限制,每个人都可以访问以进行共享。许多核心 .NET 库都有一个内部的 ValueStringBuilder 类型,这是一个基于 ref struct 的类型,它可以使用 stackalloc 分配的内存开始,然后如果需要,可以增长到 ArrayPool 数组。并且,随着 dotnet/runtime#64522 和 dotnet/runtime#69683,许多剩余的 StringBuilderCache 的使用已经被替换。我希望我们将来能完全移除 StringBuilderCache。

在同样的不做不必要工作的思路中,有一个相当常见的模式出现在 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位进程中)。

好了,关于字符串就说到这里。那么,关于 spans 呢?C# 11 中最酷的特性之一就是对 ref 字段的新支持。什么是 ref 字段?你对 C# 中的 refs 应该很熟悉,我们已经讨论过它们基本上就是被管理的指针,即运行时可以随时更新的指针,因为它引用的对象可能在堆上移动。这些引用可以指向对象的开始,也可以指向对象内部的某个地方,在这种情况下,它们被称为“内部指针”。ref 在 C# 1.0 中就已经存在,但那时它主要是用于将引用传递给方法调用,例如:

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# 版本增加了对本地 refs 的支持,例如:

void Add(ref int i)
{
    ref int j = ref i;
    j++;
}

甚至还有 ref 返回,例如:

ref int Add(ref int i)
{
    ref int j = ref i;
    j++;
    return ref j;
}

这些功能更为高级,但在高性能代码库中被广泛使用,近年来 .NET 中的许多优化在很大程度上都是由于这些 ref 相关的能力。

Span 和 ReadOnlySpan 本身就大量基于 refs。例如,许多旧的集合类型的索引器是作为 get/set 属性实现的,例如:

private T[] _items;
...
public T this[int i]
{
    get => _items[i];
    set => _items[i] = value;
}
But not span. Span<T>‘s indexer looks more like this:

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,指向实际的存储位置。这是一个可写的 ref,所以你可以给它赋值,例如,你可以写:

span[i] = value;

但这并不等同于调用某个 setter:

span.set_Item(i, value);

实际上,它等同于使用 getter 获取 ref,然后通过该 ref 写入值,例如:

ref T item = ref span.get_Item(i);
item = value;

这很好,但 getter 定义中的 _reference 是什么呢?好吧,Span 实际上只是两个字段的元组:一个引用(指向被引用的内存的开始)和一个长度(从该引用开始包含在 span 中的元素数量)。在过去,运行时必须使用一个内部类型(ByReference)来实现这个,这个类型被运行时特别识别为引用。但是从 C# 11 和 .NET 7 开始,ref 结构现在可以包含 ref 字段,这意味着今天的 Span 实际上就是这样定义的:

public readonly ref struct Span<T>
{
    internal readonly ref T _reference;
    private readonly int _length;
    ...
}

在 dotnet/runtime#71498 中,ref 字段在整个 dotnet/runtime 中的推出,跟随着 C# 语言主要在 dotnet/roslyn#62155 中获得这种支持,这本身是许多 PRs 首先进入一个特性分支的结果。ref 字段本身并不会自动提高性能,但它确实可以显著简化代码,并且它允许使用 ref 字段的新的自定义代码以及利用它们的新 API,这两者都可以帮助提高性能(特别是在不牺牲潜在安全性的情况下的性能)。一个新 API 的例子是 ReadOnlySpan 和 Span 上的新构造函数:

public Span(ref T reference);
public ReadOnlySpan(in T reference);

在 dotnet/runtime#67447 中添加(然后在 dotnet/runtime#71589 中公开并更广泛地使用)。这可能会引发一个问题,为什么 ref 字段的支持会启用两个新的接受 refs 的构造函数,考虑到 spans 已经能够存储一个 ref?毕竟,MemoryMarshal.CreateSpan(ref T reference, int length) 和相应的 CreateReadOnlySpan 方法已经存在了,只要 spans 存在,这些新的构造函数就等同于调用那些方法,长度为 1。答案是:安全性。

想象一下,如果你可以随意调用这个构造函数。你将能够写出这样的代码:

public Span<int> RuhRoh()
{
    int i = 42;
    return new Span<int>(ref i);
}

在这一点上,这个方法的调用者被交给了一个指向垃圾的 span;在预期为安全的代码中,这是不好的。你已经可以通过使用指针来实现同样的事情:

public Span<int> RuhRoh()
{
    unsafe
    {
        int i = 42;
        return new Span<int>(&i, 1);
    }
}

但在这一点上,你已经承担了使用不安全的代码和指针的风险,任何结果的问题都在你身上。使用 C# 11,如果你现在试图使用基于 ref 的构造函数写上述代码,你会收到这样的错误:

错误 CS8347: 不能在此上下文中使用 'Span<int>.Span(ref int)' 的结果,因为它可能会将参数 'reference' 引用的变量暴露在其声明范围之外

换句话说,编译器现在理解到 Span 作为一个 ref 结构可能会存储传入的 ref,如果它确实存储了它(Span 就是这样做的),这就类似于将一个 ref 传递给一个局部方法,这是不好的。因此,这与 ref 字段有关:因为 ref 字段现在是一种事物,编译器对 refs 的安全处理规则已经更新,这反过来使我们能够在 {ReadOnly}Span 上公开上述构造函数。

正如通常情况一样,解决一个问题会将问题推到路的一边并暴露出另一个问题。编译器现在认为传递给 ref 结构的方法的 ref 可能使该 ref 结构实例存储 ref(注意,这已经是传递给 ref 结构的方法的 ref 结构的情况),但如果我们不希望这样呢?如果我们希望能够说“这个 ref 不可存储,不应该逃脱调用范围”?从调用者的角度来看,我们希望编译器允许传入这样的 refs,而不会抱怨可能的生命周期延长,从被调用者的角度来看,我们希望编译器阻止方法做它不应该做的事情。进入 scoped。新的 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 到其构造函数,并允许通过复制额外的内容然后更新存储的长度来写入它。Write 方法接受一个 ReadOnlySpan。然后我们有一个 helper Append 方法,它将一个字节格式化到一些 stackalloc‘d 临时空间,并将结果格式化的字符传入到 Write。直接的。除了,这不编译:

错误 CS8350: 'SpanWriter.Write(ReadOnlySpan<char>)' 的这种参数组合是不允许的,因为它可能会将参数 'value' 引用的变量暴露在其声明范围之外

我们该怎么办?Write 方法实际上并不存储 value 参数,也永远不需要,所以我们可以改变方法的签名来注解它为 scoped:

public void Write(scoped ReadOnlySpan<char> value)

如果 Write 然后试图存储 value,编译器会抱怨:

错误 CS8352: 不能在此上下文中使用变量 'ReadOnlySpan<char>',因为它可能会将引用的变量暴露在其声明范围之外

但是因为它并没有试图这样做,所以现在一切都成功编译了。你可以在上述的 dotnet/runtime#71589 中看到如何使用这个的例子。

还有另一个方向:有一些事情是隐式 scoped 的,比如在结构上的 this 引用。考虑以下代码:

public struct SingleItemList
{
    private int _value;

    public ref int this[int i]
    {
        get
        {
            if (i != 0) throw new IndexOutOfRangeException();

            return ref _value;
        }
    }
}

这会产生一个编译器错误:

错误 CS8170: 结构成员不能通过引用返回 'this' 或其他实例成员

实际上,这是因为 this 是隐式 scoped 的(即使以前没有这个关键字)。如果我们想要使这样的项能够被返回呢?进入 [UnscopedRef]。这种需求足够罕见,以至于它没有得到自己的 C# 语言关键字,但 C# 编译器确实识别新的 [UnscopedRef] 属性。它可以放在相关参数上,也可以放在方法和属性上,在这种情况下,它适用于该成员的 this 引用。因此,我们可以修改我们之前的代码示例为:

[UnscopedRef]
public ref int this[int i]

现在代码将成功编译。当然,这也对这个方法的调用者提出了要求。对于一个调用站点,编译器看到被调用的成员上的 [UnscopedRef],然后知道返回的 ref 可能引用该结构中的某个东西,因此将返回的 ref 的生命周期与该结构的生命周期相同。所以,如果那个结构是一个在栈上的局部变量,ref 也将限制在同一个方法中。

另一个有影响的 span 相关改变来自 dotnet/runtime#70095,由 @teo-tsirpanis 提出。System.HashCode 的目标是提供一个快速、易于使用的实现,用于生成高质量的哈希码。在其当前的版本中,它包含一个随机的进程范围种子,并且是非加密哈希算法 xxHash32 的实现。在之前的版本中,HashCode 添加了一个 AddBytes 方法,它接受一个 ReadOnlySpan,并且对于包含应该是类型哈希码的一部分的数据序列非常有用,例如,BigInteger.GetHashCode 包含了构成 BigInteger 的所有数据。xxHash32 算法通过累积 4 个 32 位无符号整数,然后将它们组合成哈希码;因此,如果你调用 HashCode.Add(int),你前三次调用它时只是将值分别存储到实例中,然后你第四次调用它时,所有这些值都被组合成哈希码(并且有一个单独的过程,如果添加的 32 位值的数量不是 4 的精确倍数,那么它会包含任何剩余的值)。因此,以前的 AddBytes 只是简单地实现为从输入 span 中重复读取下一个 4 字节,并用这些字节作为整数调用 Add(int)。但是这些 Add 调用有开销。相反,这个 PR 跳过了 Add 调用,并直接处理了 16 字节的累积和组合。有趣的是,它仍然必须处理之前的 Add 调用可能留下一些状态的可能性,这意味着(至少在当前的实现中),如果有多个状态需要包含在哈希码中,比如说一个 ReadOnlySpan 和一个额外的 int,那么首先添加 span 然后添加 int 比反过来的方式更有效率。所以例如,当 dotnet/runtime#71274 由 @huoyaoyuan 改变了 BigInteger.GetHashCode 以使用 HashCode.AddBytes 时,它编码了方法,首先用 BigInteger 的 _bits 调用 AddBytes,然后用 _sign 调用 Add。

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

另一个与 span 相关的变化,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[],而且如果文本确实需要去除空格,新版本(它修剪 span 而不是原始字符串)将节省一个分配给修剪字符串的空间。这是利用新的 C# 11 功能,它支持在 ReadOnlySpan 上进行切换,就像你可以在字符串上进行切换一样,这是在 dotnet/roslyn#44388 中由 @YairHalberstadt 添加的。dotnet/runtime#68831 也在几个其他地方利用了这个特性。

当然,在某些情况下,数组完全是不必要的。在同一个 PR 中,有几个类似这样的例子:

private static readonly char[] WhiteSpaceChecks = new char[] { ' ', '\u00A0' };
...
int wsIndex = target.IndexOfAny(WhiteSpaceChecks, targetPosition);
if (wsIndex < 0)
{
    return false;
}

通过切换到使用 spans,我们可以将其改写为这样:

int wsIndex = target.AsSpan(targetPosition).IndexOfAny(' ', '\u00A0');
if (wsIndex < 0)
{
    return false;
}
wsIndex += targetPosition;

MemoryExtensions.IndexOfAny 有一个专门用于两个和三个参数的重载,此时我们根本不需要数组(这些重载也恰好更快;当传递一个包含两个字符的数组时,实现会从数组中提取两个字符,然后将它们传递给相同的两参数实现)。其他多个 PR 也类似地移除了数组分配。dotnet/runtime#60409 移除了一个被缓存的单字符数组,以便将其传递给 string.Split,并用直接接受单个字符的 Split 重载替换了它。

最后,来自 @NewellClark 的 dotnet/runtime#59670 去掉了更多的数组。我们之前看到 C# 编译器如何对使用常量长度和常量元素构造的 byte[] 进行特殊处理,然后立即将其转换为 ReadOnlySpan。因此,任何时候缓存这样的 byte[] 并将其暴露为 ReadOnlySpan 都可能是有益的。正如我在 .NET 6 文章中讨论的,这避免了你会得到的用于缓存数组的一次性数组分配,结果访问效率更高,而且向 JIT 编译器提供了更多信息,使其能够更加优化...全方位的好处。这个 PR 以这种方式移除了更多的数组,dotnet/runtime#60411、dotnet/runtime#72743、来自 @vcsjones 的 dotnet/runtime#73115 和 dotnet/runtime#70665 也是如此。

Regex

在五月份,我分享了一篇关于 .NET 7 中正则表达式改进的相当详细的文章。回顾一下,.NET 5 之前,Regex 的实现已经有相当长一段时间没有变动了。在 .NET 5 中,我们使其在性能方面达到或超过了其他多个行业实现。.NET 7 在此基础上取得了一些重大的进步。如果你还没有读过那篇文章,现在请继续阅读;我会等你的...

欢迎回来。有了这个背景,我将避免在这里重复内容,而是专注于这些改进是如何实现的以及实现它们的 PR。

RegexOptions.NonBacktracking
让我们从 Regex 中一个较大的新特性开始,新的 RegexOptions.NonBacktracking 实现。如前文所述,RegexOptions.NonBacktracking 将 Regex 的处理切换到使用基于有限自动机的新引擎。它有两种主要的执行模式,一种依赖于 DFA(确定性有限自动机),一种依赖于 NFA(非确定性有限自动机)。两种实现都提供了一个非常有价值的保证:处理时间与输入的长度成线性关系。而回溯引擎(如果没有指定 NonBacktracking,Regex 就会使用它)可能会遇到一个被称为“灾难性回溯”的情况,其中有问题的表达式和有问题的输入可能导致输入长度的指数级处理,NonBacktracking 保证它只会对输入中的每个字符做出均摊常数的工作量。在 DFA 的情况下,这个常数非常小。在 NFA 的情况下,这个常数可能会大得多,取决于模式的复杂性,但对于任何给定的模式,工作量仍然与输入的长度成线性关系。

NonBacktracking 实现投入了大量的开发年份,最初在 dotnet/runtime#60607 中添加到 dotnet/runtime 中。然而,它的原始研究和实现实际上来自微软研究院(MSR),并以 Symbolic Regex Matcher(SRM)库的形式作为一个实验性的包发布。你仍然可以在现在的 .NET 7 中看到这个的痕迹,但它已经发展得非常显著,.NET 团队的开发人员和 MSR 的研究人员之间紧密合作(在被集成到 dotnet/runtime 之前,它在 dotnet/runtimelab 中孵化了一年多,原始的 SRM 代码是通过 dotnet/runtimelab#588 从 @veanes 引入的)。
这个实现基于正则表达式导数的概念,这个概念已经存在了几十年(这个术语最初是在1960年代由 Janusz Brzozowski 在一篇论文中提出的),并且在这个实现中得到了显著的提升。正则表达式导数构成了用于处理输入的自动机(想象为“图”)构造的基础。其核心的想法相当简单:取一个正则表达式并处理一个单独的字符...处理那一个字符后剩下的新的正则表达式是什么?那就是导数。例如,给定正则表达式 \w{3} 来匹配三个单词字符,如果你将这个应用到下一个输入字符 'a',那么,这将剥离第一个 \w,留下我们的导数 \w{2}。简单,对吧?那么更复杂的东西呢,比如表达式 .(the|he)。如果下一个字符是 t 呢?那么,t 可能会被模式开头的 . 消耗掉,在这种情况下,剩下的正则表达式将与开始的正则表达式完全相同(.(the|he)),因为在匹配 t 之后我们仍然可以匹配与没有 t 时完全相同的输入。但是,t 也可能是匹配 the 的一部分,应用到 the 上,我们会剥离 t 并留下 he,所以现在我们的导数是 .(the|he)|he。那么原始交替中的 he 呢?t 不匹配 h,所以导数将是没有,我们在这里将其表示为一个空的字符类,给我们 .(the|he)|he|[]。当然,作为交替的一部分,最后的“没有”是一个 nop,所以我们可以将整个导数简化为只有 .(the|he)|he...完成。这是所有应用原始模式对下一个 t 的情况。如果它是针对 h 的呢?按照 t 的相同逻辑,这次我们得到的是 .(the|he)|e。等等。如果我们开始的是 h 导数,下一个字符是 e 呢?那么我们正在取模式 .(the|he)|e 并将其应用到 e。对于交替的左侧,它可以被 .* 消耗(但不匹配 t 或 h),所以我们只是得到了相同的子表达式。但是对于交替的右侧,e 匹配 e,留下我们的空字符串():.*(the|he)|()。在模式是“可为空”(它可以匹配空字符串)的地方,那可以被认为是一个匹配。我们可以将整个过程可视化为一个图,对于每个输入字符到来自应用它的导数的转换。

来自 NonBacktracking 引擎的 DFA,.NET 7 中的性能改进

看起来很像 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,也使用了类似的方法。

正如我在之前关于正则表达式的博客文章中提到的,回溯实现和非回溯实现都有其应用场所。非回溯实现的主要优点是可预测性:由于线性处理保证,一旦你构建了正则表达式,你就不需要担心恶意输入导致你可能容易受到影响的表达式在处理过程中出现最坏情况的行为。这并不意味着 RegexOptions.NonBacktracking 总是最快的;事实上,它经常不是。为了降低最佳性能,它提供了最佳的最坏情况性能,对于某些类型的应用,这是一个非常有价值的权衡。

New APIs

在 .NET 7 中,Regex 获得了几个新的方法,所有这些都能提高性能。新 API 的简单性可能也误导了人们对启用它们所需的工作量的理解,特别是因为新的 API 都支持将 ReadOnlySpan 输入到正则表达式引擎中。
dotnet/runtime#65473 将 Regex 带入了 .NET 的基于 span 的时代,克服了自从在 .NET Core 2.1 中引入 span 以来 Regex 的一个重大限制。Regex 历来都是基于处理 System.String 输入的,这个事实贯穿了 Regex 的设计和实现,包括为 .NET Framework 中依赖的扩展模型 Regex.CompileToAssembly 暴露的 API(CompileToAssembly 现在已被弃用,且在 .NET Core 中从未起作用)。依赖于将字符串作为输入的一个微妙之处是如何将匹配信息返回给调用者。Regex.Match 返回一个表示输入中的第一个匹配的 Match 对象,该 Match 对象暴露了一个 NextMatch 方法,该方法可以移动到下一个匹配。这意味着 Match 对象需要存储对输入的引用,以便它可以作为这样一个 NextMatch 调用的一部分反馈到匹配引擎中。如果输入是一个字符串,那么很好,没有问题。但是,如果输入是一个 ReadOnlySpan,那么作为一个 ref struct 的 span 不能存储在类 Match 对象上,因为 ref struct 只能在栈上而不是堆上。这本身就使得支持 span 成为一个挑战,但问题的根源更深。所有的正则表达式引擎都依赖于一个 RegexRunner,这是一个基类,它存储了所有需要输入到 FindFirstChar 和 Go 方法的状态,这些方法组成了正则表达式的实际匹配逻辑(这些方法包含了执行匹配的所有核心代码,其中 FindFirstChar 是一个优化,用于跳过那些不可能开始匹配的输入位置,然后 Go 执行实际的匹配逻辑)。如果你看一下内部的 RegexInterpreter 类型,这是你在构造一个新的 Regex(...) 时得到的引擎,而不是 RegexOptions.Compiled 或 RegexOptions.NonBacktracking 标志,它从 RegexRunner 派生。同样,当你使用 RegexOptions.Compiled 时,它将它反射发出的动态方法交给一个从 RegexRunner 派生的类型,RegexOptions.NonBacktracking 有一个 SymbolicRegexRunnerFactory,它产生从 RegexRunner 派生的类型,等等。最相关的是,RegexRunner 是公开的,因为由 Regex.CompileToAssembly 类型(现在是正则表达式源生成器)生成的类型包括从这个 RegexRunner 派生的类型。因此,这些 FindFirstChar 和 Go 方法是抽象的和受保护的,并且没有参数,因为它们从基类的受保护成员中获取所有需要的状态。这包括要处理的字符串输入。那么 span 呢?我们当然可以在输入 ReadOnlySpan 上调用 ToString()。这在功能上是正确的,但是完全违背了接受 span 的目的,更糟糕的是,这可能会让消费应用的性能比没有 API 时还要差。相反,我们需要一种新的方法和新的 API。

首先,我们将 FindFirstChar 和 Go 方法从抽象方法改为了虚方法。这种将这些方法分开的设计在很大程度上已经过时,特别是强制将查找下一个可能的匹配位置的处理阶段和在该位置实际执行匹配的阶段分开,这并不适合所有的引擎,比如 NonBacktracking 使用的引擎(它最初将 FindFirstChar 实现为 nop,并将所有逻辑放在 Go 中)。然后我们添加了一个新的虚方法 Scan,重要的是,这个方法接受一个 ReadOnlySpan 作为参数;span 不能从基类 RegexRunner 中暴露出来,必须传入。然后我们根据 Scan 实现了 FindFirstChar 和 Go,并使它们“正常工作”。然后,所有的引擎都是基于该 span 实现的;它们不再需要访问保护成员 RegexRunner.runtext、RegexRunner.runtextbeg 和 RegexRunner.runtextend 来获取输入;它们只是接收到 span,已经切片到输入区域,然后处理它。从性能的角度来看,这样做的一个好处是它使 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

相比之下,如果我们处理的是一个 span,它已经考虑了边界,那么我们可以写一个更加规范的循环,如下所示:

[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

即使没有所有其他基于 span 操作的好处,我们立即从以 span 为基础执行所有逻辑中获得了低级代码生成的好处。虽然上面的例子是编造的(显然匹配逻辑不仅仅是一个简单的 for 循环),但这里有一个真实的例子。当一个正则表达式包含一个 \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;

以下是 span 版本的样子:

[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 为数组、字符串或 span 发出抛出索引超出范围异常的代码时,生成的汇编代码就会是这样。它在末尾,因为它被认为是“冷门”,很少执行。在第一个版本中存在,是因为 JIT 不能基于该函数的本地分析证明 runtext[index-1] 和 runtext[index] 的访问将在字符串的范围内(它不能知道或信任 startpos、endpos 和 runtext 的边界之间的任何隐含关系)。但在第二个版本中,JIT 可以知道并信任 ReadOnlySpan 的下界是 0,上界(不包括)是 span 的 Length,而且根据方法的构造,它可以证明 span 的访问总是在边界内。因此,它不需要在方法中发出任何边界检查,方法就不会有索引超出范围抛出的标志。你可以在 dotnet/runtime#66129,dotnet/runtime#66178 和 dotnet/runtime#72728 中看到更多利用 span 成为所有引擎核心的例子,所有这些都清理了不必要的检查,这些检查总是针对边界,然后总是 0 和 span.Length。

好的,所以现在引擎能够接收 span 输入并处理它们,那么我们能做什么呢?好吧,Regex.IsMatch 很简单:它不被需要执行多个匹配的需求所困扰,因此不需要担心如何存储那个输入的 ReadOnlySpan 以供下一次匹配使用。同样,新的 Regex.Count,它提供了一个优化的实现,用于计算输入中有多少个匹配,可以绕过使用 Match 或 MatchCollection,因此也可以很容易地操作 span;dotnet/runtime#64289 添加了基于字符串的重载,dotnet/runtime#66026 添加了基于 span 的重载。我们可以通过将额外的信息传递到引擎中来进一步优化 Count,让它们知道它们实际需要计算多少信息。例如,我之前提到 NonBacktracking 在需要收集的信息相对于需要做的工作量方面是相当公平的。只确定是否有匹配是最便宜的,因为它可以在单次通过输入时就做到这一点。如果它还需要计算实际的开始和结束边界,那就需要再反向通过一部分输入。如果它还需要计算捕获信息,那就需要基于 NFA 再进行一次前向传递(即使其他两个是基于 DFA 的)。Count 需要边界信息,因为它需要知道从哪里开始寻找下一个匹配,但它不需要捕获信息,因为没有任何捕获信息被返回给调用者。dotnet/runtime#68242 更新了引擎以接收这个额外的信息,这样像 Count 这样的方法就可以变得更有效率。

所以,IsMatch 和 Count 可以使用 span。但我们仍然没有一个方法可以让你实际获取那些匹配信息。新的 EnumerateMatches 方法就是这样的方法,由 dotnet/runtime#67794 添加。EnumerateMatches 与 Match 非常相似,只是它返回的是一个 ref struct 枚举器,而不是一个 Match 类实例:

public ref struct ValueMatchEnumerator
{
    private readonly Regex _regex;
    private readonly ReadOnlySpan<char> _input;
    private ValueMatch _current;
    private int _startAt;
    private int _prevLen;
    ...
}

作为一个 ref struct,枚举器能够存储对输入 span 的引用,因此能够遍历由 ValueMatch ref struct 表示的匹配。值得注意的是,目前 ValueMatch 不提供捕获信息,这也使它能够参与之前为 Count 提到的优化。即使你有一个输入字符串,EnumerateMatches 因此是一种在输入中枚举所有匹配的分摊无分配的方式。然而,在 .NET 7 中,如果你还需要所有的捕获数据,就没有办法进行这样的无分配枚举。这是我们将来如果/根据需要,会考虑设计的一项功能。
尝试寻找下一个可能的起始位置
如前所述,所有引擎的核心都是一个接受输入文本进行匹配的 Scan(ReadOnlySpan) 方法,它结合了来自基础实例的位置信息,并在找到下一个匹配的位置或者在没有找到其他匹配的情况下耗尽输入时退出。对于回溯引擎,该方法的实现逻辑如下:

protected override void Scan(ReadOnlySpan<char> inputSpan)
{
    while (!TryMatchAtCurrentPosition(inputSpan) &&
           base.runtextpos != inputSpan.Length)
    {
        base.runtextpos++;
    }
}

我们尝试在当前位置匹配输入,如果成功,那就退出。然而,如果当前位置不匹配,那么如果还有剩余的输入,我们就“推进”位置并重新开始过程。在正则表达式引擎术语中,这通常被称为“推进循环”。然而,如果我们在每个输入字符处都运行完整的匹配过程,那可能会不必要地慢。对于许多模式,有一些关于模式的东西可以让我们更有思路地在哪里进行完全匹配,快速跳过那些不可能匹配的位置,只在有真正匹配机会的位置上花费我们的时间和资源。为了提升这个概念到一流的地位,回溯引擎的“推进循环”通常更像下面这样(我说“通常”是因为在某些情况下,编译和源生成的正则表达式能够生成更好的东西)。

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 添加了一个 switch,以快速跳转到正确的策略,并在构造解释器时预计算要使用的策略。这不仅使解释器在匹配时间的实现更快,而且使得添加额外策略实际上是免费的(在匹配时间的运行时开销方面)。

然后 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,它们都可能受到所使用的文化影响,并且可能不区分大小写地映射到超过两个值)。在覆盖了足够的常见情况后,实现就使用 IndexOfAny(char, char, ...) 来搜索开始集,而不是使用 Boyer-Moore 来执行不区分大小写的搜索,由 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 中一样。这个 PR 不再硬编码仅 ASCII 字符映射到的不区分大小写的集合,而是硬编码每个可能的字符的集合。一旦完成,我们就不再需要在匹配时间知道大小写不敏感,而可以只专注于有效地匹配集合,这是我们已经需要做得很好的事情。现在,我说它为每个可能的字符编码集合;这并不完全正确。如果是真的,那将占用大量的内存,实际上,大部分内存都会被浪费,因为绝大多数字符不参与大小写转换...我们只需要处理大约2000个字符。因此,实现采用了三层表格方案。第一个表有64个元素,将所有字符的完整范围划分为64个分组;这64个组中,有54个组的字符不参与大小写转换,所以如果我们碰到其中一个条目,我们可以立即停止搜索。对于剩下的10个至少有一个字符在其范围内参与的,字符和第一个表的值用于计算第二个表的索引;在那里,大多数条目也表示没有参与大小写转换。只有当我们在第二个表中得到一个合法的命中,这才给我们一个索引到第三个表,在那个位置我们可以找到所有被认为与第一个大小写等价的字符。

dotnet/runtime#63477(然后在 dotnet/runtime#66572 中进一步改进)继续添加了另一种搜索策略,这一策略受到了 nim-regex 的字面优化的启发。我们跟踪了许多正则表达式的性能,以确保我们在常见情况下没有退步,并帮助指导投资。其中之一是 mariomka/regex-benchmark 语言正则表达式基准测试中的模式。其中之一是用于 URIs 的:(@"[\w]+://[/\s?#]+[\s?#]+(?:?[\s#]*)?(?:#[\s]*)?"。这个模式挑战了到目前为止启用的寻找下一个好位置的策略,因为它保证以“单词字符”(\w)开始,这包括大约65000个可能字符中的50000个;我们没有好的方法来向量化搜索这样的字符类。然而,这个模式很有趣,因为它以一个循环开始,不仅如此,它是一个上界无限的循环,我们的分析将确定它是原子的,因为紧接着循环的字符保证是 ':',它本身不是一个单词字符,因此循环可能匹配并作为回溯的一部分放弃的没有什么可以匹配 ':' 的。这一切都适合于向量化的不同方法:而不是试图搜索 \w 字符类,我们可以反过来搜索子字符串 "😕/",然后一旦我们找到它,我们可以向后匹配尽可能多的 [\w]s;在这种情况下,唯一的限制是我们需要匹配至少一个。这个 PR 添加了这种策略,对于一个原子循环后的字面量,添加到所有的引擎中。

private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@"[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?", RegexOptions.Compiled);

[Benchmark]
public bool IsMatch() => _regex.IsMatch(s_haystack); // Uri's in Sherlock Holmes? "Most unlikely."
方法 运行时 平均值 比率
IsMatch .NET 6.0 4,291.77 us 1.000
IsMatch .NET 7.0 42.40 us 0.010

当然,正如其他地方所讨论的,最好的优化不是使某事更快,而是使某事完全不必要。这就是 dotnet/runtime#64177 所做的,特别是与锚点有关。.NET 正则表达式实现长期以来都有针对带有起始锚点的模式的优化:例如,如果模式以 ^ 开始(并且没有指定 RegexOptions.Multiline),则模式根植于开始,意味着它不可能在 0 以外的任何位置匹配;因此,对于这样的锚点,TryFindNextPossibleStartingPosition 根本不会进行任何搜索。然而,关键在于能够检测模式是否以这样的锚点开始。在某些情况下,比如 ^abc$,这是很简单的。在其他情况下,比如 abc|def,现有的分析在看穿那个替代来找到保证开始的 ^ 锚点方面有困难。这个 PR 修复了这个问题。它还添加了一种基于发现模式有一个像 $ 这样的结束锚点的新策略。如果分析引擎可以确定任何可能匹配的最大字符数,并且它有这样的锚点,那么它可以简单地跳到字符串结束的那个距离,甚至可以绕过在那之前的任何查看。

private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@"^abc|^def", RegexOptions.Compiled);

[Benchmark]
public bool IsMatch() => _regex.IsMatch(s_haystack);
方法 运行时 平均值 比率
IsMatch .NET 6.0 867,890.56 ns 1.000
IsMatch .NET 7.0 33.55 ns 0.000

dotnet/runtime#67732 是另一个与改进锚点处理相关的 PR。当一个 bug 修复或代码简化重构变成性能改进时,总是很有趣。这个 PR 的主要目的是简化一些复杂的代码,这些代码正在计算可能开始匹配的字符集。事实证明,这种复杂性隐藏了一个逻辑错误,这个错误表现在它错过了报告有效的开始字符类的一些机会,其影响是一些本可以向量化的搜索没有被向量化。通过简化实现,修复了这个 bug,揭示了更多的性能机会。

到这个阶段,引擎已经能够使用 IndexOf(ReadOnlySpan) 来查找模式开头的子字符串。但有时最有价值的子字符串并不在开始处,而是在中间或甚至在末尾。只要它距离模式开始的偏移量是固定的,我们就可以搜索它,然后只需回退到我们实际应该尝试匹配的位置。dotnet/runtime#67907 就是这样做的。

private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@"looking|feeling", RegexOptions.Compiled);

[Benchmark]
public int Count() => _regex.Matches(s_haystack).Count; // 将搜索 "ing"
方法 运行时 平均值 比率
Count .NET 6.0 444.2 us 1.00
Count .NET 7.0 122.6 us 0.28

循环和回溯

在编译和源代码生成的引擎中,循环处理已经得到了显著改进,无论是在加快处理速度还是在减少回溯方面。
对于常规的贪婪循环(例如 c),我们需要关注两个方向:我们消耗匹配循环的所有元素的速度有多快,以及我们回退可能需要作为表达式其余部分匹配的元素的速度有多快。而对于懒惰循环,我们主要关注的是回溯,这是前进的方向(因为懒惰循环在回溯的过程中消耗,而不是在回溯的过程中回退)。通过 PRs dotnet/runtime#63428, dotnet/runtime#68400, dotnet/runtime#64254, 和 dotnet/runtime#73910,在编译器和源代码生成器中,我们现在充分利用了所有的 IndexOf、IndexOfAny、LastIndexOf、LastIndexOfAny、IndexOfAnyExcept 和 LastIndexOfAnyExcept 的变体,以加快这些搜索。例如,在像 .abc 这样的模式中,该循环的前进方向涉及到消耗每一个字符,直到下一个换行符,我们可以用 IndexOf('\n') 来优化。然后在回溯的过程中,我们可以使用 LastIndexOf("abc") 来找到可能匹配模式剩余部分的下一个可行位置,而不是一次放弃一个字符。或者例如,在像 [^a-c]*def 这样的模式中,循环最初会贪婪地消耗除 'a'、'b' 或 'c' 之外的所有内容,所以我们可以使用 IndexOfAnyExcept('a', 'b', 'c') 来找到循环的初始结束位置。等等。这可以带来巨大的性能提升,而且通过源代码生成器,也使生成的代码更符合习惯,更容易理解。

private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@"^.*elementary.*$", RegexOptions.Compiled | RegexOptions.Multiline);

[Benchmark]
public int Count() => _regex.Matches(s_haystack).Count;
方法 运行时 平均值 比率
Count .NET 6.0 3,369.5 us 1.00
Count .NET 7.0 430.2 us 0.13

有时候,优化是好意的,但稍微偏离了目标。dotnet/runtime#63398 修复了在 .NET 5 中引入的一个优化的问题;这个优化是有价值的,但只对它打算覆盖的场景的一部分有价值。虽然 TryFindNextPossibleStartingPosition 的主要存在理由是更新 bumpalong 位置,但 TryMatchAtCurrentPosition 也可能这样做。它会这样做的一个场合是当模式以无上界的单字符贪婪循环开始时。由于处理开始于循环已经完全消耗了它可能匹配的所有内容,所以在扫描循环的后续旅程中不需要重新考虑在该循环内的任何开始位置;这样做只是在扫描循环的前一个迭代中重复已经完成的工作。因此,TryMatchAtCurrentPosition 可以更新 bumpalong 位置到循环的结束。在 .NET 5 中添加的优化就是这样做的,它以完全处理原子循环的方式做到了这一点。但是对于贪婪循环,每次我们回溯时,更新的位置都会被更新,这意味着它开始向后移动,而它应该保持在循环的结束。这个 PR 修复了这个问题,为额外覆盖的情况带来了显著的节省。

private static readonly string s_haystack = new HttpClient().GetStringAsync("https://www.gutenberg.org/files/1661/1661-0.txt").Result;
private Regex _regex = new Regex(@".*stephen", RegexOptions.Compiled);

[Benchmark]
public int Count() => _regex.Matches(s_haystack).Count;
方法 运行时 平均值 比率
Count .NET 6.0 103,962.8 us 1.000
Count .NET 7.0 336.9 us 0.003

如其他地方所述,最好的优化是那些使工作完全消失而不仅仅是使工作更快的优化。dotnet/runtime#68989、dotnet/runtime#63299 和 dotnet/runtime#63518 正是通过改进模式分析器的能力来找到和消除更多不必要的回溯,从而做到这一点,这个过程被分析器称为“自动原子性”(自动使循环原子化)。例如,在模式 a?b 中,我们有一个懒惰的 'a' 循环,后面跟着一个 'b'。这个循环只能匹配 'a',并且 'a' 不会与 'b' 重叠。所以假设输入是 "aaaaaaaab"。循环是懒惰的,所以我们首先尝试匹配 'b'。它不会匹配,所以我们会回溯到懒惰循环并尝试匹配 "ab"。它不会匹配,所以我们会回溯到懒惰循环并尝试匹配 "aab"。等等,直到我们消耗了所有的 'a',使得模式的其余部分有机会匹配输入的其余部分。这正是一个原子贪婪循环所做的,所以我们可以将模式 a?b 转换为 (?>a*)b,这样处理起来更有效率。实际上,我们可以通过查看这个模式的源代码生成的实现来看到它是如何处理的:

private bool TryMatchAtCurrentPosition(ReadOnlySpan<char> inputSpan)
{
    int pos = base.runtextpos;
    int matchStart = pos;
    ReadOnlySpan<char> slice = inputSpan.Slice(pos);

    // Match 'a' atomically any number of times.
    {
        int iteration = slice.IndexOfAnyExcept('a');
        if (iteration < 0)
        {
            iteration = slice.Length;
        }

        slice = slice.Slice(iteration);
        pos += iteration;
    }

    // Advance the next matching position.
    if (base.runtextpos < pos)
    {
        base.runtextpos = pos;
    }

    // Match 'b'.
    if (slice.IsEmpty || slice[0] != 'b')
    {
        return false; // The input didn't match.
    }

    // The input matched.
    pos++;
    base.runtextpos = pos;
    base.Capture(0, matchStart, pos);
    return true;
}

(注意,这些注释不是我为这篇博客文章添加的;源代码生成器本身就会生成带注释的代码。)

当输入一个正则表达式时,它会被解析成树形结构。前面提到的“自动原子性”分析就是一种分析方法,它会遍历这棵树,寻找可以将树的部分转换为行为等效但执行更高效的替代方案的机会。有几个 PR 引入了额外的这样的转换。例如,dotnet/runtime#63695 寻找可以移除的树中的“空”和“无”节点。“空”节点是匹配空字符串的东西,所以例如在 alternation abc|def||ghi 中,第三个分支就是空的。“无”节点是不能匹配任何东西的东西,所以例如在 concatenation abc(?!)def 中,中间的 (?!) 是一个围绕空的负向前瞻,它不可能匹配任何东西,因为它表示如果后面跟着空字符串,表达式就不会匹配,而所有东西都是后面跟着空字符串的。这些结构通常是其他转换的结果,而不是开发者通常会手写的东西,就像 JIT 中有一些优化,你可能会看着它们说“这怎么可能是开发者会写的东西”,但它最终还是成为了有价值的优化,因为内联可能会将完全合理的代码转换为匹配目标模式的东西。因此,例如,如果你有 abc(?!)def,由于这个连接需要 (?!) 匹配才能成功,所以连接本身可以简单地被替换为一个“无”。如果你使用源代码生成器尝试这个:

[GeneratedRegex(@"abc(?!)def")]

它会生成像这样的 Scan 方法(包括注释):

protected override void Scan(ReadOnlySpan<char> inputSpan)
{
    // The pattern never matches anything.
}

另一组转换是在 dotnet/runtime#59903 中引入的,特别是关于 alternations(除了循环,这是回溯的另一个来源)。这引入了两个主要的优化。首先,它可以将 alternations 重写为 alternations 的 alternations,例如,将 axy|axz|bxy|bxz 转换为 ax(?:y|z)|bx(?:y|z),然后进一步简化为 ax[yz]|bx[yz]。这可以使回溯引擎更有效地处理 alternations,因为分支更少,因此可能的回溯也更少。PR 还启用了 alternation 中分支的有限重排序。通常分支不能被重新排序,因为顺序可以影响到底匹配了什么和捕获了什么,但是如果引擎可以证明排序对结果没有影响,那么它就可以自由地重新排序。一个关键的地方是,如果 alternation 是原子的,因为它被包裹在一个原子组中(并且自动原子性分析会在某些情况下隐式地添加这样的组),那么排序就不是一个因素。重新排序分支可以启用其他优化,比如前面提到的这个 PR 中的一个。然后一旦这些优化生效,如果我们剩下的是一个原子 alternation,其中每个分支都以不同的字母开始,那么就可以进一步优化 alternation 的降低方式;这个 PR 教导源代码生成器如何发出 switch 语句,这会导致更高效和更易读的代码。(检测树中的节点是否是原子的,以及其他诸如执行捕获或引入回溯的属性,被证明是足够有价值的,以至于 dotnet/runtime#65734 添加了专门的支持。)

Net 6

Arrays, Strings, Spans

对于许多应用和服务来说,创建和操作数组、字符串和跨度是它们处理的重要部分,大量的努力投入到不断降低这些操作的成本中。.NET 6 也不例外。

让我们从 Array.Clear 开始。当前的 Array.Clear 签名接受要清除的 Array,起始位置,和要清除的元素数量。然而,如果你看看使用情况,绝大多数用例是像 Array.Clear(array, 0, array.Length) 这样的代码...换句话说,清除整个数组。对于在热路径上使用的基本操作,为了确保偏移量和计数在范围内,所需的额外验证加起来也是一笔不小的开销。dotnet/runtime#51548 和 dotnet/runtime#53388 添加了一个新的 Array.Clear(Array) 方法,避免了这些开销,并改变了 dotnet/runtime 中许多调用点使用新的重载。

private int[] _array = new int[10];

[Benchmark(Baseline = true)]
public void Old() => Array.Clear(_array, 0, _array.Length);

[Benchmark]
public void New() => Array.Clear(_array);
方法 平均值 比率
Old 5.563 ns 1.00
New 3.775 ns 0.68

类似的还有 Span.Fill,它不仅将每个元素设为零,而且将每个元素设为特定值。dotnet/runtime#51365 在这里提供了显著的改进:虽然对于 byte[] 它已经能够直接调用 initblk (memset) 实现,这是向量化的,但对于其他 T[] 数组,其中 T 是原始类型(例如,char),它现在也可以使用向量化的实现,带来了相当不错的加速。然后 dotnet/runtime#52590 从 @xtqqczze 重用 Span.Fill 作为 Array.Fill 的底层实现。

private char[] _array = new char[128];
private char _c = 'c';

[Benchmark]
public void SpanFill() => _array.AsSpan().Fill(_c);

[Benchmark]
public void ArrayFill() => Array.Fill(_array, _c);
方法 运行时 平均值 比率
SpanFill .NET 5.0 32.103 ns 1.00
SpanFill .NET 6.0 3.675 ns 0.11
ArrayFill .NET 5.0 55.994 ns 1.00
ArrayFill .NET 6.0 3.810 ns 0.07

有趣的是,Array.Fill 不能简单地委托给 Span.Fill,原因与其他希望在(可变)跨度上重建基于数组的实现的人相关。.NET 中的引用类型数组是协变的,这意味着给定一个从 A 派生的引用类型 B,你可以编写如下代码:

var arrB = new B[4];
A[] arrA = arrB;

现在你有了一个 A[],你可以愉快地读出实例作为 A,但只能存储 B 实例,例如,这是可以的:

arrA[0] = new B();

但这将抛出异常:

arrA[0] = new A();

类似于 System.ArrayTypeMismatchException:试图以与数组不兼容的类型访问元素。这也会在每次将元素存储到(大多数)引用类型的数组时产生可衡量的开销。当引入跨度时,人们认识到,如果你创建一个可写的跨度,你很可能会写入它,因此,如果需要支付检查的成本,最好在创建跨度时一次性支付,而不是每次写入跨度时都支付。因此,Span 是不变的,其构造函数包括此代码:

if (!typeof(T).IsValueType && array.GetType() != typeof(T[]))
    ThrowHelper.ThrowArrayTypeMismatchException();

这个检查,对于值类型完全被 JIT 移除,对于引用类型由 JIT 重度优化,验证指定的 T 匹配数组的具体类型。例如,如果你编写这样的代码:

new Span<A>(new B[4]);

这将抛出一个异常。为什么这与 Array.Fill 有关?它可以接受任意的 T[] 数组,没有保证 T 与数组类型完全匹配,例如:

var arr = new B[4];
Array.Fill<A>(new B[4], null);

如果 Array.Fill 是纯粹的以 new Span(array).Fill(value) 实现的,上述代码将从 Span 的构造函数中抛出一个异常。相反,Array.Fill 本身执行与 Span 构造函数相同的检查;如果检查通过,它创建 Span 并调用 Fill,但如果检查不通过,它回退到典型的循环,将值写入数组的每个元素。

只要我们在谈论向量化,这个版本中的其他支持已经被向量化。dotnet/runtime#44111 利用 SSSE3 硬件内在函数(例如 Ssse3.Shuffle)来优化内部 HexConverter.EncodeToUtf16 的实现,它在一些地方被使用,包括公共的 Convert.ToHexString:

private byte[] _data;

[GlobalSetup]
public void Setup()
{
    _data = new byte[64];
    RandomNumberGenerator.Fill(_data);
}

[Benchmark]
public string ToHexString() => Convert.ToHexString(_data);
方法 运行时 平均值 比率
ToHexString .NET 5.0 130.89 ns 1.00
ToHexString .NET 6.0 44.78 ns 0.34

dotnet/runtime#44088 也利用了向量化,尽管是间接的,通过使用已经向量化的 IndexOf 方法来提高 String.Replace(String, String) 的性能。这个 PR 是另一个很好的例子,展示了“优化”通常是权衡,以牺牲使其他场景变慢的代价来使一些场景更快,并需要根据这些场景发生的预期频率来做出决定。在这种情况下,PR 显著地改进了三个特定的情况:

  • 如果两个输入都只是一个字符(例如,str.Replace("\n", " ")),那么它可以委托给已经优化的 String.Replace(char, char) 重载。
  • 如果 oldValue 是一个字符,实现可以使用 IndexOf(char) 来找到它,而不是使用手动循环。
  • 如果 oldValue 是多个字符,实现可以使用类似于 IndexOf(string, StringComparison.Ordinal) 的方法来找到它。

第二和第三个要点如果在输入中 oldValue 不是非常频繁的话,可以显著加速操作,使向量化能够支付自身的成本并且更多。然而,如果它非常频繁(比如输入中的每个或者每隔一个字符),这个改变实际上可能会降低性能。我们的赌注,基于在各种代码库中审查用例,是这总的来说将是一个非常积极的胜利。

private string _str;

[GlobalSetup]
public async Task Setup()
{
    using var hc = new HttpClient();
    _str = await hc.GetStringAsync("https://www.gutenberg.org/cache/epub/3200/pg3200.txt"); // The Entire Project Gutenberg Works of Mark Twain
}

[Benchmark]
public string Yell() => _str.Replace(".", "!");

[Benchmark]
public string ConcatLines() => _str.Replace("\n", "");

[Benchmark]
public string NormalizeEndings() => _str.Replace("\r\n", "\n");
方法 运行时 平均值 比率
Yell .NET 5.0 32.85 ms 1.00
Yell .NET 6.0 16.99 ms 0.52
ConcatLines .NET 5.0 34.36 ms 1.00
ConcatLines .NET 6.0 22.93 ms 0.67
NormalizeEndings .NET 5.0 33.09 ms 1.00
NormalizeEndings .NET 6.0 23.61 ms 0.71

对于向量化,之前的 .NET 版本在 System.Text.Encodings.Web 的各种算法中添加了向量化,但特别是使用 x86 硬件内在函数,这样这些优化最终没有在 ARM 上应用。dotnet/runtime#49847 现在通过 AdvSimd 硬件内在函数的支持进行了增强,使 ARM64 设备能够实现类似的加速。只要我们正在查看 System.Text.Encodings.Web,值得一提的是 dotnet/runtime#49373,它完全改变了库的实现,主要目标是显著减少涉及的不安全代码量;然而,在过程中,我们已经一次又一次地看到,使用跨度和其他现代实践替换不安全的基于指针的代码,通常不仅使代码更简单、更安全,而且更快。部分更改涉及向量化所有编码器使用的“跳过所有不需要编码的 ASCII 字符”的逻辑,帮助在常见场景中产生一些显著的加速。

private string _text;

[Params("HTML", "URL", "JSON")]
public string Encoder { get; set; }

private TextEncoder _encoder;

[GlobalSetup]
public async Task Setup()
{
    using (var hc = new HttpClient())
        _text = await hc.GetStringAsync("https://www.gutenberg.org/cache/epub/3200/pg3200.txt");

    _encoder = Encoder switch
    {
        "HTML" => HtmlEncoder.Default,
        "URL" => UrlEncoder.Default,
        _ => JavaScriptEncoder.Default,
    };
}

[Benchmark]
public string Encode() => _encoder.Encode(_text);
方法 运行时 编码器 平均 比率 分配
Encode .NET Core 3.1 HTML 106.44 ms 1.00 128 MB
Encode .NET 5.0 HTML 101.58 ms 0.96 128 MB
Encode .NET 6.0 HTML 43.97 ms 0.41 36 MB
Encode .NET Core 3.1 JSON 113.70 ms 1.00 124 MB
Encode .NET 5.0 JSON 96.36 ms 0.85 124 MB
Encode .NET 6.0 JSON 39.73 ms 0.35 33 MB
Encode .NET Core 3.1 URL 165.60 ms 1.00 136 MB
Encode .NET 5.0 URL 141.26 ms 0.85 136 MB
Encode .NET 6.0 URL 70.63 ms 0.43 44 MB

在.NET 6中增强的另一个字符串API是string.Join。Join的一个重载接受一个IEnumerable<string?>作为要连接的字符串,它在迭代过程中将字符串附加到构建器。但是已经有一个基于数组的代码路径,它对字符串进行两次遍历,一次计算所需的大小,然后填充所需长度的结果字符串。dotnet/runtime#44032将该功能转换为基于ReadOnlySpan<string?>而不是string?[],然后对实际上是List<string?>的可枚举对象进行特殊处理,通过CollectionsMarshal.AsSpan方法获取List<string?>的后备数组的跨度。dotnet/runtime#56857然后对IEnumerable-based重载做同样的处理。

private List<string> _strings = new List<string>() { "Hi", "How", "are", "you", "today" };

[Benchmark]
public string Join() => string.Join(", ", _strings);
方法 运行时 平均 比率 分配
Join .NET Framework 4.8 124.81 ns 1.00 120 B
Join .NET 5.0 123.54 ns 0.99 112 B
Join .NET 6.0 51.08 ns 0.41 72 B

然而,最大的字符串相关改进来自于C# 10和.NET 6中新的插值字符串处理器支持,新的语言支持在dotnet/roslyn#54692中添加,库支持在dotnet/runtime#51086和dotnet/runtime#51653中添加。如果我写:

static string Format(int major, int minor, int build, int revision) =>
    $"{major}.{minor}.{build}.{revision}";

// C# 9 would compile that as:

static string Format(int major, int minor, int build, int revision)
{
    var array = new object[4];
    array[0] = major;
    array[1] = minor;
    array[2] = build;
    array[3] = revision;
    return string.Format("{0}.{1}.{2}.{3}", array);
}

这会产生各种开销,例如在每次调用时都必须在运行时解析复合格式字符串,装箱每个int,并分配一个数组来存储它们。使用C# 10和.NET 6,它会被编译为:

static string Format(int major, int minor, int build, int revision)
{
    var h = new DefaultInterpolatedStringHandler(3, 4);
    h.AppendFormatted(major);
    h.AppendLiteral(".");
    h.AppendFormatted(minor);
    h.AppendLiteral(".");
    h.AppendFormatted(build);
    h.AppendLiteral(".");
    h.AppendFormatted(revision);
    return h.ToStringAndClear();
}

所有的解析都在编译时处理,没有额外的数组分配,也没有额外的装箱分配。你可以通过将上述示例转化为基准测试来看到这些改变的影响:

private int Major = 6, Minor = 0, Build = 100, Revision = 21380;

[Benchmark(Baseline = true)]
public string Old()
{
    object[] array = new object[4];
    array[0] = Major;
    array[1] = Minor;
    array[2] = Build;
    array[3] = Revision;
    return string.Format("{0}.{1}.{2}.{3}", array);
}

[Benchmark]
public string New()
{
    var h = new DefaultInterpolatedStringHandler(3, 4);
    h.AppendFormatted(Major);
    h.AppendLiteral(".");
    h.AppendFormatted(Minor);
    h.AppendLiteral(".");
    h.AppendFormatted(Build);
    h.AppendLiteral(".");
    h.AppendFormatted(Revision);
    return h.ToStringAndClear();
}

方法 平均 比率 分配
旧的 127.31 ns 1.00 200 B
新的 69.62 ns 0.55 48 B

要深入了解,包括讨论.NET 6内置的各种自定义插值字符串处理器,以改进对StringBuilder、Debug.Assert和MemoryExtensions的支持,请参阅C# 10和.NET 6中的字符串插值。

热门相关:沉迷于名侦探中的姐姐   大文豪   风流医圣   一级BOSS:你结婚,我劫婚   万界点名册