Warum gibt es große Auswirkungen auf die Leistung, wenn ein Array mit 240 oder mehr Elementen durchlaufen wird?

230

Beim Ausführen einer Summenschleife über ein Array in Rust habe ich einen enormen Leistungsabfall festgestellt, wenn CAPACITY> = 240. CAPACITY= 239 etwa 80-mal schneller ist.

Gibt es eine spezielle Kompilierungsoptimierung, die Rust für "kurze" Arrays durchführt?

Zusammengestellt mit 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());
}
Guy Korland
quelle
4
Vielleicht ist mit 240 eine CPU-Cache-Zeile überfüllt? In diesem Fall wären Ihre Ergebnisse sehr CPU-spezifisch.
Rodrigo
11
Reproduzierten hier . Jetzt vermute ich, dass es etwas mit dem Abrollen der Schleife zu tun hat.
Rodrigo

Antworten:

354

Zusammenfassung : Unter 240 rollt LLVM die innere Schleife vollständig ab und stellt so fest, dass die Wiederholungsschleife optimiert werden kann, wodurch Ihr Benchmark gebrochen wird.



Sie haben einen magischen Schwellenwert gefunden, oberhalb dessen LLVM bestimmte Optimierungen nicht mehr ausführt . Der Schwellenwert beträgt 8 Bytes * 240 = 1920 Bytes (Ihr Array ist ein Array von usizes, daher wird die Länge mit 8 Bytes multipliziert, unter der Annahme einer x86-64-CPU). In diesem Benchmark ist eine bestimmte Optimierung - nur für die Länge 239 durchgeführt - für den enormen Geschwindigkeitsunterschied verantwortlich. Aber fangen wir langsam an:

(Der gesamte Code in dieser Antwort wird mit kompiliert. -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
}

Dieser einfache Code erzeugt ungefähr die Baugruppe, die man erwarten würde: eine Schleife, die Elemente addiert. Wenn Sie jedoch zu wechseln 240, 239unterscheidet sich die emittierte Baugruppe erheblich. Sehen Sie es im Godbolt Compiler Explorer . Hier ist ein kleiner Teil der Versammlung:

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

Dies wird als Schleifen-Abrollen bezeichnet : LLVM fügt den Schleifenkörper einige Zeit ein, um zu vermeiden, dass alle diese "Schleifenverwaltungsanweisungen" ausgeführt werden müssen, dh die Schleifenvariable wird inkrementiert, überprüft, ob die Schleife beendet wurde, und der Sprung zum Anfang der Schleife .

Falls Sie sich fragen: Die paddqund ähnliche Anweisungen sind SIMD-Anweisungen, mit denen mehrere Werte parallel summiert werden können. Darüber hinaus werden zwei 16-Byte-SIMD-Register ( xmm0und xmm1) parallel verwendet, so dass die Parallelität auf Befehlsebene der CPU grundsätzlich zwei dieser Befehle gleichzeitig ausführen kann. Immerhin sind sie unabhängig voneinander. Am Ende werden beide Register addiert und dann horizontal zum skalaren Ergebnis summiert.

Moderne Mainstream-x86-CPUs (nicht Atom mit geringem Stromverbrauch) können tatsächlich 2 Vektorladevorgänge pro Takt ausführen, wenn sie im L1d-Cache getroffen werden, und der paddqDurchsatz beträgt mindestens 2 pro Takt, wobei die meisten CPUs 1 Zyklus Latenz haben. Siehe https://agner.org/optimize/ und auch diese Fragen und Antworten zu mehreren Akkumulatoren, um die Latenz (von FP FMA für ein Punktprodukt) und den Engpass beim Durchsatz zu verbergen.

LLVM rollt einige kleine Schleifen ab, wenn es nicht vollständig entrollt ist, und verwendet immer noch mehrere Akkumulatoren. In der Regel sind Engpässe bei der Front-End-Bandbreite und der Back-End-Latenz kein großes Problem für LLVM-generierte Schleifen, auch ohne vollständige Abwicklung.


Das Abrollen der Schleife ist jedoch nicht für einen Leistungsunterschied von Faktor 80 verantwortlich! Zumindest nicht alleine abrollen. Werfen wir einen Blick auf den tatsächlichen Benchmarking-Code, der die eine Schleife in eine andere versetzt:

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
}

( Im Godbolt Compiler Explorer )

Die Assembly für CAPACITY = 240sieht normal aus: zwei verschachtelte Schleifen. (Zu Beginn der Funktion gibt es nur zum Initialisieren einen Code, den wir ignorieren werden.) Für 239 sieht es jedoch ganz anders aus! Wir sehen, dass die Initialisierungsschleife und die innere Schleife abgewickelt wurden: soweit so erwartet.

Der wichtige Unterschied besteht darin, dass LLVM für 239 herausfinden konnte, dass das Ergebnis der inneren Schleife nicht von der äußeren Schleife abhängt! Infolgedessen gibt LLVM Code aus, der im Grunde nur die innere Schleife ausführt (Berechnung der Summe) und dann die äußere Schleife durch mehrmaliges Addieren simuliert sum!

Zuerst sehen wir fast dieselbe Baugruppe wie oben (die Baugruppe, die die innere Schleife darstellt). Danach sehen wir dies (ich habe kommentiert, um die Versammlung zu erklären; die Kommentare mit *sind besonders wichtig):

        ; 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`

Wie Sie hier sehen können, wird das Ergebnis der inneren Schleife so oft addiert, wie die äußere Schleife gelaufen wäre, und dann zurückgegeben. LLVM kann diese Optimierung nur durchführen, weil es verstanden hat, dass die innere Schleife unabhängig von der äußeren ist.

Dies bedeutet, dass sich die Laufzeit von CAPACITY * IN_LOOPSnach ändertCAPACITY + IN_LOOPS . Und das ist verantwortlich für den enormen Leistungsunterschied.


Ein zusätzlicher Hinweis: Können Sie etwas dagegen tun? Nicht wirklich. LLVM muss solche magischen Schwellenwerte haben, dass LLVM-Optimierungen ohne sie für bestimmte Codes ewig dauern können. Wir können uns aber auch darauf einigen, dass dieser Code sehr künstlich war. In der Praxis bezweifle ich, dass ein so großer Unterschied eintreten würde. Der Unterschied aufgrund des vollständigen Abrollens der Schleife beträgt in diesen Fällen normalerweise nicht einmal Faktor 2. Sie müssen sich also keine Gedanken über echte Anwendungsfälle machen.

Als letzte Anmerkung zum idiomatischen Rust-Code: arr.iter().sum()ist eine bessere Möglichkeit, alle Elemente eines Arrays zusammenzufassen. Eine Änderung im zweiten Beispiel führt zu keinen nennenswerten Unterschieden bei der emittierten Baugruppe. Sie sollten kurze und idiomatische Versionen verwenden, es sei denn, Sie haben gemessen, dass dies die Leistung beeinträchtigt.

Lukas Kalbertodt
quelle
2
@ lukas-kalbertodt danke für die tolle antwort! Jetzt verstehe ich auch, warum der ursprüngliche Code, der sumdirekt auf keinem lokalen aktualisiert swurde, viel langsamer lief. for i in 0..arr.len() { sum += arr[i]; }
Guy Korland
4
@LukasKalbertodt Etwas anderes ist in LLVM los. Das Einschalten von AVX2 sollte keinen großen Unterschied machen. Auch in Rost
gerügt
4
@Mgetz Interessant! Aber es klingt für mich nicht zu verrückt, diesen Schwellenwert von den verfügbaren SIMD-Anweisungen abhängig zu machen, da dies letztendlich die Anzahl der Anweisungen in einer vollständig abgewickelten Schleife bestimmt. Aber leider kann ich nicht sicher sagen. Es wäre schön, wenn ein LLVM-Entwickler darauf antworten würde.
Lukas Kalbertodt
7
Warum erkennt der Compiler oder LLVM nicht, dass die gesamte Berechnung zur Kompilierungszeit durchgeführt werden kann? Ich hätte erwartet, dass das Schleifenergebnis fest codiert wird. Oder wird das Instantverhindert?
Unkreativer Name
4
@JosephGarvin: Ich gehe davon aus, dass das vollständige Abrollen passiert, damit der spätere Optimierungsdurchlauf dies erkennen kann. Denken Sie daran, dass es bei der Optimierung von Compilern immer noch darum geht, schnell zu kompilieren und einen effizienten ASM zu erstellen. Daher müssen sie die Komplexität der Analyse im schlimmsten Fall begrenzen, damit es nicht Stunden / Tage dauert, um bösen Quellcode mit komplizierten Schleifen zu kompilieren . Aber ja, dies ist offensichtlich eine verpasste Optimierung für Größe> = 240. Ich frage mich, ob eine Nichtoptimierung von Schleifen innerhalb von Schleifen beabsichtigt ist, um zu vermeiden, dass einfache Benchmarks gebrochen werden. Wahrscheinlich nicht, aber vielleicht.
Peter Cordes
30

Wenn Sie zusätzlich zu Lukas 'Antwort einen Iterator verwenden möchten, versuchen Sie Folgendes:

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

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

Vielen Dank an Chris Morgan für den Vorschlag zum Bereichsmuster.

Das optimierte Montage ist recht gut:

example::bar:
        movabs  rax, 14340000000
        ret
mja
quelle
3
Oder noch besser (0..CAPACITY).sum::<usize>() * IN_LOOPS, was das gleiche Ergebnis liefert.
Chris Morgan
11
Ich würde tatsächlich erklären, dass die Assembly die Berechnung nicht tatsächlich durchführt, aber LLVM hat die Antwort in diesem Fall vorberechnet.
Josep
Ich bin etwas überrascht, dass ich rustcdie Gelegenheit verpasse, diese Kraftreduzierung durchzuführen. In diesem speziellen Kontext scheint dies jedoch eine Zeitschleife zu sein, und Sie möchten absichtlich, dass sie nicht optimiert wird. Der springende Punkt ist, die Berechnung so oft von Grund auf zu wiederholen und durch die Anzahl der Wiederholungen zu dividieren. In C besteht die (inoffizielle) Redewendung dafür darin, den Schleifenzähler als volatilez. B. den BogoMIPS-Zähler im Linux-Kernel zu deklarieren . Gibt es eine Möglichkeit, dies in Rust zu erreichen? Es mag sein, aber ich weiß es nicht. Ein Anruf bei einem externen fnMitarbeiter kann hilfreich sein.
Davislor
1
@Davislor: Erzwingt volatiledie Synchronisierung dieses Speichers. Durch Anwenden auf den Schleifenzähler wird nur das tatsächliche Neuladen / Speichern des Schleifenzählerwerts erzwungen. Es wirkt sich nicht direkt auf den Schleifenkörper aus. Aus diesem Grund ist es normalerweise besser, das tatsächlich wichtige Ergebnis volatile int sinkoder etwas entweder nach der Schleife (wenn eine schleifenübertragene Abhängigkeit besteht) oder nach jeder Iteration zuzuweisen , damit der Compiler den Schleifenzähler nach Belieben optimieren kann, ihn aber erzwingt um das gewünschte Ergebnis in einem Register zu materialisieren, damit es es speichern kann.
Peter Cordes
1
@Davislor: Ich denke, Rust hat eine Inline-Asm-Syntax wie GNU C. Sie können Inline-Asm verwenden, um den Compiler zu zwingen, einen Wert in einem Register zu materialisieren, ohne ihn zum Speichern zu zwingen. Wenn Sie dies für das Ergebnis jeder Schleifeniteration verwenden, kann dies die Optimierung verhindern. (Aber auch von der automatischen Vektorisierung, wenn Sie nicht vorsichtig sind). Beispiel: "Escape" und "Clobber" in MSVC erklären zwei Makros (während sie gefragt werden, wie sie auf MSVC portiert werden sollen, was nicht wirklich möglich ist) und Links zu Chandler Carruths Vortrag, in dem er ihre Verwendung zeigt.
Peter Cordes