Когда компиляторы удивляют

[NeriaLab]

А что со "старенькими" компиляторами - 16-бит/32-бита Вы экспериментировали с ними?

[HyperWin]

Разработчики компиляторов гребаные волшебники.

[Refridgerator]

В данном случае - фокусники, а подобные оптимизации (по заранее известным шаблонам) и существуют только для того, чтобы производить впечатление вот в в такого рода статьях. В математике существует большая куча подобного рода формул, в частности для квадратов, кубов и даже синусов. Просто в школьную программу они не входят и не все прогеры о существовании подобного подозревают.

[Seraphimt]

существуют только для того, чтобы производить впечатление вот в в такого рода статьях.

Насколько я знаю, в LLVM есть правило - оптимизация должно быть или очевидно полезной, или подтверждаться примером из практики, что так действительно пишут.
Плюс, не надо забывать, что оптимизации идут конвейером и реальной код может быть совсем иным, а здесь уже заинлайнены функции, константы посчитаны, какие-то избыточные проверки выкинуты и т.д. и т.п.

[mark_ablov]

Не, в данном случае это не peephole оптимизация, а всё круче)

[Denis_Chernyshev]

Это же кто-то засунул в компилятор известный анекдот от математиков.

Говорят, что на одном из уроков, учитель математики решил дать задание для класса, в котором учился Гаусс, с таким расчетом, чтобы подольше занять учащихся. Недолго думая, педагог предложил обучающимся найти сумму чисел от 1 до 100. Юный Карл Фридрих Гаусс, уже с этого возраста отличавшийся незаурядными, решил задачу практически мгновенно.

[nin-jin]

Что же такого незаурядного было у юного Карла Фридриха Гаусса так останется.

[garwall]

ну насколько я помню эту легенду, там была не формула последовательной суммы, а чуть более изящное в контексте соображение: 1 + 2 + 3 ... + 97 + 98 + 99 + 100 == (1 + 99) + (2 + 98) + (3 + 97) ... + (49 + 51) + 50 + 100

[nerudo]

Осталось вбить в компилятор формулы для всех прочих известных рядов.

[avdx]

Ну с gcc думаю тут достаточно все просто и особой магии нет. Видимо компилятор сначала решил сделать частичный unroll цикла, что вроде как достаточно стандартная оптимизация и у него получилось что то вроде:

for (int x = 0; x + 1 < value; x += 2)
{
  result += x;
  result += x + 1;
}
... // обработка хвоста

После этого просто оптимизировал тело цикла.

А вот то, что clang может определять арифметическую прогрессию и знает формулу ее суммы, да, выглядит удивительно.

[mark_ablov]

LLVM не знает этого. Но в нём есть блок "Scalar evolutions" (https://www.npopov.com/2023/10/03/LLVM-Scalar-evolution.html), который определяет некоторые характеристика цикла, в том числе и способен представить значение result в виде рекуррентной формулы.

[zanzack]

В своё время меня поразил такой трюк.
Рассмотрим программу на С для деления чисел на константу 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 (плюс еще некоторые трюки).
Но красиво же!
И быстрее работает - умножение быстрее деления.