【翻譯】通過 .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 獲取