Оптимизация декодирования зигзага на AVX-512

Ключевые факты

• Зигзаг-кодирование преобразует знак числа в младший бит, позволяя кодировать малые значения с меньшим количеством байт
• Маскировка в AVX-512 позволяет условно инвертировать значения, но увеличивает latency на 1 цикл из-за замедления vptestmd
• На throughput-bound коде маски теоретически быстрее (0.75 vs 1 цикл на 3-4 инструкции), но в практике meshoptimizer дают только 3% прирост
• Clang агрессивно канонизирует векторные интринсики и отменяет оптимизации с масками, оставляя исходный код
• GFNI инструкции (Galois Field) предоставляют побитовые трансформации, но требуют отдельную проверку CPUID

Ред. Героически убрали одну инструкцию, добавили цикл latency. Чистая поэзия низкоуровневой оптимизации.

Почему это важно

Декодирование дельта-кодированных значений встречается в сжатых сетках, мешлетах и потоках данных. Ускорение этой операции на 3-5% может дать значимый выигрыш в пропускной способности. Однако не все оптимизации одинаково полезны: попытка снизить количество инструкций может привести к увеличению latency, что замедлит latency-bound код. Важно понимать, где находится узкое место конкретного алгоритма, прежде чем применять трюки с масками.

Ред. 3-5% прироста, который при неверном профиле превращается в 3-5% замедления. Знак зависит от того, читали ли вы профилировщик.

Кому это важно

Разработчикам, работающим с SIMD-оптимизациями на Zen 4 и других процессорах с AVX-512. В частности, авторам библиотек для сжатия геометрии (meshoptimizer), обработки 3D-моделей и других задач с высокой пропускной способностью. Также полезно тем, кто занимается низкоуровневой оптимизацией и борется с компилятором (Clang часто отменяет такие трюки).

Ред. Целевая аудитория это люди, которые добровольно вступают в спор с Clang. Их немного, но они упорные.

Как это применить

При оптимизации цикла декодирования зигзага сначала профилируйте: является ли он latency-bound или throughput-bound. На latency-bound коде маски вероятно замедлят выполнение из-за latency vptestmd. На throughput-bound коде стоит экспериментировать с условным XOR/SUB через маски. Для 16-битных данных используйте условный subtract вместо XOR, так как AVX-512 не поддерживает маскированный 16-битный XOR. Если компилятор Clang отменяет оптимизацию, попробуйте переструктурировать выражение (например, добавив + 1 к результату).

Ред. «Добавьте + 1, чтобы обмануть компилятор» это рецепт, который через год придёт читать ваш коллега и тихо проклянёт автора того самого + 1.

Можно ли доверять

Автор провел экспериментальные измерения на meshoptimizer и приводит точные цифры latency с uops.info. Однако результаты зависимы от конкретного процессора (данные для Zen 4) и компилятора. Поведение Clang с отменой оптимизаций документировано в LLVM как canonical behavior, что верно, но демонстрирует потребность во внимательном профилированию и проверке сгенерированного кода.

Ред. Цифры точные, но только для Zen 4 и только для этого Clang. На вашем железе доверять придётся уже своим замерам.

Риски и подводные камни

Главный риск: оптимизация по количеству инструкций может быть контрпродуктивна на latency-bound коде, так как vptestmd добавляет 3 цикла latency. Второй риск: Clang часто отменяет такие трюки, оставляя разработчика с исходным кодом. Третий: маски работают не для всех типов данных (16-битный XOR недоступен). Четвёртый: портовое давление инструкций может варьироваться в зависимости от окружающего кода.

Ред. Четыре риска ради 3% на хорошем дне. Неудивительно, что в meshoptimizer обе техники вежливо отклонили.

«We heroically reduced the instruction count by 1, but not all instructions are created equal. Is the result faster? The answer is, as all good answers are in cases like this, 'it depends'.»

— Arseny Kapoulkine, zeux.io