幾周前，我和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上能很好地工作。”
分享到:
閱讀更多 非科班碼農 的文章
