Почему эта реализация CRC32 на C# настолько медленная?

Question

Я использую следующие функции для вычисления CRC32 файла в VS2008, .NET 3.5 проекта:

public UInt32 ComputeHash(System.IO.Stream stream) 
{ 
    unchecked 
    { 
     const int BUFFER_SIZE = 1024; 

     UInt32 crc32Result = 0xFFFFFFFF; 
     byte[] buffer = new byte[BUFFER_SIZE]; 
     int count = stream.Read(buffer, 0, BUFFER_SIZE); 

     while (count > 0) 
     { 
      for (int i = 0; i < count; i++) 
      { 
       crc32Result = ((crc32Result) >> 8)^_crc32Table[(buffer[i])^(crc32Result) & _LOOKUP_TABLE_MAX_INDEX]; 
      } 
      count = stream.Read(buffer, 0, BUFFER_SIZE); 
     } 

     return ~crc32Result; 
    } 
} 

Для краткости я оставил свою функцию, которая создает таблицу поиска (_crc32Table). Таблица представляет собой массив UInt32, который создается при создании экземпляра класса и содержит 256 значений (256 также является значением _LOOKUP_TABLE_MAX_INDEX + 1).

Я провел несколько тестов, сравнивая это с функциями MD5CryptoServiceProvider и SHA1CryptoServiceProvider ComputeHash, и они намного быстрее. Функция MD5 работает в два раза быстрее, а SHA1 - на 35% быстрее. Мне сказали, что CRC32 работает быстро, но это не то, что я вижу.

Я ошибаюсь в своих предположениях? Этого можно ожидать или есть недостаток в этом алгоритме?

Answer 1

Возможно: вы считаете вычисление таблицы поиска в своем наблюдении за пропускной способностью CRC? Обычно таблица поиска вычисляется один раз и кэшируется. Если вы не кэшируете его, вы будете вычислять его каждый раз, когда вы вычисляете CRC. Также, если вы измеряете только один CRC, то, возможно, вы включили стоимость вычислений таблицы в стоимость вычислений CRC. Лучше всего измерить много итераций каждого хэша.

---

Добавление: Когда я измерил, я увидел фактор 2.6x, сравнивая свой CRC32 с хэш MD5, когда приложение был скомпилирован с/отладки + и/optimize-. Используя/debug- и/optimize +, я видел коэффициент 1,6x. Абсолютная производительность MD5 не изменилась при изменении флагов компиляции. Без отладки CRC был еще медленнее, но он был намного ближе.

Answer 2

Вы сравниваете свой код с встроенными функциями и спрашиваете, почему они быстрее. Вам нужно найти источник встроенных функций. Как они работают? Посмотрите, что другое.

Betcha встроенные функции вызываются в родную библиотеку и обманывают, не выполняя внутри управляемой памяти.

Answer 3

Я не слишком хорошо знаком с оптимизациями, которые выполняются автоматически, когда этот код выполняется, но у вас есть пара опций, если профилирование не работает для вас.

Я могу предложить попробовать небезопасный код и использовать арифметику указателя для поиска буфера [i] и _crc32Table в случае, если он еще не оптимизирован.

Единственное другое место, где я вижу, что вы столкнулись с проблемами производительности, - это вызовы Stream.Read. Вы экспериментировали с разными значениями BUFFER_SIZE?

Использование большего байтового буфера и, возможно, внесение некоторого руководства loop unrolling может помочь вам, если они не оптимизируются автоматически.

Answer 4

Профилирование может помочь определить, сколько времени занимает вызов ввода-вывода (чтение) по сравнению с вычислением CRC. Код часто связан с IO. Однако, как кто-то, кто реализовал довольно быструю функцию CRC в C#, я могу дать некоторые указания относительно того, почему она будет медленнее, чем MD5.

• Вы читаете память по одному байту за раз.Внесите slicing-by-four, чтобы вы могли читать по четыре байта за раз или, возможно, нарезать на восемь, чтобы вы могли читать по восемь байтов за один раз (но только, если код действительно работает в 64-битном режиме - вы должны вернуться к разрезанию -by-four в 32-битном режиме, который вы должны проверить, используя if (sizeof (IntPtr) < 8) или аналогичный).
• Вы обрабатываете один байт на итерацию цикла и, таким образом, оплачиваете накладные расходы цикла для каждого байта. Реализуйте slicing-by-N, иначе рассмотрите разворот цикла. (Выполнение обоих может быть ненужным.)
• Вы выполняете две проверки границ массива на каждый байт. Вы можете использовать «небезопасный» код, чтобы избежать проверок границ. С помощью небезопасного кода вы также должны убедиться, что вы выравниваете указатели на чтение, хотя, поскольку вы получаете доступ только к массивам .NET, вы можете предположить, что они уже выровнены по размеру машинного слова. Обратите внимание, что небезопасный код небезопасен, поэтому будьте осторожны!
• MD5 был разработан как очень быстрый алгоритм и не имеет проблем, перечисленных выше. Он считывает несколько байтов одновременно и обрабатывает их параллельно и реализуется в неуправляемом коде.
• Это минор, но ваша конструкция цикла не является оптимальной. Так как вы знаете count! = 0, цикл do/while, который имеет значение pre-decices count (т. Е. --count) и сравнивается с нулем, лучше, чем цикл for, который сравнивает две переменные. С вашим кодом это сохранит пару инструкций и, возможно, память, считанную за байт.

Если вы реализуете slicing-by-N, упакуйте все таблицы поиска в одну большую таблицу, чтобы к ним можно было получить доступ через один и тот же указатель. Вы также можете использовать одну и ту же таблицу для нарезки-на-4 и нарезки-на-8. Также имейте в виду, что типичная реализация slicing-by-N предполагает определенную консистенцию машины, поэтому вам может понадобиться отдельная версия для машин большого конца, которую вы можете проверить на использование BitConverter.IsLittleEndian.