Прорыв в компиляторах: оптимизация деления ускорила процессоры Apple и Intel почти вдвое
Оптимизация устраняет «проблему 33-го бита» и уже внедрена в LLVM, с обновлениями для GCC и MSVC на подходе
Инженеры-разработчики из японской компании Cybozu Labs, специализирующейся на разработке программного обеспечения и оптимизации вычислительных процессов, предложили новый метод деления на константу для 64-битных процессоров. Этот метод устраняет ограничения устаревших 32-битных алгоритмов, используя избыточную разрядность современных регистров. Патч уже интегрирован в LLVM (Low Level Virtual Machine) — популярный проект с открытым исходным кодом, который включает компилятор Clang (версия 23.0.0). Обновления для GCC (GNU Compiler Collection) и MSVC (Microsoft Visual C++) находятся на стадии тестирования.
Современные компиляторы (GCC, Clang, MSVC) до сих пор использовали алгоритмы 30-летней давности, оптимизированные под 32-битные процессоры, даже когда код исполняется на мощных 64-битных системах. С 1994 года стандартом деления на константу в компиляторах был метод Гранлунда и Монтгомери (GM-метод). Этот подход заменяет деление на умножение на «магическую константу» и битовые сдвиги. Однако метод сталкивается с ограничениями при работе с «33-битными делителями», что приводит к избыточным вычислениям и снижению производительности на современных 64-битных процессорах. Так, в 3% случаев при делении 32-битных чисел на константу (например, при делении на 7, 19 или 107) требуются промежуточные вычисления с использованием 33-битных «магических чисел», что создает длинный критический путь и ограничивает параллелизм.
Инновация Мицунари Шигео (Mitsunari Shigeo) и Хошино Такаши (Hoshino Takashi) заключается в отказе от имитации 33-битной арифметики в пользу прямой трансформации формулы с использованием 64-битной сетки. Вместо сложной последовательности команд коррекции используется элегантная математическая модель: (x⋅(264−a ⋅c))//264, где x — делимое, расширенное до 64 бит, а c — магическая константа. На процессорах с архитектурой x86-64 используется MULX (Unsigned Multiply Without Affecting Flags), которая не модифицирует флаги процессора, а на ARM/Apple Silicon — UMULH (Unsigned Multiply High), извлекающая верхние 64 бита результата умножения. Эти инструкции позволяют выполнять деление за одну операцию, что значительно ускоряет вычисления.
Для сравнения, старый GM-метод требует до 9 инструкций в цикле, включая сложение и сдвиги, что создает длинный путь. Новый метод сокращает цепочку до 3 операций, минимизируя латентность и зависимости данных. Это особенно важно для современных процессоров.
Бенчмарки, проведённые на процессорах Intel Xeon w9-3495X и Apple M4, показали ускорение до 1.67x и 1.98x соответственно. На Apple M4 прирост производительности оказался более выраженным благодаря высокой пропускной способности умножителей. На Xeon новый метод также улучшил предсказуемость времени выполнения задач, что важно для серверных нагрузок. Например, стандартное отклонение времени выполнения на Xeon снизилось с 0.013 до 0.009 секунд.
Интеграция нового метода в компиляторы LLVM и GCC обеспечит ускорение программного обеспечения, работающего с большими объемами данных, включая базы данных, криптографические системы и анализ сетевого трафика.
Это не только академический успех, но и практическая оптимизация, которая уже внедрена в индустрию. На текущий момент патч полностью интегрирован в LLVM, а обновления для GCC и MSVC находятся на стадии финального тестирования. Это означает, что в ближайшем будущем большинство программ, пересобранных с новыми компиляторами, получат значительное ускорение без необходимости изменения их исходного кода. А в компиляторах будет устранён исторический анахронизм и наконец-то задействована мощь 64-битных процессоров для базовых арифметических операций, что даёт почти двукратное ускорение в определённых сценариях.