Как можно быстро вычислить const expr

Question

Я пробовал выражения const, которые вычисляются во время компиляции. Но я играл с примером, который кажется невероятно быстрым при исполнении во время компиляции.

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

Когда я запускаю этот код, для его запуска требуется около 7 секунд. Все идет нормально. Но когда я меняю long int res = fib(45) на const long int res = fib(45), это занимает даже секунду. Насколько я понимаю, он оценивается во время компиляции. Но компиляция занимает около 0,3 секунды

Как компилятор может оценить это так быстро, но во время выполнения это занимает намного больше времени? Я использую g cc 5.4.0.

Answer 1

Компилятор кэширует меньшие значения и ему не нужно пересчитывать столько, сколько делает версия времени выполнения.
(Оптимизатор очень хорош и генерирует много кода, включая хитрость с особыми случаями, которые мне непонятны; наивный 2 ^ 45 рекурсий заняло бы часы.)

Если вы также сохраните предыдущие значения:

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

, версия во время выполнения будет намного быстрее, чем компилятор.

Answer 2

Вам может показаться интересным, что с 5.4 функция не полностью исключена, для этого вам нужно как минимум 6.1.

Я не думаю, что происходит кэширование. Я убежден, что оптимизатор достаточно умен, чтобы доказать связь между fib(n - 2) и fib(n-1) и полностью избежать второго вызова. Это вывод G CC 5.4 (полученный из godbolt) без constexpr и -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

Я должен признать, что не понимаю вывод с -O3 - сгенерированный код на удивление сложный, с большим количеством обращений к памяти и арифметикой указателей, и вполне возможно, что с этими настройками выполняется некоторое кэширование (запоминание).