übungsaufgaben - Warum ist die Leistung beim Durchlaufen eines Arrays mit 240 oder mehr Elementen stark beeinträchtigt?




übungsaufgaben arrays (2)

Beim Ausführen einer CAPACITY über ein Array in Rust stellte ich einen enormen Leistungsabfall fest, wenn CAPACITY > = 240 ist. CAPACITY = 239 ist ungefähr 80-mal schneller.

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

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

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

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.

Die optimierte Montage ist ganz gut:

example::bar:
        movabs  rax, 14340000000
        ret

Zusammenfassung : Unter 240 rollt LLVM die innere Schleife vollständig aus, sodass festgestellt wird, dass die Wiederholungsschleife optimiert werden kann, wodurch Ihr Benchmark gebrochen wird.


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

(Der gesamte Code in dieser Antwort wurde mit -C opt-level=3 kompiliert.)

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 Assembly, die man erwarten würde: eine Schleife, die Elemente addiert. Wenn Sie jedoch 240 in 239 ändern, unterscheidet sich die ausgegebene Assembly erheblich. Sehen Sie es im Godbolt Compiler Explorer . Hier ist ein kleiner Teil der Montage:

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 Loop-Unrolling bezeichnet : LLVM fügt den Loop-Body einige Zeit ein, um zu vermeiden, dass alle diese "Loop-Management-Anweisungen" ausgeführt werden müssen, dh die Loop-Variable wird inkrementiert, und es wird geprüft, ob der Loop beendet ist und zum Loop-Anfang gesprungen wird .

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

Moderne x86-Mainstream-CPUs (keine Atom-CPUs mit geringem Stromverbrauch) können tatsächlich zwei Vektorladevorgänge pro Takt ausführen, wenn sie in den L1d-Cache gelangen, und der paddq Durchsatz beträgt mindestens zwei pro Takt, wobei die meisten CPUs eine Latenzzeit von einem Zyklus aufweisen. Siehe https://agner.org/optimize/ und auch diese Fragen und Antworten zu mehreren Akkus, um stattdessen die Latenz (von FP FMA für ein Skalarprodukt) und den Engpass beim Durchsatz zu verbergen.

LLVM rollt kleine Schleifen ab, wenn es sich nicht vollständig abrollt, und verwendet immer noch mehrere Akkus. Normalerweise 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ändiges Abrollen.

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 eigentlichen Benchmarking-Code, der die eine Schleife in eine andere einfügt:

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
}

( Auf Godbolt Compiler Explorer )

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

Der wichtige Unterschied besteht darin, dass LLVM für 239 feststellen 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 (die Summe berechnet) und dann die äußere Schleife simuliert, indem die sum ein paar Mal addiert wird!

Zuerst sehen wir fast die gleiche Baugruppe wie oben (die Baugruppe, die die innere Schleife darstellt). Danach sehen wir Folgendes (ich habe kommentiert, um die Assembly 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 aufgenommen und so oft addiert, wie die äußere Schleife ausgeführt und dann zurückgegeben worden wäre. LLVM kann diese Optimierung nur durchführen, weil die innere Schleife von der äußeren unabhängig ist.

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

Ein zusätzlicher Hinweis: Können Sie etwas dagegen unternehmen? Nicht wirklich. LLVM muss über solche magischen Schwellenwerte verfügen, dass LLVM-Optimierungen bei bestimmten Codes möglicherweise ewig dauern. Wir können uns aber auch darauf einigen, dass dieser Code hochgradig künstlich war. In der Praxis bezweifle ich, dass ein so großer Unterschied auftreten würde. In diesen Fällen beträgt der Unterschied aufgrund des vollständigen Abrollens der Schleife in der Regel nicht einmal den Faktor 2. Sie müssen sich also keine Gedanken über reale Anwendungsfälle machen.

Als letzte Anmerkung zum idiomatischen Rust-Code: Mit arr.iter().sum() sich alle Elemente eines Arrays besser zusammenfassen. Und dies im zweiten Beispiel zu ändern, führt zu keinen nennenswerten Unterschieden bei der emittierten Baugruppe. Sie sollten kurze und idiomatische Versionen verwenden, es sei denn, Sie haben festgestellt, dass dies die Leistung beeinträchtigt.





llvm-codegen