我怎样才能做得快呢?
当然我可以这样做:
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。
注意我的快速回答。
当前回答
我在这里没有看到很多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();
}
其他回答
我在这里没有看到很多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();
}
我想到了许多显卡内置的块传输加速方法。但是这样你就必须按字节复制所有的数据，所以如果你不想在非托管和依赖硬件的代码中实现你的整个逻辑，这对你没有多大帮助……
Another way of optimization similar to the approach shown above would be to store as much of your data as possible in a long[] rather than a byte[] right from the start, for example if you are reading it sequentially from a binary file, or if you use a memory mapped file, read in data as long[] or single long values. Then, your comparison loop will only need 1/8th of the number of iterations it would have to do for a byte[] containing the same amount of data. It is a matter of when and how often you need to compare vs. when and how often you need to access the data in a byte-by-byte manner, e.g. to use it in an API call as a parameter in a method that expects a byte[]. In the end, you only can tell if you really know the use case...
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
让我们再加一个!
最近微软发布了一个特殊的NuGet包System.Runtime.CompilerServices.Unsafe。它的特殊之处在于它是用IL编写的，并且提供了c#中无法直接使用的低级功能。
它的一个方法unsafety . as <T>(object)允许将任何引用类型转换为另一个引用类型，跳过任何安全检查。这通常是一个非常糟糕的主意，但如果两种类型具有相同的结构，它就可以工作。因此，我们可以使用这个函数将字节[]转换为长[]:
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或固定，实现非常简单(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 |
我还为所有测试创建了一个要点。
这与其他方法类似，但这里的不同之处在于，不存在我可以一次检查的下一个最高字节数，例如，如果我有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，与现有的longpointer算法相同的方法:
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;
}
}
