Comment une const expr peut-elle être évaluée si rapidement

J'ai essayé des expressions const qui sont évaluées au moment de la compilation. Mais j'ai joué avec un exemple qui semble incroyablement rapide lorsqu'il est exécuté au moment de la compilation.

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

Lorsque j'exécute ce code, l'exécution prend environ 7 secondes. Jusqu'ici tout va bien. Mais quand je change long int res = fib(45)de const long int res = fib(45)trajet ne dure pas même une seconde. À ma connaissance, il est évalué au moment de la compilation. Mais la compilation prend environ 0,3 seconde

Comment le compilateur peut-il évaluer cela si rapidement, mais au moment de l'exécution, cela prend beaucoup plus de temps? J'utilise gcc 5.4.0.

Le compilateur met en cache des valeurs plus petites et n'a pas besoin de recalculer autant que la version d'exécution.
(L'optimiseur est très bon et génère beaucoup de code, y compris la ruse avec des cas spéciaux qui me sont incompréhensibles; les récursions naïves de 2 ^ 45 prendraient des heures.)

Si vous stockez également des valeurs précédentes:

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 version d'exécution est beaucoup plus rapide que le compilateur.

Vous pouvez trouver intéressant avec 5.4 la fonction n'est pas complètement éliminée, vous avez besoin d'au moins 6.1 pour cela.

Je ne pense pas qu'il y ait de mise en cache. Je suis convaincu que l'optimiseur est suffisamment intelligent pour prouver la relation entre fib(n - 2)et fib(n-1)et évite complètement le deuxième appel. Il s'agit de la sortie GCC 5.4 (obtenue à partir de godbolt) sans constexpret -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

Je dois admettre que je ne comprends pas la sortie avec -O3 - le code généré est étonnamment complexe, avec beaucoup d'accès à la mémoire et l'arithmétique des pointeurs et il est fort possible qu'il y ait une mise en cache (mémorisation) effectuée avec ces paramètres.