【翻译】通过 .NET Core 3.0 SIMD Intrinsics获取4倍加速

几周前，我和Den Raskovalov就C＃性能进行了一次有趣的交谈，结果变成了一个很小但有趣的编码练习。证明或反对的陈述是：

下面列出的C ++代码（转换为C＃）在速度方面永远不会接近C ++。

<code>auto computeSum(char* fileName) {
    auto fIn = open(fileName, O_RDONLY | O_BINARY, 0644);

    static constexpr size_t BUFFER_SIZE = 1 << 16;
    uint8_t buffer[BUFFER_SIZE];
    uint8_t const* pBuffer = nullptr;
    size_t bufferPos = 0;
    size_t bufferLen = 0;

    int64_t sum = 0;
    uint8_t b;
    int n = 0;
    while (bufferLen = read(fIn, buffer, BUFFER_SIZE)) {
        pBuffer = buffer;
        const uint8_t* const pBufferEnd = buffer + bufferLen;
        while (pBuffer != pBufferEnd) {
            if (*pBuffer < 128) {
                n = (n << 7) + *pBuffer;
            } else {
                n = (n << 7) + *pBuffer - 128;
                sum += n;
                n = 0;
            }
            ++pBuffer;
        }
    }
    close(fIn);
    return sum;
}
/<code>

假设：

• 保持单线程
• 读取的文件可能足够短（〜1 GB或更少），可以缓存在RAM中-即IO带宽不会成为瓶颈。

如果您不想深入研究代码，请执行以下操作：

该文件存储使用可变长度数量编码方案（ Variable-Length Quantity coding scheme）存储(0…1,000,000)范围内的整数列表。计算所有这些整数的总和。

编码方案使用每个字节中的最高有效位（MSB）来指示当前号码的位序列是否连续（MSB = 0）（MSB = 1）。

因此，我们开始改进代码计算的版本，使其总和尽可能快，同时遵守上述规则。

为了简短起见，在这里我主要关注C＃代码，尽管这里您可以同时找到C＃和C++代码（我的存储库，如果有任何情况，我将使用最新版本的C＃和C++代码进行更新）,还有此处（Den的存储库，那里有最新的C++代码）。

原始的C＃代码：

<code>public static long ComputeSum(string fileName, 
    Func<readonlymemory>, long, int, (long, int)> sumComputer)
{
    using var fs = new FileStream(fileName, FileMode.Open);
    using var lease = MemoryPool<byte>.Shared.Rent(MinBufferSize);
    var buffer = lease.Memory;

    long sum = 0;
    int n = 0;
    while (true) {
        var count = fs.Read(buffer.Span);
        if (count == 0)
            return sum + n;
        (sum, n) = sumComputer(buffer.Slice(0, count), sum, n); 

    }
}

private static (long, int) ComputeSum(ReadOnlyMemory<byte> buffer, long sum, int n)
{
    var span = buffer.Span;
    foreach (var b in span) {
        if (b < 128)
            n = (n << 7) + b;
        else {
            sum += (n << 7) + b - 128;
            n = 0;
        }
    }
    return (sum, n);
}
/<byte>/<byte>/<readonlymemory>/<code>

高级包装程序在这里读取文件；它得到一个委托，该委托指向计算逻辑的特定实现（即必须是最佳的）。

在Core i7-8700K，Ubuntu 19.04，gcc或.NET Core 3.0预览版5和约1GB的文件上测试数据的性能：

• C++ 约为430毫秒
• C＃约为500毫秒

第一轮优化相对简单：

• C++：通过编译器选项启用一组优化（-Ofast -fomit-frame-pointer -march = native -mtune = native -funroll-loops -Wno-shift-count-overflow），启用PGO（配置文件引导的优化），使用内存映射文件
• C＃：使用不安全的指针，展开主循环，添加依赖异步管道的版本。我做了最后一部分，主要是为了测试是否有任何好处-我使用的实现违反了原始的“单线程”条件，因为生产者在读取该块的同时消费者又在计算总和。另一方面，依赖于内存映射文件的C++版本隐式地执行了类似的操作-因此，在两种情况下，它看起来都不像是完全违反了我们的“单线程”规则（即，我们在这里同意文件读取操作可能并发）。

更新的C＃代码：

<code>public static async Task<long> ComputeSumAsync(string fileName, 
    Func<readonlymemory>, long, int, (long, int)> sumComputer, 
    CancellationToken ct = default)
{
    await using var fs = new FileStream(fileName, FileMode.Open);
    var pipe = new Pipe(new PipeOptions(
        minimumSegmentSize: MinBufferSize, 
        useSynchronizationContext: false));

    async Task ProduceAsync() {
        await fs.CopyToAsync(pipe.Writer, ct);
        pipe.Writer.Complete();
    }

    async Task<long> ConsumeAsync() {
        try {
            var sum = 0L;
            var n = 0;
            var lastTimeProcessed = 0L;
            var readTask = pipe.Reader.ReadAsync(ct);
            while (true) {
                var result = await readTask.ConfigureAwait(false);
                var buffer = result.Buffer;
                var toProcess = buffer.Slice(lastTimeProcessed);
                lastTimeProcessed = toProcess.Length;
                if (toProcess.IsEmpty && (result.IsCompleted || result.IsCanceled))
                    break;
                pipe.Reader.AdvanceTo(toProcess.Start, toProcess.End);
                readTask = pipe.Reader.ReadAsync(ct); // We can start it right now to read while compute
                foreach (var segment in toProcess)
                    (sum, n) = sumComputer(segment.Slice(0), sum, n);
            }
            return sum + n;
        }
        finally {
            pipe.Reader.Complete();
        }
    }

    var (produceTask, consumeTask) = (ProduceAsync(), ConsumeAsync());
        await Task.WhenAll(produceTask, consumeTask);
        return consumeTask.Result;
}
 

private static unsafe (long, int) ComputeSumUnsafeUnrolled(
    ReadOnlyMemory<byte> buffer, long sum, int n)
{
    var span = buffer.Span;
    fixed (byte* pStart = span) {
        var pEnd = pStart + span.Length;
        var pEnd16 = pEnd - 15;
        var p = pStart;
        while (p < pEnd16) {
            // Loop
            var b = p[0];
            n = (b & 127) + (n << 7);
            if ((b & 128) != 0) {
                sum += n; 
                n = 0;
            }

            // Skipping loop repeats for p[1] ... p[14]

            // Loop
            b= p[15];
            n = (b & 127) + (n << 7);
            if ((b & 128) != 0) {
                sum += n; 
                n = 0;
            }

            p += 16;
        }
        while (p < pEnd) {
            var b = *p++;
            n = (b & 127) + (n << 7);
            if ((b & 128) != 0) {
                sum += n; 
                n = 0;
            }
        }
    }
    return (sum, n);
}
/<byte>/<long>/<readonlymemory>/<long>/<code>

结果再次非常相似：

• C++版本为394毫秒
• 带有异步管道的C＃版本416ms
• 462ms（“常规” C＃版本）

我尝试实现其他一些想法-特别是实现了几乎完全依赖于非分支指令的版本，但没有一个能更好地工作。 下一轮带来了将近5倍的加速：Alexey Poyarkov编写了一个非常高效的基于AVX2的和计算代码版本。我依靠.NET Core 3.0 SIMD内联函数将他的代码逐行转换为C＃，以后又进行了一些外观上的更改。这就是C＃代码最终版本的样子：

<code>private static unsafe (long, int) ComputeSumSimd(
    ReadOnlyMemory<byte> buffer, long sum, int n)
{
    var span = buffer.Span;
    fixed (byte* pStart = span) {
        return ComputeSumSimd(new IntPtr(pStart), span.Length, sum, n);
    }
}

private static unsafe (long, int) ComputeSumSimd(
    IntPtr start, long length, long sum, int n)
{
    var b7F = (byte) 127;
    var bFF = (byte) 255;
    var m7F = Avx2.BroadcastScalarToVector256(&b7F);
    var mFF = Avx2.BroadcastScalarToVector256(&bFF);
    var sum0 = Vector256<long>.Zero;
    var sum7 = Vector256<long>.Zero;
    var sum14 = Vector256<long>.Zero;
    var sum21 = Vector256<long>.Zero;

    var p = (byte*) start;
    var pEnd = p + length;

    // The following SIMD loop assumes n == 0 when it starts,
    // so we have to reach this point "manually" here
    if (n != 0) {
        while (p < pEnd) {
            var b = *p++;
            n = (b & 127) + (n << 7);
            if ((b & 128) != 0) { 

                sum += n;
                n = 0;
                break;
            }
        }
    }

    // SIMD loop
    while (p + 36 <= pEnd) {
        // Offset 0
        var x = Avx2.LoadVector256(p);
        // f indicates whether *p has flag (assuming p iterates through vector indexes);
        // f[i] is either 0 (no flag) or -1 (i.e. all byte bits are set)
        var f = Avx2.CompareGreaterThan(Vector256<sbyte>.Zero, x.AsSByte()).AsByte();
        x = Avx2.And(x, m7F);

        // Offset 1
        var x1 = Avx2.LoadVector256(p + 1);
        var f1 = Avx2.CompareGreaterThan(Vector256<sbyte>.Zero, x1.AsSByte()).AsByte();
        // f01 indicates whether *p flag sequence is (0,1); similarly, f[i] is either 0 or -1
        var f01 = Avx2.CompareGreaterThan(f.AsSByte(), f1.AsSByte()).AsByte(); 
        
        // Offset 2
        var x2 = Avx2.LoadVector256(p + 2);
        var f2 = Avx2.CompareGreaterThan(Vector256<sbyte>.Zero, x2.AsSByte()).AsByte();
        var f00 = Avx2.Or(f, f1);
        // f001 indicates whether *p flag sequence is (0,0,1)
        var f001 = Avx2.CompareGreaterThan(f00.AsSByte(), f2.AsSByte()).AsByte();

        var f000 = Avx2.Or(f00, f2);
        // f0001 indicates whether *p flag sequence is (0,0,0,1)
        // we assume here that the 4th byte always has a flag (i.e. the encoding
        // is valid), so we don't read it.
        var f0001 = Avx2.CompareGreaterThan(f000.AsSByte(), mFF.AsSByte()).AsByte();

        sum0 = Avx2.Add(sum0, Avx2.SumAbsoluteDifferences(Avx2.And(x, f), Vector256<byte>.Zero).AsInt64());
        sum7 = Avx2.Add(sum7, Avx2.SumAbsoluteDifferences(Avx2.And(x, f01), Vector256<byte>.Zero).AsInt64());
        sum14 = Avx2.Add(sum14, Avx2.SumAbsoluteDifferences(Avx2.And(x, f001), Vector256<byte>.Zero).AsInt64());
        sum21 = Avx2.Add(sum21, Avx2.SumAbsoluteDifferences(Avx2.And(x, f0001), Vector256<byte>.Zero).AsInt64());

        p += 32;
    }

    var s07 = Avx2.Add(sum0, Avx2.ShiftLeftLogical(sum7, 7));
    var s1421 = Avx2.Add(Avx2.ShiftLeftLogical(sum14, 14), Avx2.ShiftLeftLogical(sum21, 21));
    var s = Avx2.Add(s07, s1421);

    sum += s.GetElement(0) + s.GetElement(1) + s.GetElement(2) + s.GetElement(3);
    n = 0; // Fine assuming we'll process 4+ items in the following loop
     

    while (p < pEnd) {
        var b = *p++;
        n = (b & 127) + (n << 7);
        if ((b & 128) != 0) {
            sum += n; 
            n = 0;
        }
    }
    return (sum, n);
}
/<byte>/<byte>/<byte>/<byte>/<sbyte>/<sbyte>/<sbyte>/<long>/<long>/<long>/<long>/<byte>/<code>

结果：

• C++版本为95ms
• C＃版本为130ms
• 带有异步管道的C＃版本为113ms。

最终，我发现在Ubuntu上以C＃版本使用内存映射文件实际上很有意义。我从过去的经验中知道，它们在Windows上没有提供任何好处-而且，情况恰恰相反，因此，我甚至没有尝试将其作为初始优化之一。但是似乎这是在Ubuntu上的.NET Core上读取文件的最快方法：

<code>public static long ComputeSumMMF(string fileName, 
    Func<intptr> sumComputer)
{
    using var f = MemoryMappedFile.CreateFromFile(fileName, FileMode.Open);
    using var fAccessor = f.CreateViewAccessor();
    var fHandle = fAccessor.SafeMemoryMappedViewHandle;
    var (sum, _) = sumComputer(fHandle.DangerousGetHandle(), (long) fHandle.ByteLength, 0, 0);
    return sum;
}
/<intptr>/<code>

最终排名：

• C++版本为95ms
• C＃版本为101ms 请注意，这些结果几乎是完美的：假设基线是Int64值序列，计算总和的基线测试几乎需要花费相同的时间，因此CPU不再是此代码的瓶颈-而是RAM带宽。这就是我们显然必须停止的地方。

我的结论：

• C＃绝对适合于类似的计算密集型任务，尤其是在.NET Core 3.0中
• 如果您大规模运行类似的工作负载，则预期差异会更小：仅在单线程的情况下，CPU才是该测试的瓶颈。如果我们要同时运行4个或更多类似的任务（想想这是一个Web服务器解码UTF8输入等），即使在非SIMD版本上，它们也会达到RAM带宽限制。

以下是Den Raskovalov的结论（我也完全同意他的观点）：

“我同意亚历克斯做出的大多数结论，但我想强调您对以下几件事的关注：

• 即使使用现代的编译器和库，低级优化仍然很重要。实际上，该算法的第一个版本比最终版本慢10倍。编译器仍在优化IO模式，无法像经验丰富的工程师一样使用AVX/SSE流水线。
• C＃和C++代码的最终版本几乎相同。Microsoft显然了解利用低级优化的重要性。C＃是真正的工具，而不是CS玩具。在我们开始“竞争”之前，我曾希望将原生C++的实现提高10倍，但没想到.NET可以使用相同的低级优化。
• 即使在2019年平台融合之后，Alex仍无法在Linux运行上开发的C++代码。也无法运行.NET代码。Alex的版本需要.NET核心的最新版本，即使C++版本在6年前的GCC或clang上能很好地工作。”

閱讀更多 非科班碼農 的文章

關鍵字: 几周 Scheme 获取