Почему эта реализация CRC32 в C # такая медленная? - PullRequest
Новая
       35

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

4 голосов
/ 03 июня 2009

Я использую следующую функцию для вычисления 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 быстрый, но это не то, что я вижу.

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

Ответы [ 4 ]

6 голосов
/ 03 июня 2009

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

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

3 голосов
/ 08 мая 2016

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

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

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

0 голосов
/ 03 июня 2009

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

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

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

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

0 голосов
/ 03 июня 2009

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

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

...