Jak można tak szybko ocenić const expr

Próbowałem wyrażeń stałych, które są oceniane podczas kompilacji. Ale bawiłem się przykładem, który wydaje się niewiarygodnie szybki, gdy jest wykonywany w czasie kompilacji.

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

Po uruchomieniu tego kodu uruchomienie zajmuje około 7 sekund. Na razie w porządku. Ale kiedy przejdę long int res = fib(45)na const long int res = fib(45)to, nie zajmie to ani sekundy. W moim rozumieniu jest to oceniane w czasie kompilacji. Ale kompilacja zajmuje około 0,3 sekundy

Jak kompilator może to ocenić tak szybko, ale w czasie wykonywania zajmuje to dużo więcej czasu? Używam gcc 5.4.0.

Kompilator buforuje mniejsze wartości i nie musi ponownie obliczać tak dużo, jak wersja środowiska wykonawczego.
(Optymalizator jest bardzo dobry i generuje dużo kodu, w tym oszustwa ze specjalnymi przypadkami, które są dla mnie niezrozumiałe; naiwne rekurencje 2 ^ 45 zajęłyby godziny.)

Jeśli przechowujesz również poprzednie wartości:

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

wersja środowiska wykonawczego jest znacznie szybsza niż kompilator.

Interesujące może być z 5.4, że funkcja nie jest całkowicie wyeliminowana, potrzebujesz co najmniej 6.1.

Nie sądzę, żeby miało miejsce buforowanie. Jestem przekonany, że optymalizator jest wystarczająco inteligentny, aby udowodnić związek między fib(n - 2)a fib(n-1)i unika drugie połączenie całkowicie. To jest wyjście GCC 5.4 (uzyskane z godbolt) bez constexpri -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

Muszę przyznać, że nie rozumiem danych wyjściowych z -O3 - wygenerowany kod jest zaskakująco złożony, z dużą ilością dostępów do pamięci i arytmetyki wskaźników i jest całkiem możliwe, że przy tych ustawieniach jest trochę buforowania (zapamiętywania).