При оптимизации специализированного компрессора обнаружилась необычная ситуация. Алгоритм разбивает строку на чанки и выбирает оптимальное кодирование для каждого — по сути, поиск кратчайшего пути на сетке. После сложного SIMD-цикла, который вычисляет next_j — индекс следующего чанка для каждого из 8 вариантов, — идёт простой цикл: j = next_j[i][j], а затем encoding[i] = j. Этот цикл компилируется в одну инструкцию mov, но работает медленно, потому что между итерациями есть зависимость по переменной j. Процессор не может выполнять зависимые инструкции параллельно, и производительность упирается в задержку доступа к памяти, даже если данные в кэше.
Можно ли это исправить? В данном случае — да. Поскольку next_j[i][j] чаще всего равно j (чанк остаётся в том же кодировании), можно добавить проверку: if (j != next_j[i][j]) j = next_j[i][j]. Если процессор предскажет, что условие ложно, он не увидит зависимости между итерациями и сможет выполнять их параллельно. При редком истинном условии произойдёт misprediction, но это окупается.
Проблема в том, что компилятор считает этот if бесполезным — обе ветви присваивают одно и то же значение, и любой CSE pass удалит проверку без колебаний. Чтобы обмануть компилятор, автор использовал каст к volatile: j = *(uint8_t volatile*)&next_j[i][j]. Это заставляет компилятор честно выполнить чтение и присваивание, сохраняя логику ветвления.
В синтетическом бенчмарке такой трюк сократил время выполнения цикла с 320 мкс до 80 мкс — ускорение в 4 раза. В реальной нагрузке эффект оказался слабее (примерно 2×) из-за неоптимальной кодогенерации LLVM, но всё равно заметно. Автор также отмечает, что в этом алгоритме next_j[i][j] может быть только двумя значениями: j или значение, зависящее только от i. Можно было бы хранить пару (значение, битовая маска) и проверять бит, но на x86 проверка бита обычно медленнее простого сравнения, так что такое перепроектирование скорее замедлило бы код.