在.NET中比较两个字节数组

Question

我该如何快速完成这个任务？

当然，我可以做到：

static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
    if (a1.Length != a2.Length)
        return false;

    for (int i=0; i<a1.Length; i++)
        if (a1[i]!=a2[i])
            return false;

    return true;
}

但我正在寻找一种BCL函数或者一些经过高度优化证明的方法来解决这个问题。

java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);

它运作得很好，但似乎无法适用于x64。

请注意我的超快回答这里。

- Hafthor

---

这在于数组必须以 qword 对齐开始，这是一个很大的假设。你应该修复代码以反映这一点。 - Joe Chung

返回a1.Length == a2.Length && !a1.Where((t, i) => t != a2[i]).Any()。意思是判断两个数组a1和a2的长度是否相等，以及判断它们在每个位置上的元素是否都相等。 - alerya

对于那些需要进行大于/小于类型比较的人来说，可以查看这个答案：https://dev59.com/35_ha4cB1Zd3GeqP0o63#42502969 - Hafthor

Answer 1

你可以使用Enumerable.SequenceEqual方法。

using System;
using System.Linq;
...
var a1 = new int[] { 1, 2, 3};
var a2 = new int[] { 1, 2, 3};
var a3 = new int[] { 1, 2, 4};
var x = a1.SequenceEqual(a2); // true
var y = a1.SequenceEqual(a3); // false

如果由于某些原因您无法使用.NET 3.5，那么您的方法是可以的。
编译器\运行环境将优化您的循环，因此您不需要担心性能问题。

- aku

---

SequenceEqual比不安全的比较需要更长的处理时间吗？特别是当您进行数千次比较时？ - tcables

是的，这比不安全的比较慢了大约50倍。 - Hafthor

这确实有点冤枉，但“慢”这个词在这里用真的不合适。虽然50倍速度差听起来很糟糕，但通常你并不会比较足够的数据以使它成为一个问题。如果你确实需要比较，你需要为自己的情况进行基准测试，因为有很多原因。例如，注意不安全回答的创建者指出了7倍缓慢而不是50倍（不安全方法的速度也取决于数据的对齐方式）。在这些数字很重要的罕见情况下，P/Invoke 甚至更快。 - Selali Adobor

那么速度较慢的实现获得了超过 300 个赞？我建议钩取 msvcrt.dll，因为那是完成工作最快的方式。 - TGarrett

对于企业来说，速度并不是最重要的事情。在99%的情况下，可维护性比这些代码所节省的时间更为重要。我正在使用SequenceEqual，我的整个代码运行时间少于1毫秒。你所节约的那几微秒永远无法弥补使用P/Invoke而导致的5分钟的可读性不足。 - PRMan

Answer 2

激活P/Invoke能力！

[DllImport("msvcrt.dll", CallingConvention=CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);

static bool ByteArrayCompare(byte[] b1, byte[] b2)
{
    // Validate buffers are the same length.
    // This also ensures that the count does not exceed the length of either buffer.  
    return b1.Length == b2.Length && memcmp(b1, b2, b1.Length) == 0;
}

- plinth

---

P/Invoke yaay - 这被证明是至少在位图上最快的方法：https://dev59.com/x3I-5IYBdhLWcg3wED9V#2038515 - Erik Forbes

在这种情况下不需要固定内存地址。当使用PInvoke调用本机代码时，marshaller会自动进行固定操作。 参考链接：https://dev59.com/gHE95IYBdhLWcg3wp_kg - Mark Glasgow

尽管P/Invoke可能会引起嘘声，但从所有提出的解决方案中，它是迄今为止最快的，包括我想出来使用不安全指针大小比较的实现。在调用本机代码之前，您可以进行一些优化，包括参考相等性和比较第一个和最后一个元素。 - Josh

为什么会有嘘声？海报作者希望得到一个快速实现和优化的汇编语言比较，这是无法被超越的。我不知道如何在.NET中使用"REPE CMPSD"，除非使用P/INVOKE。 - Jason Goemaat

Nitpick: MSVCR.dll 不应该被用户代码使用。要使用 MSVCR，您需要分发运行时并使用您所分发的版本。(参见http://msdn.microsoft.com/en-us/library/abx4dbyh%28VS.80%29.aspx#sectiontoggle2和http://blogs.msdn.com/b/oldnewthing/archive/2014/04/11/10516280.aspx) - Mitch

Answer 3

Span<T> 提供了一种极具竞争力的替代方案，而无需将混乱和/或不可移植的内容添加到您自己的应用程序代码库中：

// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArraysEqual(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
    return a1.SequenceEqual(a2);
}

可以在.NET 6.0.4的实现中找到（核心部分）这里。

我已经修改了@EliArbel的要点，添加了这个方法作为SpansEqual，删除了其他人基准测试中较不重要的表演者，使用不同的数组大小运行它，输出图表，并将SpansEqual标记为基准，以便报告不同方法与SpansEqual的比较情况。

下面的数字来自结果，经过轻微编辑以删除“错误”列。

|        Method |  ByteCount |               Mean |          StdDev | Ratio | RatioSD |
|-------------- |----------- |-------------------:|----------------:|------:|--------:|
|    SpansEqual |         15 |           2.074 ns |       0.0233 ns |  1.00 |    0.00 |
|  LongPointers |         15 |           2.854 ns |       0.0632 ns |  1.38 |    0.03 |
|      Unrolled |         15 |          12.449 ns |       0.2487 ns |  6.00 |    0.13 |
| PInvokeMemcmp |         15 |           7.525 ns |       0.1057 ns |  3.63 |    0.06 |
|               |            |                    |                 |       |         |
|    SpansEqual |       1026 |          15.629 ns |       0.1712 ns |  1.00 |    0.00 |
|  LongPointers |       1026 |          46.487 ns |       0.2938 ns |  2.98 |    0.04 |
|      Unrolled |       1026 |          23.786 ns |       0.1044 ns |  1.52 |    0.02 |
| PInvokeMemcmp |       1026 |          28.299 ns |       0.2781 ns |  1.81 |    0.03 |
|               |            |                    |                 |       |         |
|    SpansEqual |    1048585 |      17,920.329 ns |     153.0750 ns |  1.00 |    0.00 |
|  LongPointers |    1048585 |      42,077.448 ns |     309.9067 ns |  2.35 |    0.02 |
|      Unrolled |    1048585 |      29,084.901 ns |     428.8496 ns |  1.62 |    0.03 |
| PInvokeMemcmp |    1048585 |      30,847.572 ns |     213.3162 ns |  1.72 |    0.02 |
|               |            |                    |                 |       |         |
|    SpansEqual | 2147483591 | 124,752,376.667 ns | 552,281.0202 ns |  1.00 |    0.00 |
|  LongPointers | 2147483591 | 139,477,269.231 ns | 331,458.5429 ns |  1.12 |    0.00 |
|      Unrolled | 2147483591 | 137,617,423.077 ns | 238,349.5093 ns |  1.10 |    0.00 |
| PInvokeMemcmp | 2147483591 | 138,373,253.846 ns | 288,447.8278 ns |  1.11 |    0.01 |

我很惊讶看到在最大数组大小的方法中，SpansEqual 没有排名第一，但差异如此微小，我认为它永远不会有影响。 在刷新后使用我的新硬件运行 .NET 6.0.4 后，SpansEqual 现在在所有数组大小上都表现出色，超过了其他所有方法。

我的系统信息：

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000
AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK=6.0.202
  [Host]     : .NET 6.0.4 (6.0.422.16404), X64 RyuJIT
  DefaultJob : .NET 6.0.4 (6.0.422.16404), X64 RyuJIT

- Joe Amenta

---

感谢你，让我现在可以向同事炫耀我在所有工作中都在使用 Span<T> 或类似的东西，这是我从未想到过的。请注意，我的翻译不会改变原意，也不含解释或其他信息。 - jokab

@Zastai 是的，{ReadOnly,}Span<T> 有自己的 SequenceEqual 版本（名称相同是因为它具有与相应的 IEnumerable<T> 扩展方法相同的契约，只是更快）。请注意，由于 ref struct 类型的限制，{ReadOnly,}Span<T> 无法使用 IEnumerable<T> 扩展方法。 - Joe Amenta

@Sentinel，System.Memory包提供了“可移植”/“慢速”的Span<T>实现，适用于netstandard1.1及以上版本（因此请使用此交互式图表查看这些版本）。目前，“快速”的Span<T>仅在.NET Core 2.1中可用，但请注意，对于特定的SequenceEqual<T>，在“快速”和“慢速”/“可移植”之间几乎没有什么区别（尽管netstandard2.0目标应该会看到轻微的改进，因为它们具有矢量化代码路径）。 - Joe Amenta

安装包 System.Memory。 - Chris Moschini

从.NET 6开始，这现在是正确的答案，Span<T>.SequenceEquals 的底层实现如果CPU支持，会有矢量化的快速路径。这将在99.9%的情况下击败所有其他方法。 - Zintom

Answer 4

.NET 4中有一种新的内置解决方案 - IStructuralEquatable

static bool ByteArrayCompare(byte[] a1, byte[] a2) 
{
    return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}

- Ohad Schneider

---

根据这篇博客文章，实际上非常慢。 - Matt Johnson-Pint

非常缓慢。比简单的for循环慢大约180倍。 - Hafthor

为什么不直接使用 StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2) 呢？这里不会出现 NullReferenceException。 - ta.speot.is

@ta.speot.is 谢谢，一行代码确实无可厚非！之前的解决方案稍微更有效率一些，因为它避免了将数组转换为IStructuralEquatable（静态已知数组是IStructuralEquatable），但确实你的建议使得该方法也能处理空参数。 - Ohad Schneider

Answer 5

编辑：现代快速的方法是使用 a1.SequenceEquals(a2)

用户gil提出了不安全的代码，从而引发了这个解决方案：

// Copyright (c) 2008-2013 Hafthor Stefansson
// Distributed under the MIT/X11 software license
// Ref: http://www.opensource.org/licenses/mit-license.php.
static unsafe bool UnsafeCompare(byte[] a1, byte[] a2) {
  unchecked {
    if(a1==a2) return true;
    if(a1==null || a2==null || a1.Length!=a2.Length)
      return false;
    fixed (byte* p1=a1, p2=a2) {
      byte* x1=p1, x2=p2;
      int l = a1.Length;
      for (int i=0; i < l/8; i++, x1+=8, x2+=8)
        if (*((long*)x1) != *((long*)x2)) return false;
      if ((l & 4)!=0) { if (*((int*)x1)!=*((int*)x2)) return false; x1+=4; x2+=4; }
      if ((l & 2)!=0) { if (*((short*)x1)!=*((short*)x2)) return false; x1+=2; x2+=2; }
      if ((l & 1)!=0) if (*((byte*)x1) != *((byte*)x2)) return false;
      return true;
    }
  }
}

这个方法尽可能地对数组进行64位比较。这种方法依赖于数组以qword对齐的事实。如果不是qword对齐，它仍然有效，但速度不如对齐的情况快。

它的性能大约比简单的`for`循环快七倍。使用J#库与原始的`for`循环效果相当。使用.SequenceEqual运行速度大约慢七倍；我认为只是因为它使用了IEnumerator.MoveNext。我想LINQ-based解决方案至少会和这个一样慢或更慢。

- Hafthor

---

不错的解决方案。但是有一个小提示：如果在比较引用a1和a2是否相等时，给a1和b1相同的数组，可能会加快运行速度。 - mmmmmmmm

.NET 4 x64版本的新测试数据：IStructualEquatable.equals慢了约180倍，SequenceEqual慢了15倍，SHA1哈希比较慢了11倍，bitconverter差不多，unsafe快了7倍，pinvoke快了11倍。很酷的是，unsafe在memcmp上只比P/Invoke慢一点点。 - Hafthor

这个链接详细解释了内存对齐的重要性。因此，一种优化方法是检查数组的对齐方式，如果两个数组的偏移量相同，则进行字节比较，直到它们都在 qword 边界上。 - Hafthor

如果a1和a2都是null，那么这不会返回错误吗？ - nawfal

@CristiDiaconescu 我将KevinDriedger的答案进行了循环化。我应该做的是在github上公开测试套件和我的结果，并在我的答案中链接到它。 - Hafthor

Answer 6

如果你不反对这样做，你可以导入J#程序集 "vjslib.dll" 并使用它的 Arrays.equals(byte[], byte[]) 方法... 不过如果有人嘲笑你，可别怪我...

---

编辑：虽然价值不大，但我使用Reflector来反编译该代码，以下是其外观：

public static bool equals(sbyte[] a1, sbyte[] a2)
{
  if (a1 == a2)
  {
    return true;
  }
  if ((a1 != null) && (a2 != null))
  {
    if (a1.Length != a2.Length)
    {
      return false;
    }
    for (int i = 0; i < a1.Length; i++)
    {
      if (a1[i] != a2[i])
      {
        return false;
      }
    }
    return true;
  }
  return false;
}

- JasonBunting

Answer 7

.NET 3.5及更高版本提供了一个名为System.Data.Linq.Binary的新公共类型，它封装了byte[]。它实现了IEquatable<Binary>接口，可以（实际上）比较两个字节数组。请注意，System.Data.Linq.Binary还具有从byte[]进行隐式转换的运算符。

MSDN文档链接：System.Data.Linq.Binary

Equals方法的Reflector反编译结果：

private bool EqualsTo(Binary binary)
{
    if (this != binary)
    {
        if (binary == null)
        {
            return false;
        }
        if (this.bytes.Length != binary.bytes.Length)
        {
            return false;
        }
        if (this.hashCode != binary.hashCode)
        {
            return false;
        }
        int index = 0;
        int length = this.bytes.Length;
        while (index < length)
        {
            if (this.bytes[index] != binary.bytes[index])
            {
                return false;
            }
            index++;
        }
    }
    return true;
}

有趣的是，只有当两个Binary对象的哈希值相同时，它们才会进入按字节比较循环。然而，这样做的代价是在构造Binary对象时计算哈希（通过使用for循环遍历数组 :-) ）。

上述实现意味着在最坏情况下，您可能需要遍历数组三次：首先计算array1的哈希值，然后计算array2的哈希值，最后（因为这是最坏情况，长度和哈希值相等）将array1中的字节与array2中的字节进行比较。

总的来说，即使System.Data.Linq.Binary内置于BCL中，我认为它并不是比较两个字节数组最快的方法 :-|。

- Milan Gardian

Answer 8

我曾发布过一个类似的问题，关于如何检查byte[]是否全为零。 （SIMD代码被击败了，因此我将其从此答案中删除。）这是我比较中最快的代码：

static unsafe bool EqualBytesLongUnrolled (byte[] data1, byte[] data2)
{
    if (data1 == data2)
        return true;
    if (data1.Length != data2.Length)
        return false;

    fixed (byte* bytes1 = data1, bytes2 = data2) {
        int len = data1.Length;
        int rem = len % (sizeof(long) * 16);
        long* b1 = (long*)bytes1;
        long* b2 = (long*)bytes2;
        long* e1 = (long*)(bytes1 + len - rem);

        while (b1 < e1) {
            if (*(b1) != *(b2) || *(b1 + 1) != *(b2 + 1) || 
                *(b1 + 2) != *(b2 + 2) || *(b1 + 3) != *(b2 + 3) ||
                *(b1 + 4) != *(b2 + 4) || *(b1 + 5) != *(b2 + 5) || 
                *(b1 + 6) != *(b2 + 6) || *(b1 + 7) != *(b2 + 7) ||
                *(b1 + 8) != *(b2 + 8) || *(b1 + 9) != *(b2 + 9) || 
                *(b1 + 10) != *(b2 + 10) || *(b1 + 11) != *(b2 + 11) ||
                *(b1 + 12) != *(b2 + 12) || *(b1 + 13) != *(b2 + 13) || 
                *(b1 + 14) != *(b2 + 14) || *(b1 + 15) != *(b2 + 15))
                return false;
            b1 += 16;
            b2 += 16;
        }

        for (int i = 0; i < rem; i++)
            if (data1 [len - 1 - i] != data2 [len - 1 - i])
                return false;

        return true;
    }
}

在两个256MB字节数组上进行测量：

UnsafeCompare                           : 86,8784 ms
EqualBytesSimd                          : 71,5125 ms
EqualBytesSimdUnrolled                  : 73,1917 ms
EqualBytesLongUnrolled                  : 39,8623 ms

- ArekBulski

---

我确认。我也运行了测试。这比使用不安全的memcmp调用的答案更快。 - ujeenator

@AmberdeBlack 你确定吗？你测试过使用小型数组了吗？ - Zar Shardan

@ArekBulski，您确定这比memcmp更快吗？因为我的测试结果显示相反。 - Zar Shardan

我在这个方案和 memcmp 之间得到了几乎相同的性能，因此完全托管的解决方案得到一个加分。 - Mike Marynowski

使用 ulong* 和 long* 之间的性能有差异吗？ - tigrou

Answer 9

 using System.Linq; //SequenceEqual

 byte[] ByteArray1 = null;
 byte[] ByteArray2 = null;

 ByteArray1 = MyFunct1();
 ByteArray2 = MyFunct2();

 if (ByteArray1.SequenceEqual<byte>(ByteArray2) == true)
 {
    MessageBox.Show("Match");
 }
 else
 {
   MessageBox.Show("Don't match");
 }

- user565710

---

这就是我一直在使用的。但是，听起来像是一个顺序比较，你可以使用简单的循环来完成，因此速度不是很快。反射它并查看实际执行的操作会很好。从名称来看，它并不花哨。 - Sergey Akopov

是的，但已经在被接受的答案中提到了。顺便说一下，你可以在那里删除类型规范。 - nawfal

Answer 10

再加一个吧！

最近微软发布了一个特殊的 NuGet 包，System.Runtime.CompilerServices.Unsafe。它很特殊，因为它是用IL编写的，并提供了 C# 中没有直接可用的低级别功能。

其中一个方法 Unsafe.As<T>(object) 允许将任何引用类型强制转换为另一个引用类型，并跳过任何安全检查。这通常是一个非常不好的想法，但如果两种类型具有相同的结构，那么它可以工作。因此，我们可以使用这个方法将 byte[] 转换为 long[]：

bool CompareWithUnsafeLibrary(byte[] a1, byte[] a2)
{
    if (a1.Length != a2.Length) return false;

    var longSize = (int)Math.Floor(a1.Length / 8.0);
    var long1 = Unsafe.As<long[]>(a1);
    var long2 = Unsafe.As<long[]>(a2);

    for (var i = 0; i < longSize; i++)
    {
        if (long1[i] != long2[i]) return false;
    }

    for (var i = longSize * 8; i < a1.Length; i++)
    {
        if (a1[i] != a2[i]) return false;
    }

    return true;
}

请注意，long1.Length仍将返回原始数组的长度，因为它存储在数组的内存结构中的字段中。

该方法不像这里演示的其他方法那样快，但比朴素方法快得多，不使用不安全的代码、P/Invoke或固定，而且实现相当简单（在我看来）。以下是我的机器上的一些BenchmarkDotNet结果：

BenchmarkDotNet=v0.10.3.0, OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4870HQ CPU 2.50GHz, ProcessorCount=8
Frequency=2435775 Hz, Resolution=410.5470 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  DefaultJob : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0

                 Method |          Mean |    StdDev |
----------------------- |-------------- |---------- |
          UnsafeLibrary |   125.8229 ns | 0.3588 ns |
          UnsafeCompare |    89.9036 ns | 0.8243 ns |
           JSharpEquals | 1,432.1717 ns | 1.3161 ns |
 EqualBytesLongUnrolled |    43.7863 ns | 0.8923 ns |
              NewMemCmp |    65.4108 ns | 0.2202 ns |
            ArraysEqual |   910.8372 ns | 2.6082 ns |
          PInvokeMemcmp |    52.7201 ns | 0.1105 ns |

我还创建了一个包含所有测试的代码片段。

- Eli Arbel

---

它不使用unsafe关键字，但是通过使用System.Runtime.CompilerServices.Unsafe仍然调用了不安全的代码。 - Paulo Zemek