Эти заметки дополняют мою статью ”Параллельное вычисление CRC32”. Предлагается алгоритм вычисления CRC64, основанный на тех же идеях. Производительность алгоритма в 2-2.5 раза выше стандартной табличной реализации вычисления CRC64. На компьютере с процессором E6850/3.2GHz он расходует 2.66 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC64 составляет 0.375 байта за такт центрального процессора или 1.2*10^9 байтов в секунду.
Стандартный табличный алгоритм вычисления CRC64
Для вычисления CRC64 мы будем использовать многочлен 42F0E1EBA9EA3693 (ECMA DLT). У другого кандидата на эту роль – многочлена 000000000000001B (ISO 3309) – из-за его недостаточной плотности было обнаружено большое число коллизий на реальных данных. Стандартный табличный алгоритм вычисления CRC64 выглядит примерно так:
//Вариант 1 стандартный табличный алгоритм вычисления нормальной CRC64 procedure ReferenceRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer); asm test edx, edx jz @ret neg ecx jge @ret sub edx, ecx push ebx push esi push edi push eax mov ebx, [eax+4] mov esi, [eax] mov eax, ebx @next: movzx edi, byte [edx + ecx] shr ebx, 24 xor edi, ebx shld eax, esi, 8 xor eax, [edi*8 + ReferenceTable64 + 4] shl esi, 8 xor esi, [edi*8 + ReferenceTable64] mov ebx, eax add ecx, 1 jz @done movzx edi, byte [edx + ecx] shr eax, 24 xor edi, eax shld ebx, esi, 8 xor ebx, [edi*8 + ReferenceTable64 + 4] shl esi, 8 xor esi, [edi*8 + ReferenceTable64] mov eax, ebx add ecx, 1 jnz @next @done: pop eax mov [eax], esi mov [eax+4], ebx pop edi pop esi pop ebx @ret: end;
Развертывание цикла здесь понадобилось для того, чтобы из цепочки зависимых команд исключить операцию копирования старшего слова контрольной суммы.
Этот вариант алгоритма вычисления CRC64 мы будем использовать в качестве отправной точки, его скорость работы почти совпадает со скоростью работы стандартной реализации вычисления CRC32 на двух протестированных компьютерах (E6850 и Pentium-D).
Зачем нам кузнец
Внимательный читатель, глядя на приведенный код, наверняка заметил, что в противоположность CRC32 при подсчете CRC64 применяется нормальная, а не зеркальная форма представления многочлена и контрольной суммы. Так велит стандарт, именно нормальная форма используется, например, в PostgreSQL и других продуктах.
Понятно, что нормальный алгоритм медленнее зеркального из-за того, что требуется выполнить две лишние операции: копирование старшего слова контрольной суммы и сдвиг старшего байта контрольной суммы. Копирование мы нейтрализовали развертыванием цикла, а вот что делать со сдвигом?
Давайте на секунду отвлечемся и посмотрим, как выглядит реализация зеркального алгоритма вычисления CRC64:
//Вариант 2 стандартный табличный алгоритм вычисления зеркальной CRC64 //на E6850 работает в 1.15 раза быстрее варианта 1 //на Pentium-D работает в 1.1 раза быстрее варианта 1 procedure ReflectedRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer); asm test edx, edx jz @ret neg ecx jge @ret sub edx, ecx push ebx push esi push eax mov ebx, [eax] mov esi, [eax+4] xor eax, eax @next: mov al, byte [edx + ecx] xor al, bl shrd ebx, esi, 8 xor ebx, [eax*8 + ReflectedTable64] shr esi, 8 xor esi, [eax*8 + ReflectedTable64 + 4] add ecx, 1 jnz @next @done: pop eax mov [eax], ebx mov [eax+4], esi pop esi pop ebx @ret: end;
Сравнивая алгоритмы 1 и 2, мы видим, что их отличия заключаются в использовании разных таблиц остатков и разных направлений в операциях сдвига. Понятно также, что нормальный и зеркальный алгоритмы по-разному извлекают очередной байт контрольной суммы для формирования индекса в таблице остатков.
Сказанное наводит на мысль применить зеркальный алгоритм для работы с нормальными таблицами. Все, что нам надо сделать для того, чтобы получить нормальный результат от зеркального алгоритма,– это зеркально переставить байты в нормальной таблице при ее формировании и то же самое сделать с контрольной суммой на входе и выходе процедуры:
//Вариант 3 усовершенствованный алгоритм вычисления нормальной CRC64 //используется таблица остатков с зеркально переставленными байтами //на E6850 работает в 1.15 раза быстрее варианта 1 //на Pentium-D работает в 1.1 раза быстрее варианта 1 procedure NormalRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer); asm test edx, edx jz @ret neg ecx jge @ret sub edx, ecx push ebx push esi push eax mov ebx, [eax+4] mov esi, [eax] bswap ebx bswap esi xor eax, eax @next: mov al, byte [edx + ecx] xor al, bl shrd ebx, esi, 8 xor ebx, [eax*8 + ByteSwappedTable64] shr esi, 8 xor esi, [eax*8 + ByteSwappedTable64 + 4] add ecx, 1 jnz @next @done: bswap ebx bswap esi pop eax mov [eax+4], ebx mov [eax], esi pop esi pop ebx @ret: end;
Скорость этого варианта алгоритма равна скорости зеркального и на процессоре E6850 примерно в 1.15 раза выше, чем у первого варианта.
Кусочно-параллельный алгоритм вычисления CRC64
Теперь, когда у нас есть что оптимизировать и есть с чем сравнивать, приступим к разработке параллельного алгоритма. Все необходимые заготовки у нас уже имеются, осталось только соединить их вместе.
Но сначала заметим, что в случае вычисления CRC64 нет необходимости создавать полностью параллельный алгоритм, как мы это делали для CRC32. Вполне достаточно и кусочно-параллельного алгоритма: ведь если мы будем обрабатывать сообщение порциями по 64 бита, то старшая и младшая части контрольной суммы будут обрабатываться независимо. Причем, по сравнению с CRC32, количество операций чтения табличных данных увеличится в 2 раза, а количество операций, необходимых для формирования адреса, останется прежним, поэтому задержка генерации адреса представляется маловероятной.
Основной цикл алгоритма мы позаимствуем из кусочно-параллельного алгоритма вычисления CRC32. В случае CRC64 он будет выглядеть так:
//Вариант 4 вычисления нормальной CRC64, работа с 64-битными блоками сообщения //используется таблица остатков с зеркально переставленными байтами //на E6850 работает в 2.45 раза быстрее варианта 1 //на Pentium-D работает в 2.0 раза быстрее варианта 1 @bodyloop: mov eax, [edx + ebp - 8] xor eax, ebx movzx edi, al mov ecx, [edx + ebp - 4] xor ecx, esi mov ebx, [edi*8 + ByteSwappedTable64 + 2048*7] mov esi, [edi*8 + ByteSwappedTable64 + 2048*7 + 4] movzx edi, ah xor ebx, [edi*8 + ByteSwappedTable64 + 2048*6] xor esi, [edi*8 + ByteSwappedTable64 + 2048*6 + 4] shr eax, 16 movzx edi, al xor ebx, [edi*8 + ByteSwappedTable64 + 2048*5] xor esi, [edi*8 + ByteSwappedTable64 + 2048*5 + 4] movzx edi, ah xor ebx, [edi*8 + ByteSwappedTable64 + 2048*4] xor esi, [edi*8 + ByteSwappedTable64 + 2048*4 + 4] movzx edi, cl xor ebx, [edi*8 + ByteSwappedTable64 + 2048*3] xor esi, [edi*8 + ByteSwappedTable64 + 2048*3 + 4] movzx edi, ch xor ebx, [edi*8 + ByteSwappedTable64 + 2048*2] xor esi, [edi*8 + ByteSwappedTable64 + 2048*2 + 4] shr ecx, 16 movzx edi, cl xor ebx, [edi*8 + ByteSwappedTable64 + 2048*1] xor esi, [edi*8 + ByteSwappedTable64 + 2048*1 + 4] movzx edi, ch xor ebx, [edi*8 + ByteSwappedTable64 + 2048*0] xor esi, [edi*8 + ByteSwappedTable64 + 2048*0 + 4] add ebp, 8 jle @bodyloop
Этот цикл предназначен для обработки четного числа двойных слов сообщения, головные и хвостовые байты данных мы будем обрабатывать отдельными циклами, подобными циклу из предыдущего варианта вычисления CRC64.
Мы используем таблицу остатков размером 8x256 учетверенных слов, построенную аналогично таблице параллельного алгоритма вычисления CRC32. Еще раз заметим, что только от этой таблицы зависит, какая контрольная сумма (нормальная или зеркальная) вычисляется в основном цикле.
Скорость этого варианта алгоритма вычисления CRC64 на процессоре E6850 примерно в 2.45 раза выше, чем у первого варианта, и по очевидной причине примерно в 2 раза ниже достигнутой нами ранее скорости вычисления CRC32.
Заключение
Мы построили эффективный алгоритм вычисления CRC64, работающий со скоростью практически равной скорости чтения данных из буфера и вспомогательных таблиц. Наряду с относительно малой вероятностью совпадения вычисленных значений это делает привлекательным применение контрольных сумм CRC64 вместо CRC32.
Читатели, используя прилагаемые к статье исходные тексты, могут проверить работу алгоритмов на других процессорах. Буду признателен, если результаты тестов будут ими добавлены на мою страничку (http://guildalfa.ru/alsha/node/4).
Те, кто дочитал до конца, могут снять комментарии кое-где в исходных текстах и поэкспериментировать с зеркальной формой многочлена, который предложил David T. Jones в качестве замены ISO 3309 для хеширования белковых последовательностей. По идее этот многочлен должен хорошо хешировать текстовые данные. При сравнении результатов имейте ввиду, что David T. Jones не выполняет инвертирование значений битов результата в конце вычислений.
Прикрепленный файл | Размер |
---|---|
ShaCRC32.zip | 2.83 кб |
ShaCRC64.zip | 4.33 кб |
Comments (17)
i7-2600
ReferenceRefreshCRC64 2028 msec
NormalRefreshCRC64 1747 msec
ReflectedRefreshCRC64 1763 msec
ShaNormalRefreshCRC64 499 msec
ShaReflectedRefreshCRC64 484 msec
i5-2300
Pentium D 2.80GHz
Intel Pentium 4 HT 2400 MHz
Alexo
Тест на E7200@3.1 Ghz (Разгон)
Athlon X2 2,97 ГГц L2=2x512Кб, L3=2Мб
Причем два последних результата Normal и Reflected часто менялись местами.
Точность измерений составляет 15 msec
Так и должно быть. Для оценки времени выполнения использована функция GetTickCount. Она возвращает значения, которые на Windows XP тикают раз в 15-16 msec.
Нельзя ли преобразовать функцию ShaCrcRefresh в процедуру?
Огромная просьба - нельзя ли преобразовать функцию ShaCrcRefresh в процедуру, как ShaNormalRefreshCRC64 ?
Нельзя ли преобразовать функцию ShaCrcRefresh в процедуру?
А зачем? Ведь всегда можно написать:
Причем в этом случае мы оставляем компилятору полный простор для оптимизации распределения переменных. Скажем, если этот вызов встретится внутри цикла, то для CRC компилятор имеет возможность использовать регистр eax. Если бы у нас была процедура с var-параметром, то компилятор был бы вынужден распределить переменную в памяти.
Есть еще один плюс. Если, например, нам требуется вычислить много мелких CRC для всех слов предложения, то удобна такая форма вызова:
В случае процедуры нам потребовалось бы 2 оператора.
А если я вас не убедил, можете написать процедуру-обертку :)
Нельзя ли переделать ShaReflectedRefreshCRC64 в функцию?
Спасибо, убедили !
А почему тогда ShaReflectedRefreshCRC64 - процедура ?
И тогда нельзя ли её переделать в функцию ?
Зачем ? Чтобы было однообразие вызовов. :)
Нельзя ли переделать ShaReflectedRefreshCRC64 в функцию?
Мешают эстетические соображения.
Компилятор Delphi всегда размещает переменные типа int64 в оперативной памяти. По моим наблюдениям, в регистрах он может держать их только во время вычисления одного оператора. Кроме того, передачу параметров типа int64 по значению компилятор Delphi выполняет через стек. Получается, что после такой переделки при последовательных вызовах функции каждый раз текущее значение CRC64 (два двойных слова) будет копироваться из оперативной памяти на стек (т.е. опять же в оперативную память). В то время как сейчас просто выполняется загрузка адреса параметра.
Давайте посмотрим в окне CPU, какую последовательность инструкций компилятор генерирует при различных вариантах передачи параметров, на следующем примере:
Видно, что только в двух последних случаях компилятор Delphi использует передачу параметра по ссылке. Однако предпоследний вариант мне кажется недостаточно правильным, т.к. в нем не производится проверка типа. Кроме того, он не позволяет передавать константу -1. Поэтому процедура ShaReflectedRefreshCRC64 пока остается процедурой.
Cпасибо за подробный и
Cпасибо за подробный и исчерпывающий ответ !
Использование MMX-инструкций для вычисления CRC64.
Спасибо огромное за модули !
Скорость впечатляет !
И такой вопрос: почему бы в CRC64 не использовать MMX инструкцию PXOR ?
Интересно, как это скажется на быстродействии ?
Использование MMX-инструкций для вычисления CRC64.
Была у меня такая мысль. Для проверки поставил 2 эксперимента.
Сначала попробовал заменить пары команд вида:
на одну:
где N=0,1,2,3,4,5,6,7 или N=0,1,0,1,0,1,0,1
Понятно, что после такой замены зависимых команд не стало больше, однако время работы чуть-чуть выросло.
Выходит, что у нас не остается времени на перенос данных из MMX-регистров в обычные для формирования адреса.
Затем развернул цикл в два раза и использовал в 2 раза большую таблицу (16x256 значений). С учетом времени на перенос данных, получил примерно ту же скорость на E6850, что и без MMX. Поэтому отказался от этой затеи.
Инструкция CRC32 в SSE 4.2
Спасибо !
Любопытно что в Intel наконец-то ввели инструкцию CRC32, начиная с SSE 4.2.
Интересно насколько она оптимизирована ?
Инструкция CRC32 в SSE 4.2
Если не ошибаюсь, время выполнения команды составляет 3 такта. Это означает, что можно вычислять CRC32 еще в 1.78 раза быстрее. Но есть несколько минусов:
Тест на AMD-K6-III@500MHz
Разница в 17% у двух последних функций может показаться довольно странной, ведь основной цикл у них совпадает.
Предположил, что дело в выравнивании кода (в первом случае выравнивание метки @bodyloop 06, во втором - 0E).
Чтобы поменять смещения в процедуру ShaNormalRefreshCRC64 перед меткой вставил 8-байтовую последовательность
Предположение подтвердилось, результат изменился на противоположный:
Итого имеем ускорение 2.1-2.5 раза.