教你使用.NET快速比较两个byte数组是否相等_实用技巧_

前言

之前在群里面有群友问过一个这样的问题，在.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(); // 我们需要一些评测内存结果信息 // 并且生成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关键字 // 项目文件中也要加入true来允许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架构上提供

提示： 本文由神整理自网络，如有侵权请联系本站删除！
本站声明：
1、本站所有资源均来源于互联网，不保证100%完整、不提供任何技术支持；
2、本站所发布的文章以及附件仅限用于学习和研究目的;不得将用于商业或者非法用途；否则由此产生的法律后果，本站概不负责！

上一篇：详解ASP.NET Core高性能服务器HTTP.SYS_实用技巧_

下一篇：ASP.NET MVC自定义授权过滤器_实用技巧_