Компиляторы то и дело удивляют меня очень хитрыми трюками. Когда я впервые увидел эту оптимизацию, то едва смог поверить в её реальность. Я изучал оптимизацию циклов и написал вот такую простую функцию, суммирующую все числа до заданного значения:

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)!

Я обожаю то, что, несмотря на более чем двадцатилетний опыт работы с компиляторами, они по-прежнему удивляют и радуют меня. Годы опыта и труда, вложенные в совершенствование компиляторов, впечатляют и вдохновляют.

  1. Часть изначального кода выполняет проверку на чётность/нечётность, и учитывает их.

  2. Почему компилятор генерирует именно такую последовательность, а не чуть более простую? Думаю, частично это вызвано необходимостью избегать переполнения в случаях, когда иначе бы возникло переполнение; это просто побочный эффект того, как clang отслеживает и выводит индуктивные переменные. Впрочем, наверняка я этого не знаю.