Wie kann ein const expr so schnell ausgewertet werden?

Ich habe const-Ausdrücke ausprobiert, die zur Kompilierungszeit ausgewertet werden. Aber ich habe mit einem Beispiel gespielt, das unglaublich schnell erscheint, wenn es zur Kompilierungszeit ausgeführt wird.

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

Wenn ich diesen Code ausführe, dauert die Ausführung ca. 7 Sekunden. So weit, ist es gut. Aber wenn ich dazu wechsle long int res = fib(45), const long int res = fib(45)dauert es nicht einmal eine Sekunde. Nach meinem Verständnis wird es zur Kompilierungszeit ausgewertet. Die Kompilierung dauert jedoch ca. 0,3 Sekunden

Wie kann der Compiler dies so schnell auswerten, aber zur Laufzeit dauert es so viel länger? Ich benutze gcc 5.4.0.

Der Compiler speichert kleinere Werte zwischen und muss nicht so viel neu berechnen wie die Laufzeitversion.
(Der Optimierer ist sehr gut und generiert viel Code, einschließlich Tricks mit Sonderfällen, die für mich unverständlich sind. Die naiven 2 ^ 45-Rekursionen würden Stunden dauern.)

Wenn Sie auch vorherige Werte speichern:

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

Die Laufzeitversion ist viel schneller als der Compiler.

Vielleicht finden Sie mit 5.4 interessant, dass die Funktion nicht vollständig eliminiert ist, dafür benötigen Sie mindestens 6.1.

Ich glaube nicht, dass Caching stattfindet. Ich bin überzeugt, dass der Optimierer klug genug ist, um die Beziehung zwischen fib(n - 2)und zu beweisen fib(n-1)und den zweiten Aufruf vollständig zu vermeiden. Dies ist die GCC 5.4-Ausgabe (von Godbolt erhalten) mit no constexprund -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

Ich muss zugeben, dass ich die Ausgabe mit -O3 nicht verstehe - der generierte Code ist überraschend komplex, mit vielen Speicherzugriffen und Zeigerarithmetik, und es ist durchaus möglich, dass mit diesen Einstellungen etwas Caching (Memoization) durchgeführt wird.