.NET如何快速比較兩個byte數組是否相等

• 2022 年 4 月 6 日
• 筆記
• .NET, c#

前言

之前在群裏面有群友問過一個這樣的問題，在.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不移動它
        // 更多詳情請看 //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代碼，而其它編程語言平台或多或少支持都不是很完美。

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的方法內聯

.NET SIMD API

SSE2 Intrinsics各函數介紹

Checking equality for two byte arrays