¿Cómo se puede evaluar un const expr tan rápido?

He estado probando expresiones constantes que se evalúan en tiempo de compilación. Pero jugué con un ejemplo que parece increíblemente rápido cuando se ejecuta en tiempo de compilación.

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

Cuando ejecuto este código, tarda unos 7 segundos en ejecutarse. Hasta aquí todo bien. Pero cuando me cambio long int res = fib(45)a const long int res = fib(45)ella no lleva ni un segundo. A mi entender, se evalúa en tiempo de compilación. Pero la compilación tarda unos 0.3 segundos

¿Cómo puede el compilador evaluar esto tan rápido, pero en tiempo de ejecución lleva mucho más tiempo? Estoy usando gcc 5.4.0.

El compilador almacena en caché valores más pequeños y no necesita volver a calcular tanto como la versión de tiempo de ejecución.
(El optimizador es muy bueno y genera mucho código, incluyendo trucos con casos especiales que son incomprensibles para mí; las ingenuas 2 ^ 45 recursiones tomarían horas).

Si también almacena 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));
} 

La versión de tiempo de ejecución es mucho más rápida que el compilador.

Puede encontrar interesante con 5.4 la función no se elimina por completo, necesita al menos 6.1 para eso.

No creo que haya ningún almacenamiento en caché. Estoy convencido de que el optimizador es lo suficientemente inteligente como para demostrar la relación entre fib(n - 2)y fib(n-1)y evita la segunda llamada por completo. Esta es la salida GCC 5.4 (obtenida de godbolt) sin constexpry -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

Tengo que admitir que no entiendo la salida con -O3: el código generado es sorprendentemente complejo, con muchos accesos a la memoria y aritmética de puntero y es muy posible que haya algún almacenamiento en caché (memorización) con esa configuración.