Vergleichen von zwei Byte-Arrays in .NET

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 nach einer BCL- Funktion oder nach einer hochoptimierten, bewährten Methode, um dies zu tun.

java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);

funktioniert gut, aber es sieht nicht so aus, als würde das für x64 funktionieren.

Beachten Sie meine superschnelle Antwort hier .

Sie können die Enumerable.SequenceEqual- Methode verwenden.

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 \ Runtime-Umgebung optimiert Ihre Schleife, sodass Sie sich keine Gedanken über die Leistung machen müssen.

P / Invoke 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;
}

In .NET 4 gibt es dafür eine neue integrierte Lösung - IStructuralEquatable

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

Benutzer gil schlug unsicheren Code vor, der diese Lösung hervorbrachte:

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

Dies führt einen 64-Bit-basierten Vergleich für so viel Array wie möglich durch. Diese Art von zählt auf der Tatsache, dass die Arrays qword ausgerichtet beginnen. Es wird funktionieren, wenn qword nicht ausgerichtet ist, nur nicht so schnell, als ob es wäre.

Es führt ungefähr sieben Timer schneller aus als die einfache forSchleife. Die Verwendung der J # -Bibliothek entspricht der ursprünglichen forSchleife. Die Verwendung von .SequenceEqual läuft etwa siebenmal langsamer. Ich denke nur, weil es IEnumerator.MoveNext verwendet. Ich stelle mir vor, dass LINQ-basierte Lösungen mindestens so langsam oder schlechter sind.

Span<T> bietet eine äußerst wettbewerbsfähige Alternative, ohne verwirrende und / oder nicht tragbare Flusen in die Codebasis Ihrer eigenen Anwendung werfen zu 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 3.1.0 finden Sie hier .

Ich habe @ EliArbels Kern überarbeitet , um diese Methode hinzuzufügen, indem SpansEqualdie meisten weniger interessanten Darsteller in den Benchmarks anderer gelöscht, mit unterschiedlichen Arraygrößen ausgeführt, Diagramme ausgegeben und SpansEqualals Basislinie markiert werden, damit angegeben wird, wie die verschiedenen Methoden verglichen werden SpansEqual.

Die folgenden Zahlen stammen aus den Ergebnissen und wurden leicht bearbeitet, um die Spalte "Fehler" zu entfernen.

|        Method |  ByteCount |               Mean |            StdDev | Ratio |
|-------------- |----------- |-------------------:|------------------:|------:|
|    SpansEqual |         15 |           3.562 ns |         0.0035 ns |  1.00 |
|  LongPointers |         15 |           4.611 ns |         0.0028 ns |  1.29 |
|      Unrolled |         15 |          18.035 ns |         0.0195 ns |  5.06 |
| PInvokeMemcmp |         15 |          11.210 ns |         0.0353 ns |  3.15 |
|               |            |                    |                   |       |
|    SpansEqual |       1026 |          20.048 ns |         0.0286 ns |  1.00 |
|  LongPointers |       1026 |          63.347 ns |         0.1062 ns |  3.16 |
|      Unrolled |       1026 |          39.175 ns |         0.0304 ns |  1.95 |
| PInvokeMemcmp |       1026 |          40.830 ns |         0.0350 ns |  2.04 |
|               |            |                    |                   |       |
|    SpansEqual |    1048585 |      44,070.526 ns |        35.3348 ns |  1.00 |
|  LongPointers |    1048585 |      59,973.407 ns |        80.4145 ns |  1.36 |
|      Unrolled |    1048585 |      55,032.945 ns |        24.4745 ns |  1.25 |
| PInvokeMemcmp |    1048585 |      55,593.719 ns |        22.4301 ns |  1.26 |
|               |            |                    |                   |       |
|    SpansEqual | 2147483591 | 253,648,180.000 ns | 1,112,524.3074 ns |  1.00 |
|  LongPointers | 2147483591 | 249,412,064.286 ns | 1,079,409.5670 ns |  0.98 |
|      Unrolled | 2147483591 | 246,329,091.667 ns |   852,021.7992 ns |  0.97 |
| PInvokeMemcmp | 2147483591 | 247,795,940.000 ns | 3,390,676.3644 ns |  0.98 |

Ich war überrascht zu sehen SpansEqual, dass die Methoden mit maximaler Array-Größe nicht die Nase vorn haben, aber der Unterschied ist so gering, dass ich nicht denke, dass es jemals eine Rolle spielen wird.

Meine Systeminfo:

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=3.1.100
  [Host]     : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT
  DefaultJob : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT

Wenn Sie nicht dagegen sind, können Sie die J # -Baugruppe "vjslib.dll" importieren und die Methode Arrays.equals (byte [], byte []) verwenden ...

Beschuldige mich nicht, wenn dich jemand auslacht ...

EDIT: Für das Wenige, das es wert ist, habe ich Reflector verwendet, um den Code dafür zu zerlegen, und hier ist, wie es aussieht:

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 und höher haben einen neuen öffentlichen Typ, System.Data.Linq.Binaryder kapselt byte[]. Es implementiert, IEquatable<Binary>dass (tatsächlich) zwei Byte-Arrays verglichen werden. Beachten Sie, dass System.Data.Linq.Binaryauch implizite Konvertierungsoperator von hat byte[].

MSDN-Dokumentation: System.Data.Linq.Binary

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

Interessant ist, dass sie nur dann zu einer byteweisen Vergleichsschleife übergehen, wenn die Hashes der beiden Binärobjekte gleich sind. Dies geht jedoch zu Lasten der Berechnung des Hash im Konstruktor von BinaryObjekten (durch Durchlaufen des Arrays mit forSchleife :-)).

Die obige Implementierung bedeutet, dass Sie im schlimmsten Fall die Arrays möglicherweise dreimal durchlaufen müssen: zuerst den Hash von Array1 berechnen, dann den Hash von Array2 berechnen und schließlich (da dies das Worst-Case-Szenario ist, Längen und Hashes gleich) vergleichen Bytes in Array1 mit Bytes in Array 2.

Obwohl dies System.Data.Linq.Binaryin BCL integriert ist, ist es meiner Meinung nach nicht der schnellste Weg, zwei Byte-Arrays zu vergleichen: - |.

Ich habe eine ähnliche Frage zur Überprüfung gestellt, ob Byte [] voller Nullen ist. (Der SIMD-Code wurde geschlagen, 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 eine hinzu!

Kürzlich hat Microsoft ein spezielles NuGet-Paket veröffentlicht, System.Runtime.CompilerServices.Unsafe . Es ist etwas Besonderes, weil es in IL geschrieben ist und Funktionen auf niedriger Ebene bietet, die in C # nicht direkt verfügbar sind.

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 eine sehr schlechte Idee, aber wenn beide Typen dieselbe Struktur haben, kann es funktionieren. Wir können dies also verwenden, um a byte[]in a umzuwandeln 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.Lengthdie ursprüngliche Array-Länge weiterhin zurückgegeben wird, 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 von meinem Computer:

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 einen Kern mit allen Tests erstellt .

Ich habe eine Methode entwickelt, die auf meinem PC leicht schlägt memcmp()(Antwort von Sockel) und sehr leicht schlägt (Antwort von EqualBytesLongUnrolled()Arek Bulski). Grundsätzlich wird die Schleife um 4 statt um 8 abgewickelt.

Update 30. März 2019 :

Ab .NET Core 3.0 bieten wir SIMD-Unterstützung!

Diese Lösung ist auf meinem PC mit großem 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 die forSchleife ausführen, um Int32-Zeiger zu vergleichen.

Vielleicht sollten Sie auch in Betracht ziehen, die Arrays als 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 eine "unsichere" Zeigerimplementierung aufweist. .NET Reflector ist Ihr Freund, um zu sehen, wie Dinge intern erledigt werden.

Dies kann als Vorlage für den Byte-Array-Vergleich verwendet werden, für den ich eine Implementierung im Blog-Beitrag Fast Byte-Array-Vergleich in C # durchgeführt habe . Ich habe auch einige rudimentäre Benchmarks durchgeführt, um festzustellen, wann eine sichere Implementierung schneller ist als die unsichere.

Das heißt, wenn Sie nicht wirklich Killer-Performance brauchen, würde ich einen einfachen Fr-Loop-Vergleich anstellen.

Ich konnte keine Lösung finden, mit der ich völlig zufrieden bin (angemessene Leistung, aber kein unsicherer Code / Pinvoke), also habe ich mir etwas ausgedacht, nichts wirklich Originelles, aber es 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 Zecken, 1,00

* BitConverter: 4886 Ticks, 4.06

UnsafeCompare: 1636 Ticks, 12.12

EqualBytesLongUnrolled: 637 Ticks, 31.09

P / Memcmp aufrufen: 369 Ticks, 53,67

Getestet in Linqpad, 1000000 Bytes identische Arrays (Worst-Case-Szenario), jeweils 500 Iterationen.

Es scheint, dass EqualBytesLongUnrolled das Beste aus dem oben vorgeschlagenen ist.

Übersprungene Methoden (Enumerable.SequenceEqual, StructuralComparisons.StructuralEqualityComparer.Equals) waren nicht geduldig für 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 der Auswirkungen auf die Leistung nicht sicher, halte mich jedoch im Allgemeinen an linqdie Faustregel und optimiere sie später, falls erforderlich.

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. Eine Erweiterung könnte so 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 angehängten Programm .net 4.7 Release Build ohne den angehängten Debugger durchgeführt. Ich denke, die Leute haben die falsche Metrik verwendet, da es bei der Geschwindigkeit darum geht, wie lange es dauert, herauszufinden, ob zwei Byte-Arrays gleich sind. dh 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 memcmpund es ist um Größenordnungen schneller. Eine einfache forSchleife ist die zweitbeste Option. Und es verwirrt mich immer noch, warum Microsoft nicht einfach eine Buffer.CompareMethode einschließen kann.

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

Für den Vergleich von Kurzbyte-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.

Für diejenigen unter Ihnen, die sich für die Reihenfolge interessieren (dh möchten, dass Sie memcmpein intähnliches Ergebnis wie nichts zurückgeben), enthält .NET Core 3.0 (und vermutlich .NET Standard 2.1, auch bekannt als .NET 5.0) eine Span.SequenceCompareTo(...)Erweiterungsmethode (plus a Span.SequenceEqualTo), die dies kann verwendet werden, um zwei ReadOnlySpan<T>Instanzen zu vergleichen ( where T: IComparable<T>).

Im ursprünglichen GitHub-Vorschlag umfasste die Diskussion Ansätze mit Sprungtabellenberechnungen, Lesen von a byte[]as long[], SIMD-Verwendung und p / invoke für die CLR-Implementierung memcmp.

In Zukunft sollte dies Ihre Methode sein, um Byte-Arrays oder Byte-Bereiche zu vergleichen (wie sie Span<byte>anstelle byte[]Ihrer .NET Standard 2.1-APIs verwendet werden sollten), und sie ist schnell genug, sodass Sie sich nicht mehr um die Optimierung kümmern sollten (und nein, trotz der Ähnlichkeiten im Namen ist es nicht so miserabel wie das schreckliche 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

Ich dachte über Blocktransfer-Beschleunigungsmethoden nach, die in viele Grafikkarten eingebaut sind. Aber dann müssten Sie alle Daten byteweise kopieren, was Ihnen 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 zur Optimierung, die dem oben gezeigten Ansatz ähnelt, besteht darin, von Anfang an so viele Daten wie möglich in einem langen [] statt in einem Byte [] zu speichern, beispielsweise wenn Sie sie nacheinander aus einer Binärdatei lesen. oder wenn Sie eine Speicherzuordnungsdatei verwenden, lesen Sie Daten als lange [] oder einzelne lange Werte ein. Dann benötigt Ihre Vergleichsschleife nur 1/8 der Anzahl der Iterationen, die sie für ein Byte [] mit derselben Datenmenge ausführen müsste. Es kommt darauf an, wann und wie oft Sie vergleichen müssen und wann und wie oft Sie byteweise auf die Daten zugreifen müssen, z. B. um sie in einem API-Aufruf als Parameter in einer erwarteten Methode zu verwenden ein Byte []. Am Ende können Sie nur feststellen, ob Sie den Anwendungsfall wirklich kennen ...

Dies ist mit ziemlicher Sicherheit viel langsamer als jede andere hier angegebene Version, aber es hat Spaß gemacht, sie zu schreiben.

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

Ich entschied mich für eine Lösung, die von der von ArekBulski veröffentlichten EqualBytesLongUnrolled-Methode inspiriert war, mit einer zusätzlichen Optimierung. In meinem Fall liegen die Array-Unterschiede in Arrays in der Regel nahe am Ende der Arrays. Beim Testen stellte ich fest, dass der Vergleich von Array-Elementen in umgekehrter Reihenfolge bei großen Arrays einen enormen Leistungsgewinn gegenüber der memcmp-basierten Lösung bedeutet. 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;
}

Entschuldigung, wenn Sie nach einer verwalteten Methode suchen, die Sie bereits korrekt ausführen, und meines Wissens gibt es in der BCL keine integrierte Methode, um dies zu tun.

Sie sollten einige anfängliche Nullprüfungen hinzufügen und sie dann einfach wiederverwenden, als ob sie in BCL wären.

Verwenden Sie SequenceEqualsdazu zum Vergleich.

Wenn Sie nach einem sehr schnellen Vergleich von Byte-Array-Gleichheit suchen, empfehlen wir Ihnen, diesen Artikel von STSdb ​​Labs zu lesen: Vergleich von Byte-Array-Gleichheit. Es enthält einige der schnellsten Implementierungen für den Vergleich von Byte [] -Array-Gleichheit, die vorgestellt, auf Leistung getestet und zusammengefasst werden.

Sie können sich auch auf folgende Implementierungen konzentrieren:

BigEndianByteArrayComparer - schneller byte [] Array Vergleich von links nach rechts (BigEndian) BigEndianByteArrayEqualityComparer - - schnellen byte [] Gleichheitsvergleich von links nach rechts (BigEndian) LittleEndianByteArrayComparer - schnellen byte [] Array Vergleich von rechts nach links (LittleEndian) LittleEndianByteArrayEqualityComparer - schneller Byte [] Gleichheitsvergleich von rechts nach links (LittleEndian)

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-Zeichenfolgenvergleich verwenden, um ein Byte-Array zu vergleichen, ohne dass unsicherer Code geschrieben werden muss. So geht das im 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, drücke ich Ihnen meine Version für dieses Problem. Um dem Vergleich zu entgehen, 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);