教你使用.NET快速比較兩個byte陣列是否相等

2022-04-06 16:00:18

前言

之前在群裡面有群友問過一個這樣的問題，在.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)
            if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(xPtr + 32), Sse2.LoadVector128(yPtr + 32))) != mask)
            if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(xPtr + 48), Sse2.LoadVector128(yPtr + 48))) != mask)
            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)
            if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(xPtr + 64), Avx.LoadVector256(yPtr + 64))) != mask)
            if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(xPtr + 96), Avx.LoadVector256(yPtr + 96))) != mask)
            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);
}