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

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 aus irgendeinem Grund .NET 3.5 nicht verwenden können, ist Ihre Methode in Ordnung.
Compiler \run -Umgebung wird Ihre Schleife optimiert, so dass Sie sich keine Sorgen um die Leistung machen müssen.

Answer 2

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

Answer 3

Span<T> bietet eine äußerst wettbewerbsfähige Alternative, ohne dass Sie verwirrenden und/oder nicht portierbaren Ballast in die Codebasis Ihrer eigenen Anwendung einbringen müssen:

// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
    return a1.SequenceEqual(a2);
}

Die (Grundzüge der) Implementierung ab .NET 5.0.0 finden Sie unter ici .

Ich habe überarbeitet @EliArbel's gist um diese Methode hinzuzufügen als SpansEqual , lassen Sie die meisten uninteressanten Leistungen in anderen Benchmarks weg, führen Sie ihn mit verschiedenen Array-Größen aus, geben Sie Graphen aus und markieren Sie SpansEqual als Ausgangsbasis, so dass sie berichtet, wie die verschiedenen Methoden im Vergleich zu SpansEqual .

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

|        Method |  ByteCount |               Mean |            StdDev | Ratio | RatioSD |
|-------------- |----------- |-------------------:|------------------:|------:|--------:|
|    SpansEqual |         15 |           4.629 ns |         0.0289 ns |  1.00 |    0.00 |
|  LongPointers |         15 |           4.598 ns |         0.0416 ns |  0.99 |    0.01 |
|      Unrolled |         15 |          18.199 ns |         0.0291 ns |  3.93 |    0.02 |
| PInvokeMemcmp |         15 |           9.872 ns |         0.0441 ns |  2.13 |    0.02 |
|               |            |                    |                   |       |         |
|    SpansEqual |       1026 |          19.965 ns |         0.0880 ns |  1.00 |    0.00 |
|  LongPointers |       1026 |          63.005 ns |         0.5217 ns |  3.16 |    0.04 |
|      Unrolled |       1026 |          38.731 ns |         0.0166 ns |  1.94 |    0.01 |
| PInvokeMemcmp |       1026 |          40.355 ns |         0.0202 ns |  2.02 |    0.01 |
|               |            |                    |                   |       |         |
|    SpansEqual |    1048585 |      43,761.339 ns |        30.8744 ns |  1.00 |    0.00 |
|  LongPointers |    1048585 |      59,585.479 ns |        17.3907 ns |  1.36 |    0.00 |
|      Unrolled |    1048585 |      54,646.243 ns |        35.7638 ns |  1.25 |    0.00 |
| PInvokeMemcmp |    1048585 |      55,198.289 ns |        23.9732 ns |  1.26 |    0.00 |
|               |            |                    |                   |       |         |
|    SpansEqual | 2147483591 | 240,607,692.857 ns | 2,733,489.4894 ns |  1.00 |    0.00 |
|  LongPointers | 2147483591 | 238,223,478.571 ns | 2,033,769.5979 ns |  0.99 |    0.02 |
|      Unrolled | 2147483591 | 236,227,340.000 ns | 2,189,627.0164 ns |  0.98 |    0.00 |
| PInvokeMemcmp | 2147483591 | 238,724,660.000 ns | 3,726,140.4720 ns |  0.99 |    0.02 |

Ich war überrascht, als ich sah SpansEqual bei den max-array-size-Methoden nicht die Nase vorn haben, aber der Unterschied ist so gering, dass ich nicht glaube, dass es jemals eine Rolle spielen wird.

Meine Systeminformationen:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=5.0.100
  [Host]     : .NET Core 5.0.0 (CoreCLR 5.0.20.51904, CoreFX 5.0.20.51904), X64 RyuJIT
  DefaultJob : .NET Core 5.0.0 (CoreCLR 5.0.20.51904, CoreFX 5.0.20.51904), X64 RyuJIT

Answer 4

In .NET 4 gibt es eine neue eingebaute Lösung für dieses Problem - IStructuralEquatable

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

Answer 5

Benutzer gil einen unsicheren Code vorgeschlagen, 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;
  }
}

die einen 64-Bit-basierten Vergleich für einen möglichst großen Teil des Arrays durchführt. Diese Art der zählt auf die Tatsache, dass die Arrays beginnen qword ausgerichtet. Es wird funktionieren, wenn nicht qword ausgerichtet, nur nicht so schnell wie wenn es war.

Sie führt etwa sieben Timer schneller aus als die einfache for Schleife. Die Verwendung der J#-Bibliothek entspricht der ursprünglichen for Schleife. Mit .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 langsamer sind.