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

a

aku

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，那么您的方法是可以的。编译器\运行时环境将优化您的循环，因此您无需担心性能。

但是，SequenceEqual 的处理时间不会比不安全的比较长吗？尤其是当您进行 1000 次比较时？

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

这真的是在这里起死回生，但在这里用慢真的是一个不好的词。慢 50 倍听起来很糟糕，但您通常不会比较足够的数据来产生影响，如果是这样，出于无数原因，您确实需要针对自己的情况进行基准测试。例如，注意不安全答案的创建者注意到慢了 7 倍，而不是慢了 50 倍（不安全方法的速度还取决于数据的对齐方式）。在这些数字很重要的极少数情况下，P/Invoke 甚至更快。

所以较慢的实现获得了超过 300 个赞？我建议挂钩 msvcrt.dll，因为这将是完成工作的最快方法。

对企业来说，最快并不是最重要的事情。可维护性比在 99% 的情况下节省的代码要“快”得多。我正在使用 SequenceEqual，我的整个代码小于 1ms。您节省的那些 µs 永远不会导致 P/Invoke 缺乏可读性的 5 分钟。

P

Peter Mortensen

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;
}

P/Invoke 是的 - 这至少在位图上被证明是最快的：stackoverflow.com/questions/2031217/…

在这种情况下，不需要固定。编组器在使用 PInvoke 调用本机代码时执行自动固定。参考：stackoverflow.com/questions/2218444/…

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

为什么是嘘声？海报想要一个快速的实现和一个优化的汇编语言比较无法被击败。我不知道如何在没有 P/INVOKE 的情况下从 .NET 中获取“REPE CMPSD”。

Nitpick：用户代码不应使用 MSVCR.dll。要使用 MSVCR，您必须使用您分发的版本分发运行时。（msdn.microsoft.com/en-us/library/… 和 blogs.msdn.com/b/oldnewthing/archive/2014/04/11/10516280.aspx）

O

Ohad Schneider

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

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

根据 this blog post，这实际上非常慢。

疯狂慢。比简单的 for 循环慢大约 180 倍。

为什么不只是 StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2)。这里没有NullReferenceException。

@ta.speot.is 谢谢，不能与一个班轮争论！先前的解决方案效率稍高一些，因为它将强制转换保存到 IStructuralEquatable （数组静态已知为 IStructuralEquatable），但确实您的建议使该方法也适用于空参数。

J

Joe Amenta

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

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

可以在 here 中找到 .NET 6.0.4 的（实现的）实现。

我有 revised @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 在 max-array-size 方法中没有名列前茅，但差异是如此之小，以至于我认为这无关紧要。~~ 刷新到使用我的较新硬件在 .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

我从没想过我会在我所做的所有事情中使用 Span 或接近它的东西。多亏了你，我现在可以向我的同事吹嘘这件事了。

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

@Sentinel System.Memory 包具有 netstandard1.1 及更高版本的“便携式”/“慢速”Span<T> 实现（因此请与 this interactive chart 一起玩，看看它们是什么）。 “Fast”Span<T> 目前仅在 .NET Core 2.1 中可用，但请注意，对于 SequenceEqual<T>，“fast”和“slow”/“portable”之间应该几乎没有区别（尽管 {7 } 目标应该会看到轻微的改进，因为它们具有矢量化代码路径）。

安装包 system.memory

这现在基本上是 .NET 6 及以后的正确答案，如果 CPU 支持，Span<T>.SequenceEquals 的底层实现具有矢量化快速路径。这将在 99.9% 的情况下击败所有其他方法。

G

Glenn Slayden

用户 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) {
  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 循环执行大约七个计时器。使用与原始 for 循环等效的 J# 库。使用 .SequenceEqual 会慢七倍左右；我认为只是因为它使用的是 IEnumerator.MoveNext。我想基于 LINQ 的解决方案至少会那么慢或更糟。

很好的解决方案。但是一个（小）提示：如果引用 a1 和 a2 相等，则比较可能会加快速度，如果为 a1 和 b1 提供相同的数组。

.NET 4 x64 版本上的新测试数据：IStructualEquatable.equals 慢 180 倍，SequenceEqual 慢 15 倍，SHA1 哈希比较慢 11 倍，bitconverter 相同，不安全快 7 倍，pinvoke 快 11 倍。很酷，不安全只比 memcmp 上的 P/Invoke 慢一点。

此链接提供了有关内存对齐为何重要的详细信息ibm.com/developerworks/library/pa-dalign - 因此，优化可能是检查对齐，如果两个数组的对齐量相同，则进行字节比较，直到它们都在 qword 边界上。

当 a1 和 a2 都为空时，这不会给出错误吗？

@CristiDiaconescu 我循环了 KevinDriedger 的回答。我可能应该做的是在 github 上提供测试套件和我的结果，并在我的答案中链接到它。

J

Jason Bunting

如果您不反对这样做，您可以导入 J# 程序集“vjslib.dll”并使用它的 Arrays.equals(byte[], byte[]) method...

如果有人嘲笑你，请不要怪我……

编辑：对于它的价值，我使用 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;
}

M

Milan Gardian

.NET 3.5 和更高版本有一个新的公共类型 System.Data.Linq.Binary，它封装了 byte[]。它实现了（实际上）比较两个字节数组的 IEquatable<Binary>。请注意，System.Data.Linq.Binary 还具有来自 byte[] 的隐式转换运算符。

MSDN 文档：System.Data.Linq.Binary

Equals方法的反射器反编译：

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 循环遍历数组:-)）。

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

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

A

ArekBulski

I posted 关于检查 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

我确定。我也进行了测试。这比使用 memcmp 不安全调用的答案要快。

@AmberdeBlack 你确定吗？您是否使用微型阵列进行了测试？

@ArekBulski 你确定这比 memcmp 快，因为我的测试显示不是这样吗？

我在这和 memcmp 之间获得了几乎相同的性能，因此 +1 是完全托管的解决方案。

使用 ulong* 和 long* 在性能上是否存在差异？

u

user565710

 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");
 }

这就是我一直在使用的。但它嗯......听起来像一个顺序比较，否则你会使用一个简单的循环来做，因此不是很快。反映它并看看实际在做什么会很好。从名字上看，并没有什么花哨的。

是的，但已在接受的答案中提到。顺便说一句，您可以在那里删除类型规范。

E

Eli Arbel

让我们再添加一个！

最近微软发布了一个特殊的 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 或 pinning，并且实现非常简单 (IMO)。以下是我机器上的一些 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 |

我还创建了一个 gist with all the tests。

它不使用 unsafe 关键字，但它仍然通过使用 System.Runtime.CompilerServices.Unsafe 调用不安全代码

M

Mr Anderson

我开发了一种方法，在我的 PC 上稍微优于 memcmp()（plinth 的答案）和非常轻微的 EqualBytesLongUnrolled()（Arek Bulski 的答案）。基本上，它将循环展开 4 而不是 8。

2019 年 3 月 30 日更新：

从 .NET core 3.0 开始，我们支持 SIMD！

此解决方案在我的 PC 上速度最快：

#if NETCOREAPP3_0
using System.Runtime.Intrinsics.X86;
#endif
…

public static unsafe bool Compare(byte[] arr0, byte[] arr1)
{
    if (arr0 == arr1)
    {
        return true;
    }
    if (arr0 == null || arr1 == null)
    {
        return false;
    }
    if (arr0.Length != arr1.Length)
    {
        return false;
    }
    if (arr0.Length == 0)
    {
        return true;
    }
    fixed (byte* b0 = arr0, b1 = arr1)
    {
#if NETCOREAPP3_0
        if (Avx2.IsSupported)
        {
            return Compare256(b0, b1, arr0.Length);
        }
        else if (Sse2.IsSupported)
        {
            return Compare128(b0, b1, arr0.Length);
        }
        else
#endif
        {
            return Compare64(b0, b1, arr0.Length);
        }
    }
}
#if NETCOREAPP3_0
public static unsafe bool Compare256(byte* b0, byte* b1, int length)
{
    byte* lastAddr = b0 + length;
    byte* lastAddrMinus128 = lastAddr - 128;
    const int mask = -1;
    while (b0 < lastAddrMinus128) // unroll the loop so that we are comparing 128 bytes at a time.
    {
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0), Avx.LoadVector256(b1))) != mask)
        {
            return false;
        }
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 32), Avx.LoadVector256(b1 + 32))) != mask)
        {
            return false;
        }
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 64), Avx.LoadVector256(b1 + 64))) != mask)
        {
            return false;
        }
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 96), Avx.LoadVector256(b1 + 96))) != mask)
        {
            return false;
        }
        b0 += 128;
        b1 += 128;
    }
    while (b0 < lastAddr)
    {
        if (*b0 != *b1) return false;
        b0++;
        b1++;
    }
    return true;
}
public static unsafe bool Compare128(byte* b0, byte* b1, int length)
{
    byte* lastAddr = b0 + length;
    byte* lastAddrMinus64 = lastAddr - 64;
    const int mask = 0xFFFF;
    while (b0 < lastAddrMinus64) // unroll the loop so that we are comparing 64 bytes at a time.
    {
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0), Sse2.LoadVector128(b1))) != mask)
        {
            return false;
        }
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 16), Sse2.LoadVector128(b1 + 16))) != mask)
        {
            return false;
        }
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 32), Sse2.LoadVector128(b1 + 32))) != mask)
        {
            return false;
        }
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 48), Sse2.LoadVector128(b1 + 48))) != mask)
        {
            return false;
        }
        b0 += 64;
        b1 += 64;
    }
    while (b0 < lastAddr)
    {
        if (*b0 != *b1) return false;
        b0++;
        b1++;
    }
    return true;
}
#endif
public static unsafe bool Compare64(byte* b0, byte* b1, int length)
{
    byte* lastAddr = b0 + length;
    byte* lastAddrMinus32 = lastAddr - 32;
    while (b0 < lastAddrMinus32) // unroll the loop so that we are comparing 32 bytes at a time.
    {
        if (*(ulong*)b0 != *(ulong*)b1) return false;
        if (*(ulong*)(b0 + 8) != *(ulong*)(b1 + 8)) return false;
        if (*(ulong*)(b0 + 16) != *(ulong*)(b1 + 16)) return false;
        if (*(ulong*)(b0 + 24) != *(ulong*)(b1 + 24)) return false;
        b0 += 32;
        b1 += 32;
    }
    while (b0 < lastAddr)
    {
        if (*b0 != *b1) return false;
        b0++;
        b1++;
    }
    return true;
}

我对 .NET 462 的测量结果与 NETCORE 不同：

比较两个长度为 0 的数组时，代码会崩溃，因为 pinning 返回 null。

memcmp 不仅仅是一个股权比较器。它提供了对象更大或更小的信息。您可以为此目的采用您的算法并检查性能吗？

它比 Span 和 memcpy 快吗？

@silkfire 在 .NET core 3 和现代 CPU 上，大型阵列的速度应该快 2-3 倍。

P

Peter Mortensen

我会使用不安全的代码并运行 for 循环比较 Int32 指针。

也许您还应该考虑检查数组是否为非空。

P

Peter Mortensen

如果您查看 .NET 如何处理 string.Equals，您会发现它使用了一个名为 EqualsHelper 的私有方法，该方法具有“不安全”的指针实现。 .NET Reflector 是您的朋友，可以了解内部工作的方式。

这可以用作字节数组比较的模板，我在博文 Fast byte array comparison in C# 中做了一个实现。我还做了一些基本的基准测试，看看什么时候安全的实现比不安全的更快。

也就是说，除非您真的需要出色的性能，否则我会进行简单的 fr 循环比较。

M

Mahmoud Al-Qudsi

对于那些关心订单的人（即，希望您的 memcmp 返回一个 int，而不是什么都没有），.NET Core 3.0（可能是 .NET Standard 2.1 aka .NET 5.0）will include a Span.SequenceCompareTo(...) extension method（加上Span.SequenceEqualTo)，可用于比较两个 ReadOnlySpan<T> 实例 (where T: IComparable<T>)。

在 the original GitHub proposal 中，讨论包括与跳转表计算的方法比较、将 byte[] 读取为 long[]、SIMD 使用以及对 CLR 实现的 memcmp 的 p/invoke。

展望未来，这应该是您比较字节数组或字节范围的首选方法（对于您的 .NET Standard 2.1 API 应该使用 Span<byte> 而不是 byte[]），并且它足够快，您不应该再关心优化它（不，尽管名称相似，但它的性能不如可怕的 Enumerable.SequenceEqual）。

#if NETCOREAPP3_0_OR_GREATER
// Using the platform-native Span<T>.SequenceEqual<T>(..)
public static int Compare(byte[] range1, int offset1, byte[] range2, int offset2, int count)
{
    var span1 = range1.AsSpan(offset1, count);
    var span2 = range2.AsSpan(offset2, count);

    return span1.SequenceCompareTo(span2);
    // or, if you don't care about ordering
    // return span1.SequenceEqual(span2);
}
#else
// The most basic implementation, in platform-agnostic, safe C#
public static bool Compare(byte[] range1, int offset1, byte[] range2, int offset2, int count)
{
    // Working backwards lets the compiler optimize away bound checking after the first loop
    for (int i = count - 1; i >= 0; --i)
    {
        if (range1[offset1 + i] != range2[offset2 + i])
        {
            return false;
        }
    }

    return true;
}
#endif

J

John Leidegren

我使用未附加调试器的附加程序 .net 4.7 版本进行了一些测量。我认为人们一直在使用错误的指标，因为如果您关心速度，那么您所关心的就是确定两个字节数组是否相等需要多长时间。即以字节为单位的吞吐量。

StructuralComparison :              4.6 MiB/s
for                  :            274.5 MiB/s
ToUInt32             :            263.6 MiB/s
ToUInt64             :            474.9 MiB/s
memcmp               :           8500.8 MiB/s

如您所见，没有比 memcmp 更好的方法了，而且速度要快几个数量级。一个简单的 for 循环是第二好的选择。我仍然无法理解为什么 Microsoft 不能简单地包含 Buffer.Compare 方法。

[程序.cs]：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace memcmp
{
    class Program
    {
        static byte[] TestVector(int size)
        {
            var data = new byte[size];
            using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
            {
                rng.GetBytes(data);
            }
            return data;
        }

        static TimeSpan Measure(string testCase, TimeSpan offset, Action action, bool ignore = false)
        {
            var t = Stopwatch.StartNew();
            var n = 0L;
            while (t.Elapsed < TimeSpan.FromSeconds(10))
            {
                action();
                n++;
            }
            var elapsed = t.Elapsed - offset;
            if (!ignore)
            {
                Console.WriteLine($"{testCase,-16} : {n / elapsed.TotalSeconds,16:0.0} MiB/s");
            }
            return elapsed;
        }

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

        static void Main(string[] args)
        {
            // how quickly can we establish if two sequences of bytes are equal?

            // note that we are testing the speed of different comparsion methods

            var a = TestVector(1024 * 1024); // 1 MiB
            var b = (byte[])a.Clone();

            // was meant to offset the overhead of everything but copying but my attempt was a horrible mistake... should have reacted sooner due to the initially ridiculous throughput values...
            // Measure("offset", new TimeSpan(), () => { return; }, ignore: true);
            var offset = TimeZone.Zero

            Measure("StructuralComparison", offset, () =>
            {
                StructuralComparisons.StructuralEqualityComparer.Equals(a, b);
            });

            Measure("for", offset, () =>
            {
                for (int i = 0; i < a.Length; i++)
                {
                    if (a[i] != b[i]) break;
                }
            });

            Measure("ToUInt32", offset, () =>
            {
                for (int i = 0; i < a.Length; i += 4)
                {
                    if (BitConverter.ToUInt32(a, i) != BitConverter.ToUInt32(b, i)) break;
                }
            });

            Measure("ToUInt64", offset, () =>
            {
                for (int i = 0; i < a.Length; i += 8)
                {
                    if (BitConverter.ToUInt64(a, i) != BitConverter.ToUInt64(b, i)) break;
                }
            });

            Measure("memcmp", offset, () =>
            {
                memcmp(a, b, a.Length);
            });
        }
    }
}

memcmp 调用是否依赖于与 Visual C++ 相关的 msvc 或者它也可以使用 clang 吗？

只要有一些元数据可以绑定到它，您几乎可以导入任何函数。我使用 msvcrt 的原因是它随 CLR 一起提供。但它并没有什么特别之处。您可以DllImport任何东西。只需确保编组和调用约定匹配即可。

Z

Zar Shardan

找不到我完全满意的解决方案（合理的性能，但没有不安全的代码/pinvoke）所以我想出了这个，没有什么真正的原创，但有效：

    /// <summary>
    /// 
    /// </summary>
    /// <param name="array1"></param>
    /// <param name="array2"></param>
    /// <param name="bytesToCompare"> 0 means compare entire arrays</param>
    /// <returns></returns>
    public static bool ArraysEqual(byte[] array1, byte[] array2, int bytesToCompare = 0)
    {
        if (array1.Length != array2.Length) return false;

        var length = (bytesToCompare == 0) ? array1.Length : bytesToCompare;
        var tailIdx = length - length % sizeof(Int64);

        //check in 8 byte chunks
        for (var i = 0; i < tailIdx; i += sizeof(Int64))
        {
            if (BitConverter.ToInt64(array1, i) != BitConverter.ToInt64(array2, i)) return false;
        }

        //check the remainder of the array, always shorter than 8 bytes
        for (var i = tailIdx; i < length; i++)
        {
            if (array1[i] != array2[i]) return false;
        }

        return true;
    }

与此页面上的其他一些解决方案相比的性能：

简单循环：19837 滴答，1.00

*BitConverter：4886 滴答，4.06

UnsafeCompare：1636 滴答，12.12

EqualBytesLongUnrolled：637 滴答，31.09

P/Invoke memcmp：369 滴答，53.67

在 linqpad 中测试，1000000 字节相同的数组（最坏的情况），每个 500 次迭代。

是的，我注意到在 stackoverflow.com/a/1445280/4489 的评论中，我的测试表明这实际上比我在原始问题中的简单 for 循环慢一点。

你确定吗？在我的测试中它快了 4 倍？尽管如此，没有什么比好的旧本机代码更好的了，即使有编组开销。

M

Motlicek Petr

似乎 EqualBytesLongUnrolled 是上述建议中最好的。

跳过的方法（Enumerable.SequenceEqual、StructuralComparisons.StructuralEqualityComparer.Equals）不是慢的。在 265MB 阵列上，我测量了这个：

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-3770 CPU 3.40GHz, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0

Type=CompareMemoriesBenchmarks  Mode=Throughput  

                 Method |      Median |    StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
             NewMemCopy |  30.0443 ms | 1.1880 ms |   1.00 |      0.00 |
 EqualBytesLongUnrolled |  29.9917 ms | 0.7480 ms |   0.99 |      0.04 |
          msvcrt_memcmp |  30.0930 ms | 0.2964 ms |   1.00 |      0.03 |
          UnsafeCompare |  31.0520 ms | 0.7072 ms |   1.03 |      0.04 |
       ByteArrayCompare | 212.9980 ms | 2.0776 ms |   7.06 |      0.25 |

OS=Windows
Processor=?, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=CORE, Arch=64-bit ? [RyuJIT]
GC=Concurrent Workstation
dotnet cli version: 1.0.0-preview2-003131

Type=CompareMemoriesBenchmarks  Mode=Throughput  

                 Method |      Median |    StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
             NewMemCopy |  30.1789 ms | 0.0437 ms |   1.00 |      0.00 |
 EqualBytesLongUnrolled |  30.1985 ms | 0.1782 ms |   1.00 |      0.01 |
          msvcrt_memcmp |  30.1084 ms | 0.0660 ms |   1.00 |      0.00 |
          UnsafeCompare |  31.1845 ms | 0.4051 ms |   1.03 |      0.01 |
       ByteArrayCompare | 212.0213 ms | 0.1694 ms |   7.03 |      0.01 |

K

Kevin Driedger

为了比较短字节数组，以下是一个有趣的技巧：

if(myByteArray1.Length != myByteArray2.Length) return false;
if(myByteArray1.Length == 8)
   return BitConverter.ToInt64(myByteArray1, 0) == BitConverter.ToInt64(myByteArray2, 0); 
else if(myByteArray.Length == 4)
   return BitConverter.ToInt32(myByteArray2, 0) == BitConverter.ToInt32(myByteArray2, 0);

那么我可能会陷入问题中列出的解决方案。

对此代码进行性能分析会很有趣。

诠释我=0； for(;i

Z

Zapnologica

我在这里没有看到很多 linq 解决方案。

我不确定性能影响，但我通常坚持使用 linq 作为经验法则，然后在必要时进行优化。

public bool CompareTwoArrays(byte[] array1, byte[] array2)
 {
   return !array1.Where((t, i) => t != array2[i]).Any();
 }

请注意，这仅在它们是相同大小的数组时才有效。扩展可能看起来像这样

public bool CompareTwoArrays(byte[] array1, byte[] array2)
 {
   if (array1.Length != array2.Length) return false;
   return !array1.Where((t, i) => t != array2[i]).Any();
 }

问题的重点是问题中发布的功能更快的解决方案。

M

Mirko Klemm

我想到了许多显卡内置的块传输加速方法。但是你必须逐字节复制所有数据，所以如果你不想在非托管和硬件相关的代码中实现整个逻辑部分，这对你没有多大帮助......

与上面显示的方法类似的另一种优化方法是从一开始就将尽可能多的数据存储在 long[] 而不是 byte[] 中，例如，如果您从二进制文件中顺序读取它，或者，如果您使用内存映射文件，则将数据读入 long[] 或单个 long 值。然后，您的比较循环只需要对包含相同数据量的 byte[] 进行的迭代次数的 1/8。这是您需要比较的时间和频率与需要以逐字节方式访问数据的时间和频率的问题，例如，在 API 调用中将其用作期望的方法中的参数一个字节[]。最后，您只能判断您是否真的了解用例...

接受的答案将字节缓冲区重新转换为长缓冲区并按照您的描述进行比较。

C

Casey Chester

我选择了一个受 ArekBulski 发布的 EqualBytesLongUnrolled 方法启发的解决方案，并进行了额外的优化。在我的例子中，数组中的数组差异往往靠近数组的尾部。在测试中，我发现在大型数组的情况下，能够以相反的顺序比较数组元素使该解决方案与基于 memcmp 的解决方案相比具有巨大的性能提升。这是解决方案：

public enum CompareDirection { Forward, Backward }

private static unsafe bool UnsafeEquals(byte[] a, byte[] b, CompareDirection direction = CompareDirection.Forward)
{
    // returns when a and b are same array or both null
    if (a == b) return true;

    // if either is null or different lengths, can't be equal
    if (a == null || b == null || a.Length != b.Length)
        return false;

    const int UNROLLED = 16;                // count of longs 'unrolled' in optimization
    int size = sizeof(long) * UNROLLED;     // 128 bytes (min size for 'unrolled' optimization)
    int len = a.Length;
    int n = len / size;         // count of full 128 byte segments
    int r = len % size;         // count of remaining 'unoptimized' bytes

    // pin the arrays and access them via pointers
    fixed (byte* pb_a = a, pb_b = b)
    {
        if (r > 0 && direction == CompareDirection.Backward)
        {
            byte* pa = pb_a + len - 1;
            byte* pb = pb_b + len - 1;
            byte* phead = pb_a + len - r;
            while(pa >= phead)
            {
                if (*pa != *pb) return false;
                pa--;
                pb--;
            }
        }

        if (n > 0)
        {
            int nOffset = n * size;
            if (direction == CompareDirection.Forward)
            {
                long* pa = (long*)pb_a;
                long* pb = (long*)pb_b;
                long* ptail = (long*)(pb_a + nOffset);
                while (pa < ptail)
                {
                    if (*(pa + 0) != *(pb + 0) || *(pa + 1) != *(pb + 1) ||
                        *(pa + 2) != *(pb + 2) || *(pa + 3) != *(pb + 3) ||
                        *(pa + 4) != *(pb + 4) || *(pa + 5) != *(pb + 5) ||
                        *(pa + 6) != *(pb + 6) || *(pa + 7) != *(pb + 7) ||
                        *(pa + 8) != *(pb + 8) || *(pa + 9) != *(pb + 9) ||
                        *(pa + 10) != *(pb + 10) || *(pa + 11) != *(pb + 11) ||
                        *(pa + 12) != *(pb + 12) || *(pa + 13) != *(pb + 13) ||
                        *(pa + 14) != *(pb + 14) || *(pa + 15) != *(pb + 15)
                    )
                    {
                        return false;
                    }
                    pa += UNROLLED;
                    pb += UNROLLED;
                }
            }
            else
            {
                long* pa = (long*)(pb_a + nOffset);
                long* pb = (long*)(pb_b + nOffset);
                long* phead = (long*)pb_a;
                while (phead < pa)
                {
                    if (*(pa - 1) != *(pb - 1) || *(pa - 2) != *(pb - 2) ||
                        *(pa - 3) != *(pb - 3) || *(pa - 4) != *(pb - 4) ||
                        *(pa - 5) != *(pb - 5) || *(pa - 6) != *(pb - 6) ||
                        *(pa - 7) != *(pb - 7) || *(pa - 8) != *(pb - 8) ||
                        *(pa - 9) != *(pb - 9) || *(pa - 10) != *(pb - 10) ||
                        *(pa - 11) != *(pb - 11) || *(pa - 12) != *(pb - 12) ||
                        *(pa - 13) != *(pb - 13) || *(pa - 14) != *(pb - 14) ||
                        *(pa - 15) != *(pb - 15) || *(pa - 16) != *(pb - 16)
                    )
                    {
                        return false;
                    }
                    pa -= UNROLLED;
                    pb -= UNROLLED;
                }
            }
        }

        if (r > 0 && direction == CompareDirection.Forward)
        {
            byte* pa = pb_a + len - r;
            byte* pb = pb_b + len - r;
            byte* ptail = pb_a + len;
            while(pa < ptail)
            {
                if (*pa != *pb) return false;
                pa++;
                pb++;
            }
        }
    }

    return true;
}

M

Markus Olsson

抱歉，如果您正在寻找一种托管方式，那么您已经在正确地执行此操作，并且据我所知，BCL 中没有内置方法可以执行此操作。

您应该添加一些初始空检查，然后就像在 BCL 中一样重用它。

你写的时候是对的，但是在 2010 年（.NET 4.0）出现了 BCL 方法，请参阅 Ohad Schneider 的回答。在提出问题时，.NET 3.5 有 Linq（请参阅 aku 的回答）。

J

James Curran

这几乎可以肯定比这里给出的任何其他版本都要慢得多，但写起来很有趣。

static bool ByteArrayEquals(byte[] a1, byte[] a2) 
{
    return a1.Zip(a2, (l, r) => l == r).All(x => x);
}

A

Antidisestablishmentarianism

这与其他类似，但这里的区别在于，没有下降到我可以一次检查的下一个最高字节数，例如，如果我有 63 个字节（在我的 SIMD 示例中），我可以检查第一个字节的相等性32 字节，然后是最后 32 字节，这比检查 32 字节、16 字节、8 字节等要快。您输入的第一个检查是您需要比较所有字节的唯一检查。

这在我的测试中确实名列前茅，但只是一根头发。

以下代码正是我在 airbreather/ArrayComparePerf.cs 中测试它的方式。

public unsafe bool SIMDNoFallThrough()    #requires  System.Runtime.Intrinsics.X86
{
    if (a1 == null || a2 == null)
        return false;

    int length0 = a1.Length;

    if (length0 != a2.Length) return false;

    fixed (byte* b00 = a1, b01 = a2)
    {
        byte* b0 = b00, b1 = b01, last0 = b0 + length0, last1 = b1 + length0, last32 = last0 - 31;

        if (length0 > 31)
        {
            while (b0 < last32)
            {
                if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0), Avx.LoadVector256(b1))) != -1)
                    return false;
                b0 += 32;
                b1 += 32;
            }
            return Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(last0 - 32), Avx.LoadVector256(last1 - 32))) == -1;
        }

        if (length0 > 15)
        {
            if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0), Sse2.LoadVector128(b1))) != 65535)
                return false;
            return Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(last0 - 16), Sse2.LoadVector128(last1 - 16))) == 65535;
        }

        if (length0 > 7)
        {
            if (*(ulong*)b0 != *(ulong*)b1)
                return false;
            return *(ulong*)(last0 - 8) == *(ulong*)(last1 - 8);
        }

        if (length0 > 3)
        {
            if (*(uint*)b0 != *(uint*)b1)
                return false;
            return *(uint*)(last0 - 4) == *(uint*)(last1 - 4);
        }

        if (length0 > 1)
        {
            if (*(ushort*)b0 != *(ushort*)b1)
                return false;
            return *(ushort*)(last0 - 2) == *(ushort*)(last1 - 2);
        }

        return *b0 == *b1;
    }
}

如果不首选 SIMD，则将相同的方法应用于现有的 LongPointers 算法：

public unsafe bool LongPointersNoFallThrough()
{
    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;
        if ((l & 8) != 0)
        {
            for (int i = 0; i < l / 8; i++, x1 += 8, x2 += 8)
                if (*(long*)x1 != *(long*)x2) return false;
            return *(long*)(x1 + (l - 8)) == *(long*)(x2 + (l - 8));
        }
        if ((l & 4) != 0)
        {
            if (*(int*)x1 != *(int*)x2) return false; x1 += 4; x2 += 4;
            return *(int*)(x1 + (l - 4)) == *(int*)(x2 + (l - 4));
        }
        if ((l & 2) != 0)
        {
            if (*(short*)x1 != *(short*)x2) return false; x1 += 2; x2 += 2;
            return *(short*)(x1 + (l - 2)) == *(short*)(x2 + (l - 2));
        }
        return *x1 == *x2;
    }
}

M

Magnilex

使用 SequenceEquals 进行比较。

K

Kris Dimitrov

如果您正在寻找一个非常快速的字节数组相等比较器，我建议您看看这篇 STSdb 实验室文章：Byte array equality comparer. 它提供了一些最快的 byte[] 数组相等比较实现，这些实现经过了性能测试和总结。

您还可以专注于这些实现：

BigEndianByteArrayComparer - 从左到右的快速字节[] 数组比较器 (BigEndian) BigEndianByteArrayEqualityComparer - - 从左到右 (BigEndian) 的快速字节[] 相等比较器 LittleEndianByteArrayComparer - 从右到左的快速字节[] 数组比较器 ( LittleEndian) LittleEndianByteArrayEqualityComparer - 从右到左的快速字节 [] 相等比较器 (LittleEndian)

P

Peter Mortensen

简短的回答是这样的：

    public bool Compare(byte[] b1, byte[] b2)
    {
        return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
    }

通过这种方式，您可以使用优化的 .NET 字符串比较来进行字节数组比较，而无需编写不安全的代码。这是在 background 中的完成方式：

private unsafe static bool EqualsHelper(String strA, String strB)
{
    Contract.Requires(strA != null);
    Contract.Requires(strB != null);
    Contract.Requires(strA.Length == strB.Length);

    int length = strA.Length;

    fixed (char* ap = &strA.m_firstChar) fixed (char* bp = &strB.m_firstChar)
    {
        char* a = ap;
        char* b = bp;

        // Unroll the loop

        #if AMD64
            // For the AMD64 bit platform we unroll by 12 and
            // check three qwords at a time. This is less code
            // than the 32 bit case and is shorter
            // pathlength.

            while (length >= 12)
            {
                if (*(long*)a     != *(long*)b)     return false;
                if (*(long*)(a+4) != *(long*)(b+4)) return false;
                if (*(long*)(a+8) != *(long*)(b+8)) return false;
                a += 12; b += 12; length -= 12;
            }
       #else
           while (length >= 10)
           {
               if (*(int*)a != *(int*)b) return false;
               if (*(int*)(a+2) != *(int*)(b+2)) return false;
               if (*(int*)(a+4) != *(int*)(b+4)) return false;
               if (*(int*)(a+6) != *(int*)(b+6)) return false;
               if (*(int*)(a+8) != *(int*)(b+8)) return false;
               a += 10; b += 10; length -= 10;
           }
       #endif

        // This depends on the fact that the String objects are
        // always zero terminated and that the terminating zero is not included
        // in the length. For odd string sizes, the last compare will include
        // the zero terminator.
        while (length > 0)
        {
            if (*(int*)a != *(int*)b) break;
            a += 2; b += 2; length -= 2;
        }

        return (length <= 0);
    }
}

在我的测试中，转换为字符串会破坏更快比较的优势。这比简单的 for 循环慢了大约 2.5 倍。

当我做同样的事情时，简单的 for 慢了大约 8 倍。你能在这里写你的代码吗？

如果一个字节包含空 (0) 值，这会中断吗？

-1 正如@DougClutter 所指出的，由于转换为字符串会很慢，如果字节数组包含非ASCII 数据，这将失败。要获得正确的结果，需要使用 iso-8859-1。

Compare(new byte[]{128}, new byte[]{ 255 }) == true 完全没有错误...

R

Raymond Osterbrink

由于上述许多花哨的解决方案不适用于 UWP，并且因为我喜欢 Linq 和函数式方法，所以我向您展示了我的版本来解决这个问题。为了避免出现第一个差异时的比较，我选择了 .FirstOrDefault()

public static bool CompareByteArrays(byte[] ba0, byte[] ba1) =>
    !(ba0.Length != ba1.Length || Enumerable.Range(1,ba0.Length)
        .FirstOrDefault(n => ba0[n] != ba1[n]) > 0);

-1 因为此代码已损坏且显然未经测试。这会在比较非空数组时引发 IndexOutOfRangeException，因为您正在访问元素 1 到 ba0.Length，而它应该是 0 到 ba0.Length - 1。如果您使用 Enumerable.Range(0, ba0.Length) 修复该问题，它仍然会错误地返回 true 对于长度相等的数组，其中只有第一个元素不同，因为您无法区分满足 predicate 和 no 元素的第一个元素满足predicate； FirstOrDefault<int>() 在这两种情况下都会返回 0。

孩子们的教训：枪战不要带刀

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

关注公众号

想领先一步获取最新的外包任务吗？

相似问题

平台

支持

联系我们