Предлагаю вашему вниманию еще один подход к построению алгоритмов вычисления CRC32. Хотя многие использованные в нем идеи в той или иной мере содержатся в известных руководствах по оптимизации кода для IA32 и вычислению CRC32, он может представлять некоторый интерес. Использование свойств CRC-арифметики позволило разработать алгоритм вычисления CRC32, имеющий производительность в 3-5 раз выше стандартной табличной реализации. Например, на компьютере с процессором E6850/3.2GHz он расходует 1.33 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC32 составляет 0.75 байта за такт центрального процессора или 2.4*10^9 байтов в секунду.
Продолжение читайте в статье ”Параллельное вычисление CRC64”.
Несколько слов о CRC-арифметике
CRC-арифметика оперирует многочленами, имеющими коэффициенты 0 и 1. Для представления таких многочленов в компьютере используются двоичные числа, имеющие соответствующие значения битов. Операции над битами этих чисел выполняются без межразрядных переносов и заемов. В качестве операций сложения и вычитания используется "исключающее или". Умножение и деление с остатком выполняются как обычно при помощи серии сдвигов и сложений.
CRC-арифметика обладает двумя важными свойствами, которые лежат в основе всех связанных с ней алгоритмов:
- Свойство 1. Остаток от деления суммы многочленов на многочлен равен сумме остатков от деления этих многочленов на тот же делитель.
- Свойство 2. Если остатки от деления двух многочленов на третий совпадают, то совпадут и остатки от деления на тот же делитель их произведений на некоторый многочлен.
В частности, свойство 2 означает, что произведение многочлена на x^n имеет такой же остаток от деления на некоторый делитель, как и произведение на x^n остатка от деления этого многочлена на тот же делитель.
Применяя теорию
Известно, что при вычислении контрольной суммы по алгоритму CRC32 сообщение рассматривается как многочлен и что (если не учитывать инициализацию и финализацию) контрольная сумма CRC32 представляет собой остаток от деления этого многочлена, умноженного на x^32, на "магический" многочлен 32-й степени.
Делить многочлены "столбиком" со сдвигом на 1 бит на каждой итерации слишком медленно, поэтому на практике используют более быстрые алгоритмы, основанные на свойствах CRC-арифметики. Давайте рассмотрим, как это делается, на примере алгоритма, работающего с группами из восьми битов. Пусть в качестве сообщений у нас выступают ASCII-строки, и предположим, что мы уже умеем вычислять остаток для любого односимвольного сообщения. Требуется вычислить остаток для строки 'ABC'.
Будем вычислять остаток посимвольно. Присвоим текущей строке значение, равное первому символу 'A'. Это односимвольное сообщение, и по условию задачи для него мы умеем вычислять остаток. Запишем это значение в текущий остаток. Текущий остаток может храниться в 32-битной переменной, т.к. его степень всегда меньше 32. Текущая строка — понятие виртуальное, вместо нее можно хранить адрес текущего байта данных.
Припишем к текущей строке второй символ 'B'. Как теперь вычислить остаток для получившейся строки 'AB'? Мысленно разобьем ее биты на две строки: двухсимвольную 'A'#0 и односимвольную 'B'. Сумма многочленов, соответствующих этим строкам, равна многочлену, соответствующему неразбитой строке. В таком случае свойство 1 позволяет нам вычислить остатки для строк, полученных в результате разбиения, и сложить. Причем по условию задачи для односимвольной строки мы умеем вычислять остаток.
Чтобы вычислить остаток для двухсимвольной строки 'A'#0 воспользуемся свойством 2. Заметим, что ее значение получено из прежнего текущего значения приписыванием справа нулевого символа, что эквивалентно умножению соответствующего строке многочлена на x^8. Значит, мы должны просто умножить текущий остаток на x^8 (сдвинуть влево на 8 разрядов) и вычислить остаток для полученного произведения. Произведение будет состоять из двух частей: старшие 8 бит, вытолкнутые за разрядную сетку, и младшие 24 бита, сдвинутые влево. Понятно, что младшая часть сама по себе продолжает оставаться остатком, а старшая часть соответствует некоторому односимвольному сообщению (для которого мы умеем вычислять остаток), и по свойству 1 нам остается лишь сложить эти остатки.
Наконец, припишем к текущей строке третий символ и разобьем ее на две 'AB'#0 и 'C'. Снова пересчитаем текущий остаток. Задача решена.
Таким образом, для каждого байта данных мы в цикле делаем следующее:
- сдвигаем текущее значение CRC на 8 битов влево,
- прибавляем к результату значение CRC для байта, выдвинутого за разрядную сетку,
- прибавляем к результату значение CRC для очередного байта.
Если мы планируем хранить значения CRC для однобайтовых сообщений в таблице, то имеет смысл для уменьшения числа обращений к таблице еще раз применить свойство 1 и модифицировать алгоритм следующим образом:
- сдвигаем текущее значение CRC на 8 битов влево,
- складываем (по правилам CRC-арифметики) очередной байт данных и байт, выдвинутый за разрядную сетку,
- прибавляем к текущему значению CRC значение CRC для полученного байта.
Стандартный табличный алгоритм
Фактически в приведенном выше примере описан стандартный табличный алгоритм вычисления CRC32: обработка битов сообщения группами по 8 бит, хранение в таблице предварительно вычисленных значений остатков для всех однобайтовых сообщений. Некоторые несущественные детали остались за кадром, например, использование сдвига вправо вместо сдвига влево для совместимости с аппаратурой.
Существуют две примерно равных по скорости ассемблерных реализации стандартного табличного алгоритма, которые различаются способом загрузки в регистр очередного байта данных:
//Вариант 1 загрузка данных командой MOVZX function RefreshCRC11(OldCRC: cardinal; StPtr: pointer; StLen: integer): cardinal; asm test edx, edx jz @ret neg ecx jz @ret sub edx,ecx push ebx @next: movzx ebx, byte [edx + ecx] xor bl, al shr eax, 8 xor eax, [ebx*4 + tbl] add ecx, 1 jnz @next pop ebx @ret: end;
//Вариант 2 загрузка данных командой LODSB //на E6850 работает в 1.16 раза БЫСТРЕЕ варианта 1 //на Pentium-D работает в 1.66 раза МЕДЛЕННЕЕ варианта 1 function RefreshCRC11s(OldCRC: cardinal; StPtr: pointer; StLen: integer): cardinal; asm test edx, edx jz @ret test ecx, ecx jz @ret push esi push edi mov esi, edx lea edi, tbl add ecx, edx mov edx, eax xor eax, eax @next: lodsb xor al, dl shr edx, 8 xor edx, [eax*4 + edi] cmp esi, ecx jne @next mov eax, edx pop edi pop esi @ret: end;
Соотношение скоростей этих вариантов может меняться в зависимости от процессора.
Больше незачем платить?
Чтобы ускорить вычисления обычно пробуют развернуть цикл, а чтение данных выполнять двойными словами. В одном платном продукте мне тоже встречался этот прием. Забавно, что он совсем не влияет на скорость выполнения алгоритма на процессорах, с которыми мне доводилось иметь дело. Даже если в развернутом цикле удалить операторы сдвига текущего значения остатка, время работы останется прежним.
//Вариант 3 - развернутый цикл, загрузка данных командой MOVZX //на E6850 и Pentium-D работает с той же скоростью, что и вариант 1 //Предупреждение: часть команд в теле цикла специально удалена, // вычисление CRC32 выполняется неверно @next: mov edx, [esi + ecx] movzx ebx, dl xor bl, al xor eax, [ebx*4 + tbl] movzx ebx, dh xor bl, al xor eax, [ebx*4 + tbl] shr edx, 16 movzx ebx, dl xor bl, al xor eax, [ebx*4 + tbl] movzx ebx, dh xor bl, al xor eax, [ebx*4 + tbl] add ecx, 4 jnz @next
Результат закономерный. В нашем случае весь цикл представляет собой одну длинную цепочку зависимых вычислений: почти в каждой команде операнд зависит от результата выполнения предыдущей инструкции. И что особенно плохо, несколько раз этим операндом оказывается адрес данных для следующей инструкции, и, как следствие, происходит задержка генерации адреса.
Большой табличный алгоритм
Попробуем пойти другим путем. Увеличим количество битов в группе в два раза, т.е. будем работать со словами, а не с байтами. Естественно, при этом нам придется увеличить размер таблицы в 256 раз, т.к. теперь в ней будут храниться контрольные суммы для всех двухбайтовых сообщений. Размер таблицы составит 256K.
При этом, с одной стороны, скорость должна возрасти, т.к. мы прочитаем сообщение в два раза быстрее. С другой стороны, скорость должна уменьшиться, т.к. размер таблицы превышает размер процессорного кэша первого уровня. Это означает, что могут случаться промахи при чтении сообщения и табличных данных.
//Вариант 4 – пословная обработка, таблица на 64K значений CRC //на E6850 работает примерно в 1.3 раза медленнее варианта 1 @next: lodsw xor ax, dx shr edx, 16 xor edx, [eax*4 + edi] cmp esi, ecx jne @next
В результате этот вариант работает заметно медленнее первоначального алгоритма. В реальных условиях кэш будет содержать другие данные приложения, и скорость будет еще меньше.
Кусочно-параллельный алгоритм
Давайте представим себе, какой должна быть оптимальная реализация. Во-первых, скорость чтения сообщения должна быть достаточно высокой, поэтому желательно чтение сообщения выполнять двойными словами. Во-вторых, желательно уменьшить зависимость между инструкциями, относящимися к различным группам битов. Нам хотелось бы оперировать большими группами битов, например, также двойными словами. Но в этом случае таблица будет просто огромной – 2^32 элементов. Даже если ее было бы возможно поместить в памяти приложения, из-за промахов чтения скорость работы с ней была бы очень низкой.
Снова вспомним о свойстве 1 CRC-арифметики. Благодаря ему мы можем вместо обращения к большой таблице за значением остатка для четырехбайтовой строки stuv вычислить это значение на лету как сумму остатков для строк s#0#0#0, t#0#0, u#0, v. Естественно, для этого нам потребуются еще 3 дополнительных таблицы остатков, содержащие по 256 элементов каждая. Работа с 32-битными порциями данных упрощает алгоритм и может дополнительно увеличить его скорость, т.к. теперь все инструкции логического сложения становятся 32-битными, а сдвиг текущего остатка на 32 бита можно опустить:
//Вариант 5 – таблица на 1K значений CRC //на E6850 работает примерно в 2.5 раза быстрее варианта 1 @next: mov edx, [esi + ecx] xor edx, eax movzx ebx, dl mov eax, [ebx*4 + tbl + 1024*3] movzx ebx, dh xor eax, [ebx*4 + tbl + 1024*2] shr edx, 16 movzx ebx, dl xor eax, [ebx*4 + tbl + 1024*1] movzx ebx, dh xor eax, [ebx*4 + tbl + 1024*0] add ecx, 4 jnz @next
Этот вариант алгоритма показывает скорость примерно в 2.5 раза выше, чем первый. Такой скачек производительности стал возможен потому, что здесь уже нет зависимости между вычислениями для байтов в одном двойном слове. Соответствующие микрокоманды процессор исполняет параллельно. Но зависимость между вычислениями для двойных слов сохраняется. Попробуем развернуть цикл и занять процессор полезной работой во время вынужденных простоев:
//Вариант 6 – таблица на 1K значений CRC, развернутый цикл //на E6850 работает примерно в 2.7 раза быстрее варианта 1 @next: xor eax, [edx + ecx - 8] mov ebx, [edx + ecx - 4] movzx esi, al movzx edi, ah xor ebx, [esi*4 + tbl + 1024*3] xor ebx, [edi*4 + tbl + 1024*2] shr eax, 16 movzx esi, al movzx edi, ah xor ebx, [esi*4 + tbl + 1024*1] xor ebx, [edi*4 + tbl + 1024*0] movzx esi, bl mov eax, [esi*4 + tbl + 1024*3] movzx esi, bh shr ebx, 16 xor eax, [esi*4 + tbl + 1024*2] movzx esi, bl xor eax, [esi*4 + tbl + 1024*1] movzx esi, bh xor eax, [esi*4 + tbl + 1024*0] add ecx, 8 jle @next
Нам удалось повысить скорость еще на 10%, но так и не удалось устранить зависимость вычислений при переходе через границу двойного слова.
Параллельный алгоритм
Попробуем читать и обрабатывать данные двумя цепочками инструкций: в одной — четные двойные слова, в другой — нечетные. При этом "четная" цепочка каждый раз начинает вычислять CRC с нулевого значения, и полученный результат потом добавляется к результату вычислений "нечетной" цепочки. Понятно, что при таком построении алгоритма риск получить задержку генерации адреса заметно ниже.
Фактически мы будем обрабатывать сообщение 64-битными блоками. Аналогично предыдущему варианту алгоритма мы будем рассматривать каждый блок как восьмибайтовое сообщение и разбивать его на 8 сообщений, для которых будем брать значение CRC из таблицы.
Таблица остатков содержит 2K значений и представляет собой матрицу 8x256, каждая цепочка инструкций использует половину строк этой таблицы. Значения в первой строке матрицы совпадают со значениями в таблице стандартного табличного алгоритма — это остатки для всевозможных однобайтовых сообщений. Во второй строке содержатся остатки для всевозможных двухбайтовых сообщений, оканчивающихся нулевым байтом. В третьей — остатки для трехбайтовых сообщений, оканчивающихся двумя нулевыми байтами, и т.д.
Чтобы исключить операции пересылки текущего значения остатка, основной цикл алгоритма пришлось развернуть:
//Вариант 7 – таблица на 2K значений CRC, развернутый цикл //на E6850 работает примерно в 4.65 раза быстрее варианта 1 //0.75 байта за такт на E6850 @next: mov ebx, [edi + ecx - 4] xor edx, [edi + ecx - 8] movzx esi, bl mov eax, [esi*4 + tbl + 1024*3] movzx esi, bh xor eax, [esi*4 + tbl + 1024*2] shr ebx, 16 movzx esi, bl xor eax, [esi*4 + tbl + 1024*1] movzx esi, bh xor eax, [esi*4 + tbl + 1024*0] movzx esi, dl xor eax, [esi*4 + tbl + 1024*7] movzx esi, dh xor eax, [esi*4 + tbl + 1024*6] shr edx, 16 movzx esi, dl xor eax, [esi*4 + tbl + 1024*5] movzx esi, dh xor eax, [esi*4 + tbl + 1024*4] add ecx, 8 jg @done mov ebx, [edi + ecx - 4] xor eax, [edi + ecx - 8] movzx esi, bl mov edx, [esi*4 + tbl + 1024*3] movzx esi, bh xor edx, [esi*4 + tbl + 1024*2] shr ebx, 16 movzx esi, bl xor edx, [esi*4 + tbl + 1024*1] movzx esi, bh xor edx, [esi*4 + tbl + 1024*0] movzx esi, al xor edx, [esi*4 + tbl + 1024*7] movzx esi, ah xor edx, [esi*4 + tbl + 1024*6] shr eax, 16 movzx esi, al xor edx, [esi*4 + tbl + 1024*5] movzx esi, ah xor edx, [esi*4 + tbl + 1024*4] add ecx, 8 jle @next mov eax, edx @done:
Скорость этого алгоритма на процессоре E6850 близка к пределу. Она примерно в 4.65 раза выше, чем у первого алгоритма. Даже если выбросить из него все операции, кроме операций, работающих с оперативной памятью и операций управления циклом, его скорость возрастет всего в 1.06 раза.
Соответствующие результаты для процессора Pentium-D не так впечатляют (3.13 и 1.48). Читатели, используя прилагаемые к статье исходные тексты, могут проверить работу алгоритма на других процессорах. Буду признателен, если результаты тестов будут ими добавлены на мою страничку (http://guildalfa.ru/alsha/node/2).
Заключение
Используя свойства CRC-арифметики, мы разработали эффективный алгоритм, позволяющий процессору параллельно выполнять микроинструкции выборки и обработки данных с минимальными простоями и со скоростью практически равной скорости чтения данных из буфера и вспомогательных таблиц.
На свойствах CRC-арифметики построены и другие алгоритмические трюки. В ряде публикаций, например, приводится описание алгоритма подгонки CRC файла к заданному значению при помощи изменения четырех смежных байтов. Если вы дочитали до этого места, то, вероятно, вам будет интересно самим разобраться, как это делается. А может быть, вы предложите алгоритм вычисления CRC нескольких сцепленных файлов? Или алгоритм вычисления CRC всех фраз предложения, состоящих из N последовательных слов? Или собственную реализацию CRC64?
Продолжение читайте в статье ”Параллельное вычисление CRC64”.
Comments (25)
развёрнутый код (два блока а посередине условный выход)
Вы писали "чтобы исключить операции пересылки текущего значения остатка, основной цикл алгоритма пришлось развернуть", то есть получилось два блока, а посередине условный выход.
Вы привели код по такой схеме:
Если удалить второй блок, то код будет выглядеть примерно так:
При этом скорость не уменьшится, а даже увеличится, за счёт уменьшения числа ветвлений. Если код будет вызываться каждый раз с разным размером буфера, то мы уменьшаем вероятность "branch mispredition penalty", и упрощам код, что позволяет процессору легче спрогнозировать окончание цикла. Для простых циклов процессоры, такие как Skylake, c MacroOp fusion, прогнозирует его окончание удивительно хорошо.
А можно попросить сделать x64
А можно попросить сделать x64 версию этого всего? Чтобы можно было это откомпилить под Winx64?
x64-версия
Есть x64-версия на https://github.com/maximmasiutin/CRC32-Slicing-x64-Asm-Pas
А можно попросить сделать x64
Это не актуально, т.к. версия x64,
полностью написанная на Delphi,
должна работать достаточно быстро.
x64-версия на ассемблере всё равно быстрее
Версия на ассемблере на один байт данных тратит 1,20 циклов процессора, а версия на паскале (Delphi 10.3.3) тратит 1,84 цикла, а на FPC ещё больше, так что ассемблерная версия более чем актуальна. Прчем количество циклов на байт что в 32-битном что в 64-битном коде практически одинаково, будь то ассемблерная или паскалевская версия.
AMD A10-6800K 4.10 GHz
CRC=261DAEE5
Res=261DAEE5
CRC=C39FDC84
Res=C39FDC84
ReferenceCrcRefresh 16239 msec
ShaCrcRefresh 3261 msec
Модуль
Огромное спасибо за ваши исследования, вы настоящий учёный. Очень понравился ваш быстрый и
компактный модуль подсчёта CRC32, несколько перебрал - ваш вне конкуренции
i5-2300
Быстрее в 4.5 раза
Number of cores 1 (max
Number of cores 1 (max 1)
Number of threads 2 (max 2)
Name Intel Pentium 4
Codename Northwood
Specification Intel(R) Pentium(R) 4 CPU 2.80GHz
ReferenceCrcRefresh 18422 msec
ShaCrcRefresh 9890 msec
Ускорение в 1.86 раз. Очень неплохо!
Duo T9400
Duo T9400
ускорение в 4,6 раза. Просто здорово :)
Pentium D 2.80GHz
Быстрее в 3.1 раза
Intel Pentium 4 HT 2400 MHz
Кэш L1 трассировки 12K
Кэш L1 данных 8 Кб
Кэш L2 512 Кб
1 ядро
ReferenceCrcRefresh 21141 msec
ShaCrcRefresh 11312 msec
2 как бы ядра
ReferenceCrcRefresh 20969 msec
ShaCrcRefresh 11266 msec
всего лишь в 2 раза
Atlon X2 2,97ГГц L2=2x512Мб, L3=2Мб
Тест на Athlon 64
Тест на Athlon 64 6000+
Тест на AMD-K6-III@500MHz
Ускорение 4 раза.
Athlon64 3500+ (2.2 ГГц)
Тест на Pentium3 @ 866MHz
Ускорение 6.5 раз!
Core 2 Duo E6750 @ 2.66 Ghz
Core2duo T5870@2.0 Ghz/667Mhz
Core2duo T5870@2.0 Ghz/667Mhz ram
Тест на Xeon E5410 2.33 12Mb L2
Тест на Xeon 3.0 2Mb L2
Тест на Celeron D 2.6
Обладаю достаточно древним процессором "Celeron D 2.6" (трудяга пережил разряд статики и несколько апгрейдов, висту гоняет нормально, в общем лень менять :) А результаты он показал такие:
Тест на Celeron D 3.3
Тест на AthlonXP@2,1ГГц
Тест на Intel Core 2 Duo E6700