Vergleich von zwei Byte-Arrays in .NET

Question

Wie kann ich das schnell machen?

Sicher kann ich das tun:

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 andere hoch optimierte und 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 würde das für x64 funktionieren.

Beachten Sie meine superschnelle Antwort ici .

Answer 1

Konnte nicht finden, eine Lösung, die ich bin völlig glücklich mit (vernünftige Leistung, aber keine unsicheren Code/pinvoke), so kam ich mit diesem, nichts wirklich originell, 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 der anderen Lösungen auf dieser Seite:

Einfache Schleife: 19837 Ticks, 1,00

*BitConverter: 4886 Ticks, 4,06

UnsafeCompare: 1636 Zecken, 12.12

EqualBytesLongUnrolled: 637 Ticks, 31.09

P/Aufruf memcmp: 369 Ticks, 53,67

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

Answer 2

Es scheint, dass EqualBytesLongUnrolled ist die beste der oben vorgeschlagenen Möglichkeiten.

Übersprungene Methoden (Enumerable.SequenceEqual,StructuralComparisons.StructuralEqualityComparer.Equals), waren nicht geduldig-für-langsam. Auf 265MB Arrays habe ich dies 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 |

Answer 3

Für den Vergleich kurzer Byte-Arrays gibt es einen interessanten 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 genannte Lösung zurückgreifen.

Es wäre interessant, eine Leistungsanalyse dieses Codes durchzuführen.

Answer 4

Ich habe hier nicht viele Linq-Lösungen gesehen.

Ich bin mir über die Auswirkungen auf die Leistung nicht sicher, aber ich halte mich im Allgemeinen an linq als Faustregel und optimieren Sie dann später, wenn nötig.

public bool CompareTwoArrays(byte[] array1, byte[] array2)
 {
   return !array1.Where((t, i) => t != array2[i]).Any();
 }

Bitte beachten Sie, dass dies nur funktioniert, wenn die Arrays die gleiche Größe haben. Eine Erweiterung könnte wie folgt aussehen

public bool CompareTwoArrays(byte[] array1, byte[] array2)
 {
   if (array1.Length != array2.Length) return false;
   return !array1.Where((t, i) => t != array2[i]).Any();
 }

Answer 5

Ich habe über die in vielen Grafikkarten eingebauten Blocktransfer-Beschleunigungsmethoden nachgedacht. Aber dann müsste man alle Daten byteweise rüberkopieren, so dass das nicht viel hilft, wenn man nicht einen ganzen Teil seiner Logik in unverwaltetem und hardwareabhängigem Code implementieren will...

Eine andere Möglichkeit der Optimierung, die dem oben gezeigten Ansatz ähnelt, besteht darin, von Anfang an so viele Daten wie möglich in einem long[] statt in einem byte[] zu speichern, z. B. wenn Sie die Daten sequentiell aus einer Binärdatei einlesen, oder wenn Sie eine Memory-Mapped-Datei verwenden, lesen Sie die Daten als long[] oder einzelne long-Werte ein. Dann benötigt Ihre Vergleichsschleife nur 1/8 der Anzahl von Iterationen, die sie für ein Byte[] mit derselben Datenmenge durchführen müsste. Es kommt darauf an, wann und wie oft Sie vergleichen müssen und wann und wie oft Sie auf die Daten Byte für Byte zugreifen müssen, z. B. um sie in einem API-Aufruf als Parameter in einer Methode zu verwenden, die ein Byte[] erwartet. Letztendlich kann man das nur feststellen, wenn man den Anwendungsfall genau kennt...