Jak można tak szybko ocenić const expr

13

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.

Peter234
źródło
7
Przypuszczam, że kompilator buforuje wywołania funkcji fib. Wdrożenie powyższych liczb Fibonacciego jest bardzo powolne. Spróbuj buforować wartości funkcji w kodzie wykonawczym, a będzie to znacznie szybsze.
n314159
4
To rekurencyjne fibonacci jest strasznie nieefektywne (ma wykładniczy czas działania), więc zgaduję, że ocena czasu kompilacji jest bardziej sprytna i optymalizuje obliczenia.
Blaze
1
@AlanBirtles Tak. Skompilowałem to z -O3.
Peter234
1
Zakładamy, że wywołania funkcji pamięci podręcznej kompilatora muszą zostać ewakuowane tylko 46 razy (raz dla każdego możliwego argumentu 0–45) zamiast 2 ^ 45 razy. Nie wiem jednak, czy gcc tak działa.
churill
3
@Someprogrammerdude Wiem. Ale w jaki sposób kompilacja może być tak szybka, gdy ocena zajmuje tyle czasu w środowisku wykonawczym?
Peter234

Odpowiedzi:

5

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.

molbdnilo
źródło
Nie ma możliwości uniknięcia dwukrotnego powtarzania, chyba że zrobisz buforowanie. Czy uważasz, że optymalizator implementuje buforowanie? Czy potrafisz to pokazać w danych wyjściowych kompilatora, ponieważ byłoby to naprawdę interesujące?
Suma
... możliwe jest również, że kompilator zamiast buforowania kompilator jest w stanie udowodnić pewien związek między fib (n-2) i fib (n-1) i zamiast wywoływać fib (n-1) używa do fib (n-2) ) wartość, aby to obliczyć. Myślę, że pasuje to do tego, co widzę w wynikach 5.4, gdy usuwam constexpr i używa -O2.
Suma
1
Czy masz link lub inne źródło, które wyjaśnia, jakie optymalizacje można wykonać w czasie kompilacji?
Peter234
Dopóki obserwowalne zachowanie pozostaje niezmienione, optymalizator może zrobić prawie wszystko. Dana fibfunkcja nie ma skutków ubocznych (nie ma zewnętrznych zmiennych, dane wyjściowe zależą tylko od danych wejściowych), przy pomocy sprytnego optymalizatora można wiele zrobić.
Suma
@Suma Nie ma problemu, aby powtórzyć się tylko raz. Ponieważ istnieje wersja iteracyjna, istnieje oczywiście również wersja rekurencyjna, która wykorzystuje na przykład rekurencję ogona.
Ctx
1

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).

Suma
źródło
Myślę, że się mylę. W .L3 jest pętla, a fib zapętla wszystkie dolne fibry. W przypadku -O2 jest on nadal wykładniczy.
Suma