目錄
- 前言
- 評測方案
- 幾種不同的方案
- rtuSse
- Avx2
- For循環
- Memcmp
- 64字長優化
- SIMD
- SequenceCompare
- 總結
- 參考文獻
前言
之前在群裡面有群友問過一個這樣的問題，在.NET中如何快速的比較兩個byte數組是否完全相等，聽起來是一個比較兩個byte數組是完全相等是一個簡單的問題，但是深入研究以後，覺得還是有很多方案的，這裡和大家一起分享下。
評測方案
這裡為了評測不同方案的性能，我們用到了
BenchmarkDotNet
這個庫，這個庫目前已經被收入.NET基金會下，
BenchmarkDotNet
可以很友善的評測方法執行的性能，支援幾乎所有的.NET運作環境，并且能輸出詳細的報表。使用起來也非常簡單，你隻需要安裝
BenchmakrDotNet
的Nuget包，然後使用其提供的類和方法即可，這裡是它的項目位址和幫助文檔。
BenchmarkDotNet項目位址
BenchmarkDotNet幫助文檔
我們通過BenchmarkDotNet來建構一個這樣的評測用例.
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using CompareByte;
// 需要引入BenchmarkDotNet的命名空間
// 運作Benchmark相當簡單，隻需要執行這個靜态方法，泛型是需要評測的類
var summary = BenchmarkRunner.Run<BenchmarkCompareMethod>();
// 我們需要一些評測記憶體結果資訊
// 并且生成HTML報表
[MemoryDiagnoser]
[HtmlExporter]
public class BenchmarkCompareMethod
{
// 準備兩個數組，填充4MB大小的資料
private static readonly byte[] XBytes = Enumerable.Range(0, 4096000).Select(c => (byte) c).ToArray();
private static readonly byte[] YBytes = Enumerable.Range(0, 4096000).Select(c => (byte) c).ToArray();
public BenchmarkCompareMethod()
{
// 修改數組最後一個元素，使其不同
XBytes[4095999] = 1;
YBytes[4095999] = 2;
}
[Benchmark(Baseline = true)]
public void ForCompare()
{
.....
}
} 需要注意的是，為了保證評測的結果與生産環境一緻，
BenchmarkDotNet
是要求使用
Release
模式運作程式，這樣的話不僅代碼編譯成
IL
時優化，程式運作中
JIT
也會更加積極的參與生産機器碼優化。需要在項目檔案夾下面使用
dotnet run -c Release
來運作評測。
幾種不同的方案
For循環
一開始看到這個需求，第一個想到的就是直接使用
for
循環對
byte[]
進行按下标比較，我覺得也是大家第一時間能想到的方案，那我們就上代碼跑跑看速度。
public static bool ForCompare(byte[]? x, byte[]? y)
{
if (ReferenceEquals(x, y)) return true; // 引用相等，可以直接認為相等
if (x is null || y is null) return false; // 兩者引用不相等情況下,一方為null那就不相等
if (x.Length != y.Length) return false; // 兩者長度不等，那麼肯定也不相等
for (var index = 0; index < x.Length; index++)
{
if (x[index] != y[index]) return false;
}
return true;
} 最終的結果如下所示，我們可以看到其實使用
for
循環進行比較是很快的，4MB大小的數組2ms左右就能比較完畢。
其實還有一個優化點，.NET的
JIT
對一些方法預設是不做
inline
内聯優化的，這樣每次還有一個方法調用的開銷，我們讓
jit
去積極的進行内聯，再來試試。方法也很簡單，隻需要引入
System.Runtime.CompilerServices
命名空間，然後在方法上面打上頭标記即可。
要搞清楚為什麼方法内聯有用，首先要知道當一個方法被調用的時候發生了什麼
- 1、首先會有個執行棧，存儲目前所有活躍的方法，以及它們的本地變量和參數
- 2、當一個新的方法被調用了，一個新的棧幀會被加到棧頂，配置設定的本地變量和參數會存儲在這個棧幀
- 3、跳到目标方法代碼執行
- 4、方法傳回的時候，本地方法和參數會被銷毀，棧頂被移除
- 5、傳回原來位址執行
這就是通常說的方法調用的壓棧和出棧過程，是以，方法調用需要有一定的時間開銷和空間開銷，當一個方法體不大，但又頻繁被調用時，這個時間和空間開銷會相對變得很大，變得非常不劃算，同時降低了程式的性能。是以内聯簡單的說就是把目标方法裡面代碼複制到調用方法的地方，無需壓棧、跳轉和出棧。
不過并不是所有的方法内聯都有益處，需要方法體比較小，如果方法體很大的話在每一個調用的地方都會發生替換，浪費記憶體。
using System.Runtime.CompilerServices;
.....
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static bool ForCompare(byte[]? x, byte[]? y) 再來跑一下試試。
最後可以看到性能提升了30%呀，配置設定的位元組數少了50% (雖然本來就隻有2位元組)，講道理就可以直接交差了。
Memcmp
但是群裡面還有小夥伴就不滿足了，有沒有其它的方案？有個小夥伴就跳出來說，作業系統是不是提供了類似的功能？會不會使用C/C++代碼運作起來會更加快速？
沒錯，作業系統确實提供了這樣的函數，微軟提供了一個名為
mscrt
(微軟C運作時庫)的庫，裡面就提到了
memcmp
這個函數就可以來比較兩個
buffer
是否相等。MSDN連結.
函數簽名是這樣的，這個函數位于
mscrt.dll
内。
int memcmp(
const void *buffer1, // 數組1指針
const void *buffer2, // 數組2指針
size_t count // 比較位元組數
); 既然有現成的C語言代碼，那麼C#應該如何調用它呢？實際上C#經常被大家成為C++++是有一定道理的，它在設計之初就考慮了和C、C++等代碼的互動。這裡使用到了C#的
Native Interop - P/Invoke
技術，可以很友善的使用C風格的ABI（C++、Rust等等都提供C語言ABI生成），在.NET底層大量的代碼都是通過這種方式和底層互動，有興趣的可以戳連結了解更詳細的資訊。
那麼如何使用它呢？以我們上面的函數為例，我們隻需要引入
System.Runtime.InteropServices
命名空間，然後按照上面
memcmp
函數的簽名轉換為C#代碼就行了，最終的代碼如下所示。
using System;
using System.Runtime.InteropServices;
namespace CompareByte;
public static class BytesCompare
{
[DllImport("msvcrt.dll")] // 需要使用的dll名稱
private static extern unsafe int memcmp(byte* b1, byte* b2, int count);
// 由于指針使用是記憶體不安全的操作，是以需要使用unsafe關鍵字
// 項目檔案中也要加入<AllowUnsafeBlocks>true</AllowUnsafeBlocks>來允許unsafe代碼
public static unsafe bool MemcmpCompare(byte[]? x,byte[]? y)
{
if (ReferenceEquals(x, y)) return true;
if (x is null || y is null) return false;
if (x.Length != y.Length) return false;
// 在.NET程式的運作中，垃圾回收器可能會整理和壓縮記憶體，這樣會導緻數組位址變動
// 是以，我們需要使用fixed關鍵字，将x和y數組'固定'在記憶體中，讓GC不移動它
// 更多詳情請看 https://docs.microsoft.com/zh-cn/dotnet/csharp/language-reference/keywords/fixed-statement
fixed (byte* xPtr = x, yPtr = y)
{
return memcmp(xPtr, yPtr, x.Length) == 0;
}
}
} 那我們來跑個分吧，看看結果怎麼樣。
結果真的是Amazing呀，比我們使用的
for
循環方案足足快了80+%，從原來需要1.7ms左右到現在隻需要300us。
64字長優化
那是不是證明C#就是沒有C跑的那麼快呢？C#那還有沒有優化的空間呢？當然是有方法的，實際上
memcmp
使用的算法和我們現在用的不一樣。
我們知道衡量算法的時間複雜度是使用大O來表示，而這個其實是代碼執行時間随資料規模增長的變化趨勢的一個展現。比如我輸入的資料量大小為n，完成這個函數我近似需要執行n次，那麼時間複雜度就是O(n)。
再來回到我們的問題中，在最壞的情況下(
x
和
y
引用不相等且的長度相等)，我們上面寫的
ForCompare
就會進入
for
循環來周遊
x
和
y
每一個元素進行比較，是以它的時間複雜度就是
O(n)
，那麼問題的關鍵就是如何降低它的時間複雜度。
一個數組它的位址空間是連續的，另外
byte
類型的長度是
8bit
，預設比較方式就像下圖一樣，一個元素一個元素的比較，也就是每
8bit
每
8bit
進行比較。
那我們能讓他一次比較更多的位數嗎？比如一次16位、32位、64位？當然是可以的，畢竟我們現在基本都是64位的CPU，不嚴謹的說實際上CPU一次能處理64位資料，那麼我們如何讓它一次性能比較64位呢？
有小夥伴就說，很簡單嘛，
byte
是
8bit
，我們直接用
long
不就有
64bit
了嗎？沒錯，就是這麼簡單，我們可以把
byte*
指針強轉為
long*
指針，然後一次性比較64位，如下圖所示。
上代碼（我這用的是
UInt64
包裝的
ulong
,一樣是64位，沒有符号位會更快一點）：
public static unsafe bool UlongCompare(byte[]? x, byte[]? y)
{
if (ReferenceEquals(x, y)) return true;
if (x is null || y is null) return false;
if (x.Length != y.Length) return false;
fixed (byte* xPtr = x, yPtr = y)
{
return UlongCompareInternal(xPtr, yPtr, x.Length);
}
}
private static unsafe bool UlongCompareInternal(byte* xPtr, byte* yPtr, int length)
{
// 指針+偏移量計算出數組最後一個元素位址
byte* lastAddr = xPtr + length;
byte* lastAddrMinus32 = lastAddr - 32;
while (xPtr < lastAddrMinus32) // 我們一次循環比較32位元組，也就是256位
{
// 一次判斷比較前64位
if (*(ulong*) xPtr != *(ulong*) yPtr) return false;
// 第二次從64為開始，比較接下來的64位，需要指針偏移64位，一個byte指針是8為，是以需要偏移8個位置才能到下一輪起始位置
// 是以代碼就是xPtr+8
if (*(ulong*) (xPtr + 8) != *(ulong*) (yPtr + 8)) return false;
// 同上面一樣，第三次從第128位開始比較64位
if (*(ulong*) (xPtr + 16) != *(ulong*) (yPtr + 16)) return false;
// 第四次從第192位開始比較64位
if (*(ulong*) (xPtr + 24) != *(ulong*) (yPtr + 24)) return false;
// 一輪總共比較了256位，讓指針偏移256位
xPtr += 32;
yPtr += 32;
}
// 因為上面是一次性比較32位元組(256位)，可能數組不能為32整除，最後隻留下比如30位元組，20位元組
// 最後的幾個位元組，我們用循環來逐位元組比較
while (xPtr < lastAddr)
{
if (*xPtr != *yPtr) return false;
xPtr++;
yPtr++;
}
return true;
} 那我們來跑個分吧。
可以看到基本和
memcmp
打平了，幾us的差别可以看做是誤差。大佬們一直說，C#是一門下限低，上限高的語言，你開心的話寫出來的代碼完全媲美C++，代碼裡面還能嵌入彙編，隻是有點麻煩，O(∩_∩)O哈哈~
SIMD
那麼我們就這樣滿足了嗎？
小夥伴又問了，既然我們可以一次性比較64位，那我們能比較更多的位數嗎？比如128位，256位？答案是當然可以，這個是CPU的一個技術，叫Single Instruction Multiple Data，簡稱為SIMD，SIMD主要就是說CPU中可以單條指令實作資料的并行處理，這類指令在數字信号處理、圖像處理、以及多媒體資訊處理等領域非常有效。
我們打開CPU-Z，可以看到指令集有很多，這都是CPU為了特殊的程式單獨做的優化。
MMX：MMX 是MultiMedia eXtensions（多媒體擴充）的縮寫，是第六代CPU晶片的重要特點。MMX技術是在CPU中加入了特地為視訊信号(Video Signal)，音頻信号(Audio Signal)以及圖像處理(Graphical Manipulation)而設計的57條指令，是以，MMX CPU極大地提高了電腦的多媒體（如立體聲、視訊、三維動畫等）處理功能。
SSE：SSE是 “網際網路資料流單指令序列擴充 ( Internet Streaming SIMD Extensions)的縮寫。SSE除保持原有的MMX指令外，又新增了70條指令，在加快浮點運算的同時，改善了記憶體的使用效率，使記憶體速度更快，後面有一些增強版SSE2、SSE3等等。
EM64T：Intel的EM64T技術，EM64T技術官方全名是Extended Memory 64 Technology，中文解釋就是擴充64bit記憶體技術。
AES：AES（Advanced Encryption Standard，進階加密标準）指令集，是專門為加密解密設計的，與此前相比AES加密/解密之性能高出3倍。
AVX：Advanced Vector eXtentions（AVX）在2008年由Intel與AMD提出，并于2011年分别在Sandy Bridge以及Bulldozer架構上提供⽀持。AVX的主要改進在于對寄存器長度的擴充以及提供了更靈活的指令集。AVX對 XMM 寄存器做了擴充，從原來的128-bit擴充到了256-bit，256-bit的寄存器命名為 YMM 。YMM的低128-bit是與XMM混⽤ 的。
對于這些指令集，在.NET上提供了
System.Runtime.Intrinsics.X86
命名空間，其中支援了各種指令集原生的通路，想了解更多的東西，可以戳這個連結。由于SIMD在.NET上有着天然的支援，可以很友善的寫出SIMD代碼，而其它程式設計語言平台或多或少支援都不是很完美。
| 類名 | 作用 |
| Aes | 此類通過内部函數提供對 Intel AES 硬體指令的通路權限。 |
| Avx | 該類通過内聯函數提供對 Intel AVX 硬體指令的通路權限。 |
| Avx2 | 此類通過内部函數提供對 Intel AVX2 硬體指令的通路。 |
| Bmi1 | 此類通過内部函數提供對 Intel BMI1 硬體指令的通路權限。 |
| Bmi2 | 此類通過内部函數提供對 Intel BMI2 硬體指令的通路權限。 |
| Fma | 此類通過内部函數提供對 Intel FMA 硬體指令的通路權限。 |
| Lzcnt | 此類通過内部函數提供對 Intel LZCNT 硬體指令的通路權限。 |
| Pclmulqdq | 此類通過内部函數提供對 Intel PCLMULQDQ 硬體指令的通路權限。 |
| Popcnt | 此類通過内部函數提供對 Intel POPCNT 硬體指令的通路權限。 |
| Sse | 此類通過内部函數提供對 Intel SSE 硬體指令的通路權限。 |
| Sse2 | 此類通過内部函數提供對 Intel SSE2 硬體指令的通路權限。 |
| Sse3 | 此類通過内部函數提供對 Intel SSE3 硬體指令的通路權限。 |
| Sse41 | 此類通過内部函數提供對 Intel SSE 4.1 硬體指令的通路。 |
| Sse42 | 此類通過内部函數提供對 Intel SSE4.2 硬體指令的通路權限。 |
| Ssse3 | 此類通過内部函數提供對 Intel SSSE3 硬體指令的通路權限。 |
| X86Base | 通過内部函數提供對 x86 基本硬體指令的通路。 |
Sse
我們看到SSE系列的指令集可以操作128位，那我們就來試試128位會不會更快一些，直接上代碼。
using System.Runtime.Intrinsics.X86; // 需要引入這個命名空間
namespace CompareByte;
public static class BytesCompare
{
......
public static unsafe bool Sse2Compare(byte[]? x, byte[]? y)
{
if (ReferenceEquals(x, y)) return true;
if (x is null || y is null) return false;
if (x.Length != y.Length) return false;
fixed (byte* xPtr = x, yPtr = y)
{
return Sse2CompareInternal(xPtr, yPtr, x.Length);
}
}
private static unsafe bool Sse2CompareInternal(byte* xPtr, byte* yPtr, int length)
{
// 這裡的算法與64位大體一樣，隻是位數變成了128位
byte* lastAddr = xPtr + length;
byte* lastAddrMinus64 = lastAddr - 64;
const int mask = 0xFFFF;
while (xPtr < lastAddrMinus64)
{
// 使用Sse2.LoadVector128()各加載x和y的128位資料
// 再使用Sse2.CompareEqual()比較是否相等，它的傳回值是一個128位向量，如果相等，該位置傳回0xffff，否則傳回0x0
// CompareEqual的結果是128位的，我們可以通過Sse2.MoveMask()來重新排列成32位，最終看是否等于0xffff就好
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(xPtr), Sse2.LoadVector128(yPtr))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(xPtr + 16), Sse2.LoadVector128(yPtr + 16))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(xPtr + 32), Sse2.LoadVector128(yPtr + 32))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(xPtr + 48), Sse2.LoadVector128(yPtr + 48))) != mask)
{
return false;
}
xPtr += 64;
yPtr += 64;
}
while (xPtr < lastAddr)
{
if (*xPtr != *yPtr) return false;
xPtr++;
yPtr++;
}
return true;
}
} 放到JIT裡面看看，有沒有生成SIMD代碼，可以明顯的看到彙編代碼裡面已經有了SIMD代碼。
來看看跑分結果。
可以看到對比
memcmp
的方式快了2+%，那按道理來說從64位到128位應該快50%左右才對，為什麼隻快了2+%呢？
其實這是因為SIMD是單條指令多資料處理，其中運算還是CPU内部的64位單元處理，隻是少了多條指令的開銷。另外是因為原本64位是隻比較了一次，而SIMD需要經曆
CompareEqual
、
MoveMask
最後還需和
mask
掩碼比較，總共次數多了2次。隻能說明在我們的這個場景下，提升會比較有限。
需要注意目标平台需要能支援這些特殊的指令集，可以通過
Sse2.IsSupported
方法來判斷。
Avx2
既然128位的SSE系列指令集能在原來的基礎上提升2%，那我們來看看支援256位的Avx2指令集會提升多少。代碼和SSE指令集幾乎一樣，隻是調用的方法類名變動了。
using System.Runtime.Intrinsics.X86; // 需要引入這個命名空間
namespace CompareByte;
public static class BytesCompare
{
......
public static unsafe bool Avx2Compare(byte[]? x, byte[]? y)
{
if (ReferenceEquals(x, y)) return true;
if (x is null || y is null) return false;
if (x.Length != y.Length) return false;
fixed (byte* xPtr = x, yPtr = y)
{
return Avx2CompareInternal(xPtr, yPtr, x.Length);
}
}
private static unsafe bool Avx2CompareInternal(byte* xPtr, byte* yPtr, int length)
{
byte* lastAddr = xPtr + length;
byte* lastAddrMinus128 = lastAddr - 128;
const int mask = -1;
while (xPtr < lastAddrMinus128)
{
// 更換為Avx2指令集，一次加載256位
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(xPtr), Avx.LoadVector256(yPtr))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(xPtr + 32), Avx.LoadVector256(yPtr + 32))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(xPtr + 64), Avx.LoadVector256(yPtr + 64))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(xPtr + 96), Avx.LoadVector256(yPtr + 96))) != mask)
{
return false;
}
xPtr += 128;
yPtr += 128;
}
while (xPtr < lastAddr)
{
if (*xPtr != *yPtr) return false;
xPtr++;
yPtr++;
}
return true;
}
}
再來看看跑分結果。
可以看到，Avx2指令集對于
memcmp
和
Sse2
是有一定的提升的，有2+%左右的速度提升，另外相較于原本的
for
循環比較提升了86%。
SequenceCompare
那麼是不是以後我們寫比較兩個數組相等的代碼都要寫這一長串的unsafe代碼呢？其實并不是，在.NET Core時代引入了Span這個特性，這個特性就是為了能安全的直接操作記憶體；與此同時，也提供了
SequenceEquals
方法，能快速的比較兩個序列，使用也非常簡單，那究竟性能怎麼樣呢？我們上代碼，跑個分。
// 代碼非常簡單，隻需要調用System.Linq.SequenceEqual方法即可
public static bool SequenceCompare(byte[]? x, byte[]? y)
{
if (ReferenceEquals(x, y)) return true;
if (x is null || y is null) return false;
if (x.Length != y.Length) return false;
return x.SequenceEqual(y);
} 結果也是相當不錯的，比
memcmp
和SSE2的方式都要快一點，略遜于Avx2，但是它用起來很簡單，那麼它是如何做到這麼快的呢？讓我們看看它的源碼,
連結貌似也沒有什麼技巧，那是不是JIT編譯的時候有優化，給自動向量化了呢？我們将代碼複制出來，然後單獨跑了一下，再用WinDBG打開，我們可以看到确實JIT優化引入了一些自動向量化(SIMD)的操作。
總結
通過這幾種方案的對比，最推薦的用法當然就是直接使用.NET庫提供的
SequenceEquals
方法來完成比較，如果是在.NET Framework中，由于沒有這樣的優化，是以大家也可以嘗試上文中提到的SSE2等方法。
那麼大家還有什麼其它好的方式呢？歡迎檢視原文，在部落格園原帖評論區留言！
筆者水準有限，如有錯漏請批評指正 ：）
本文源碼連結
參考文獻
BenchmarkDotNet項目位址
BenchmarkDotNet幫助文檔
MSCRT庫參考
C# Interop
JVM的方法内聯