我怎样才能做得快呢?
当然我可以这样做:
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。
注意我的快速回答。
当前回答
找不到一个我完全满意的解决方案(合理的性能，但没有不安全的代码/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
*位收敛器:4886 ticks, 4.06
unsafcompare: 1636 ticks, 12.12
EqualBytesLongUnrolled: 637 tick, 31.09
P/Invoke memcmp: 369 ticks, 53.67
在linqpad上测试，1000000字节的相同数组(最坏的情况)，每个数组500次迭代。
其他回答
Span<T>提供了一个极具竞争力的替代方案，而不必在您自己的应用程序的代码库中添加令人困惑和/或不可移植的错误:
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(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没有在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
我开发了一个方法，稍微击败memcmp() (plinth的答案)和非常轻微击败EqualBytesLongUnrolled() (Arek Bulski的答案)在我的PC上。基本上，它以4而不是8展开循环。
2019年3月30日更新：
从。net核心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 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对象的哈希值相同时，它们才会进行逐字节比较循环。然而，这是以在二进制对象的构造函数中计算哈希值为代价的(通过使用for loop:-)遍历数组)。
上述实现意味着，在最坏的情况下，您可能必须遍历数组三次:首先计算array1的哈希值，然后计算array2的哈希值，最后(因为这是最坏的情况，长度和哈希值相等)比较array1中的字节和数组2中的字节。
总的来说，即使System.Data.Linq.Binary被内置到BCL中，我不认为这是比较两个字节数组的最快方法:-|。
几乎可以肯定，这个版本比这里给出的任何其他版本都要慢得多，但编写起来很有趣。
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
我发布了一个类似的关于检查byte[]是否全是0的问题。(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
