Vergleich zweier Byte-Arrays in .NET
https://stackoverflow.com/questions/43289
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie kann ich das schnell machen?
Klar kann ich das machen:
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;
}
Aber ich suche entweder einen BCL Funktion oder eine hochoptimierte bewährte Methode, dies zu tun.
java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);
Funktioniert gut, aber es sieht nicht so aus, als ob das für x64 funktionieren würde.
Beachten Sie meine superschnelle Antwort Hier.
Lösung 4
Benutzer Gil vorgeschlagener unsicherer Code, der diese Lösung hervorgebracht hat:
// 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;
}
}
Dadurch wird ein 64-Bit-basierter Vergleich für einen möglichst großen Teil des Arrays durchgeführt.Diese Art setzt voraus, dass die Arrays qword-ausgerichtet beginnen.Es funktioniert, wenn es nicht qword-ausgerichtet ist, nur nicht so schnell, als ob es wäre.
Es ist etwa sieben Timer schneller als das einfache for Schleife.Die Verwendung der J#-Bibliothek entspricht der des Originals for Schleife.Die Verwendung von .SequenceEqual läuft etwa siebenmal langsamer;Ich denke, nur weil es IEnumerator.MoveNext verwendet.Ich kann mir vorstellen, dass LINQ-basierte Lösungen mindestens so langsam oder noch schlimmer sind.
Andere Tipps
Sie können verwenden Enumerable.SequenceEqual Methode.
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
Wenn Sie .NET 3.5 aus irgendeinem Grund nicht verwenden können, ist Ihre Methode in Ordnung.
Die Compiler-/Laufzeitumgebung optimiert Ihre Schleife, sodass Sie sich keine Sorgen um die Leistung machen müssen.
P/Aufrufen Kräfte aktivieren!
[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;
}
Dafür gibt es in .NET 4 eine neue integrierte Lösung: IStructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
Wenn Sie nichts dagegen haben, können Sie die J#-Assembly „vjslib.dll“ importieren und verwenden Arrays.equals(byte[], byte[])-Methode...
Aber gib mir nicht die Schuld, wenn dich jemand auslacht ...
BEARBEITEN:Für das Wenige, das es wert ist, habe ich Reflector verwendet, um den Code dafür zu zerlegen, und so sieht es aus:
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;
}
Span<T> bietet eine äußerst wettbewerbsfähige Alternative, ohne dass Sie verwirrenden und/oder nicht tragbaren Schnickschnack in die Codebasis Ihrer eigenen Anwendung werfen müssen:
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
return a1.SequenceEqual(a2);
}
Die (Eingeweide der) Implementierung ab .NET Core 2.2.3 finden Sie hier Hier.
Ich habe überarbeitet @EliArbels Kern, diese Methode hinzuzufügen als SpansEqual, Entfernen Sie die meisten der weniger interessanten Performer in den Benchmarks anderer, führen Sie es mit unterschiedlichen Array-Größen aus, geben Sie Diagramme aus und markieren Sie es SpansEqual als Basislinie, sodass angezeigt wird, wie die verschiedenen Methoden im Vergleich abschneiden SpansEqual.
Die folgenden Zahlen stammen aus den Ergebnissen, leicht bearbeitet, um die Spalte „Fehler“ zu entfernen.
| 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 |
Ich war überrascht zu sehen SpansEqual Ich bin bei den Methoden mit maximaler Array-Größe nicht ganz vorne mit dabei, aber der Unterschied ist so gering, dass ich nicht glaube, dass er jemals eine Rolle spielen wird.
Meine Systeminformationen:
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
.NET 3.5 und neuer haben einen neuen öffentlichen Typ, System.Data.Linq.Binary das kapselt byte[].Es setzt um IEquatable<Binary> das vergleicht (tatsächlich) zwei Byte-Arrays.Beachten Sie, dass System.Data.Linq.Binary hat auch einen impliziten Konvertierungsoperator von byte[].
MSDN-Dokumentation:System.Data.Linq.Binary
Reflektor-Dekompilierung der Equals-Methode:
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;
}
Eine interessante Wendung besteht darin, dass sie nur dann mit der Byte-für-Byte-Vergleichsschleife fortfahren, wenn die Hashes der beiden Binärobjekte gleich sind.Dies geht jedoch zu Lasten der Berechnung des Hashs im Konstruktor von Binary Objekte (durch Durchlaufen des Arrays mit for Schleife :-) ).
Die obige Implementierung bedeutet, dass Sie im schlimmsten Fall die Arrays möglicherweise dreimal durchlaufen müssen:Zuerst wird der Hash von Array1 berechnet, dann wird der Hash von Array2 berechnet und schließlich (da dies das Worst-Case-Szenario ist, Längen und Hashes gleich sind) werden die Bytes in Array1 mit den Bytes in Array 2 verglichen.
Insgesamt jedoch System.Data.Linq.Binary ist in BCL integriert, ich glaube nicht, dass es der schnellste Weg ist, zwei Byte-Arrays zu vergleichen :-|.
Ich habe gepostet eine ähnliche Frage zur Überprüfung, ob byte[] voller Nullen ist.(Der SIMD-Code wurde beschädigt, daher habe ich ihn aus dieser Antwort entfernt.) Hier ist der schnellste Code aus meinen Vergleichen:
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;
}
}
Gemessen an zwei 256-MB-Byte-Arrays:
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");
}
Fügen wir noch einen hinzu!
Kürzlich hat Microsoft ein spezielles NuGet-Paket veröffentlicht, System.Runtime.CompilerServices.Unsafe.Es ist etwas Besonderes, weil es geschrieben ist IL, und bietet Low-Level-Funktionalität, die in C# nicht direkt verfügbar ist.
Eine seiner Methoden, Unsafe.As<T>(object) Ermöglicht das Umwandeln eines beliebigen Referenztyps in einen anderen Referenztyp, wobei Sicherheitsüberprüfungen übersprungen werden.Dies ist normalerweise ein sehr schlechte Idee, aber wenn beide Typen die gleiche Struktur haben, kann es funktionieren.Wir können dies also verwenden, um a zu wirken byte[] zu einem 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;
}
Beachten Sie, dass long1.Length würde immer noch die Länge des ursprünglichen Arrays zurückgeben, da sie in einem Feld in der Speicherstruktur des Arrays gespeichert ist.
Diese Methode ist nicht ganz so schnell wie andere hier gezeigte Methoden, aber sie ist viel schneller als die naive Methode, verwendet keinen unsicheren Code oder P/Invoke oder Pinning und die Implementierung ist recht einfach (IMO).Hier sind einige BenchmarkDotNet Ergebnisse meiner Maschine:
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 |
Ich habe auch eine erstellt Kern mit allen Tests.
Ich habe eine Methode entwickelt, die leicht schlägt memcmp() (Plinths Antwort) und sehr leichte Beats EqualBytesLongUnrolled() (Arek Bulskis Antwort) auf meinem PC.Im Grunde wird die Schleife um 4 statt um 8 abgerollt.
Update 30. März2019:
Ab .NET Core 3.0 haben wir SIMD-Unterstützung!
Diese Lösung ist auf meinem PC mit Abstand am schnellsten:
#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;
}
Ich würde unsicheren Code verwenden und den ausführen for Schleife zum Vergleichen von Int32-Zeigern.
Vielleicht sollten Sie auch in Betracht ziehen, die Arrays auf Nicht-Null zu überprüfen.
Wenn Sie sich ansehen, wie .NET string.Equals ausführt, sehen Sie, dass es eine private Methode namens EqualsHelper verwendet, die über eine „unsichere“ Zeigerimplementierung verfügt. .NET-Reflektor ist Ihr Freund, um zu sehen, wie die Dinge intern erledigt werden.
Dies kann als Vorlage für den Byte-Array-Vergleich verwendet werden, den ich im Blogbeitrag implementiert habe Schneller Byte-Array-Vergleich in C#.Ich habe auch einige rudimentäre Benchmarks durchgeführt, um zu sehen, wann eine sichere Implementierung schneller ist als die unsichere.
Das heißt, wenn Sie nicht wirklich eine Killerleistung benötigen, würde ich einen einfachen Fr-Loop-Vergleich durchführen.
Ich konnte keine Lösung finden, mit der ich vollkommen zufrieden bin (angemessene Leistung, aber kein unsicherer Code/Pinvoke), also habe ich mir Folgendes ausgedacht, nichts wirklich Originelles, aber funktioniert:
/// <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;
}
Leistung im Vergleich zu einigen anderen Lösungen auf dieser Seite:
Einfache Schleife:19837 Ticks, 1,00
*BitConverter:4886 Ticks, 4.06
UnsicherVergleich:1636 Ticks, 12.12
EqualBytesLongUnrolled:637 Ticks, 31.09
P/memcmp aufrufen:369 Ticks, 53,67
Getestet in Linqpad, 1000000 Byte identische Arrays (Worst-Case-Szenario), jeweils 500 Iterationen.
Es scheint, dass EqualBytesLongUnrolled ist das Beste aus den oben genannten Vorschlägen.
Übersprungene Methoden (Enumerable.SequenceEqual,StructuralComparisons.StructuralEqualityComparer.Equals) waren nicht langsam.Auf 265-MB-Arrays habe ich Folgendes gemessen:
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 |
Ich habe hier nicht viele Linq-Lösungen gesehen.
Ich bin mir über die Auswirkungen auf die Leistung nicht sicher, bleibe aber grundsätzlich dabei linq als Faustregel festlegen und bei Bedarf später optimieren.
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
return !array1.Where((t, i) => t != array2[i]).Any();
}
Bitte beachten Sie, dass dies nur funktioniert, wenn es sich um Arrays gleicher Größe handelt.So könnte eine Erweiterung aussehen
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
if (array1.Length != array2.Length) return false;
return !array1.Where((t, i) => t != array2[i]).Any();
}
Ich habe einige Messungen mit dem beigefügten Programm .net 4.7 Release Build ohne angeschlossenen Debugger durchgeführt.Ich denke, die Leute haben die falsche Metrik verwendet, denn wenn es Ihnen um Geschwindigkeit geht, geht es darum, wie lange es dauert, herauszufinden, ob zwei Byte-Arrays gleich sind.d.h.Durchsatz in Bytes.
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
Wie Sie sehen, gibt es keinen besseren Weg als memcmp und es ist um Größenordnungen schneller.Eine einfache for Schleife ist die zweitbeste Option.Und es ist mir immer noch ein Rätsel, warum Microsoft nicht einfach eine einbinden kann Buffer.Compare Methode.
[Programm.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);
});
}
}
}
Für den Vergleich kurzer Byte-Arrays ist Folgendes ein interessanter Hack:
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);
Dann würde ich wahrscheinlich auf die in der Frage aufgeführte Lösung zurückgreifen.
Es wäre interessant, eine Leistungsanalyse dieses Codes durchzuführen.
Ich habe über Blocktransfer-Beschleunigungsmethoden nachgedacht, die in viele Grafikkarten integriert sind.Aber dann müssten Sie alle Daten byteweise kopieren, sodass Ihnen das nicht viel hilft, wenn Sie nicht einen ganzen Teil Ihrer Logik in nicht verwaltetem und hardwareabhängigem Code implementieren möchten ...
Eine andere Möglichkeit der Optimierung, die dem oben gezeigten Ansatz ähnelt, besteht darin, so viele Ihrer Daten wie möglich von Anfang an in einem Long[] statt in einem Byte[] zu speichern, wenn Sie sie beispielsweise sequentiell aus einer Binärdatei lesen. oder wenn Sie eine speicherzugeordnete Datei verwenden, lesen Sie Daten als long[] oder einzelne lange Werte ein.Dann benötigt Ihre Vergleichsschleife nur 1/8 der Anzahl an Iterationen, die sie für ein Byte[] mit der gleichen Datenmenge durchführen müsste.Es kommt darauf an, wann und wie oft Sie vergleichen müssen.wann und wie oft Sie byteweise auf die Daten zugreifen müssen, z.B.um es in einem API-Aufruf als Parameter in einer Methode zu verwenden, die ein Byte[] erwartet.Am Ende kann man nur sagen, ob man den Anwendungsfall wirklich kennt ...
Dies ist mit ziemlicher Sicherheit viel langsamer als jede andere hier gegebene Version, aber es hat Spaß gemacht, es zu schreiben.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
Ich habe mich für eine Lösung entschieden, die von der von ArekBulski veröffentlichten EqualBytesLongUnrolled-Methode mit einer zusätzlichen Optimierung inspiriert ist.In meinem Fall liegen Array-Unterschiede in Arrays tendenziell am Ende der Arrays.Beim Testen habe ich herausgefunden, dass, wenn dies bei großen Arrays der Fall ist, die Möglichkeit, Array-Elemente in umgekehrter Reihenfolge zu vergleichen, dieser Lösung einen enormen Leistungsgewinn gegenüber der Memcmp-basierten Lösung verleiht.Hier ist diese Lösung:
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;
}
Tut mir leid, wenn Sie nach einer verwalteten Methode suchen, machen Sie es bereits richtig und meines Wissens gibt es in der BCL keine integrierte Methode dafür.
Sie sollten einige anfängliche Nullprüfungen hinzufügen und es dann einfach wiederverwenden, als ob es in BCL wäre.
Verwenden SequenceEquals dazu zum Vergleich.
Die kurze Antwort lautet:
public bool Compare(byte[] b1, byte[] b2)
{
return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
}
Auf diese Weise können Sie den optimierten .NET-String-Vergleich verwenden, um einen Byte-Array-Vergleich durchzuführen, ohne unsicheren Code schreiben zu müssen.So wird es in der gemacht Hintergrund:
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);
}
}
Da viele der oben genannten ausgefallenen Lösungen nicht mit UWP funktionieren und ich Linq und funktionale Ansätze liebe, präsentiere ich Ihnen meine Version dieses Problems.Um den Vergleich zu umgehen, wenn der erste Unterschied auftritt, habe ich .FirstOrDefault() gewählt
public static bool CompareByteArrays(byte[] ba0, byte[] ba1) =>
!(ba0.Length != ba1.Length || Enumerable.Range(1,ba0.Length)
.FirstOrDefault(n => ba0[n] != ba1[n]) > 0);
Wenn Sie nach einem sehr schnellen Byte-Array-Gleichheitsvergleicher suchen, empfehle ich Ihnen, einen Blick auf diesen Artikel von STSdb Labs zu werfen: Byte-Array-Gleichheitsvergleicher. Es enthält einige der schnellsten Implementierungen für den Gleichheitsvergleich von Byte[]-Arrays, die vorgestellt, leistungsgetestet und zusammengefasst werden.
Sie können sich auch auf diese Implementierungen konzentrieren:
BigEndianByteArrayComparer - schneller Byte[]-Array-Vergleich von links nach rechts (BigEndian)BigEndianByteArrayEqualityComparer - - schneller Byte[]-Gleichheitsvergleicher von links nach rechts (BigEndian)LittleEndianByteArrayComparer - schneller Byte[]-Array-Vergleich von rechts nach links (LittleEndian)LittleEndianByteArrayEqualityComparer - schneller Byte[]-Gleichheitsvergleicher von rechts nach links (LittleEndian)
Falls Sie über ein großes Byte-Array verfügen, können Sie diese vergleichen, indem Sie sie in einen String konvertieren.
Sie können so etwas wie verwenden
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
Ich habe dies verwendet und eine enorme Auswirkung auf die Leistung festgestellt.
