Компиляторы то и дело удивляют меня очень хитрыми трюками. Когда я впервые увидел эту оптимизацию, то едва смог поверить в её реальность. Я изучал оптимизацию циклов и написал вот такую простую функцию, суммирующую все числа до заданного значения:
Compiler Explorer
aoco.compiler-explorer.com
Пока всё вполне привычно: 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:
Compiler Explorer
aoco.compiler-explorer.com
И вот на этом моменте я чуть не упал со стула: цикла нет! 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 отслеживает и выводит индуктивные переменные. Впрочем, наверняка я этого не знаю.
Источник: habr.com
Источник: ai-news.ru
