Dlaczego występuje duży wpływ na wydajność przy zapętlaniu tablicy z 240 lub więcej elementami?

Podczas uruchamiania pętli sumy nad tablicą w Rust zauważyłem ogromny spadek wydajności, gdy CAPACITY> = 240. CAPACITY= 239 jest około 80 razy szybszy.

Czy istnieje specjalna optymalizacja kompilacji, którą Rust robi dla „krótkich” tablic?

Kompilowany z rustc -C opt-level=3.

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}

Podsumowanie : poniżej 240 LLVM całkowicie rozwija wewnętrzną pętlę, co pozwala zauważyć, że może zoptymalizować pętlę powtarzania, przełamując twój test porównawczy.

Znalazłeś magiczny próg, powyżej którego LLVM przestaje dokonywać pewnych optymalizacji . Próg wynosi 8 bajtów * 240 = 1920 bajtów (twoja tablica jest tablicą usizes, dlatego długość jest mnożona przez 8 bajtów, przy założeniu, że CPU x86-64). W tym teście, jedna szczególna optymalizacja - przeprowadzona tylko dla długości 239 - odpowiada za ogromną różnicę prędkości. Ale zacznijmy powoli:

(Cały kod w tej odpowiedzi jest kompilowany -C opt-level=3)

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

Ten prosty kod utworzy z grubsza taki zestaw, jakiego można się spodziewać: pętla sumująca elementy. Jeśli jednak zmienisz 240na 239, emitowany zestaw różni się bardzo. Zobacz to w Godbolt Compiler Explorer . Oto niewielka część zestawu:

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

To się nazywa rozwijanie pętli : LLVM wkleja ciało pętli przez pewien czas, aby uniknąć konieczności wykonywania wszystkich tych „instrukcji zarządzania pętlą”, tj. Zwiększania zmiennej pętli, sprawdzania, czy pętla się zakończyła i przejścia do początku pętli .

Jeśli się zastanawiasz: paddqpodobne instrukcje są instrukcjami SIMD, które umożliwiają sumowanie wielu wartości równolegle. Co więcej, dwa 16-bajtowe rejestry SIMD ( xmm0i xmm1) są używane równolegle, aby równoległość procesora na poziomie instrukcji mogła w zasadzie wykonać dwie z tych instrukcji jednocześnie. W końcu są od siebie niezależni. Na koniec oba rejestry są sumowane, a następnie sumowane poziomo do wyniku skalarnego.

Współczesne procesory głównego nurtu x86 (nie Atom o niskiej mocy) naprawdę potrafią wykonać 2 obciążenia wektorowe na zegar, gdy trafią w pamięć podręczną L1d, a paddqprzepustowość wynosi również co najmniej 2 na zegar, z 1 opóźnieniem cyklu na większości procesorów. Zobacz https://agner.org/optimize/, a także niniejsze pytania i odpowiedzi dotyczące wielu akumulatorów w celu ukrycia opóźnień (FP FMA dla produktu kropkowego) i wąskiego gardła w zakresie przepustowości.

LLVM rozwija niektóre małe pętle, gdy nie jest w pełni rozwijane, i nadal używa wielu akumulatorów. Tak więc zwykle wąskie gardła przepustowości frontonu i opóźnienia nie są dużym problemem dla pętli generowanych przez LLVM, nawet bez pełnego rozwinięcia.

Ale rozwijanie pętli nie jest odpowiedzialne za różnicę wydajności wynoszącą współczynnik 80! Przynajmniej nie rozwijania pętli sam. Rzućmy okiem na rzeczywisty kod testu porównawczego, który umieszcza jedną pętlę w drugiej:

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

( W Godbolt Compiler Explorer )

Zestaw CAPACITY = 240wygląda normalnie: dwie zagnieżdżone pętle. (Na początku funkcji jest trochę kodu do inicjalizacji, który zignorujemy.) W przypadku 239 wygląda to jednak zupełnie inaczej! Widzimy, że pętla inicjująca i pętla wewnętrzna zostały rozwinięte: jak dotąd się spodziewano.

Ważną różnicą jest to, że dla 239 LLVM był w stanie stwierdzić, że wynik wewnętrznej pętli nie zależy od zewnętrznej pętli! W rezultacie LLVM emituje kod, który w zasadzie najpierw wykonuje tylko wewnętrzną pętlę (obliczając sumę), a następnie symuluje zewnętrzną pętlę, sumując sumkilka razy!

Najpierw widzimy prawie taki sam zespół jak powyżej (zespół reprezentujący wewnętrzną pętlę). Następnie widzimy to (skomentowałem, aby wyjaśnić zgromadzenie; komentarze z *są szczególnie ważne):

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

Jak widać tutaj, wynik pętli wewnętrznej jest pobierany, dodawany tak często, jak pętla zewnętrzna biegnie, a następnie wraca. LLVM może przeprowadzić tę optymalizację tylko dlatego, że zrozumiał, że wewnętrzna pętla jest niezależna od zewnętrznej.

Oznacza to, że środowisko wykonawcze zmienia się z CAPACITY * IN_LOOPSnaCAPACITY + IN_LOOPS . A to odpowiada za ogromną różnicę wydajności.

Dodatkowa uwaga: czy możesz coś z tym zrobić? Nie całkiem. LLVM musi mieć takie magiczne progi, ponieważ bez nich optymalizacje LLVM mogą trwać wiecznie na pewnym kodzie. Ale możemy również zgodzić się, że ten kod był bardzo sztuczny. W praktyce wątpię, by nastąpiła tak ogromna różnica. Różnica wynikająca z pełnego rozwinięcia pętli zwykle nie wynosi nawet w tych przypadkach 2. Więc nie musisz się martwić o rzeczywiste przypadki użycia.

Ostatnia uwaga na temat idiomatycznego kodu Rust: arr.iter().sum()jest lepszym sposobem na podsumowanie wszystkich elementów tablicy. A zmiana tego w drugim przykładzie nie prowadzi do zauważalnych różnic w emitowanym zestawie. Powinieneś używać krótkich i idiomatycznych wersji, chyba że zmierzyłeś, że to obniża wydajność.

Oprócz odpowiedzi Lukasa, jeśli chcesz użyć iteratora, spróbuj tego:

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

Dzięki @Chris Morgan za sugestię dotyczącą wzorca zasięgu.

Zoptymalizowany montaż jest bardzo dobra:

example::bar:
        movabs  rax, 14340000000
        ret