Как можно быстро вычислить const expr

Я пробовал константные выражения, которые оцениваются во время компиляции. Но я играл с примером, который кажется невероятно быстрым при исполнении во время компиляции.

#include<iostream> 

constexpr long int fib(int n) { 
    return (n <= 1)? n : fib(n-1) + fib(n-2); 
} 

int main () {  
    long int res = fib(45); 
    std::cout << res; 
    return 0; 
} 

Когда я запускаю этот код, требуется около 7 секунд для запуска. Все идет нормально. Но когда я перехожу long int res = fib(45)на const long int res = fib(45)это, не требуется даже секунды. Насколько я понимаю, он оценивается во время компиляции. Но компиляция занимает около 0,3 секунды

Как компилятор может оценить это так быстро, но во время выполнения это занимает намного больше времени? Я использую GCC 5.4.0.

Компилятор кэширует меньшие значения и не должен пересчитывать столько, сколько делает версия времени выполнения.
(Оптимизатор очень хорош и генерирует много кода, включая хитрости с особыми случаями, которые мне непонятны; наивные 2 ^ 45 рекурсии заняли бы часы.)

Если вы также сохраняете предыдущие значения:

int cache[100] = {1, 1};

long int fib(int n) {
    int res = cache[n];
    return res ? res : (cache[n] = fib(n-1) + fib(n-2));
} 

версия во время выполнения намного быстрее, чем компилятор.

В версии 5.4 может показаться интересным, что эта функция полностью не устранена, для этого вам нужно как минимум 6.1.

Я не думаю, что происходит кэширование. Я убежден , что оптимизатор достаточно умен , чтобы доказать связь между fib(n - 2)и fib(n-1)и полностью исключает второй вызов. Это вывод GCC 5.4 (полученный из Godbolt) без constexprи -O2:

fib(long):
        cmp     rdi, 1
        push    r12
        mov     r12, rdi
        push    rbp
        push    rbx
        jle     .L4
        mov     rbx, rdi
        xor     ebp, ebp
.L3:
        lea     rdi, [rbx-1]
        sub     rbx, 2
        call    fib(long)
        add     rbp, rax
        cmp     rbx, 1
        jg      .L3
        and     r12d, 1
.L2:
        lea     rax, [r12+rbp]
        pop     rbx
        pop     rbp
        pop     r12
        ret
.L4:
        xor     ebp, ebp
        jmp     .L2

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