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

Ich habe eine Methode entwickelt, die etwas besser ist als memcmp() (die Antwort von plinth) und schlägt ganz leicht EqualBytesLongUnrolled() (die Antwort von Arek Bulski) auf meinem PC. Im Grunde wird die Schleife um 4 statt um 8 abgerollt.

Update 30. Mär. 2019 :

Ab .NET Core 3.0 haben 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;
}

Answer 2

Ich würde unsicheren Code verwenden und die for Schleife zum Vergleich von Int32-Zeigern.

Vielleicht sollten Sie auch prüfen, ob die Arrays nicht leer sind.

Answer 3

Für diejenigen unter Ihnen, denen die Ordnung wichtig ist (d. h. die ihre memcmp zur Rückgabe einer int wie es sein sollte, statt nichts), .NET Core 3.0 (und vermutlich .NET Standard 2.1 alias .NET 5.0) wird eine Span.SequenceCompareTo(...) 拡張方法 (plus eine Span.SequenceEqualTo ), die zum Vergleich zweier ReadOnlySpan<T> Instanzen ( where T: IComparable<T> ).

で der ursprüngliche GitHub-Vorschlag Die Diskussion umfasste Ansatzvergleiche mit Sprungtafelberechnungen, das Lesen einer byte[] als long[] , SIMD-Nutzung und p/invoke zur CLR-Implementierung memcmp .

In Zukunft sollte dies Ihre bevorzugte Methode für den Vergleich von Byte-Arrays oder Byte-Bereichen sein (ebenso wie die Verwendung von Span<byte> 代わりに byte[] für Ihre .NET Standard 2.1-APIs), und es ist schnell genug, dass Sie sich nicht mehr um die Optimierung kümmern sollten (und nein, trotz der Ähnlichkeiten im Namen ist es nicht so abgrundtief schlecht wie das schreckliche Enumerable.SequenceEqual ).

#if NETCOREAPP3_0_OR_GREATER
// 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

Answer 4

Wenn Sie sich ansehen, wie .NET string.Equals ausführt, sehen Sie, dass es eine private Methode namens EqualsHelper verwendet, die eine "unsichere" Zeigerimplementierung hat. .NET-Reflektor ist Ihr Freund, um zu sehen, wie die Dinge intern ablaufen.

Dies kann als Vorlage für Byte-Array-Vergleich, die ich eine Implementierung auf in Blog-Post verwendet werden 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 eine unsichere.

Das heißt, wenn Sie nicht wirklich eine Spitzenleistung benötigen, würde ich mich für einen einfachen Fr-Loop-Vergleich entscheiden.

Answer 5

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.