Инженеры компании Cybozu Labs, специализирующиеся на глубокой оптимизации низкоуровневых вычислений, представили инновационный подход к делению на константу для 64-битных архитектур. Новый метод успешно обходит ограничения устаревших алгоритмов, эффективно используя преимущества увеличенной разрядности современных процессоров. Предложенное решение уже стало частью кодовой базы LLVM (включая Clang 23.0.0), а аналогичные обновления для компиляторов GCC и MSVC сейчас проходят финальное тестирование.
На протяжении десятилетий современные компиляторы полагались на методы, разработанные еще в середине 90-х годов под 32-битные системы. Стандартом деления на константу с 1994 года оставался алгоритм Гранлунда–Монтгомери (GM), который заменяет операцию деления на умножение с помощью «магических чисел» и сдвигов. Однако при работе с 64-битными процессорами этот подход демонстрирует неэффективность в так называемых «33-битных сценариях». Примерно в 3% случаев (например, при делении на 7, 19 или 107) метод требует промежуточных вычислений с 33-битными множителями, что искусственно удлиняет критический путь и мешает параллельному исполнению инструкций.
Разработчики Мицунари Шигео и Хошино Такаши предложили отойти от имитации 33-битной арифметики, перейдя к прямой обработке данных в 64-битной сетке. Математическая модель, предложенная авторами, выглядит как (x⋅(264−a ⋅c))//264, где x — делимое, а c — константа. Ключевое преимущество метода заключается в использовании специфических инструкций процессоров: MULX на платформе x86-64 (умножение без влияния на флаги) и UMULH на архитектурах ARM/Apple Silicon (извлечение старших 64 бит результата). Такой переход позволяет свести операцию деления к минимально возможному количеству тактов.
Если классический GM-метод требовал выполнения цикла из 9 инструкций, включая цепочку сложений и сдвигов, то новая техника сокращает этот путь всего до 3 операций. Снижение латентности и уменьшение количества зависимых данных обеспечивают существенный прирост производительности на современном «железе».
Результаты тестов на чипах Intel Xeon w9-3495X и Apple M4 показали впечатляющие результаты: ускорение составило 1.67x и 1.98x соответственно. На процессорах Apple M4 столь высокий результат обусловлен архитектурными особенностями блока умножения, тогда как на Xeon решение дополнительно повысило стабильность времени выполнения кода — стандартное отклонение сократилось с 0.013 до 0.009 секунд, что критически важно для высоконагруженных серверных систем.
Внедрение этой технологии в ключевые компиляторы позволит оптимизировать работу высоконагруженного ПО: баз данных, криптографических библиотек и систем обработки сетевых пакетов. Фактически, это масштабное избавление от «технологического багажа» прошлого, которое позволит разработчикам получать значительный прирост быстродействия своих приложений без изменения исходного кода, просто за счет пересборки проекта с использованием актуальных версий компиляторов.
Источник: iXBT
