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

Wenn Sie sich nicht dagegen sträuben, können Sie die J#-Assembly "vjslib.dll" importieren und deren Arrays.equals(byte[], byte[]) Methode ...

Aber gib mir nicht die Schuld, wenn dich jemand auslacht...

---

EDIT: Ich habe Reflector benutzt, um den Code zu disassemblieren, und so sieht er 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;
}

Answer 2

.NET 3.5 und neuere Versionen haben einen neuen öffentlichen Typ, System.Data.Linq.Binary die kapselt byte[] . Es implementiert IEquatable<Binary> die (in der Tat) zwei Byte-Arrays vergleicht. Beachten Sie, dass System.Data.Linq.Binary hat auch einen impliziten Konvertierungsoperator von byte[] .

MSDN-Dokumentation: System.Data.Linq.Binary

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

Interessant ist, dass sie nur dann zur Byte-für-Byte-Vergleichsschleife übergehen, wenn die Hashes der beiden binären Objekte gleich sind. Dies geht jedoch auf Kosten der Berechnung des Hashes im Konstruktor von Binary Objekte (durch Durchlaufen des Arrays mit for Schleife :-) ).

Die obige Implementierung bedeutet, dass man im schlimmsten Fall die Arrays dreimal durchlaufen muss: zuerst, um den Hash von Array1 zu berechnen, dann, um den Hash von Array2 zu berechnen und schließlich (da dies der schlimmste Fall ist, sind Längen und Hashes gleich), um Bytes in Array1 mit Bytes in Array 2 zu vergleichen.

Insgesamt, auch wenn System.Data.Linq.Binary in BCL eingebaut ist, denke ich nicht, dass es der schnellste Weg ist, zwei Byte-Arrays zu vergleichen :-|.

Answer 3

Ich habe eine ähnliche Frage über die Überprüfung, ob byte[] voll von Nullen ist. (SIMD-Code wurde geschlagen, also 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

Answer 4

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

Answer 5

Fügen wir einen weiteren hinzu!

Vor kurzem hat Microsoft ein spezielles NuGet-Paket veröffentlicht, System.Runtime.CompilerServices.Unsafe . Es ist etwas Besonderes, weil es in IL und bietet Low-Level-Funktionen, die in C# nicht direkt verfügbar sind.

Eine ihrer Methoden, Unsafe.As<T>(object) ermöglicht das Casting eines beliebigen Referenztyps in einen anderen Referenztyp, wobei alle Sicherheitsüberprüfungen übersprungen werden. Dies ist normalerweise ein sehr eine schlechte Idee, aber wenn beide Typen die gleiche Struktur haben, kann es funktionieren. Wir können dies also verwenden, um eine byte[] zu einer 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 würde immer noch die ursprüngliche Länge des Arrays zurückgeben, da sie in einem Feld in der Speicherstruktur des Arrays gespeichert ist.

Diese Methode ist nicht ganz so schnell wie die anderen hier vorgestellten 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 Rechner:

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 gist mit allen Tests .