C# byte [] comparación sin controles vinculados

Question

Estoy buscando formas eficientes de rendimiento para comparar dos bytes [] para la igualdad. Los tamaños son superiores a 1 MB, por lo que la sobrecarga de cada elemento de la matriz debe reducirse al mínimo.

Mi objetivo es superar las velocidades de SequenceEqual o hand-coded for-loop over every item, por avoiding the repetitive bound checks para ambas matrices. De la misma manera que Array.Copy podría conducir a memcpy rápido, ¿qué conducirá a memcmp?

Answer 1

Si el rendimiento realmente importa entonces la forma más rápida de hacerlo es mediante el uso de la biblioteca CRT incluye con cada versión de Windows. Este código toma ~ 51 ms penas se percibía en mi portátil, funciona en equipos de 64 bits también:

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

Puede usar un código no seguro para realizar operaciones de puntero. Puede comparar los bytes cuatro a la vez como enteros:

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

Un probado esto en contra de un bucle simple, y es aproximadamente seis veces más rápido.

Según lo sugerido por Josh Einstein, long podría usarse en un sistema de 64 bits. En realidad, parece ser casi dos veces más rápido tanto en 32 y 64 bits sistemas:

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")] insegura extern int estática memcmp (void * b1, b2 void * , cuenta larga);

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

Desde: http://www.pinvoke.net/default.aspx/msvcrt.memcmp: Belowmentioned firma (por Saar) de memcmp es un x64 solamente firma. El uso de las firmas x64 solo en una máquina x86 dará como resultado un desequilibrio de pila PInvoke. Para x86 y x64 compatibilidad de la plataforma que asegúrese de usar una firma que especifica el convenio de llamada Cdecl y utiliza el tipo UIntPtr a Marshall correctamente el argumento size_t 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; 
    } 

Puedo utilizar este código con éxito, pero no tenía tiempo para medir el rendimiento (aún). Estoy usando pequeñas matrices de aproximadamente 600 bytes. Tengo que usar un código compatible con x86 porque la gran mayoría de las computadoras de nuestra organización sin fines de lucro es x86.

Obviamente necesita un algoritmo rápido para convertir el mapa de bits a byte [].