C# byte [] Vergleich ohne gebundene Überprüfungen

Question

Ich bin auf der Suche nach leistungsfähigen Möglichkeiten, zwei Byte [] für die Gleichheit zu vergleichen. Größen liegen über 1 MB, daher sollte der Overhead für jedes Array-Element minimiert werden.

Ich ziele darauf ab, die Geschwindigkeiten von SequenceEqual oder hand-coded for-loop over every item, von avoiding the repetitive bound checks für beide Arrays zu schlagen. In der gleichen Weise, wie Array.Copy zu schnell memcpy führen könnte, was führt zu einem memcmp?

Answer 1

Wenn Leistung wirklich zählt dann dem schnellsten Weg, es zu tun ist durch die CRT-Bibliothek mit jeder Version von Windows enthalten. Dieser Code nimmt ~ 51 msec auf meinem poky Laptop arbeitet auf 64-Bit-Maschinen zu:

using System; 
using System.Runtime.InteropServices; 
using System.Diagnostics; 

class Program { 
    static void Main(string[] args) { 
    byte[] arr1 = new byte[50 * 1024 * 1024]; 
    byte[] arr2 = new byte[50 * 1024 * 1024]; 
    var sw = Stopwatch.StartNew(); 
    bool equal = memcmp(arr1, arr2, arr1.Length) == 0; 
    sw.Stop(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    Console.ReadLine(); 
    } 
    [DllImport("msvcrt.dll")] 
    private static extern int memcmp(byte[] arr1, byte[] arr2, int cnt); 
} 

Answer 2

Sie können unsicheren Code verwenden, um Zeigeroperationen auszuführen. Sie können die Bytes vier zu einem Zeitpunkt, als ganze Zahlen vergleichen:

public static bool ArrayCompare(byte[] a, byte[] b) { 
    if (a.Length != b.Length) return false; 
    int len = a.Length; 
    unsafe { 
    fixed(byte* ap = a, bp = b) { 
     int* aip = (int*)ap, bip = (int*)bp; 
     for (;len >= 4;len-=4) { 
     if (*aip != *bip) return false; 
     aip++; 
     bip++; 
     } 
     byte* ap2 = (byte*)aip, bp2 = (byte*)bip; 
     for (;len>0;len--) { 
     if (*ap2 != *bp2) return false; 
     ap2++; 
     bp2++; 
     } 
    } 
    } 
    return true; 
} 

A diese gegen eine einfache Schleife getestet, und es ist etwa sechsmal schneller.

Wie von Josh Einstein vorgeschlagen, könnte lange auf einem 64-Bit-System verwendet werden. Eigentlich scheint es fast doppelt so schnell sowohl auf 32- und 64-Bit-Systeme zu sein:

public static bool ArrayCompare64(byte[] a, byte[] b) { 
    if (a.Length != b.Length) return false; 
    int len = a.Length; 
    unsafe { 
    fixed (byte* ap = a, bp = b) { 
     long* alp = (long*)ap, blp = (long*)bp; 
     for (; len >= 8; len -= 8) { 
     if (*alp != *blp) return false; 
     alp++; 
     blp++; 
     } 
     byte* ap2 = (byte*)alp, bp2 = (byte*)blp; 
     for (; len > 0; len--) { 
     if (*ap2 != *bp2) return false; 
     ap2++; 
     bp2++; 
     } 
    } 
    } 
    return true; 
} 

Answer 3

[DllImport ("msvcrt.dll")] unsicheres statischen extern int memcmp (void * b1, b2 void * , lange Zählung);

unsafe static int ByteArrayCompare1(byte[] b1, int b1Index, int b1Length, byte[] b2, int b2Index, int b2Length) 
    { 
     CompareCount++; 
     fixed (byte* p1 = b1) 
     fixed (byte* p2 = b2) 
     { 
      int cmp = memcmp(p1 + b1Index, p2 + b2Index, Math.Min(b1Length, b2Length)); 
      if (cmp == 0) 
      { 
       cmp = b1Length.CompareTo(b2Length); 
      } 

      return cmp; 
     } 
    } 

Answer 4

Von: http://www.pinvoke.net/default.aspx/msvcrt.memcmp: Belowmentioned Signatur (von Saar) von memcmp ist eine x64 nur Signatur. Die Verwendung der x64-Einzelsignaturen auf einer x86-Maschine führt zu einem PInvoke-Stack-Ungleichgewicht. Für x86 und x64-Plattform-Kompatibilität sicherstellen, verwenden Sie eine Signatur, die die Cdecl Aufrufkonvention und verwenden den UIntPtr Typen gibt richtig marshall das size_t Argument count:

[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] 
    static extern int memcmp(byte[] b1, byte[] b2, UIntPtr count); 

    static bool doImagesMatch(byte[] b1, byte[] b2) 
    {  
     return b1.Length == b2.Length && memcmp(b1, b2, new UIntPtr((uint)b1.Length)) == 0; 
    } 

ich diesen Code mit Erfolg verwenden, aber ich habe nicht haben Zeit, Leistung zu messen (noch). Ich benutze kleine Arrays von ungefähr 600 Bytes. Ich muss x86-kompatiblen Code verwenden, da die große Mehrheit der Computer in unserer Non-Profit-Organisation x86 ist.

Offensichtlich benötigen Sie einen schnellen Algorithmus, um Bitmap in Byte [] zu konvertieren.