C # byte [] сравнение без привязанных проверок

Question

Я ищу эффективные способы сравнить два байта [] на равенство. Размеры превышают 1 МБ, поэтому накладные расходы для каждого элемента массива должны быть сведены к минимуму.

Я стремлюсь побить скорости SequenceEqual или ручной цикл for для каждого элемента , с помощью избегая повторных проверок привязки для оба массива. Точно так же, как Array.Copy может привести к быстрому memcpy, что приведет к memcmp?

Answer 1

Вы можете использовать небезопасный код для выполнения операций с указателями. Вы можете сравнить четыре байта за раз как целые числа:

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 проверил это по простой петле, и это примерно в шесть раз быстрее.

Как предположил Джош Эйнштейн, long можно использовать в 64-битной системе. На самом деле он кажется почти вдвое быстрее как на 32, так и на 64-битных системах:

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 2

Если производительность действительно имеет значение, то самый быстрый способ сделать это - использовать библиотеку CRT, включенную в каждую версию Windows. Этот код занимает ~ 51 мсек на моем портативном ноутбуке, также работает на 64-битных машинах:

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 3

От: http://www.pinvoke.net/default.aspx/msvcrt.memcmp: Подпись ниже (Saar) memcmp является подписью только для x64. Использование только подписей x64 на компьютере x86 приведет к дисбалансу стека PInvoke. Для совместимости с платформами x86 и x64 убедитесь, что вы используете сигнатуру, которая задает соглашение о вызовах Cdecl и использует тип UIntPtr для правильной сортировки аргумента 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;
    } 

Я успешно использую этот код, но у меня не было времени измерить производительность (пока). Я использую небольшой массив примерно 600 байтов. Я должен использовать x86-совместимый код, потому что подавляющее большинство компьютеров в нашей некоммерческой организации - x86.

Очевидно, вам нужен быстрый алгоритм для преобразования растрового изображения в байт [].

Answer 4

[DllImport ( "msvcrt.dll")] unsafe static extern int memcmp (void * b1, void * b2, long count);

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