Porównanie dwóch tablic bajtowych w .NET

Jak mogę to zrobić szybko?

Jasne, że mogę to zrobić:

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

Ale szukam albo funkcji BCL, albo jakiegoś wysoce zoptymalizowanego, sprawdzonego sposobu na zrobienie tego.

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

działa ładnie, ale nie wygląda na to, że działałoby to dla x64.

Zwróć uwagę na moją superszybką odpowiedź tutaj .

Możesz użyć metody Enumerable.SequenceEqual .

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

Jeśli z jakiegoś powodu nie możesz użyć .NET 3.5, twoja metoda jest OK.
Środowisko wykonawcze kompilatora zoptymalizuje pętlę, abyś nie musiał się martwić wydajnością.

Moce P / Invoke aktywują się!

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

Istnieje nowe wbudowane rozwiązanie dla tego w .NET 4 - IStructuralEquatable

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

Użytkownik gil zasugerował niebezpieczny kod, który zrodził to rozwiązanie:

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

który wykonuje 64-bitowe porównanie dla jak największej liczby tablic. Ten rodzaj polega na tym, że tablice rozpoczynają wyrównanie qworda. Będzie działać, jeśli nie dopasuje qword, tylko nie tak szybko, jakby to było.

Wykonuje około siedem timerów szybciej niż prosta forpętla. Korzystanie z biblioteki J # wykonywane równorzędnie z oryginalną forpętlą. Korzystanie z .SequenceEqual działa około siedem razy wolniej; Myślę, że tylko dlatego, że używa IEnumerator.MoveNext. Wyobrażam sobie, że rozwiązania oparte na LINQ są co najmniej tak wolne lub gorsze.

Span<T> oferuje niezwykle konkurencyjną alternatywę bez konieczności wrzucania mylących i / lub nieprzenośnych puchów w bazę kodu własnej aplikacji:

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

Implementację (wnętrzności) od .NET Core 3.1.0 można znaleźć tutaj .

Mam poprawione @ GIST EliArbel by dodać tę metodę jako SpansEqual, spadek większości mniej ciekawych wykonawców w benchmarkach innych, uruchom go z różnych rozmiarach tablic, wykresów wyjściowych i oznacz SpansEqualjako bazowej tak, że informuje, w jaki sposób różne metody w porównaniu doSpansEqual .

Poniższe liczby pochodzą z wyników, lekko zmodyfikowanych w celu usunięcia kolumny „Błąd”.

|        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 |

Byłem zaskoczony widząc SpansEqual nie wyszedłem na szczyt w przypadku metod maksymalnego rozmiaru macierzy, ale różnica jest tak niewielka, że ​​nie sądzę, żeby to kiedykolwiek miało znaczenie.

Informacje o moim systemie:

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

Jeśli nie masz nic przeciwko temu, możesz zaimportować zestaw J # „vjslib.dll” i użyć jego metody Arrays.equals (byte [], byte []) ...

Nie obwiniaj mnie, jeśli ktoś się z ciebie śmieje ...

EDYCJA: Za ile to jest warte, użyłem Reflectora, aby zdemontować kod, a oto jak to wygląda:

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 i nowsze mają nowy typ publiczny, System.Data.Linq.Binaryktóry zawiera byte[]. Implementuje, IEquatable<Binary>że (w efekcie) porównuje dwie tablice bajtów. Zauważ, że System.Data.Linq.Binaryma także domyślny operator konwersji zbyte[] .

Dokumentacja MSDN: System.Data.Linq.Binary

Dekompilacja odbłyśnika metody Equals:

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

Ciekawe jest to, że przechodzą do pętli porównywania bajt po bajcie tylko wtedy, gdy skróty dwóch obiektów binarnych są takie same. Jest to jednak kosztem obliczenia skrótu w konstruktorze Binaryobiektów (przez przemierzanie tablicy za pomocą forpętli :-)).

Powyższa implementacja oznacza, że ​​w najgorszym przypadku może być konieczne trzykrotne przejrzenie tablic: najpierw oblicza się skrót tablicy 1, następnie oblicza skrót tablicy 2, a na koniec (ponieważ jest to najgorszy scenariusz, długości i skróty są równe) w celu porównania bajty w tablicy 1 z bajtami w tablicy 2.

Ogólnie rzecz biorąc, mimo że System.Data.Linq.Binaryjest wbudowany w BCL, nie sądzę, że jest to najszybszy sposób na porównanie dwóch bajtów: - |

Zadałem podobne pytanie o sprawdzenie, czy bajt [] jest pełny zer. (Kod SIMD został pobity, więc usunąłem go z tej odpowiedzi.) Oto najszybszy kod z moich porównań:

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

Mierzone na dwóch tablicach 256 MB:

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

Dodajmy jeszcze jeden!

Ostatnio Microsoft wydał specjalny pakiet NuGet, System.Runtime.CompilerServices.Unsafe . Jest wyjątkowy, ponieważ jest napisany w IL i zapewnia funkcje niskiego poziomu, które nie są bezpośrednio dostępne w języku C #.

Jedna z jego metod Unsafe.As<T>(object)pozwala na rzutowanie dowolnego typu odniesienia na inny typ odniesienia, pomijając wszelkie kontrole bezpieczeństwa. Jest to zwykle bardzo zły pomysł, ale jeśli oba typy mają tę samą strukturę, może działać. Możemy więc użyć tego do byte[]przesłania 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;
}

Zauważ, że long1.Length że nadal zwróci oryginalną długość tablicy, ponieważ jest ona przechowywana w polu w strukturze pamięci tablicy.

Ta metoda nie jest tak szybka, jak inne metody tutaj pokazane, ale jest znacznie szybsza niż metoda naiwna, nie używa niebezpiecznego kodu, P / Invoke ani przypinania, a implementacja jest dość prosta (IMO). Oto niektóre wyniki BenchmarkDotNet z mojej maszyny:

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 |

Stworzyłem również istotę wszystkich testów .

Opracowałem metodę, która lekko bije memcmp()(odpowiedź cokołu) i bardzo lekko bije (odpowiedź Arka EqualBytesLongUnrolled()Bulskiego) na moim komputerze. Zasadniczo rozwija pętlę o 4 zamiast 8.

Aktualizacja 30 marca 2019 r . :

Począwszy od .NET core 3.0, mamy obsługę SIMD!

To rozwiązanie jest najszybsze dzięki znacznemu marginesowi na moim komputerze:

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

Chciałbym użyć niebezpiecznego kodu i uruchomić forpętlę porównującą wskaźniki Int32.

Być może powinieneś również rozważyć sprawdzenie tablic jako niepustych.

Jeśli spojrzysz na to, jak .NET robi string.Equals, zobaczysz, że używa prywatnej metody o nazwie EqualsHelper, która ma „niebezpieczną” implementację wskaźnika. .NET Reflector jest Twoim przyjacielem, aby zobaczyć, jak rzeczy są wykonywane wewnętrznie.

Może to być użyte jako szablon do porównania tablicy bajtów, którą wykonałem na blogu. Szybkie porównanie tablicy bajtów w C # . Zrobiłem również podstawowe testy porównawcze, aby zobaczyć, kiedy bezpieczna implementacja jest szybsza niż niebezpieczna.

To powiedziawszy, jeśli naprawdę nie potrzebujesz zabójczej wydajności, wybrałbym proste porównanie pętli fr.

Nie mogłem znaleźć rozwiązania, z którego jestem całkowicie zadowolony (rozsądna wydajność, ale brak niebezpiecznego kodu / pinvoke), więc wymyśliłem to, nic naprawdę oryginalnego, ale działa:

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

Wydajność w porównaniu z niektórymi innymi rozwiązaniami na tej stronie:

Prosta pętla: 19837 tyknięć, 1,00

* BitConverter: 4886 tyknięć, 4.06

Niebezpieczne Porównaj: 1636 tyknięć, 12.12

EqualBytesLongUnrolled: 637 tyknięć, 31.09

P / Invoke memcmp: 369 tyknięć, 53,67

Testowane na Linqpad, 1000000 bajtów identycznych tablic (najgorszy scenariusz), 500 iteracji każda.

Wygląda na to, że EqualBytesLongUnrolled jest najlepszy z powyższych sugerowanych.

Pominięte metody (Enumerable.SequenceEqual, StructuralComparisons.StructuralEqualityComparer.Equals) nie były zbyt powolne. Na tablicach 265 MB zmierzyłem to:

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 |

Nie widziałem tutaj wielu rozwiązań linq.

Nie jestem pewien wpływu na wydajność, jednak ogólnie trzymam się linqzasady i w razie potrzeby optymalizuję później.

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

Należy pamiętać, że działa to tylko wtedy, gdy są tablicami tego samego rozmiaru. rozszerzenie może tak wyglądać

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

Zrobiłem kilka pomiarów przy użyciu dołączonej wersji programu .net 4.7 bez dołączonego debugera. Myślę, że ludzie używają niewłaściwych danych, ponieważ zależy ci na szybkości, jak długo zajmuje ustalenie, czy dwie tablice bajtów są równe. tzn. przepływność w bajtach.

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

Jak widać, nie ma lepszego sposobu memcmpi jest o rząd wielkości szybszy. Prosta forpętla jest drugą najlepszą opcją. I wciąż zastanawia mnie, dlaczego Microsoft nie może po prostu włączyć Buffer.Comparemetody.

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

Dla porównania tablic krótkich bajtów interesujący jest 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); 

Wtedy prawdopodobnie wpadłbym na rozwiązanie wymienione w pytaniu.

Interesujące byłoby wykonanie analizy wydajności tego kodu.

Dla tych, którzy dbają o porządek (tj. Chcą, memcmpaby zwracany był inttak, jak powinien, zamiast niczego), .NET Core 3.0 (i prawdopodobnie .NET Standard 2.1 aka .NET 5.0) będzie zawierać Span.SequenceCompareTo(...)metodę rozszerzenia (plus a Span.SequenceEqualTo), która może być używane do porównywania dwóch ReadOnlySpan<T>instancji (where T: IComparable<T> ).

W pierwotnym wniosku GitHub dyskusja zawarte porównań podejścia z obliczeń stołowych skok, czytanie byte[]jak long[], SIMD użytkowania, a P / Invoke do tych realizacji CLRmemcmp .

W przyszłości powinna to być twoja metoda porównywania tablic bajtów lub zakresów bajtów (co powinno być używane Span<byte>zamiast byte[]interfejsów API .NET Standard 2.1) i jest wystarczająco szybka, abyś nie przejmował się optymalizacją (i nie, pomimo podobieństw w nazwie nie działa tak bezdennie jak okropny 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

Myślałem o metodach przyspieszania transferu bloków wbudowanych w wiele kart graficznych. Ale wtedy musiałbyś skopiować wszystkie dane bajtowo, więc to ci nie pomoże, jeśli nie chcesz zaimplementować całej logiki w niezarządzanym i zależnym od sprzętu kodzie ...

Innym sposobem optymalizacji podobnym do podejścia pokazanego powyżej byłoby przechowywanie jak największej ilości danych w długim [], a nie w bajcie [] od samego początku, na przykład, jeśli czytasz je sekwencyjnie z pliku binarnego, lub jeśli używasz pliku odwzorowanego w pamięci, wczytaj dane jako długie [] lub pojedyncze długie wartości. Wtedy twoja pętla porównawcza będzie potrzebować tylko 1/8 liczby iteracji, które musiałby wykonać dla bajtu [] zawierającego tę samą ilość danych. To, kiedy i jak często trzeba porównywać, kiedy i jak często trzeba uzyskiwać dostęp do danych bajt po bajcie, np. Aby użyć ich w wywołaniu API jako parametru w metodzie, która oczekuje bajt []. W końcu możesz stwierdzić tylko, czy naprawdę znasz przypadek użycia ...

Jest to prawie na pewno znacznie wolniejsze niż jakakolwiek inna wersja tutaj podana, ale pisanie było fajne.

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

Postawiłem na rozwiązanie inspirowane metodą EqualBytesLongUnrolled opublikowaną przez ArekBulski z dodatkową optymalizacją. W moim przypadku różnice między tablicami w tablicach wydają się być blisko ogona tablic. Podczas testowania odkryłem, że w przypadku dużych tablic możliwość porównania elementów tablicy w odwrotnej kolejności daje temu rozwiązaniu ogromny wzrost wydajności w porównaniu z rozwiązaniem opartym na memcmp. Oto to rozwiązanie:

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

Przepraszamy, jeśli szukasz sposobu zarządzania, to już robisz to poprawnie i, o ile wiem, nie ma wbudowanej metody w BCL.

Powinieneś dodać kilka początkowych kontroli zerowych, a następnie ponownie użyć go tak, jakby to było w BCL.

Użyj SequenceEqualstego do porównania.

Jeśli szukasz bardzo szybkiego narzędzia do porównywania równości w tablicy bajtów, sugeruję zajrzeć do tego artykułu STSdb ​​Labs: Narzędzie do porównywania równości w bajtach.Zawiera niektóre z najszybszych implementacji do porównywania równości macierzy bajtów [], które są prezentowane, testowane i podsumowywane pod kątem wydajności.

Możesz także skupić się na tych implementacjach:

BigEndianByteArrayComparer - szybka byte [] comparer tablica od strony lewej do prawej (bigEndian) BigEndianByteArrayEqualityComparer - - szybki byte [] comparer równość od lewej do prawej (bigEndian) LittleEndianByteArrayComparer - szybki byte [] comparer tablicy od prawej do lewej (littleEndian) LittleEndianByteArrayEqualityComparer - szybka bajt [] porównywarka równości od prawej do lewej (LittleEndian)

Krótka odpowiedź brzmi:

    public bool Compare(byte[] b1, byte[] b2)
    {
        return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
    }

W ten sposób możesz użyć zoptymalizowanego ciągu .NET, aby porównać tablicę bajtów bez potrzeby pisania niebezpiecznego kodu. Oto jak to się robi w tle :

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

Ponieważ wiele powyższych fantazyjnych rozwiązań nie działa z UWP, a ponieważ kocham Linq i podejście funkcjonalne, przedstawiam wam moją wersję tego problemu. Aby uniknąć porównania, gdy pojawi się pierwsza różnica, wybrałem .FirstOrDefault ()

public static bool CompareByteArrays(byte[] ba0, byte[] ba1) =>
    !(ba0.Length != ba1.Length || Enumerable.Range(1,ba0.Length)
        .FirstOrDefault(n => ba0[n] != ba1[n]) > 0);