В ядре Linux оптимизирована реализация алгоритма CRC32C

Для включения в состав будущей ветки ядра Linux 6.13 предложен патч с переработанной реализацией алгоритма нахождения контрольной суммы CRC32C. Код реализации CRC32C уменьшен примерно в 10 раз (с 4546 до 418 байт). При выключенной защите retpoline от атак класса Spectre прирост производительности при использовании новой реализации достигает 11.8% на процессорах AMD Zen 2, 6.4% – Intel Emerald Rapids и 4.8% Intel Haswell. При включении retpoline прирост производительности более заметен и достигает 66.8% на системах с процессорами Intel Emerald Rapids, 35.0% – Intel Haswell и 29.5% – AMD Zen 2.

retpoline enabled | 512 | 833 | 1024 | 2000 | 3173 | 4096 | ———————+——-+——-+——-+—— +——-+——-+ Intel Haswell | 35.0% | 20.7% | 17.8% | 9.7% | -0.2% | 4.4% | Intel Emerald Rapids | 66.8% | 45.2% | 36.3% | 19.3% | 0.0% | 5.4% | AMD Zen 2 | 29.5% | 17.2% | 13.5% | 8.6% | -0.5% | 2.8% | retpoline disabled: | 512 | 833 | 1024 | 2000 | 3173 | 4096 | ———————+——-+——-+——-+—— +——-+——-+ Intel Haswell | 3.3% | 4.8% | 4.5% | 0.9% | -2.9% | 0.3% | Intel Emerald Rapids | 7.5% | 6.4% | 5.2% | 2.3% | -0.0% | 0.6% | AMD Zen 2 | 11.8% | 1.4% | 0.2% | 1.3% | -0.9% | -0.2% |

Изначальный вариант CRC32C включал 128 развёрнутых циклов (unroll), что приводило к довольно большому коду. Так как современные процессоры c поддержкой выполнения инструкций не по порядку (out of order) могут выполнять команды параллельно, подобная оптимизация команд перехода в циклах получилась избыточной и приводила лишь к чрезмерно большому коду. Вместо 128 итераций в новом варианте было оставлено только 4, что не только сильно сократило объем кода, но и ускорило выполнение операции.

Release. Ссылка here.