.NET에서 두 바이트 배열 비교
어떻게 빨리 할 수 있습니까?
물론 내가 할 수있는 일 :
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에서는 작동하지 않는 것 같습니다.
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를 사용할 수 없으면 방법이 정상입니다.
컴파일러 \ 런타임 환경은 루프를 최적화하므로 성능에 대해 걱정할 필요가 없습니다.
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;
}
.NET 4에는이를위한 새로운 내장 솔루션이 있습니다 -IStructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
사용자 길은 이 솔루션을 생성 한 안전하지 않은 코드를 제안했습니다.
// 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루프 보다 약 7 개의 타이머를 더 빠르게 수행합니다 . J # 라이브러리 사용은 원래 for루프 와 동일하게 수행 됩니다. .SequenceEqual을 사용하면 약 7 배 느리게 실행됩니다. IEnumerator.MoveNext를 사용하고 있기 때문에 생각합니다. 나는 LINQ 기반 솔루션이 적어도 느리거나 더 나쁘다고 생각합니다.
Span<T> 혼란스럽고 이식 불가능한 보풀을 자신의 응용 프로그램 코드 기반에 넣지 않고도 매우 경쟁력있는 대안을 제공합니다.
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
return a1.SequenceEqual(a2);
}
.NET Core 2.2.3의 구현은 여기 에서 찾을 수 있습니다 .
나는 한 개정 이 같은 방법을 추가 EliArbel의 요점 @ SpansEqual, 다른 배열 크기, 출력 그래프를 실행, 다른 사람의 벤치 마크에서 덜 흥미로운 공연의 대부분을 삭제하고 마크 SpansEqual는 다른 방법을 비교하는 방법을보고 그렇게하는 기준으로 SpansEqual.
아래 숫자는 결과에서 가져온 것으로 "오류"열을 제거하기 위해 약간 편집되었습니다.
| Method | ByteCount | Mean | StdDev | Ratio |
|-------------- |----------- |-------------------:|------------------:|------:|
| SpansEqual | 15 | 3.813 ns | 0.0043 ns | 1.00 |
| LongPointers | 15 | 4.768 ns | 0.0081 ns | 1.25 |
| Unrolled | 15 | 17.763 ns | 0.0319 ns | 4.66 |
| PInvokeMemcmp | 15 | 12.280 ns | 0.0221 ns | 3.22 |
| | | | | |
| SpansEqual | 1026 | 29.181 ns | 0.0461 ns | 1.00 |
| LongPointers | 1026 | 63.050 ns | 0.0785 ns | 2.16 |
| Unrolled | 1026 | 39.070 ns | 0.0412 ns | 1.34 |
| PInvokeMemcmp | 1026 | 44.531 ns | 0.0581 ns | 1.53 |
| | | | | |
| SpansEqual | 1048585 | 43,838.865 ns | 56.7144 ns | 1.00 |
| LongPointers | 1048585 | 59,629.381 ns | 194.0304 ns | 1.36 |
| Unrolled | 1048585 | 54,765.863 ns | 34.2403 ns | 1.25 |
| PInvokeMemcmp | 1048585 | 55,250.573 ns | 49.3965 ns | 1.26 |
| | | | | |
| SpansEqual | 2147483591 | 247,237,201.379 ns | 2,734,143.0863 ns | 1.00 |
| LongPointers | 2147483591 | 241,535,134.852 ns | 2,720,870.8915 ns | 0.98 |
| Unrolled | 2147483591 | 240,170,750.054 ns | 2,729,935.0576 ns | 0.97 |
| PInvokeMemcmp | 2147483591 | 238,953,916.032 ns | 2,692,490.7016 ns | 0.97 |
SpansEqualmax-array-size 방법을 사용하지 않는 것에 대해 놀랐지 만 그 차이는 너무 작아서 중요하지 않다고 생각합니다.
내 시스템 정보 :
BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17134.706 (1803/April2018Update/Redstone4)
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
Frequency=3515626 Hz, Resolution=284.4444 ns, Timer=TSC
.NET Core SDK=2.2.202
[Host] : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
DefaultJob : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
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;
}
.NET 3.5 이상에는 System.Data.Linq.Binary을 캡슐화 하는 새로운 공개 유형이 byte[]있습니다. 실제로 IEquatable<Binary>2 바이트 배열을 비교합니다. 의 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객체 생성자에서 해시를 계산하는 비용이 듭니다 ( forloop :-)으로 배열을 순회하여 ).
위의 구현은 최악의 경우 배열을 세 번 통과해야 함을 의미합니다. 먼저 배열 1의 해시를 계산 한 다음 배열 2의 해시를 계산하고 마지막으로 (이는 최악의 시나리오이기 때문에 길이와 해시가 동일하므로) 배열 1의 바이트와 배열 2의 바이트
전반적 System.Data.Linq.Binary으로 BCL에 내장되어 있지만 두 바이트 배열을 비교하는 가장 빠른 방법이라고는 생각하지 않습니다.
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
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");
}
하나 더 추가합시다!
최근 Microsoft는 특별한 NuGet 패키지 인 System.Runtime.CompilerServices.Unsafe를 출시했습니다 . IL로 작성 되었으므로 C #에서 직접 사용할 수없는 저수준 기능을 제공 하기 때문에 특별 합니다.
그 방법 중 하나는 Unsafe.As<T>(object)모든 참조 유형을 다른 참조 유형으로 캐스팅하여 안전 검사를 건너 뛸 수 있습니다. 이것은 일반적으로 매우 나쁜 생각이지만 두 유형이 동일한 구조를 가지고 있다면 작동 할 수 있습니다. 따라서 이것을 사용 byte[]하여 a 를 캐스트 할 수 있습니다 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 또는 고정을 사용하지 않으며 구현이 매우 간단합니다 (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 |
나는 내 PC에서 약간 두들겨 memcmp()(Plinth 's answer)와 매우 EqualBytesLongUnrolled()매끈한 Beats (Arek Bulski 's answer) 방법을 개발했습니다 . 기본적으로 루프가 8이 아닌 4 씩 풀립니다.
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;
}
안전하지 않은 코드를 사용하고 forInt32 포인터를 비교 하는 루프를 실행합니다 .
아마도 배열이 null이 아닌지 확인하는 것이 좋습니다.
.NET이 string.Equals를 수행하는 방법을 살펴보면 "안전하지 않은"포인터 구현이있는 EqualsHelper라는 전용 메서드를 사용한다는 것을 알 수 있습니다. .NET Reflector 는 내부에서 수행되는 작업을 확인하는 친구입니다.
이것은 블로그 게시물 에서 C #의 빠른 바이트 배열 비교에서 구현 한 바이트 배열 비교를위한 템플릿으로 사용할 수 있습니다 . 또한 안전한 구현이 안전하지 않은 것보다 빠른지 알아보기 위해 기초적인 벤치 마크를 수행했습니다.
즉, 킬러 성능이 실제로 필요한 경우가 아니라면 간단한 fr 루프 비교를 원할 것입니다.
내가 완전히 만족하는 솔루션을 찾을 수 없었습니다 (합리적인 성능이지만 안전하지 않은 코드 / 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 틱, 4.06
안전하지 않은 비교 : 1636 틱, 12.12
길게 펴기 : 637 틱, 31.09
P / Invoke memcmp : 369 틱, 53.67
linqpad에서 1000000 바이트의 동일한 배열 (최악의 시나리오), 각각 500 회 반복 테스트되었습니다.
위의 제안에서 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 |
나는 여기에서 많은 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();
}
디버거를 연결하지 않고 연결된 프로그램 .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방법을 포함시킬 수 없는지에 대해서는 여전히 제 생각이 들었습니다 .
[Program.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);
});
}
}
}
짧은 바이트 배열을 비교할 때 다음은 흥미로운 해킹입니다.
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);
그런 다음 아마도 질문에 나열된 해결책에 빠질 것입니다.
이 코드의 성능 분석을 수행하는 것이 흥미로울 것입니다.
많은 그래픽 카드에 내장 된 블록 전송 가속 방법에 대해 생각했습니다. 그러나 모든 데이터를 바이트 단위로 복사해야하므로 관리되지 않는 하드웨어 종속 코드로 논리의 전체 부분을 구현하지 않으려는 경우 도움이되지 않습니다 ...
위에 표시된 접근 방식과 유사한 다른 최적화 방법은 시작부터 바로 byte []가 아닌 long []에 가능한 많은 데이터를 저장하는 것입니다 (예 : 바이너리 파일에서 순차적으로 데이터를 읽는 경우) 또는 메모리 매핑 된 파일을 사용하는 경우 long [] 또는 단일 long 값으로 데이터를 읽습니다. 그런 다음 비교 루프는 동일한 양의 데이터를 포함하는 바이트 []에 대해 수행해야하는 반복 횟수의 1/8 만 필요합니다. 바이트 단위 방식으로 데이터에 액세스해야하는시기와 빈도를 비교해야하는시기와 빈도, 예를 들어 API 호출에서 데이터를 예상되는 메소드의 매개 변수로 사용하는 경우 바이트 []. 결국 유스 케이스를 실제로 알고 있는지 여부 만 알 수 있습니다 ...
이것은 여기에 주어진 다른 버전보다 거의 느리지 만 작성하는 것은 재미있었습니다.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
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;
}
관리되는 방법을 찾고 있다면 이미 올바르게하고 있으며 내 지식으로는 BCL 에이 작업을 수행하는 방법이 내장되어 있지 않습니다.
초기 null 확인을 추가 한 다음 BCL에서와 같이 재사용해야합니다.
순서에 대한 당신의 사람들이 치료를 위해 (즉, 당신이 원하는 memcmp를 반환 int, .NET 코어 대신 아무것도해야처럼) 3.0 (그리고 아마도 .NET 5.0 일명 .NET 표준 2.1) 포함 Span.SequenceCompareTo(...)확장 메서드 (플러스 Span.SequenceEqualTo) 있음을 캔 두 ReadOnlySpan<T>인스턴스 를 비교하는 데 사용됩니다 ( where T: IComparable<T>).
에서 원래의 GitHub의 제안 , 토론, 점프 테이블 계산과 접근 방식의 비교를 포함 읽기 byte[]로 long[], SIMD 사용, P / CLR은 구현의에 호출 memcmp.
앞으로이 방법은 바이트 배열 또는 바이트 범위를 비교할 수있는 방법이어야 합니다 (.NET 표준 2.1 API Span<byte>대신 byte[]사용해야 함). 더 이상 최적화에 신경 쓸 필요가 없을 정도로 충분히 빠릅니다 (및 아니요, 이름의 유사성에도 불구하고 끔찍한만큼 무시 무시하지 않습니다 Enumerable.SequenceEqual.
#if NETCOREAPP3_0
// 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
SequenceEquals이것을 비교하는 데 사용하십시오 .
짧은 대답은 다음과 같습니다.
public bool Compare(byte[] b1, byte[] b2)
{
return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
}
이러한 방식으로 최적화 된 .NET 문자열 비교를 사용하여 안전하지 않은 코드를 작성할 필요없이 바이트 배열을 비교할 수 있습니다. 이것이 백그라운드 에서 수행되는 방법입니다 .
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);
}
}
위의 많은 멋진 솔루션이 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);
매우 빠른 바이트 배열 평등 비교기를 찾고 있다면이 STSdb Labs 기사 : 바이트 배열 평등 비교기를 살펴보십시오 . byte [] array equality 비교를 위해 가장 빠른 구현 중 일부를 제공하며, 성능, 테스트 및 요약을 제공합니다.
다음 구현에 집중할 수도 있습니다.
BigEndianByteArrayComparer - 빠르고 바이트 [] 오른쪽 (bigEndian의) 왼쪽에서 배열 비교 자 BigEndianByteArrayEqualityComparer - - 빠르고 바이트 [] 같음 비교 오른쪽 (bigEndian의) 왼쪽에서 LittleEndianByteArrayComparer - 빠르고 바이트 왼쪽 (littleEndian의) 오른쪽에서 [] 배열 비교 자 LittleEndianByteArrayEqualityComparer - 빠르고 바이트 [] 오른쪽에서 왼쪽으로 평등 비교기 (LittleEndian)
참고 URL : https://stackoverflow.com/questions/43289/comparing-two-byte-arrays-in-net
'Programing' 카테고리의 다른 글
| 커맨드 라인의 Node.js 버전? (0) | 2020.02.12 |
|---|---|
| Bash에서 해시 테이블을 정의하는 방법은 무엇입니까? (0) | 2020.02.12 |
| 물체가 날짜인지 확인하는 방법? (0) | 2020.02.12 |
| 내용에 맞게 UITextView의 크기를 어떻게 조정합니까? (0) | 2020.02.12 |
| event.layerX 및 event.layerY와 관련된 WebKit 문제 (0) | 2020.02.12 |