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