Компиляторы то и дело удивляют меня очень хитрыми трюками. Когда я впервые увидел эту оптимизацию, то едва смог поверить в её реальность. Я изучал оптимизацию циклов и написал вот такую простую функцию, суммирующую все числа до заданного значения:
Пока всё вполне привычно: GCC выполнил предварительные проверки, затем попал в цикл, который суммирует числа при помощи lea (мы уже видели такое раньше). Но приглядевшись к циклу, мы найдём нечто необычное:
.L3:
lea edx, [rdx+1+rax*2] ; result = result + 1 + x*2
add eax, 2 ; x += 2
cmp edi, eax ; x != value
jne .L3 ; продолжаем циклУмный компилятор понял, что может обрабатывать по два числа1 за раз благодаря тому что увидел суммирование x и x + 1, что эквивалентно сложению x*2 + 1. Думаю, вы согласитесь, что это очень разумное поведение!
Если повысить уровень оптимизатора до -O3 , то можно увидеть, что компилятор прилагает ещё больше усилий к векторизации цикла при помощи параллельных сложений. Тоже очень умное действие.
С компилятором GCC мы разобрались. Давайте посмотрим, что с нашим кодом делает clang:
И вот на этом моменте я чуть не упал со стула: цикла нет! Clang проверяет, положительно ли value, и если да, то выполняет следующее:
lea eax, [rdi - 1] ; eax = value - 1
lea ecx, [rdi - 2] ; ecx = value - 2
imul rcx, rax ; rcx = (value - 1) * (value - 2)
shr rcx ; rcx >>= 1
lea eax, [rdi + rcx] ; eax = value + rcx
dec eax ; --eax
retДля меня было не совсем очевидно, что же, чёрт побери, здесь происходит. Но если немного разобраться с математикой, то становится понятно, что это эквивалентно такой записи:
v + ((v - 1)(v - 2) / 2) - 1;Раскроем скобки:
v + (v² - 2v - v + 2) / 2 - 1Немного изменим порядок:
(v² - 3v + 2) / 2 + (v - 1)Умножаем (v - 1) на 2 / 2:
(v² - 3v + 2) / 2 + (2v - 2)/2Объединяем их и сокращаем:
(v² - v) / 2Упростив и вынеся за скобки, получим v(v - 1) / 2 , то есть решение в аналитическом виде «суммы целых чисел»! Поистине великолепно2 — мы выполнили переход написанного в коде от алгоритма O(n) к O(1)!
Я обожаю то, что, несмотря на более чем двадцатилетний опыт работы с компиляторами, они по-прежнему удивляют и радуют меня. Годы опыта и труда, вложенные в совершенствование компиляторов, впечатляют и вдохновляют.
Часть изначального кода выполняет проверку на чётность/нечётность, и учитывает их.
Почему компилятор генерирует именно такую последовательность, а не чуть более простую? Думаю, частично это вызвано необходимостью избегать переполнения в случаях, когда иначе бы возникло переполнение; это просто побочный эффект того, как clang отслеживает и выводит индуктивные переменные. Впрочем, наверняка я этого не знаю.
Комментарии (30)
HyperWin
26.12.2025 07:02Разработчики компиляторов гребаные волшебники.
Refridgerator
26.12.2025 07:02В данном случае - фокусники, а подобные оптимизации (по заранее известным шаблонам) и существуют только для того, чтобы производить впечатление вот в в такого рода статьях. В математике существует большая куча подобного рода формул, в частности для квадратов, кубов и даже синусов. Просто в школьную программу они не входят и не все прогеры о существовании подобного подозревают.
Seraphimt
26.12.2025 07:02существуют только для того, чтобы производить впечатление вот в в такого рода статьях.
Насколько я знаю, в LLVM есть правило - оптимизация должно быть или очевидно полезной, или подтверждаться примером из практики, что так действительно пишут.
Плюс, не надо забывать, что оптимизации идут конвейером и реальной код может быть совсем иным, а здесь уже заинлайнены функции, константы посчитаны, какие-то избыточные проверки выкинуты и т.д. и т.п.
Denis_Chernyshev
26.12.2025 07:02Это же кто-то засунул в компилятор известный анекдот от математиков.
Говорят, что на одном из уроков, учитель математики решил дать задание для класса, в котором учился Гаусс, с таким расчетом, чтобы подольше занять учащихся. Недолго думая, педагог предложил обучающимся найти сумму чисел от 1 до 100. Юный Карл Фридрих Гаусс, уже с этого возраста отличавшийся незаурядными, решил задачу практически мгновенно.
nin-jin
26.12.2025 07:02Что же такого незаурядного было у юного Карла Фридриха Гаусса так останется.
garwall
26.12.2025 07:02ну насколько я помню эту легенду, там была не формула последовательной суммы, а чуть более изящное в контексте соображение: 1 + 2 + 3 ... + 97 + 98 + 99 + 100 == (1 + 99) + (2 + 98) + (3 + 97) ... + (49 + 51) + 50 + 100
avdx
26.12.2025 07:02Ну с gcc думаю тут достаточно все просто и особой магии нет. Видимо компилятор сначала решил сделать частичный unroll цикла, что вроде как достаточно стандартная оптимизация и у него получилось что то вроде:
for (int x = 0; x + 1 < value; x += 2) { result += x; result += x + 1; } ... // обработка хвостаПосле этого просто оптимизировал тело цикла.
А вот то, что clang может определять арифметическую прогрессию и знает формулу ее суммы, да, выглядит удивительно.
mark_ablov
26.12.2025 07:02LLVM не знает этого. Но в нём есть блок "Scalar evolutions" (https://www.npopov.com/2023/10/03/LLVM-Scalar-evolution.html), который определяет некоторые характеристика цикла, в том числе и способен представить значение
resultв виде рекуррентной формулы.
zanzack
26.12.2025 07:02В своё время меня поразил такой трюк.
Рассмотрим программу на С для деления чисел на константу 450 (файл main.cpp)
На самом деле подойдёт любая константа, необязательно 450.#include <stdio.h> #include <stdint.h> uint64_t div450(uint64_t a) { return a/450; } int main(void) { uint64_t a; scanf("%lld", &a); printf("result = %lld\n", div450(a)); return 0; }Компилируем с опцией -O2
call "C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Auxiliary\Build\vcvars64.bat" cl.exe -O2 main.cppСмотрим, что получилось -
.00000001`40001024: 488D542430 lea rdx,[rsp][030] .00000001`40001029: 488D0D00B30100 lea rcx,[00000001`4001C330] ;'%lld' .00000001`40001030: E89B000000 call .00000001`400010D0 ;scanf .00000001`40001035: 488B4C2430 mov rcx,[rsp][030] .00000001`4000103A: 48B813F0CDAB89674523 mov rax,23456789`ABCDF013 .00000001`40001044: 48F7E1 mul rcx .00000001`40001047: 482BCA sub rcx,rdx .00000001`4000104A: 48D1E9 shr rcx,1 .00000001`4000104D: 4803D1 add rdx,rcx .00000001`40001050: 488D0DE1B20100 lea rcx,[00000001`4001C338] ;'result = %lld' .00000001`40001057: 48C1EA08 shr rdx,8 .00000001`4000105B: E810000000 call .00000001`40001070 ;printf .00000001`40001060: 33C0 xor eax,eax .00000001`40001062: 4883C428 add rsp,028 ;'(' .00000001`40001066: C3 retnДеление на 450 превращается... превращается...
В элегантное умножение на 0x23456789ABCDF013 (плюс еще некоторые трюки).
Но красиво же!
И быстрее работает - умножение быстрее деления.
R0bur
26.12.2025 07:02И быстрее работает - умножение быстрее деления.
Хоть что-то в этом мире пока не перевернулось! Как в бейсик-интерпретаторах умножение было быстрее деления, так и сейчас f = g * m1 * m2 * r2, где r2 = 1 / r^2, вычисляется быстрее, чем f = g * m1 * m2 / r^2. Несмотря на FPU, MMX, SSE2 и другие страшные аббревиатуры.
R0bur
26.12.2025 07:02Компиляторы то и дело удивляют меня очень хитрыми трюками.
Я не против таких трюков со стороны компилятора до тех пор, пока их можно отключать. Иногда требуется, чтобы машинный код отражал буквально то, что записано в высокоуровневом тексте программы.
Siemargl
26.12.2025 07:02-О0
VladD-exrabbit
26.12.2025 07:02Забудьте. Вот тут даже с -O0 компилятор заменил
x * 2наx + x. As-if-rule действует всегда.Siemargl
26.12.2025 07:02Невелика оптимизация, clang и icc используют shl, zig c умножает, но пролог ужас.
Возможно, стоит брать компилятор потупее, например tcc или вообще freepascal.
Вопрос, какие цели ставятся при этом.
Upd. Я ошибся - даже -O0 не надо ставить, без опций и gcc умножает.
VladD-exrabbit
26.12.2025 07:02Но вы хотели, чтобы код компилировался наивно, «как написано». Гарантии нету даже с -O0.
VladD-exrabbit
26.12.2025 07:02Или вот ещё: в коде умножение на 0, но в компиляте нету умножения даже с -O0.
Siemargl
26.12.2025 07:02Здесь нет нарушения As-if-rule
VladD-exrabbit
26.12.2025 07:02А я и не говорил, что as-if-rule нарушается. Наоборот, as-if-rule говорит, что ожидать наивной, «буквальной» компиляции не имеет смысла. Компилятор имеет право на любое равносильное преобразование.
R0bur
26.12.2025 07:02Вот тут даже с -O0 компилятор заменил
x * 2наx + x.Интересно, а чем x + x в данном случае лучше сдвига x << 1?
nin-jin
26.12.2025 07:02Задействованы разные блоки процессора, разные инструкции могут быть исполнены параллельно на разных блоках.
R0bur
26.12.2025 07:02Интересно, в моём представлении сдвиговые и битовые операции "лучше" любых арифметических - с точки зрения скорости выполнения и занимаемой памяти. А вот про многопоточность не подумал.
VladD-exrabbit
26.12.2025 07:02Возможно, это особенность конкретного процессора (я указал
-march=haswell). Именно поэтому ручная оптимизация наподобие замены умножения на сдвиг может оказаться и пессимизацией (но продвинутый компилятор всё равно из множества операций с одинаковой семантикой (x + x,x << 1,x * 2) выберет самую оптимальную, даже если программист ошибся в ручной «оптимизации»).
j123123
26.12.2025 07:02Не, тут все не так однозначно. Вот https://godbolt.org/z/MzTd3fx7T для наглядности переписал на uint32_t и результат возвращается в uint64_t. Вручную записанная формула лучше компилируется, и никаких переполнений тут нет
#include <inttypes.h> uint64_t sum_up_to2(uint32_t value) { return ((uint64_t)value*(value-1))/2; } uint64_t sum_up_to(uint32_t value) { uint64_t result = 0; for (uint32_t x = 0; x < value; ++x) { result += x; } return result; }
NeriaLab
А что со "старенькими" компиляторами - 16-бит/32-бита Вы экспериментировали с ними?
Siemargl
Они такого не умеют. Это появилось в последних поколениях Gcc (ну может с 9) и clang раньше, причём подходы кардинально разные. Gcc был ближе к эвристикам, а clang (и ICC) к моделированию.
Про msvc не скажу, не интересовался.
NeriaLab
Благодарю за ответ