Como uma const expr pode ser avaliada tão rapidamente

Eu tenho experimentado expressões const que são avaliadas em tempo de compilação. Mas eu brinquei com um exemplo que parece incrivelmente rápido quando executado em tempo de compilação.

#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; 
} 

Quando executo esse código, leva cerca de 7 segundos para executar. Por enquanto, tudo bem. Mas quando eu mudar long int res = fib(45)para const long int res = fib(45)não leva nem um segundo. No meu entender, é avaliado em tempo de compilação. Mas a compilação leva cerca de 0,3 segundos

Como o compilador pode avaliar isso tão rapidamente, mas em tempo de execução, leva muito mais tempo? Estou usando o gcc 5.4.0.

O compilador armazena em cache valores menores e não precisa recalcular tanto quanto a versão de tempo de execução.
(O otimizador é muito bom e gera muito código, incluindo truques com casos especiais que são incompreensíveis para mim; as recursões ingênuas de 2 ^ 45 levariam horas.)

Se você também armazenar valores anteriores:

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));
} 

a versão em tempo de execução é muito mais rápida que o compilador.

Você pode achar interessante com 5.4 que a função não é completamente eliminada, você precisa de pelo menos 6.1 para isso.

Eu não acho que haja algum cache acontecendo. Estou convencido de que o otimizador é inteligente o suficiente para provar relação entre fib(n - 2)e fib(n-1)e evita a segunda chamada completamente. Esta é a saída do GCC 5.4 (obtida do godbolt) sem constexpre -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

Devo admitir que não entendo a saída com -O3 - o código gerado é surpreendentemente complexo, com muitos acessos à memória e aritmética de ponteiros e é bem possível que exista algum cache (memorização) feito com essas configurações.