Warum ist die Verarbeitung eines sortierten Arrays schneller als die Verarbeitung eines unsortierten Arrays?

24446

Hier ist ein Teil des C ++ - Codes, der ein sehr eigenartiges Verhalten zeigt. Aus irgendeinem seltsamen Grund macht das Sortieren der Daten auf wundersame Weise den Code fast sechsmal schneller:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Ohne std::sort(data, data + arraySize);läuft der Code in 11,54 Sekunden.
  • Mit den sortierten Daten läuft der Code in 1,93 Sekunden.

Anfangs dachte ich, dies könnte nur eine Sprach- oder Compiler-Anomalie sein, also habe ich Java ausprobiert:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Mit einem ähnlichen, aber weniger extremen Ergebnis.


Mein erster Gedanke war, dass das Sortieren die Daten in den Cache bringt, aber dann dachte ich, wie dumm das war, weil das Array gerade generiert wurde.

  • Was ist los?
  • Warum ist die Verarbeitung eines sortierten Arrays schneller als die Verarbeitung eines unsortierten Arrays?

Der Code fasst einige unabhängige Begriffe zusammen, daher sollte die Reihenfolge keine Rolle spielen.

GManNickG
quelle
16
@SachinVerma Auf den ersten Blick: 1) Die JVM ist möglicherweise endlich klug genug, um bedingte Bewegungen auszuführen. 2) Der Code ist speichergebunden. 200M sind viel zu groß, um in den CPU-Cache zu passen. Die Leistung wird also durch Speicherbandbreite und nicht durch Verzweigung beeinträchtigt.
Mysticial
12
@ Mysticial, ungefähr 2). Ich dachte, die Vorhersage-Tabelle verfolgt Muster (unabhängig von den tatsächlichen Variablen, die für dieses Muster überprüft wurden) und ändert die Vorhersage-Ausgabe basierend auf dem Verlauf. Könnten Sie mir bitte einen Grund nennen, warum ein super großes Array nicht von der Verzweigungsvorhersage profitieren würde?
Sachin Verma
15
@SachinVerma Das tut es, aber wenn das Array so groß ist, kommt wahrscheinlich ein noch größerer Faktor ins Spiel - die Speicherbandbreite. Der Speicher ist nicht flach . Der Zugriff auf den Speicher ist sehr langsam und die Bandbreite ist begrenzt. Um die Dinge zu vereinfachen, gibt es nur so viele Bytes, die in einer festgelegten Zeit zwischen CPU und Speicher übertragen werden können. Einfacher Code wie der in dieser Frage wird wahrscheinlich diese Grenze erreichen, selbst wenn er durch falsche Vorhersagen verlangsamt wird. Dies ist bei einem Array von 32768 (128 KB) nicht der Fall, da es in den L2-Cache der CPU passt.
Mysticial
13
Es gibt eine neue Sicherheitslücke namens BranchScope: cs.ucr.edu/~nael/pubs/asplos18.pdf
Veve

Antworten:

31791

Sie sind ein Opfer des Fehlschlags der Zweigvorhersage.


Was ist Zweigvorhersage?

Betrachten Sie einen Eisenbahnknotenpunkt:

Bild zeigt einen Eisenbahnknotenpunkt Bild von Mecanismo, über Wikimedia Commons. Wird unter der CC-By-SA 3.0- Lizenz verwendet.

Nehmen wir zum Zwecke der Argumentation an, dass dies im 19. Jahrhundert war - vor Ferngesprächen oder Funkkommunikation.

Sie sind der Betreiber einer Kreuzung und hören einen Zug kommen. Sie haben keine Ahnung, in welche Richtung es gehen soll. Sie halten den Zug an, um den Fahrer zu fragen, in welche Richtung er möchte. Und dann stellen Sie den Schalter entsprechend ein.

Züge sind schwer und haben viel Trägheit. Es dauert also ewig, bis sie anfangen und langsamer werden.

Gibt es einen besseren Weg? Sie raten, in welche Richtung der Zug fahren wird!

  • Wenn Sie richtig geraten haben, geht es weiter.
  • Wenn Sie falsch geraten haben, hält der Kapitän an, fährt zurück und schreit Sie an, um den Schalter umzulegen. Dann kann es auf dem anderen Pfad neu starten.

Wenn Sie jedes Mal richtig raten , muss der Zug niemals anhalten.
Wenn Sie zu oft falsch raten , verbringt der Zug viel Zeit damit, anzuhalten, zu sichern und neu zu starten.


Betrachten Sie eine if-Anweisung: Auf Prozessorebene handelt es sich um eine Verzweigungsanweisung:

Screenshot des kompilierten Codes mit einer if-Anweisung

Sie sind ein Prozessor und sehen einen Zweig. Sie haben keine Ahnung, in welche Richtung es gehen wird. Wie geht's? Sie stoppen die Ausführung und warten, bis die vorherigen Anweisungen vollständig sind. Dann gehen Sie den richtigen Weg weiter.

Moderne Prozessoren sind kompliziert und haben lange Pipelines. Es dauert also ewig, bis sie sich "aufgewärmt" und "verlangsamt" haben.

Gibt es einen besseren Weg? Sie raten, in welche Richtung der Zweig gehen wird!

  • Wenn Sie richtig geraten haben, fahren Sie mit der Ausführung fort.
  • Wenn Sie falsch geraten haben, müssen Sie die Pipeline spülen und zum Zweig zurückrollen. Dann können Sie den anderen Pfad neu starten.

Wenn Sie jedes Mal richtig raten , muss die Ausführung niemals aufhören.
Wenn Sie zu oft falsch raten , verbringen Sie viel Zeit damit, anzuhalten, zurückzurollen und neu zu starten.


Dies ist eine Verzweigungsvorhersage. Ich gebe zu, es ist nicht die beste Analogie, da der Zug die Richtung nur mit einer Flagge signalisieren könnte. Bei Computern weiß der Prozessor jedoch bis zum letzten Moment nicht, in welche Richtung ein Zweig gehen wird.

Wie würden Sie strategisch raten, um die Häufigkeit zu minimieren, mit der der Zug auf dem anderen Weg zurückfahren und fahren muss? Sie schauen auf die Vergangenheit! Wenn der Zug 99% der Zeit nach links fährt, raten Sie nach links. Wenn es sich abwechselt, wechseln Sie Ihre Vermutungen. Wenn es alle drei Male in eine Richtung geht, raten Sie dasselbe ...

Mit anderen Worten, Sie versuchen, ein Muster zu identifizieren und ihm zu folgen. So funktionieren Zweigprädiktoren mehr oder weniger.

Die meisten Anwendungen haben gut erzogene Zweige. Moderne Branchenprädiktoren erzielen daher in der Regel Trefferquoten von> 90%. Bei unvorhersehbaren Verzweigungen ohne erkennbare Muster sind Verzweigungsvorhersagen jedoch praktisch nutzlos.

Weiterführende Literatur: Artikel "Branch Predictor" auf Wikipedia .


Wie von oben angedeutet, ist der Schuldige diese if-Aussage:

if (data[c] >= 128)
    sum += data[c];

Beachten Sie, dass die Daten gleichmäßig zwischen 0 und 255 verteilt sind. Wenn die Daten sortiert werden, wird ungefähr die erste Hälfte der Iterationen nicht in die if-Anweisung eingegeben. Danach geben alle die if-Anweisung ein.

Dies ist für den Zweigprädiktor sehr freundlich, da der Zweig viele Male nacheinander in dieselbe Richtung geht. Selbst ein einfacher Sättigungszähler sagt den Zweig bis auf die wenigen Iterationen nach dem Richtungswechsel korrekt voraus.

Schnelle Visualisierung:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Wenn die Daten jedoch vollständig zufällig sind, wird der Verzweigungsprädiktor unbrauchbar, da er keine zufälligen Daten vorhersagen kann. Daher wird es wahrscheinlich eine Fehlvorhersage von etwa 50% geben (nicht besser als zufälliges Erraten).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Was kann also getan werden?

Wenn der Compiler den Zweig nicht in eine bedingte Verschiebung optimieren kann, können Sie einige Hacks versuchen, wenn Sie bereit sind, die Lesbarkeit für die Leistung zu opfern.

Ersetzen:

if (data[c] >= 128)
    sum += data[c];

mit:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Dies eliminiert den Zweig und ersetzt ihn durch einige bitweise Operationen.

(Beachten Sie, dass dieser Hack nicht unbedingt der ursprünglichen if-Anweisung entspricht. In diesem Fall gilt er jedoch für alle Eingabewerte von data[].)

Benchmarks: Core i7 920 bei 3,5 GHz

C ++ - Visual Studio 2010 - x64-Version

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Beobachtungen:

  • Mit der Verzweigung: Es gibt einen großen Unterschied zwischen sortierten und unsortierten Daten.
  • Mit dem Hack: Es gibt keinen Unterschied zwischen sortierten und unsortierten Daten.
  • Im C ++ - Fall ist der Hack tatsächlich etwas langsamer als beim Verzweigen, wenn die Daten sortiert werden.

Eine allgemeine Faustregel besteht darin, eine datenabhängige Verzweigung in kritischen Schleifen (wie in diesem Beispiel) zu vermeiden.


Aktualisieren:

  • GCC 4.6.1 mit -O3oder -ftree-vectorizeauf x64 kann eine bedingte Verschiebung generieren. Es gibt also keinen Unterschied zwischen sortierten und unsortierten Daten - beide sind schnell.

    (Oder etwas schnell: Für den bereits sortierten Fall cmovkann er langsamer sein, insbesondere wenn GCC ihn auf den kritischen Pfad stellt, anstatt nur add, insbesondere bei Intel vor Broadwell, wo cmoveine Latenz von 2 Zyklen vorliegt : Das gcc-Optimierungsflag -O3 macht den Code langsamer als -O2 )

  • VC ++ 2010 kann auch unter keine bedingten Verschiebungen für diesen Zweig generieren /Ox.

  • Intel C ++ Compiler (ICC) 11 macht etwas Wunderbares. Es vertauscht die beiden Schleifen und hebt dadurch den unvorhersehbaren Zweig zur äußeren Schleife. Es ist also nicht nur immun gegen falsche Vorhersagen, sondern auch doppelt so schnell wie alles, was VC ++ und GCC erzeugen können! Mit anderen Worten, ICC nutzte die Testschleife, um den Benchmark zu besiegen ...

  • Wenn Sie dem Intel-Compiler den verzweigungslosen Code geben, vektorisiert er ihn einfach nach rechts ... und ist genauso schnell wie bei der Verzweigung (mit dem Schleifenaustausch).

Dies zeigt, dass selbst ausgereifte moderne Compiler in ihrer Fähigkeit, Code zu optimieren, sehr unterschiedlich sein können ...

Mystisch
quelle
256
Schauen Sie sich diese Folgefrage an : stackoverflow.com/questions/11276291/… Der Intel Compiler war fast vollständig von der äußeren Schleife befreit.
Mysticial
24
@Mysticial Woher weiß der Zug / Compiler, dass er den falschen Weg eingeschlagen hat?
onmyway133
26
@obe: Angesichts hierarchischer Speicherstrukturen ist es unmöglich zu sagen, wie hoch die Kosten eines Cache-Fehlers sein werden. Es könnte in L1 fehlen und in langsamerem L2 aufgelöst werden oder in L3 fehlen und im Systemspeicher aufgelöst werden. Sofern dieser Cache-Fehler nicht aus bizarren Gründen dazu führt, dass der Speicher einer nicht residenten Seite von der Festplatte geladen wird, haben Sie einen guten Punkt ... Der Speicher hatte in etwa 25 bis 30 Jahren keine Zugriffszeit im Bereich von Millisekunden ;)
Andon M. Coleman
21
Faustregel für das Schreiben von Code, der auf einem modernen Prozessor effizient ist: Alles, was die Ausführung Ihres Programms regelmäßiger (weniger ungleichmäßig) macht, macht es tendenziell effizienter. Die Sortierung in diesem Beispiel hat diesen Effekt aufgrund der Verzweigungsvorhersage. Die Zugriffslokalität (anstelle von weit und breit zufälligen Zugriffen) hat diesen Effekt aufgrund von Caches.
Lutz Prechelt
22
@ Sandeep Ja. Prozessoren haben immer noch eine Verzweigungsvorhersage. Wenn sich etwas geändert hat, sind es die Compiler. Heutzutage wette ich, dass sie eher das tun, was ICC und GCC (unter -O3) hier getan haben - das heißt, den Zweig entfernen. Angesichts des hohen Bekanntheitsgrades dieser Frage ist es sehr wahrscheinlich, dass Compiler aktualisiert wurden, um den Fall in dieser Frage speziell zu behandeln. Die achten auf jeden Fall auf SO. Und es geschah bei dieser Frage, bei der GCC innerhalb von 3 Wochen aktualisiert wurde. Ich verstehe nicht, warum es hier nicht auch passieren würde.
Mysticial
4086

Verzweigungsvorhersage.

Bei einem sortierten Array gilt die Bedingung data[c] >= 128zunächst falsefür einen Wertestreifen und dann truefür alle späteren Werte. Das ist leicht vorherzusagen. Bei einem unsortierten Array zahlen Sie die Verzweigungskosten.

Daniel Fischer
quelle
105
Funktioniert die Verzweigungsvorhersage bei sortierten Arrays besser als bei Arrays mit unterschiedlichen Mustern? Zum Beispiel ist für das Array -> {10, 5, 20, 10, 40, 20, ...} das nächste Element im Array aus dem Muster 80. Würde diese Art von Array durch Verzweigungsvorhersage in beschleunigt Welches ist das nächste Element hier 80, wenn das Muster befolgt wird? Oder hilft es normalerweise nur bei sortierten Arrays?
Adam Freeman
133
Also ist im Grunde alles, was ich herkömmlicherweise über Big-O gelernt habe, aus dem Fenster? Besser Sortierkosten als Verzweigungskosten?
Agrim Pathak
133
@AgrimPathak Das kommt darauf an. Für nicht zu große Eingaben ist ein Algorithmus mit höherer Komplexität schneller als ein Algorithmus mit geringerer Komplexität, wenn die Konstanten für den Algorithmus mit höherer Komplexität kleiner sind. Wo der Break-Even-Punkt liegt, kann schwer vorherzusagen sein. Auch vergleicht diese Lokalität ist wichtig. Big-O ist wichtig, aber nicht das einzige Leistungskriterium.
Daniel Fischer
65
Wann findet eine Verzweigungsvorhersage statt? Wann weiß die Sprache, dass das Array sortiert ist? Ich denke an eine Array-Situation, die wie folgt aussieht: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? Wird diese obskure 3 die Laufzeit verlängern? Wird es so lange dauern wie ein unsortiertes Array?
Filip Bartuzi
63
@FilipBartuzi Die Verzweigungsvorhersage findet im Prozessor unterhalb der Sprachstufe statt (die Sprache bietet jedoch möglicherweise Möglichkeiten, dem Compiler mitzuteilen, was wahrscheinlich ist, sodass der Compiler den dafür geeigneten Code ausgeben kann). In Ihrem Beispiel führt die Abweichung 3 zu einer Fehlvorhersage der Verzweigung (unter geeigneten Bedingungen, bei denen 3 ein anderes Ergebnis als 1000 ergibt), und daher wird die Verarbeitung dieses Arrays wahrscheinlich ein paar Dutzend oder hundert Nanosekunden länger dauern als a sortiertes Array würde kaum jemals auffallen. Was Zeit kostet, ist eine hohe Rate an Fehlvorhersagen, eine Fehlvorhersage pro 1000 ist nicht viel.
Daniel Fischer
3310

Der Grund, warum sich die Leistung beim Sortieren der Daten drastisch verbessert, besteht darin, dass die Strafe für die Verzweigungsvorhersage entfernt wird, wie in der Antwort von Mysticial ausführlich erläutert .

Nun, wenn wir uns den Code ansehen

if (data[c] >= 128)
    sum += data[c];

Wir können feststellen, dass die Bedeutung dieses bestimmten if... else...Zweigs darin besteht, etwas hinzuzufügen, wenn eine Bedingung erfüllt ist. Diese Art von Verzweigung kann leicht in eine bedingte Verschiebungsanweisung umgewandelt werden, die in einer bedingten Verschiebungsanweisung cmovlin einem x86System kompiliert wird. Die Verzweigung und damit die mögliche Verzweigungsvorhersagestrafe wird entfernt.

In C, so C++ist die Aussage, die direkt (ohne Optimierung) kompilieren würden in den bedingten Bewegungsbefehl in x86ist der ternäre Operator ... ? ... : .... Also schreiben wir die obige Aussage in eine äquivalente um:

sum += data[c] >=128 ? data[c] : 0;

Unter Beibehaltung der Lesbarkeit können wir den Beschleunigungsfaktor überprüfen.

Auf einem Intel Core i7 -2600K bei 3,4 GHz und Visual Studio 2010 Release-Modus lautet der Benchmark (Format von Mysticial kopiert):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Das Ergebnis ist in mehreren Tests robust. Wir erhalten eine große Beschleunigung, wenn das Verzweigungsergebnis nicht vorhersehbar ist, aber wir leiden ein wenig, wenn es vorhersehbar ist. Wenn Sie eine bedingte Verschiebung verwenden, ist die Leistung unabhängig vom Datenmuster gleich.

Schauen wir uns nun die von x86ihnen erzeugte Baugruppe genauer an . Der Einfachheit halber verwenden wir zwei Funktionen max1und max2.

max1verwendet den bedingten Zweig if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2verwendet den ternären Operator ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

GCC -SGeneriert auf einem x86-64-Computer die folgende Baugruppe.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2verwendet aufgrund der Verwendung von Anweisungen viel weniger Code cmovge. Der eigentliche Gewinn besteht jedoch darin, dass max2keine Verzweigungssprünge erforderlich sind jmp, die einen erheblichen Leistungsverlust bedeuten würden, wenn das vorhergesagte Ergebnis nicht stimmt.

Warum ist eine bedingte Bewegung besser?

In einem typischen x86Prozessor ist die Ausführung eines Befehls in mehrere Stufen unterteilt. Wir haben ungefähr unterschiedliche Hardware, um mit verschiedenen Phasen fertig zu werden. Wir müssen also nicht warten, bis eine Anweisung abgeschlossen ist, um eine neue zu starten. Dies wird als Pipelining bezeichnet .

In einem Verzweigungsfall wird die folgende Anweisung durch die vorhergehende bestimmt, sodass wir kein Pipelining durchführen können. Wir müssen entweder warten oder vorhersagen.

In einem Fall eines bedingten Verschiebens ist der Befehl zum bedingten Verschieben der Ausführung in mehrere Stufen unterteilt, aber die früheren Stufen mögen Fetchund Decodehängen nicht vom Ergebnis der vorherigen Anweisung ab; nur letztere Stufen brauchen das Ergebnis. Wir warten also einen Bruchteil der Ausführungszeit eines Befehls. Aus diesem Grund ist die Version für bedingte Verschiebungen langsamer als der Zweig, wenn die Vorhersage einfach ist.

Das Buch Computersysteme: Die Perspektive eines Programmierers, zweite Ausgabe, erklärt dies ausführlich. In Abschnitt 3.6.6 finden Sie Anweisungen für bedingte Verschiebungen , in Kapitel 4 für Prozessorarchitektur und in Abschnitt 5.11.2 finden Sie eine spezielle Behandlung für Strafen für Verzweigungsvorhersagen und Fehlvorhersagen .

Manchmal können einige moderne Compiler unseren Code für eine Assemblierung mit besserer Leistung optimieren, manchmal können einige Compiler dies nicht (der betreffende Code verwendet den nativen Compiler von Visual Studio). Wenn wir den Leistungsunterschied zwischen Verzweigung und bedingter Verschiebung kennen, wenn dies nicht vorhersehbar ist, können wir Code mit besserer Leistung schreiben, wenn das Szenario so komplex wird, dass der Compiler sie nicht automatisch optimieren kann.

WiSaGaN
quelle
7
@ BlueRaja-DannyPflughoeft Dies ist die nicht optimierte Version. Der Compiler hat den ternären Operator NICHT optimiert, sondern nur ÜBERSETZT. GCC kann Wenn-Dann optimieren, wenn ein ausreichendes Optimierungsniveau gegeben ist. Dieses zeigt jedoch die Kraft der bedingten Bewegung, und die manuelle Optimierung macht einen Unterschied.
WiSaGaN
100
@WiSaGaN Der Code zeigt nichts, da Ihre beiden Codeteile mit demselben Maschinencode kompiliert werden. Es ist von entscheidender Bedeutung, dass die Leute nicht auf die Idee kommen, dass sich die if-Anweisung in Ihrem Beispiel irgendwie von der in Ihrem Beispiel unterscheidet. Es ist wahr, dass Sie der Ähnlichkeit in Ihrem letzten Absatz gewachsen sind, aber das löscht nicht die Tatsache aus, dass der Rest des Beispiels schädlich ist.
Justin L.
55
@WiSaGaN Meine Abwertung würde sich definitiv in eine Aufwertung verwandeln, wenn Sie Ihre Antwort ändern würden, um das irreführende -O0Beispiel zu entfernen und den Unterschied im optimierten Asm auf Ihren beiden Testfällen zu zeigen.
Justin L.
56
@UpAndAdam Zum Zeitpunkt des Tests kann VS2010 den ursprünglichen Zweig nicht in eine bedingte Verschiebung optimieren, selbst wenn eine hohe Optimierungsstufe angegeben wird, während dies bei gcc möglich ist.
WiSaGaN
9
Dieser ternäre Operator-Trick funktioniert wunderbar für Java. Nachdem ich die Antwort von Mystical gelesen hatte, fragte ich mich, was für Java getan werden könnte, um eine falsche Verzweigungsvorhersage zu vermeiden, da Java nichts hat, was -O3 entspricht. ternärer Operator: 2.1943s und Original: 6.0303s.
Kin Cheung
2271

Wenn Sie neugierig auf weitere Optimierungen sind, die an diesem Code vorgenommen werden können, beachten Sie Folgendes:

Beginnend mit der ursprünglichen Schleife:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Mit dem Schleifenaustausch können wir diese Schleife sicher ändern in:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Dann können Sie sehen, dass die ifBedingung während der Ausführung der iSchleife konstant ist , sodass Sie das ifOut hochziehen können :

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Dann sehen Sie, dass die innere Schleife zu einem einzigen Ausdruck zusammengefasst werden kann, vorausgesetzt, das Gleitkommamodell erlaubt dies ( /fp:fastwird beispielsweise ausgelöst).

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Dieser ist 100.000 Mal schneller als zuvor.

vulkanischer Rabe
quelle
276
Wenn du schummeln willst, kannst du die Multiplikation auch außerhalb der Schleife nehmen und nach der Schleife * = 100000 summieren.
Jyaif
78
@Michael - Ich glaube, dass dieses Beispiel tatsächlich ein Beispiel für die Optimierung des schleifeninvarianten Hebens (LIH) und NICHT für den Schleifentausch ist . In diesem Fall ist die gesamte innere Schleife unabhängig von der äußeren Schleife und kann daher aus der äußeren Schleife herausgezogen werden, woraufhin das Ergebnis einfach mit einer Summe ivon einer Einheit = 1e5 multipliziert wird. Es macht keinen Unterschied zum Endergebnis, aber ich wollte nur den Rekord korrigieren, da dies eine so frequentierte Seite ist.
Yair Altman
54
Obwohl dies nicht im einfachen Sinne des Austauschs von Schleifen geschieht, könnte das Innere ifan dieser Stelle in Folgendes konvertiert werden: auf sum += (data[j] >= 128) ? data[j] * 100000 : 0;das der Compiler möglicherweise reduzieren kann cmovgeoder gleichwertig ist.
Alex North-Keys
43
Die äußere Schleife soll die Zeit, die die innere Schleife benötigt, groß genug machen, um ein Profil zu erstellen. Warum sollten Sie also einen Schleifentausch durchführen? Am Ende wird diese Schleife sowieso entfernt.
Saurabheights
34
@saurabheights: Falsche Frage: Warum sollte der Compiler NICHT Loop Swap. Microbenchmarks ist schwer;)
Matthieu M.
1884

Zweifellos wären einige von uns daran interessiert, Code zu identifizieren, der für den Verzweigungsprädiktor der CPU problematisch ist. Das Valgrind-Tool cachegrindverfügt über einen Branch-Predictor-Simulator, der mithilfe des --branch-sim=yesFlags aktiviert wird . Wenn Sie die Beispiele in dieser Frage durchgehen, wobei die Anzahl der äußeren Schleifen auf 10000 reduziert und mit kompiliert wurde g++, erhalten Sie folgende Ergebnisse:

Sortiert:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Unsortiert:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

cg_annotateWir gehen auf die zeilenweise Ausgabe ein, die wir für die betreffende Schleife sehen:

Sortiert:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Unsortiert:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Auf diese Weise können Sie die problematische Zeile leicht identifizieren. In der unsortierten Version verursacht die if (data[c] >= 128)Zeile 164.050.007 falsch vorhergesagte bedingte Verzweigungen ( Bcm) unter dem Verzweigungsvorhersagemodell von cachegrind, während sie in der sortierten Version nur 10.006 verursacht.


Alternativ können Sie unter Linux das Subsystem für Leistungsindikatoren verwenden, um dieselbe Aufgabe auszuführen, jedoch mit nativer Leistung unter Verwendung von CPU-Leistungsindikatoren.

perf stat ./sumtest_sorted

Sortiert:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Unsortiert:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Es kann auch Quellcode-Annotationen mit Demontage durchführen.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Weitere Informationen finden Sie im Performance-Tutorial .

caf
quelle
74
Dies ist beängstigend. In der unsortierten Liste sollte eine 50% ige Chance bestehen, das Add zu treffen. Irgendwie hat die Branchenvorhersage nur eine Fehlerquote von 25%. Wie kann sie besser als 50% Fehler sein?
TallBrian
128
@ tall.b.lo: Die 25% entfallen auf alle Zweige - es gibt zwei Zweige in der Schleife, einen für data[c] >= 128(mit einer Fehlerrate von 50%, wie Sie vorschlagen) und einen für die Schleifenbedingung mit einer Fehlerrate von c < arraySize~ 0% .
Café
1340

Ich habe gerade diese Frage und ihre Antworten gelesen und habe das Gefühl, dass eine Antwort fehlt.

Ein üblicher Weg, um die Verzweigungsvorhersage zu eliminieren, die in verwalteten Sprachen besonders gut funktioniert, ist die Tabellensuche anstelle der Verwendung einer Verzweigung (obwohl ich sie in diesem Fall nicht getestet habe).

Dieser Ansatz funktioniert im Allgemeinen, wenn:

  1. Es ist eine kleine Tabelle und wird wahrscheinlich im Prozessor zwischengespeichert
  2. Sie führen die Dinge in einer ziemlich engen Schleife aus und / oder der Prozessor kann die Daten vorladen.

Hintergrund und warum

Aus Prozessorsicht ist Ihr Speicher langsam. Um den Geschwindigkeitsunterschied auszugleichen, sind in Ihrem Prozessor einige Caches integriert (L1 / L2-Cache). Stellen Sie sich also vor, Sie machen Ihre netten Berechnungen und finden heraus, dass Sie ein Stück Gedächtnis brauchen. Der Prozessor erhält seine 'Lade'-Operation und lädt den Speicher in den Cache - und verwendet dann den Cache, um den Rest der Berechnungen durchzuführen. Da der Speicher relativ langsam ist, verlangsamt dieses "Laden" Ihr Programm.

Wie bei der Verzweigungsvorhersage wurde dies bei den Pentium-Prozessoren optimiert: Der Prozessor sagt voraus, dass er ein Datenelement laden muss, und versucht, dieses in den Cache zu laden, bevor die Operation tatsächlich den Cache erreicht. Wie wir bereits gesehen haben, geht die Verzweigungsvorhersage manchmal furchtbar schief - im schlimmsten Fall müssen Sie zurückgehen und tatsächlich auf eine Speicherauslastung warten, die ewig dauern wird ( mit anderen Worten: Eine fehlgeschlagene Verzweigungsvorhersage ist schlecht, ein Speicher Laden nach einem Ausfall der Verzweigungsvorhersage ist einfach schrecklich! ).

Glücklicherweise lädt der Prozessor das Speicherzugriffsmuster in seinen schnellen Cache, wenn das Speicherzugriffsmuster vorhersehbar ist, und alles ist in Ordnung.

Das erste, was wir wissen müssen, ist, was klein ist ? Während kleiner im Allgemeinen besser ist, gilt als Faustregel, dass Sie sich an Nachschlagetabellen mit einer Größe von <= 4096 Byte halten. Als Obergrenze: Wenn Ihre Nachschlagetabelle größer als 64 KB ist, lohnt es sich wahrscheinlich, sie zu überdenken.

Eine Tabelle erstellen

Wir haben also herausgefunden, dass wir einen kleinen Tisch erstellen können. Als nächstes müssen Sie eine Suchfunktion einrichten. Suchfunktionen sind normalerweise kleine Funktionen, die einige grundlegende Ganzzahloperationen verwenden (und / oder xor verschieben, hinzufügen, entfernen und möglicherweise multiplizieren). Sie möchten, dass Ihre Eingabe von der Suchfunktion in eine Art "eindeutigen Schlüssel" in Ihrer Tabelle übersetzt wird, der Ihnen dann einfach die Antwort auf alle gewünschten Arbeiten gibt.

In diesem Fall bedeutet> = 128, dass wir den Wert behalten können, <128 bedeutet, dass wir ihn loswerden. Der einfachste Weg, dies zu tun, ist die Verwendung eines 'UND': Wenn wir es behalten, UND UND mit 7FFFFFFF; Wenn wir es loswerden wollen, UND wir es mit 0. Beachten Sie auch, dass 128 eine Potenz von 2 ist - also können wir eine Tabelle mit 32768/128 ganzen Zahlen erstellen und sie mit einer Null und viel füllen 7FFFFFFFF's.

Verwaltete Sprachen

Sie fragen sich vielleicht, warum dies in verwalteten Sprachen gut funktioniert. Schließlich überprüfen verwaltete Sprachen die Grenzen der Arrays mit einem Zweig, um sicherzustellen, dass Sie nichts falsch machen ...

Na ja, nicht genau ... :-)

Es wurde viel daran gearbeitet, diesen Zweig für verwaltete Sprachen zu entfernen. Zum Beispiel:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

In diesem Fall ist es für den Compiler offensichtlich, dass die Randbedingung niemals getroffen wird. Zumindest der Microsoft JIT-Compiler (aber ich gehe davon aus, dass Java ähnliche Dinge tut) wird dies bemerken und die Prüfung insgesamt entfernen. WOW, das heißt kein Zweig. Ebenso werden andere offensichtliche Fälle behandelt.

Wenn Sie Probleme mit Suchvorgängen in verwalteten Sprachen haben - der Schlüssel besteht darin & 0x[something]FFF, Ihrer Suchfunktion eine hinzuzufügen , um die Grenzüberprüfung vorhersehbar zu machen - und zu beobachten, wie sie schneller abläuft.

Das Ergebnis dieses Falles

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
atlaste
quelle
57
Sie möchten den Verzweigungsprädiktor umgehen, warum? Es ist eine Optimierung.
Dustin Oprea
108
Weil kein Zweig besser ist als ein Zweig :-) In vielen Situationen ist dies einfach viel schneller ... Wenn Sie optimieren, ist es definitiv einen Versuch wert. Sie verwenden es auch ziemlich oft in f.ex. graphics.stanford.edu/~seander/bithacks.html
atlaste
36
Im Allgemeinen können Nachschlagetabellen schnell sein, aber haben Sie die Tests für diese bestimmte Bedingung ausgeführt? Ihr Code enthält weiterhin eine Verzweigungsbedingung. Erst jetzt wird er in den Teil zur Generierung von Nachschlagetabellen verschoben. Sie würden immer noch nicht Ihren Perf Boost bekommen
Zain Rizvi
38
@Zain wenn du es wirklich wissen willst ... Ja: 15 Sekunden mit dem Zweig und 10 Sekunden mit meiner Version. Unabhängig davon ist es eine nützliche Technik, so oder so zu wissen.
Atlaste
42
Warum nicht, sum += lookup[data[j]]wo lookupist ein Array mit 256 Einträgen, wobei die ersten Null und die letzten gleich dem Index sind?
Kris Vandermotten
1200

Da die Daten beim ifSortieren des Arrays zwischen 0 und 255 verteilt werden, wird in der ersten Hälfte der Iterationen nicht die Anweisung angegeben (die ifAnweisung wird unten geteilt).

if (data[c] >= 128)
    sum += data[c];

Die Frage ist: Warum wird die obige Anweisung in bestimmten Fällen nicht ausgeführt, wie bei sortierten Daten? Hier kommt der "Branch Predictor". Ein Verzweigungsprädiktor ist eine digitale Schaltung, die versucht zu erraten, in welche Richtung eine Verzweigung (z. B. eine if-then-elseStruktur) gehen wird, bevor dies sicher bekannt ist. Der Zweck des Verzweigungsprädiktors besteht darin, den Fluss in der Befehlspipeline zu verbessern. Branchenprädiktoren spielen eine entscheidende Rolle bei der Erzielung einer hohen effektiven Leistung!

Lassen Sie uns ein Benchmarking durchführen, um es besser zu verstehen

Die Leistung einer ifAnweisung hängt davon ab, ob ihr Zustand ein vorhersehbares Muster aufweist. Wenn die Bedingung immer wahr oder immer falsch ist, nimmt die Verzweigungsvorhersagelogik im Prozessor das Muster auf. Wenn andererseits das Muster nicht vorhersehbar ist, ist die ifAussage viel teurer.

Lassen Sie uns die Leistung dieser Schleife unter verschiedenen Bedingungen messen:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Hier sind die Timings der Schleife mit verschiedenen True-False-Mustern:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF           513

(i & 2) == 0             TTFFTTFF           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF   1275

(i & 8) == 0             8T 8F 8T 8F        752

(i & 16) == 0            16T 16F 16T 16F    490

Ein " schlechtes " ifRichtig -Falsch-Muster kann eine Aussage bis zu sechsmal langsamer machen als ein " gutes " Muster! Welches Muster gut und welches schlecht ist, hängt natürlich von den genauen Anweisungen ab, die vom Compiler und vom jeweiligen Prozessor generiert werden.

Es besteht also kein Zweifel über den Einfluss der Branchenvorhersage auf die Leistung!

Saqlain
quelle
23
@MooingDuck Weil es keinen Unterschied macht - dieser Wert kann alles sein, aber er wird immer noch im Rahmen dieser Schwellenwerte liegen. Warum also einen zufälligen Wert anzeigen, wenn Sie die Grenzen bereits kennen? Obwohl ich damit einverstanden bin, dass Sie der Vollständigkeit halber einen zeigen können, und "nur zum Teufel".
cst1992
24
@ cst1992: Im Moment ist TTFFTTFFTTFF sein langsamstes Timing, was für mein menschliches Auge ziemlich vorhersehbar erscheint. Random ist von Natur aus unvorhersehbar, daher ist es durchaus möglich, dass es noch langsamer ist und somit außerhalb der hier gezeigten Grenzen liegt. OTOH, es könnte sein, dass TTFFTTFF den pathologischen Fall perfekt trifft. Kann nicht sagen, da er die Timings nicht für zufällig angezeigt hat.
Mooing Duck
21
@MooingDuck Für ein menschliches Auge ist "TTFFTTFFTTFF" eine vorhersehbare Sequenz, aber wir sprechen hier über das Verhalten des in eine CPU eingebauten Verzweigungsprädiktors. Der Verzweigungsprädiktor ist keine Mustererkennung auf AI-Ebene. es ist sehr einfach. Wenn Sie nur Zweige wechseln, wird dies nicht gut vorhergesagt. In den meisten Codes gehen Zweige fast immer auf die gleiche Weise. Betrachten Sie eine Schleife, die tausendmal ausgeführt wird. Der Zweig am Ende der Schleife kehrt 999 Mal zum Anfang der Schleife zurück, und dann macht das tausendste Mal etwas anderes. Ein sehr einfacher Verzweigungsprädiktor funktioniert normalerweise gut.
Steveha
18
@steveha: Ich denke, Sie machen Annahmen darüber, wie der CPU-Verzweigungsprädiktor funktioniert, und ich bin mit dieser Methode nicht einverstanden. Ich weiß nicht, wie fortgeschritten dieser Zweigprädiktor ist, aber ich glaube, er ist weitaus fortgeschrittener als Sie. Sie haben wahrscheinlich Recht, aber die Messungen wären definitiv gut.
Mooing Duck
5
@steveha: Der zweistufige adaptive Prädiktor kann sich ohne Probleme auf das TTFFTTFF-Muster festlegen. "Varianten dieser Vorhersagemethode werden in den meisten modernen Mikroprozessoren verwendet". Lokale Verzweigungsvorhersage und globale Verzweigungsvorhersage basieren auf einem adaptiven Prädiktor auf zwei Ebenen. "Globale Verzweigungsvorhersage wird in AMD-Prozessoren sowie in Intel Pentium M-, Core-, Core 2- und Silvermont-basierten Atom-Prozessoren verwendet." Fügen Sie dieser Liste auch Agree Predictor, Hybrid Predictor und Prediction of Indirect Jumps hinzu. Der Schleifenprädiktor wird nicht aktiviert, erreicht jedoch 75%. Das lässt nur 2, die nicht
einrasten
1126

Eine Möglichkeit, Verzweigungsvorhersagefehler zu vermeiden, besteht darin, eine Nachschlagetabelle zu erstellen und diese anhand der Daten zu indizieren. Stefan de Bruijn hat das in seiner Antwort besprochen.

In diesem Fall wissen wir jedoch, dass die Werte im Bereich [0, 255] liegen, und wir kümmern uns nur um Werte> = 128. Das bedeutet, dass wir leicht ein einzelnes Bit extrahieren können, das uns sagt, ob wir einen Wert wollen oder nicht: durch Verschieben Bei den Daten rechts von 7 Bits bleibt ein 0-Bit oder ein 1-Bit übrig, und wir möchten den Wert nur hinzufügen, wenn wir ein 1-Bit haben. Nennen wir dieses Bit das "Entscheidungsbit".

Indem wir den 0/1-Wert des Entscheidungsbits als Index für ein Array verwenden, können wir Code erstellen, der gleich schnell ist, unabhängig davon, ob die Daten sortiert sind oder nicht. Unser Code fügt immer einen Wert hinzu, aber wenn das Entscheidungsbit 0 ist, fügen wir den Wert an einer Stelle hinzu, die uns egal ist. Hier ist der Code:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Dieser Code verschwendet die Hälfte der Adds, hat jedoch nie einen Fehler bei der Verzweigungsvorhersage. Bei zufälligen Daten ist es enorm schneller als bei der Version mit einer tatsächlichen if-Anweisung.

In meinen Tests war eine explizite Nachschlagetabelle jedoch etwas schneller als diese, wahrscheinlich weil die Indizierung in eine Nachschlagetabelle etwas schneller war als die Bitverschiebung. Dies zeigt, wie mein Code die Nachschlagetabelle luteinrichtet und verwendet ( im Code einfallslos als "LookUp-Tabelle" bezeichnet). Hier ist der C ++ - Code:

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

In diesem Fall war die Nachschlagetabelle nur 256 Byte groß, passt also gut in einen Cache und alles war schnell. Diese Technik würde nicht gut funktionieren, wenn die Daten 24-Bit-Werte wären und wir nur die Hälfte davon wollten ... die Nachschlagetabelle wäre viel zu groß, um praktisch zu sein. Auf der anderen Seite können wir die beiden oben gezeigten Techniken kombinieren: Verschieben Sie zuerst die Bits und indizieren Sie dann eine Nachschlagetabelle. Für einen 24-Bit-Wert, für den wir nur den Wert der oberen Hälfte wünschen, können wir die Daten möglicherweise um 12 Bit nach rechts verschieben und einen 12-Bit-Wert für einen Tabellenindex erhalten. Ein 12-Bit-Tabellenindex impliziert eine Tabelle mit 4096 Werten, was praktisch sein kann.

Die Technik der Indizierung in ein Array anstelle einer ifAnweisung kann verwendet werden, um zu entscheiden, welcher Zeiger verwendet werden soll. Ich sah eine Bibliothek, die Binärbäume implementierte, und anstatt zwei benannte Zeiger ( pLeftund pRightwas auch immer) zu haben, hatte ich ein Array von Zeigern der Länge 2 und verwendete die "Entscheidungsbit" -Technik, um zu entscheiden, welchem ich folgen sollte. Zum Beispiel anstelle von:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

Diese Bibliothek würde so etwas tun wie:

i = (x < node->value);
node = node->link[i];

Hier ist ein Link zu diesem Code: Red Black Trees , Eternally Confuzzled

steveha
quelle
29
Richtig, Sie können das Bit auch einfach direkt verwenden und multiplizieren ( data[c]>>7- was hier auch irgendwo besprochen wird); Ich habe diese Lösung absichtlich weggelassen, aber natürlich haben Sie Recht. Nur eine kleine Anmerkung: Die Faustregel für Nachschlagetabellen lautet: Wenn es in 4 KB passt (aufgrund von Caching), funktioniert es - machen Sie die Tabelle vorzugsweise so klein wie möglich. Für verwaltete Sprachen würde ich das auf 64 KB erhöhen, für einfache Sprachen wie C ++ und C würde ich es wahrscheinlich noch einmal überdenken (das ist nur meine Erfahrung). Seitdem typeof(int) = 4würde ich versuchen, mich an maximal 10 Bit zu halten.
atlaste
17
Ich denke, die Indizierung mit dem Wert 0/1 ist wahrscheinlich schneller als eine ganzzahlige Multiplikation, aber ich denke, wenn die Leistung wirklich kritisch ist, sollten Sie sie profilieren. Ich bin damit einverstanden, dass kleine Nachschlagetabellen wichtig sind, um den Cache-Druck zu vermeiden. Wenn Sie jedoch einen größeren Cache haben, können Sie mit einer größeren Nachschlagetabelle davonkommen. 4 KB sind also eher eine Faustregel als eine harte Regel. Ich denke du meintest sizeof(int) == 4? Das wäre für 32-Bit wahr. Mein zwei Jahre altes Handy verfügt über einen 32-KB-L1-Cache, sodass möglicherweise sogar eine 4-KB-Nachschlagetabelle funktioniert, insbesondere wenn die Nachschlagewerte ein Byte anstelle eines int sind.
Steveha
12
Möglicherweise bin ich etwas fehlt , aber in Ihrem jgleich 0 oder 1 - Methode , warum Sie nicht nur multiplizieren Sie den Wert durch , jbevor sie anstatt mit der Array - Indizierung Zugabe (möglicherweise durch multipliziert werden sollte , 1-janstatt j)
Richard Tingle
6
@steveha Die Multiplikation sollte schneller sein. Ich habe versucht, sie in den Intel-Büchern nachzuschlagen, konnte sie aber nicht finden. In beiden Fällen liefert mir das Benchmarking auch hier dieses Ergebnis.
Atlaste
10
@steveha PS: Eine andere mögliche Antwort wäre, int c = data[j]; sum += c & -(c >> 7);die überhaupt keine Multiplikationen erfordert.
Atlaste
1021

Im sortierten Fall können Sie es besser machen, als sich auf eine erfolgreiche Verzweigungsvorhersage oder einen verzweigungslosen Vergleichstrick zu verlassen: Entfernen Sie die Verzweigung vollständig.

In der Tat ist das Array in einer zusammenhängenden Zone mit data < 128und einer anderen mit aufgeteilt data >= 128. Sie sollten also den Partitionspunkt mit einer dichotomischen Suche (unter Verwendung von Lg(arraySize) = 15Vergleichen) finden und dann eine direkte Akkumulation von diesem Punkt aus durchführen.

So etwas wie (nicht markiert)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

oder etwas verschleierter

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Ein noch schnellerer Ansatz, der eine ungefähre Lösung für sortierte oder unsortierte ergibt, ist: sum= 3137536;(unter der Annahme einer wirklich gleichmäßigen Verteilung, 16384 Proben mit dem erwarteten Wert 191,5) :-)

Yves Daoust
quelle
23
sum= 3137536- klug. Das ist offensichtlich nicht der Punkt der Frage. Bei der Frage geht es eindeutig darum, überraschende Leistungsmerkmale zu erklären. Ich neige dazu zu sagen, dass das Hinzufügen von Tun std::partitionstatt std::sortWertvoll ist. Die eigentliche Frage erstreckt sich jedoch nicht nur auf den angegebenen synthetischen Benchmark.
sehe
12
@DeadMG: Dies ist in der Tat nicht die dichotomische Standardsuche nach einem bestimmten Schlüssel, sondern eine Suche nach dem Partitionierungsindex. Es ist ein einzelner Vergleich pro Iteration erforderlich. Aber verlassen Sie sich nicht auf diesen Code, ich habe ihn nicht überprüft. Wenn Sie an einer garantierten korrekten Implementierung interessiert sind, lassen Sie es mich wissen.
Yves Daoust
831

Das obige Verhalten tritt aufgrund der Verzweigungsvorhersage auf.

Um die Verzweigungsvorhersage zu verstehen, muss man zuerst die Anweisungspipeline verstehen :

Jeder Befehl ist in eine Folge von Schritten unterteilt, so dass verschiedene Schritte gleichzeitig parallel ausgeführt werden können. Diese Technik ist als Befehlspipeline bekannt und wird verwendet, um den Durchsatz in modernen Prozessoren zu erhöhen. Um dies besser zu verstehen, sehen Sie sich bitte dieses Beispiel auf Wikipedia an .

Im Allgemeinen haben moderne Prozessoren ziemlich lange Pipelines, aber zur Vereinfachung betrachten wir nur diese 4 Schritte.

  1. IF - Ruft die Anweisung aus dem Speicher ab
  2. ID - Dekodieren Sie die Anweisung
  3. EX - Führen Sie die Anweisung aus
  4. WB - In das CPU-Register zurückschreiben

4-stufige Pipeline im Allgemeinen für 2 Anweisungen. 4-stufige Pipeline im Allgemeinen

Zurück zur obigen Frage: Betrachten wir die folgenden Anweisungen:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Ohne Verzweigungsvorhersage würde Folgendes auftreten:

Um Befehl B oder Befehl C auszuführen, muss der Prozessor warten, bis der Befehl A nicht bis zur EX-Stufe in der Pipeline reicht, da die Entscheidung, zu Befehl B oder Befehl C zu gehen, vom Ergebnis von Befehl A abhängt wird so aussehen.

Wenn if-Bedingung true zurückgibt: Geben Sie hier die Bildbeschreibung ein

Wann, wenn die Bedingung false zurückgibt: Geben Sie hier die Bildbeschreibung ein

Infolge des Wartens auf das Ergebnis von Befehl A beträgt die Gesamtmenge der im obigen Fall verbrachten CPU-Zyklen (ohne Verzweigungsvorhersage; sowohl für wahr als auch für falsch) 7.

Was ist also eine Zweigvorhersage?

Der Zweigprädiktor wird versuchen zu erraten, in welche Richtung ein Zweig (eine Wenn-Dann-Sonst-Struktur) gehen wird, bevor dies sicher bekannt ist. Es wird nicht darauf warten, dass die Anweisung A die EX-Stufe der Pipeline erreicht, sondern die Entscheidung erraten und zu dieser Anweisung gehen (B oder C in unserem Beispiel).

Im Falle einer korrekten Vermutung sieht die Pipeline ungefähr so ​​aus: Geben Sie hier die Bildbeschreibung ein

Wenn später festgestellt wird, dass die Vermutung falsch war, werden die teilweise ausgeführten Anweisungen verworfen und die Pipeline beginnt mit der richtigen Verzweigung von vorne, was zu einer Verzögerung führt. Die Zeit, die im Falle einer Verzweigungsfehlvorhersage verschwendet wird, entspricht der Anzahl der Stufen in der Pipeline von der Abrufstufe zur Ausführungsstufe. Moderne Mikroprozessoren neigen dazu, ziemlich lange Pipelines zu haben, so dass die Fehlvorhersageverzögerung zwischen 10 und 20 Taktzyklen liegt. Je länger die Pipeline ist, desto größer ist der Bedarf an einem guten Verzweigungsprädiktor .

Im OP-Code verfügt der Verzweigungsprädiktor beim ersten Mal, wenn die Bedingung erfüllt ist, über keine Informationen, um die Vorhersage zu stützen. Daher wählt er beim ersten Mal zufällig den nächsten Befehl aus. Später in der for-Schleife kann die Vorhersage auf dem Verlauf basieren. Für ein Array in aufsteigender Reihenfolge gibt es drei Möglichkeiten:

  1. Alle Elemente sind kleiner als 128
  2. Alle Elemente sind größer als 128
  3. Einige neue Startelemente sind kleiner als 128 und später größer als 128

Nehmen wir an, dass der Prädiktor beim ersten Lauf immer den wahren Zweig annimmt.

Im ersten Fall wird es also immer den wahren Zweig nehmen, da historisch alle seine Vorhersagen korrekt sind. Im zweiten Fall wird zunächst eine falsche Vorhersage getroffen, nach einigen Iterationen jedoch eine korrekte Vorhersage. Im dritten Fall wird es zunächst korrekt vorhergesagt, bis die Elemente kleiner als 128 sind. Danach wird es für einige Zeit fehlschlagen und sich selbst korrigieren, wenn es einen Fehler bei der Verzweigungsvorhersage in der Geschichte sieht.

In all diesen Fällen ist die Anzahl der Fehler zu gering. Infolgedessen müssen die teilweise ausgeführten Anweisungen nur einige Male verworfen und mit der richtigen Verzweigung neu begonnen werden, was zu weniger CPU-Zyklen führt.

Im Fall eines zufälligen unsortierten Arrays muss die Vorhersage jedoch die teilweise ausgeführten Anweisungen verwerfen und die meiste Zeit mit der richtigen Verzweigung neu beginnen, was zu mehr CPU-Zyklen im Vergleich zum sortierten Array führt.

Harter Sharma
quelle
1
Wie werden zwei Anweisungen zusammen ausgeführt? Wird dies mit separaten CPU-Kernen durchgeführt oder ist der Pipeline-Befehl in einen einzelnen CPU-Kern integriert?
M. Kazem Akhgary 11.
1
@ M.kazemAkhgary Es ist alles in einem logischen Kern. Wenn Sie interessiert sind, ist dies zum Beispiel im Intel Software Developer Manual
Sergey.quixoticaxis.Ivanov
727

Eine offizielle Antwort wäre von

  1. Intel - Vermeidung von Kosten für Branchenfehlvorhersagen
  2. Intel - Reorganisation von Filialen und Schleifen zur Verhinderung von Fehlvorhersagen
  3. Wissenschaftliche Arbeiten - Computerarchitektur zur Vorhersage von Zweigen
  4. Bücher: JL Hennessy, DA Patterson: Computerarchitektur: ein quantitativer Ansatz
  5. Artikel in wissenschaftlichen Publikationen: TY Yeh, YN Patt haben viele davon zu Branchenvorhersagen gemacht.

Sie können auch anhand dieses schönen Diagramms sehen, warum der Verzweigungsprädiktor verwirrt wird.

2-Bit-Zustandsdiagramm

Jedes Element im Originalcode ist ein zufälliger Wert

data[c] = std::rand() % 256;

Der Prädiktor wechselt also als std::rand()Schlag die Seite.

Auf der anderen Seite wird der Prädiktor, sobald er sortiert ist, zuerst in einen Zustand versetzt, in dem er stark nicht genommen wurde, und wenn sich die Werte auf den hohen Wert ändern, ändert sich der Prädiktor in drei Durchläufen vollständig von stark nicht genommen zu stark genommen.


Surt
quelle
696

In derselben Zeile (ich denke, dies wurde durch keine Antwort hervorgehoben) ist es gut zu erwähnen, dass manchmal (insbesondere in Software, bei der die Leistung von Bedeutung ist - wie im Linux-Kernel) einige if-Anweisungen wie die folgenden gefunden werden können:

if (likely( everything_is_ok ))
{
    /* Do something */
}

oder ähnlich:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Beides likely()und unlikely()tatsächlich sind Makros, die definiert werden, indem so etwas wie die GCCs verwendet werden __builtin_expect, um dem Compiler zu helfen, Vorhersagecode einzufügen, um die Bedingung unter Berücksichtigung der vom Benutzer bereitgestellten Informationen zu begünstigen. GCC unterstützt andere integrierte Funktionen, die das Verhalten des laufenden Programms ändern oder Anweisungen auf niedriger Ebene wie das Löschen des Caches usw. ausgeben können. Weitere Informationen finden Sie in dieser Dokumentation , die die verfügbaren integrierten Funktionen des GCC enthält.

Normalerweise finden sich diese Optimierungen hauptsächlich in Echtzeitanwendungen oder eingebetteten Systemen, in denen die Ausführungszeit wichtig und kritisch ist. Wenn Sie beispielsweise nach einer Fehlerbedingung suchen, die nur 1/10000000 Mal auftritt, informieren Sie den Compiler darüber. Auf diese Weise würde die Verzweigungsvorhersage standardmäßig annehmen, dass die Bedingung falsch ist.

rkachach
quelle
678

Häufig verwendete Boolesche Operationen in C ++ erzeugen viele Zweige im kompilierten Programm. Wenn sich diese Zweige in Schleifen befinden und schwer vorherzusagen sind, können sie die Ausführung erheblich verlangsamen. Boolesche Variablen werden als 8-Bit-Ganzzahlen mit dem Wert 0für falseund 1für gespeichert true.

Boolesche Variablen sind in dem Sinne überbestimmt, dass alle Operatoren, die Boolesche Variablen als Eingabe haben, prüfen, ob die Eingaben einen anderen Wert als 0oder haben 1, aber Operatoren, die Boolesche Werte als Ausgabe haben, keinen anderen Wert als 0oder erzeugen können 1. Dies macht Operationen mit Booleschen Variablen als Eingabe weniger effizient als nötig. Betrachten Sie ein Beispiel:

bool a, b, c, d;
c = a && b;
d = a || b;

Dies wird normalerweise vom Compiler folgendermaßen implementiert:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Dieser Code ist alles andere als optimal. Bei Fehleinschätzungen können die Zweige lange dauern. Die Booleschen Operationen können viel effizienter gemacht werden, wenn mit Sicherheit bekannt ist, dass die Operanden keine anderen Werte als haben0 und haben 1. Der Grund, warum der Compiler eine solche Annahme nicht macht, ist, dass die Variablen möglicherweise andere Werte haben, wenn sie nicht initialisiert sind oder aus unbekannten Quellen stammen. Der obige Code kann , wenn optimiert werden aund bhat auf gültige Werte initialisiert oder wenn sie von den Betreibern kommen , die Boolesche Ausgabe. Der optimierte Code sieht folgendermaßen aus:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charwird anstelle von boolverwendet, um die Verwendung der bitweisen Operatoren ( &und |) anstelle der Booleschen Operatoren ( &&und ||) zu ermöglichen. Die bitweisen Operatoren sind einzelne Befehle, die nur einen Taktzyklus benötigen. Der OR - Operator ( |) funktioniert auch , wenn aund bhaben andere Werte als 0oder1 . Der AND-Operator ( &) und der EXCLUSIVE OR-Operator ( ^) können inkonsistente Ergebnisse liefern, wenn die Operanden andere Werte als 0und haben 1.

~kann nicht für NOT verwendet werden. Stattdessen können Sie einen Booleschen Wert NICHT für eine bekannte Variable festlegen01 Wert oder durch XOR-Verknüpfung mit 1folgenden festlegen :

bool a, b;
b = !a;

kann optimiert werden für:

char a = 0, b;
b = a ^ 1;

a && bkann nicht durch a & bif ersetzt werden, bist ein Ausdruck, der nicht ausgewertet werden sollte, wenn ais false( &&wird nicht ausgewertet b, &wird). Ebenso a || bkann nicht durch a | bif ersetzt werden, bist ein Ausdruck, der nicht ausgewertet werden sollte, wenn ais true.

Die Verwendung bitweiser Operatoren ist vorteilhafter, wenn die Operanden Variablen sind, als wenn die Operanden Vergleiche sind:

bool a; double x, y, z;
a = x > y && z < 5.0;

ist in den meisten Fällen optimal (es sei denn, Sie erwarten, dass der &&Ausdruck viele Verzweigungsfehler erzeugt).

Maciej
quelle
341

Das ist sicher!...

Durch die Verzweigungsvorhersage wird die Logik langsamer ausgeführt, da in Ihrem Code umgeschaltet wird! Es ist, als ob Sie eine gerade Straße oder eine Straße mit vielen Abbiegungen fahren, sicher wird die gerade Straße schneller gemacht! ...

Wenn das Array sortiert ist, ist Ihre Bedingung im ersten Schritt falsch: data[c] >= 128 und wird dann zu einem wahren Wert für den gesamten Weg bis zum Ende der Straße. So kommen Sie schneller zum Ende der Logik. Auf der anderen Seite müssen Sie bei Verwendung eines unsortierten Arrays viel drehen und verarbeiten, wodurch Ihr Code mit Sicherheit langsamer läuft ...

Schauen Sie sich das Bild an, das ich unten für Sie erstellt habe. Welche Straße wird schneller fertig?

Verzweigungsvorhersage

Also programmatisch Verzweigungsvorhersage dass der Prozess langsamer wird ...

Auch am Ende ist es gut zu wissen, dass wir zwei Arten von Verzweigungsvorhersagen haben, die sich jeweils unterschiedlich auf Ihren Code auswirken werden:

1. Statisch

2. Dynamisch

Verzweigungsvorhersage

Die statische Verzweigungsvorhersage wird vom Mikroprozessor verwendet, wenn zum ersten Mal eine bedingte Verzweigung auftritt, und die dynamische Verzweigungsvorhersage wird für nachfolgende Ausführungen des bedingten Verzweigungscodes verwendet.

Um Ihren Code effektiv zu schreiben und diese Regeln zu nutzen , überprüfen Sie beim Schreiben von if-else- oder switch- Anweisungen zuerst die häufigsten Fälle und arbeiten Sie schrittweise bis zu den am wenigsten verbreiteten. Schleifen erfordern nicht unbedingt eine spezielle Reihenfolge des Codes für die statische Verzweigungsvorhersage, da normalerweise nur die Bedingung des Schleifeniterators verwendet wird.

Alireza
quelle
304

Diese Frage wurde bereits mehrfach hervorragend beantwortet. Trotzdem möchte ich die Aufmerksamkeit der Gruppe auf eine weitere interessante Analyse lenken.

Kürzlich wurde dieses Beispiel (geringfügig geändert) auch verwendet, um zu demonstrieren, wie ein Code innerhalb des Programms selbst unter Windows profiliert werden kann. Unterwegs zeigt der Autor auch, wie anhand der Ergebnisse ermittelt werden kann, wo der Code die meiste Zeit sowohl im sortierten als auch im unsortierten Fall verbringt. Schließlich zeigt das Stück auch, wie man eine wenig bekannte Funktion der HAL (Hardware Abstraction Layer) verwendet, um zu bestimmen, wie viel Verzweigungsfehlvorhersage in dem unsortierten Fall auftritt.

Der Link ist hier: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

ForeverLearning
quelle
3
Das ist ein sehr interessanter Artikel (tatsächlich habe ich gerade alles gelesen), aber wie beantwortet er die Frage?
Peter Mortensen
2
@PeterMortensen Ich bin ein bisschen verblüfft von Ihrer Frage. Zum Beispiel ist hier eine relevante Zeile aus diesem Artikel: Der When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. Autor versucht, die Profilerstellung im Kontext des hier veröffentlichten Codes zu diskutieren und dabei zu erklären, warum der sortierte Fall so viel schneller ist.
ForeverLearning
260

Wie bereits von anderen erwähnt, steckt hinter dem Rätsel der Branch Predictor .

Ich versuche nicht, etwas hinzuzufügen, sondern das Konzept auf andere Weise zu erklären. Im Wiki gibt es eine kurze Einführung, die Text und Diagramme enthält. Ich mag die folgende Erklärung, die ein Diagramm verwendet, um den Branch Predictor intuitiv zu erarbeiten.

In der Computerarchitektur ist ein Verzweigungsprädiktor eine digitale Schaltung, die versucht zu erraten, in welche Richtung eine Verzweigung (z. B. eine Wenn-Dann-Sonst-Struktur) gehen wird, bevor dies sicher bekannt ist. Der Zweck des Verzweigungsprädiktors besteht darin, den Fluss in der Befehlspipeline zu verbessern. Verzweigungsprädiktoren spielen eine entscheidende Rolle bei der Erzielung einer hohen effektiven Leistung in vielen modernen Pipeline-Mikroprozessorarchitekturen wie x86.

Die bidirektionale Verzweigung wird normalerweise mit einer bedingten Sprunganweisung implementiert. Ein bedingter Sprung kann entweder "nicht ausgeführt" werden und die Ausführung mit dem ersten Codezweig fortsetzen, der unmittelbar nach dem bedingten Sprung folgt, oder er kann "ausgeführt" werden und an eine andere Stelle im Programmspeicher springen, an der sich der zweite Codezweig befindet gelagert. Es ist nicht sicher bekannt, ob ein bedingter Sprung ausgeführt wird oder nicht, bis die Bedingung berechnet wurde und der bedingte Sprung die Ausführungsphase in der Befehlspipeline passiert hat (siehe 1).

Abbildung 1

Basierend auf dem beschriebenen Szenario habe ich eine Animationsdemo geschrieben, um zu zeigen, wie Anweisungen in einer Pipeline in verschiedenen Situationen ausgeführt werden.

  1. Ohne den Branch Predictor.

Ohne Verzweigungsvorhersage müsste der Prozessor warten, bis der bedingte Sprungbefehl die Ausführungsstufe passiert hat, bevor der nächste Befehl in die Abrufstufe in der Pipeline eintreten kann.

Das Beispiel enthält drei Anweisungen und die erste ist eine bedingte Sprunganweisung. Die beiden letztgenannten Befehle können in die Pipeline eingehen, bis der bedingte Sprungbefehl ausgeführt wird.

ohne Verzweigungsprädiktor

Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

  1. Verwenden Sie Branch Predictor und machen Sie keinen bedingten Sprung. Nehmen wir an, dass die Vorhersage nicht den bedingten Sprung macht.

Geben Sie hier die Bildbeschreibung ein

Es dauert 7 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

  1. Verwenden Sie Branch Predictor und machen Sie einen bedingten Sprung. Nehmen wir an, dass die Vorhersage nicht den bedingten Sprung macht.

Geben Sie hier die Bildbeschreibung ein

Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

Die Zeit, die im Falle einer Verzweigungsfehlvorhersage verschwendet wird, entspricht der Anzahl der Stufen in der Pipeline von der Abrufstufe zur Ausführungsstufe. Moderne Mikroprozessoren neigen dazu, ziemlich lange Pipelines zu haben, so dass die Fehlvorhersageverzögerung zwischen 10 und 20 Taktzyklen liegt. Infolgedessen erhöht die Verlängerung einer Pipeline den Bedarf an einem fortschrittlicheren Verzweigungsprädiktor.

Wie Sie sehen, haben wir anscheinend keinen Grund, Branch Predictor nicht zu verwenden.

Es ist eine recht einfache Demo, die den grundlegenden Teil von Branch Predictor verdeutlicht. Wenn diese Gifs ärgerlich sind, können Sie sie gerne aus der Antwort entfernen. Besucher können auch den Live-Demo-Quellcode von BranchPredictorDemo erhalten

Eugene
quelle
1
Fast so gut wie die Intel-Marketinganimationen, und sie waren nicht nur von Branchenvorhersagen besessen, sondern auch von der Ausführung außerhalb der Reihenfolge. Beide Strategien waren "spekulativ". Das Vorauslesen von Speicher und Speicher (sequentielles Pre-Fetch to Buffer) ist ebenfalls spekulativ. Das alles summiert sich.
McKenzm
@mckenzm: Spekulative Ausführung außerhalb der Reihenfolge macht die Verzweigungsvorhersage noch wertvoller; Neben dem Ausblenden von Abruf- / Dekodierungsblasen werden durch Verzweigungsvorhersage und spekulative Ausführung Steuerungsabhängigkeiten von der Latenz kritischer Pfade entfernt. Code innerhalb oder nach einem if()Block kann ausgeführt werden, bevor die Verzweigungsbedingung bekannt ist. Oder für eine Suchschleife wie strlenoder memchrkönnen sich Interaktionen überlappen. Wenn Sie warten müssten, bis das Match-or-Not-Ergebnis bekannt ist, bevor Sie eine der nächsten Iterationen ausführen, würden Sie einen Engpass bei der Cache-Last + ALU-Latenz anstelle des Durchsatzes haben.
Peter Cordes
209

Verzweigungsvorhersagegewinn!

Es ist wichtig zu verstehen, dass eine falsche Vorhersage von Zweigen Programme nicht verlangsamt. Die Kosten für eine fehlende Vorhersage sind so, als ob keine Verzweigungsvorhersage vorhanden wäre und Sie auf die Auswertung des Ausdrucks gewartet haben, um zu entscheiden, welcher Code ausgeführt werden soll (weitere Erläuterungen im nächsten Absatz).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Immer wenn eine if-else\ switch-Anweisung vorhanden ist, muss der Ausdruck ausgewertet werden, um zu bestimmen, welcher Block ausgeführt werden soll. In den vom Compiler generierten Assemblycode werden Anweisungen für bedingte Verzweigungen eingefügt.

Ein Verzweigungsbefehl kann dazu führen, dass ein Computer mit der Ausführung einer anderen Befehlssequenz beginnt und somit von seinem Standardverhalten beim Ausführen von Befehlen in der Reihenfolge abweicht (dh wenn der Ausdruck falsch ist, überspringt das Programm den Code des ifBlocks), abhängig von einer bestimmten Bedingung die Ausdrucksbewertung in unserem Fall.

Abgesehen davon versucht der Compiler, das Ergebnis vorherzusagen, bevor es tatsächlich ausgewertet wird. Es werden Anweisungen aus dem ifBlock abgerufen, und wenn sich der Ausdruck als wahr herausstellt, dann wunderbar! Wir haben die Zeit für die Bewertung gewonnen und Fortschritte im Code erzielt. Wenn nicht, wird der falsche Code ausgeführt, die Pipeline wird geleert und der richtige Block wird ausgeführt.

Visualisierung:

Angenommen, Sie müssen Route 1 oder Route 2 auswählen. Während Sie darauf warten, dass Ihr Partner die Karte überprüft, haben Sie bei ## angehalten und gewartet, oder Sie können einfach Route1 auswählen und wenn Sie Glück haben (Route 1 ist die richtige Route). Dann war es großartig, dass Sie nicht darauf warten mussten, dass Ihr Partner die Karte überprüfte (Sie haben die Zeit gespart, die er für die Überprüfung der Karte benötigt hätte), sonst kehren Sie einfach zurück.

Während das Spülen von Pipelines sehr schnell ist, lohnt es sich heutzutage, dieses Glücksspiel zu spielen. Das Vorhersagen sortierter Daten oder von Daten, die sich langsam ändern, ist immer einfacher und besser als das Vorhersagen schneller Änderungen.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
Tony Tannous
quelle
Während das Spülen von Rohrleitungen superschnell ist Nicht wirklich. Es ist schnell im Vergleich zu einem Cache-Miss bis zum DRAM, aber auf einem modernen Hochleistungs-x86 (wie der Intel Sandybridge-Familie) sind es ungefähr ein Dutzend Zyklen. Obwohl eine schnelle Wiederherstellung es ermöglicht, zu vermeiden, dass alle älteren unabhängigen Anweisungen vor Beginn der Wiederherstellung in den Ruhestand versetzt werden, verlieren Sie dennoch viele Front-End-Zyklen aufgrund einer Fehlvorhersage. Was genau passiert, wenn eine Skylake-CPU einen Zweig falsch vorhersagt? . (Und jeder Zyklus kann ungefähr 4 Arbeitsanweisungen enthalten.) Schlecht für Code mit hohem Durchsatz.
Peter Cordes
153

In ARM ist keine Verzweigung erforderlich, da jeder Befehl über ein 4-Bit-Bedingungsfeld verfügt, das (zu Nullkosten) 16 verschiedene Bedingungen testet , die im Prozessorstatusregister auftreten können, und ob die Bedingung in einem Befehl vorliegt false, die Anweisung wird übersprungen. Dies macht kurze Verzweigungen überflüssig und es würde keinen Verzweigungsvorhersage-Treffer für diesen Algorithmus geben. Daher würde die sortierte Version dieses Algorithmus aufgrund des zusätzlichen Sortieraufwands langsamer als die unsortierte Version in ARM ausgeführt.

Die innere Schleife für diesen Algorithmus würde in der ARM-Assemblersprache ungefähr so ​​aussehen:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

Aber das ist eigentlich Teil eines Gesamtbildes:

CMPOpcodes aktualisieren immer die Statusbits im Prozessorstatusregister (PSR), da dies ihr Zweck ist. Die meisten anderen Anweisungen berühren den PSR jedoch nur, wenn Sie Sdem Befehl ein optionales Suffix hinzufügen , das angibt, dass der PSR basierend auf dem PSR aktualisiert werden soll Ergebnis der Anweisung. Genau wie das 4-Bit-Bedingungssuffix ist die Möglichkeit, Anweisungen auszuführen, ohne den PSR zu beeinflussen, ein Mechanismus, der den Bedarf an Verzweigungen auf ARM verringert und auch den Versand außerhalb der Reihenfolge auf Hardwareebene erleichtert , da nach Ausführung einer Operation X diese aktualisiert wird Mit den Statusbits können Sie anschließend (oder parallel) eine Reihe anderer Arbeiten ausführen, die sich explizit nicht auf die Statusbits auswirken sollten. Anschließend können Sie den Status der zuvor von X festgelegten Statusbits testen.

Das Bedingungstestfeld und das optionale Feld "Statusbit setzen" können kombiniert werden, zum Beispiel:

  • ADD R1, R2, R3wird ausgeführt, R1 = R2 + R3ohne dass Statusbits aktualisiert werden.
  • ADDGE R1, R2, R3 führt dieselbe Operation nur aus, wenn ein vorheriger Befehl, der die Statusbits beeinflusste, zu einer Bedingung größer oder gleich führte.
  • ADDS R1, R2, R3die Zugabe führt und aktualisiert dann die N, Z, Cund VFlags im Prozessorstatusregister basierend darauf , ob das Ergebnis war negativ, null Carried (für nicht signierten Zusatz) oder übergelaufene (für signierten Zusatz).
  • ADDSGE R1, R2, R3führt die Addition nur durch, wenn der GETest wahr ist, und aktualisiert anschließend die Statusbits basierend auf dem Ergebnis der Addition.

Die meisten Prozessorarchitekturen können nicht angeben, ob die Statusbits für eine bestimmte Operation aktualisiert werden sollen oder nicht. Dies kann das Schreiben von zusätzlichem Code zum Speichern und späteren Wiederherstellen von Statusbits erforderlich machen oder zusätzliche Verzweigungen erfordern oder den Ausfall des Prozessors einschränken Effizienz der Auftragsausführung: Einer der Nebeneffekte der meisten CPU-Befehlssatzarchitekturen, die Statusbits nach den meisten Befehlen zwangsweise aktualisieren, besteht darin, dass es viel schwieriger ist, auseinanderzuhalten, welche Befehle parallel ausgeführt werden können, ohne sich gegenseitig zu stören. Das Aktualisieren von Statusbits hat Nebenwirkungen und wirkt sich daher linearisierend auf den Code aus.Die Fähigkeit von ARM, verzweigungsfreie Bedingungstests für jeden Befehl zu mischen und abzugleichen, mit der Option, die Statusbits nach einem Befehl entweder zu aktualisieren oder nicht zu aktualisieren, ist sowohl für Assembler-Programmierer als auch für Compiler äußerst leistungsfähig und erzeugt sehr effizienten Code.

Wenn Sie sich jemals gefragt haben, warum ARM so phänomenal erfolgreich war, sind die brillante Effektivität und das Zusammenspiel dieser beiden Mechanismen ein großer Teil der Geschichte, da sie eine der größten Quellen für die Effizienz der ARM-Architektur darstellen. Die Brillanz der ursprünglichen Designer der ARM ISA aus dem Jahr 1983, Steve Furber und Roger (jetzt Sophie) Wilson, kann nicht genug betont werden.

Luke Hutchison
quelle
1
Die andere Neuerung in ARM ist das Hinzufügen des S-Befehlssuffixes, das auch für (fast) alle Befehle optional ist. Wenn dies nicht vorhanden ist, können Befehle die Statusbits nicht ändern (mit Ausnahme des CMP-Befehls, dessen Aufgabe es ist, Statusbits zu setzen). es braucht also nicht das Suffix S). Auf diese Weise können Sie in vielen Fällen CMP-Anweisungen vermeiden, solange der Vergleich mit Null oder ähnlich ist (z. B. setzt SUBS R0, R0, # 1 das Z-Bit (Null), wenn R0 Null erreicht). Bedingungen und das Suffix S verursachen keinen Overhead. Es ist eine ziemlich schöne ISA.
Luke Hutchison
2
Wenn Sie das Suffix S nicht hinzufügen, können Sie mehrere bedingte Anweisungen hintereinander haben, ohne befürchten zu müssen, dass einer von ihnen die Statusbits ändert, was andernfalls den Nebeneffekt haben könnte, dass der Rest der bedingten Anweisungen übersprungen wird.
Luke Hutchison
Beachten Sie, dass die OP ist nicht die Zeit , auch in ihrer Messung zu sortieren. Es ist wahrscheinlich ein Gesamtverlust, zuerst zu sortieren, bevor eine x86-Zweigschleife ausgeführt wird, obwohl der nicht sortierte Fall die Ausführung der Schleife erheblich verlangsamt. Das Sortieren eines großen Arrays erfordert jedoch viel Arbeit.
Peter Cordes
Übrigens können Sie eine Anweisung in der Schleife speichern, indem Sie sie relativ zum Ende des Arrays indizieren. Richten Sie vor der Schleife ein und R2 = data + arraySizebeginnen Sie mit R1 = -arraySize. Der Boden der Schleife wird adds r1, r1, #1/ bnz inner_loop. Compiler verwenden diese Optimierung aus irgendeinem Grund nicht: / Die prädizierte Ausführung des Add unterscheidet sich in diesem Fall jedoch nicht grundlegend von dem, was Sie mit verzweigtem Code auf anderen ISAs wie x86 tun können cmov. Obwohl es nicht so schön ist: gcc Optimierungsflag -O3 macht Code langsamer als -O2
Peter Cordes
1
(ARM-prädizierte Ausführung führt den Befehl wirklich zu NOPs, sodass Sie ihn im Gegensatz zu x86 cmovmit einem Speicherquellenoperanden sogar für Ladevorgänge oder Speicher verwenden können, die fehlerhaft sind . Die meisten ISAs, einschließlich AArch64, verfügen nur über ALU-Auswahloperationen. Daher kann die ARM-Prädikation leistungsstark sein. und auf den meisten ISAs effizienter als verzweigungsloser Code verwendbar.)
Peter Cordes
146

Es geht um die Vorhersage von Zweigen. Was ist es?

  • Ein Zweigprädiktor ist eine der alten Techniken zur Leistungsverbesserung, die in modernen Architekturen immer noch Relevanz finden. Während die einfachen Vorhersagetechniken eine schnelle Suche und Energieeffizienz bieten, leiden sie unter einer hohen Fehlvorhersagerate.

  • Auf der anderen Seite bieten komplexe Verzweigungsvorhersagen - entweder auf neuronaler Basis oder Varianten der zweistufigen Verzweigungsvorhersage - eine bessere Vorhersagegenauigkeit, verbrauchen jedoch mehr Leistung und die Komplexität nimmt exponentiell zu.

  • Darüber hinaus ist bei komplexen Vorhersagetechniken die Zeit, die zur Vorhersage der Zweige benötigt wird, selbst sehr hoch - im Bereich von 2 bis 5 Zyklen -, was mit der Ausführungszeit der tatsächlichen Zweige vergleichbar ist.

  • Die Verzweigungsvorhersage ist im Wesentlichen ein Optimierungsproblem (Minimierungsproblem), bei dem der Schwerpunkt auf der Erzielung einer möglichst geringen Fehlerrate, eines geringen Stromverbrauchs und einer geringen Komplexität bei minimalen Ressourcen liegt.

Es gibt wirklich drei verschiedene Arten von Zweigen:

Vorwärtsbedingte Verzweigungen - Basierend auf einer Laufzeitbedingung wird der PC (Programmzähler) so geändert, dass er auf eine Adresse zeigt, die im Befehlsstrom weitergeleitet wird.

Rückwärts bedingte Verzweigungen - Der PC wird so geändert, dass er im Befehlsstrom rückwärts zeigt. Die Verzweigung basiert auf einer bestimmten Bedingung, z. B. einer Rückwärtsverzweigung zum Anfang einer Programmschleife, wenn ein Test am Ende der Schleife angibt, dass die Schleife erneut ausgeführt werden soll.

Unbedingte Verzweigungen - Dies umfasst Sprünge, Prozeduraufrufe und Rückgaben ohne bestimmte Bedingung. Beispielsweise kann ein bedingungsloser Sprungbefehl in Assemblersprache einfach als "jmp" codiert werden, und der Befehlsstrom muss sofort zu dem Zielort geleitet werden, auf den der Sprungbefehl zeigt, während ein bedingter Sprung, der als "jmpne" codiert werden kann. würde den Befehlsstrom nur umleiten, wenn das Ergebnis eines Vergleichs von zwei Werten in einem vorherigen "Vergleich" -Anweisungen zeigt, dass die Werte nicht gleich sind. (Das von der x86-Architektur verwendete segmentierte Adressierungsschema erhöht die Komplexität, da Sprünge entweder "nah" (innerhalb eines Segments) oder "fern" (außerhalb des Segments) sein können. Jeder Typ hat unterschiedliche Auswirkungen auf Verzweigungsvorhersagealgorithmen.)

Statische / dynamische Verzweigungsvorhersage : Die statische Verzweigungsvorhersage wird vom Mikroprozessor verwendet, wenn zum ersten Mal eine bedingte Verzweigung auftritt, und die dynamische Verzweigungsvorhersage wird für die erfolgreiche Ausführung des bedingten Verzweigungscodes verwendet.

Verweise:

Farhad
quelle
145

Neben der Tatsache, dass die Verzweigungsvorhersage Sie verlangsamen kann, hat ein sortiertes Array einen weiteren Vorteil:

Sie können eine Stoppbedingung haben, anstatt nur den Wert zu überprüfen. Auf diese Weise durchlaufen Sie nur die relevanten Daten und ignorieren den Rest.
Die Verzweigungsvorhersage wird nur einmal fehlen.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
Yochai Timmer
quelle
1
Richtig, aber die Einrichtungskosten für das Sortieren des Arrays betragen O (N log N). Frühes Brechen hilft Ihnen also nicht, wenn der einzige Grund, warum Sie das Array sortieren, darin besteht, dass Sie früh brechen können. Wenn Sie jedoch andere Gründe haben, das Array vorab zu sortieren, ist dies hilfreich.
Luke Hutchison
Hängt davon ab, wie oft Sie die Daten sortieren und wie oft Sie sie durchlaufen. Die Sortierung in diesem Beispiel ist nur ein Beispiel, es muss nicht kurz vor der Schleife sein
Yochai Timmer
2
Ja, genau das habe ich in meinem ersten Kommentar angesprochen :-) Sie sagen "Die Verzweigungsvorhersage wird nur einmal fehlen." Sie zählen jedoch nicht die O (N log N) -Zweigvorhersagefehler innerhalb des Sortieralgorithmus, der tatsächlich größer ist als die O (N) -Zweigvorhersagefehler im unsortierten Fall. Sie müssten also die Gesamtheit der sortierten Daten O (log N) -Zeiten verwenden, um die Gewinnschwelle zu erreichen (wahrscheinlich tatsächlich näher an O (10 log N), abhängig vom Sortieralgorithmus, z. B. für Quicksort aufgrund von Cache-Fehlern - Mergesort ist cache-kohärenter, so dass Sie näher an O (2 log N) Verwendungen benötigen würden, um die Gewinnschwelle zu erreichen.)
Luke Hutchison
Eine signifikante Optimierung wäre jedoch, nur "eine halbe Quicksortierung" durchzuführen und nur Elemente zu sortieren, die kleiner als der Ziel-Pivot-Wert von 127 sind (vorausgesetzt, alles, was kleiner oder gleich dem Pivot ist, wird nach dem Pivot sortiert). Wenn Sie den Drehpunkt erreicht haben, addieren Sie die Elemente vor dem Drehpunkt. Dies würde in der Startzeit von O (N) und nicht in der Startzeit von O (N log N) ablaufen, obwohl es immer noch viele Fehlvorhersagen geben wird, wahrscheinlich in der Größenordnung von O (5 N), basierend auf den Zahlen, die ich zuvor angegeben habe Es ist eine halbe Quicksort.
Luke Hutchison
132

Sortierte Arrays werden aufgrund eines Phänomens, das als Verzweigungsvorhersage bezeichnet wird, schneller verarbeitet als ein unsortiertes Array.

Der Verzweigungsprädiktor ist eine digitale Schaltung (in der Computerarchitektur), die versucht vorherzusagen, in welche Richtung eine Verzweigung gehen wird, wodurch der Fluss in der Befehlspipeline verbessert wird. Die Schaltung / der Computer sagt den nächsten Schritt voraus und führt ihn aus.

Wenn Sie eine falsche Vorhersage treffen, kehren Sie zum vorherigen Schritt zurück und führen eine andere Vorhersage aus. Unter der Annahme, dass die Vorhersage korrekt ist, fährt der Code mit dem nächsten Schritt fort. Eine falsche Vorhersage führt dazu, dass derselbe Schritt wiederholt wird, bis eine korrekte Vorhersage erfolgt.

Die Antwort auf Ihre Frage ist sehr einfach.

In einem unsortierten Array macht der Computer mehrere Vorhersagen, was zu einer erhöhten Fehlerwahrscheinlichkeit führt. In einem sortierten Array macht der Computer weniger Vorhersagen, wodurch die Wahrscheinlichkeit von Fehlern verringert wird. Mehr Vorhersagen zu treffen erfordert mehr Zeit.

Sortiertes Array: Gerade Straße ____________________________________________________________________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Unsortiertes Array: Kurvenstraße

______   ________
|     |__|

Verzweigungsvorhersage: Erraten / Vorhersagen, welche Straße gerade ist, und Folgen dieser ohne Überprüfung

___________________________________________ Straight road
 |_________________________________________|Longer road

Obwohl beide Straßen dasselbe Ziel erreichen, ist die gerade Straße kürzer und die andere länger. Wenn Sie dann versehentlich den anderen wählen, gibt es kein Zurück mehr, und Sie verschwenden zusätzliche Zeit, wenn Sie die längere Straße wählen. Dies ähnelt dem, was im Computer passiert, und ich hoffe, dies hat Ihnen geholfen, besser zu verstehen.


Auch ich möchte @Simon_Weaver aus den Kommentaren zitieren :

Es macht nicht weniger Vorhersagen - es macht weniger falsche Vorhersagen. Es muss immer noch für jedes Mal durch die Schleife vorhersagen ...

Omkaar.K
quelle
123

Ich habe den gleichen Code mit MATLAB 2011b mit meinem MacBook Pro (Intel i7, 64 Bit, 2,4 GHz) für den folgenden MATLAB-Code ausprobiert:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Die Ergebnisse für den obigen MATLAB-Code sind wie folgt:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Die Ergebnisse des C-Codes wie in @GManNickG bekomme ich:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Basierend darauf sieht es so aus, als ob MATLAB fast 175-mal langsamer als die C-Implementierung ohne Sortierung und 350-mal langsamer mit Sortierung ist. Mit anderen Worten, der Effekt (der Verzweigungsvorhersage) beträgt 1,46x für die MATLAB-Implementierung und 2,7x für die C-Implementierung.

Shan
quelle
7
Der Vollständigkeit halber würden Sie dies wahrscheinlich nicht so in Matlab implementieren. Ich wette, es wäre viel schneller, wenn es nach der Vektorisierung des Problems erledigt wäre.
Ysap
1
Matlab führt in vielen Situationen eine automatische Parallelisierung / Vektorisierung durch. Hier geht es jedoch darum, den Effekt der Verzweigungsvorhersage zu überprüfen. Matlab ist sowieso nicht immun!
Shan
1
Verwendet Matlab native Zahlen oder eine mattenlaborspezifische Implementierung (unendlich viele Ziffern oder so?)
Thorbjørn Ravn Andersen
54

Die Annahme durch andere Antworten, dass man die Daten sortieren muss, ist nicht korrekt.

Der folgende Code sortiert nicht das gesamte Array, sondern nur Segmente mit 200 Elementen und wird dabei am schnellsten ausgeführt.

Das Sortieren nur von k-Element-Abschnitten schließt die Vorverarbeitung in linearer Zeit ab O(n)und nicht in der O(n.log(n))Zeit, die zum Sortieren des gesamten Arrays benötigt wird.

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Dies "beweist" auch, dass es nichts mit einem algorithmischen Problem wie der Sortierreihenfolge zu tun hat, und es ist in der Tat eine Verzweigungsvorhersage.

user2297550
quelle
4
Ich sehe nicht wirklich, wie das etwas beweist? Das einzige, was Sie gezeigt haben, ist, dass "das Sortieren des gesamten Arrays nicht die ganze Arbeit erledigt und weniger Zeit in Anspruch nimmt als das Sortieren des gesamten Arrays". Ihre Behauptung, dass dies "auch am schnellsten läuft", ist sehr architekturabhängig. Siehe meine Antwort dazu, wie dies auf ARM funktioniert. PS: Sie können Ihren Code auf Nicht-ARM-Architekturen beschleunigen, indem Sie die Summierung in die 200-Elemente-Blockschleife einfügen, umgekehrt sortieren und dann Yochai Timmers Vorschlag verwenden, zu brechen, sobald Sie einen Wert außerhalb des Bereichs erhalten. Auf diese Weise kann jede 200-Elemente-Blocksummierung vorzeitig beendet werden.
Luke Hutchison
Wenn Sie den Algorithmus nur effizient über unsortierte Daten implementieren möchten, würden Sie diese Operation verzweigungslos ausführen (und mit SIMD, z. B. mit x86 pcmpgtb, um Elemente mit gesetztem High-Bit zu finden, dann UND auf Null kleinerer Elemente). Es wäre langsamer, Zeit damit zu verbringen, tatsächlich Brocken zu sortieren. Eine verzweigungslose Version hätte eine datenunabhängige Leistung, was auch beweist, dass die Kosten durch eine falsche Vorhersage der Branche entstanden sind. Oder verwenden Sie einfach Leistungsindikatoren, um dies direkt zu beobachten, wie z. B. Skylake, int_misc.clear_resteer_cyclesoder int_misc.recovery_cyclesum Front-End-Leerlaufzyklen von falschen Vorhersagen zu zählen
Peter Cordes,
Beide obigen Kommentare scheinen die allgemeinen algorithmischen Probleme und die Komplexität zu ignorieren, um spezielle Hardware mit speziellen Maschinenanweisungen zu befürworten. Ich finde die erste besonders kleinlich, weil sie die wichtigen allgemeinen Erkenntnisse in dieser Antwort zugunsten blinder Maschinenanweisungen blitzschnell ablehnt.
user2297550
36

Bjarne Stroustrups Antwort auf diese Frage:

Das klingt nach einer Interviewfrage. Ist es wahr? Wie würdest du wissen? Es ist eine schlechte Idee, Fragen zur Effizienz zu beantworten, ohne vorher einige Messungen durchzuführen. Daher ist es wichtig zu wissen, wie man misst.

Also versuchte ich es mit einem Vektor von einer Million Ganzzahlen und bekam:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

Ich habe das ein paar Mal gemacht, um sicher zu sein. Ja, das Phänomen ist real. Mein Schlüsselcode war:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1  t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Zumindest ist das Phänomen bei diesen Einstellungen für Compiler, Standardbibliothek und Optimierer real. Unterschiedliche Implementierungen können und geben unterschiedliche Antworten. Tatsächlich hat jemand eine systematischere Studie durchgeführt (eine schnelle Websuche wird sie finden), und die meisten Implementierungen zeigen diesen Effekt.

Ein Grund ist die Verzweigungsvorhersage: Die Schlüsseloperation im Sortieralgorithmus ist “if(v[i] < pivot]) …” oder äquivalent. Für eine sortierte Sequenz ist dieser Test immer wahr, während für eine zufällige Sequenz der ausgewählte Zweig zufällig variiert.

Ein weiterer Grund ist, dass wir, wenn der Vektor bereits sortiert ist, Elemente niemals an ihre richtige Position verschieben müssen. Die Wirkung dieser kleinen Details ist der Faktor fünf oder sechs, den wir gesehen haben.

Quicksort (und Sortieren im Allgemeinen) ist eine komplexe Studie, die einige der größten Köpfe der Informatik angezogen hat. Eine gute Sortierfunktion ergibt sich sowohl aus der Auswahl eines guten Algorithmus als auch aus der Berücksichtigung der Hardwareleistung bei seiner Implementierung.

Wenn Sie effizienten Code schreiben möchten, müssen Sie etwas über die Maschinenarchitektur wissen.

Selcuk
quelle
28

Diese Frage basiert auf Branch Prediction Models auf CPUs. Ich würde empfehlen, dieses Papier zu lesen:

Erhöhen der Befehlsabrufrate über die Vorhersage mehrerer Zweige und einen Zweigadressen-Cache

Wenn Sie Elemente sortiert haben, konnte IR nicht die Mühe machen, alle CPU-Anweisungen immer wieder abzurufen. Es ruft sie aus dem Cache ab.

hatirlatici
quelle
Die Anweisungen bleiben ungeachtet falscher Vorhersagen im L1-Anweisungscache der CPU heiß. Das Problem besteht darin, sie in der richtigen Reihenfolge in die Pipeline zu holen , bevor die unmittelbar vorherigen Anweisungen dekodiert und ausgeführt wurden.
Peter Cordes
15

Eine Möglichkeit, Verzweigungsvorhersagefehler zu vermeiden, besteht darin, eine Nachschlagetabelle zu erstellen und diese anhand der Daten zu indizieren. Stefan de Bruijn hat das in seiner Antwort besprochen.

In diesem Fall wissen wir jedoch, dass die Werte im Bereich [0, 255] liegen, und wir kümmern uns nur um Werte> = 128. Das bedeutet, dass wir leicht ein einzelnes Bit extrahieren können, das uns sagt, ob wir einen Wert wollen oder nicht: durch Verschieben Bei den Daten rechts von 7 Bits bleibt ein 0-Bit oder ein 1-Bit übrig, und wir möchten den Wert nur hinzufügen, wenn wir ein 1-Bit haben. Nennen wir dieses Bit das "Entscheidungsbit".

Indem wir den 0/1-Wert des Entscheidungsbits als Index für ein Array verwenden, können wir Code erstellen, der gleich schnell ist, unabhängig davon, ob die Daten sortiert sind oder nicht. Unser Code fügt immer einen Wert hinzu, aber wenn das Entscheidungsbit 0 ist, fügen wir den Wert an einer Stelle hinzu, die uns egal ist. Hier ist der Code:

// Prüfung

clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Dieser Code verschwendet die Hälfte der Adds, hat jedoch nie einen Fehler bei der Verzweigungsvorhersage. Bei zufälligen Daten ist es enorm schneller als bei der Version mit einer tatsächlichen if-Anweisung.

In meinen Tests war eine explizite Nachschlagetabelle jedoch etwas schneller als diese, wahrscheinlich weil die Indizierung in eine Nachschlagetabelle etwas schneller war als die Bitverschiebung. Dies zeigt, wie mein Code die Nachschlagetabelle einrichtet und verwendet (im Code einfallslos lut für "LookUp Table" genannt). Hier ist der C ++ - Code:

// Deklariere und fülle dann die Nachschlagetabelle aus

int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

In diesem Fall war die Nachschlagetabelle nur 256 Byte groß, passt also gut in einen Cache und alles war schnell. Diese Technik würde nicht gut funktionieren, wenn die Daten 24-Bit-Werte wären und wir nur die Hälfte davon wollten ... die Nachschlagetabelle wäre viel zu groß, um praktisch zu sein. Auf der anderen Seite können wir die beiden oben gezeigten Techniken kombinieren: Verschieben Sie zuerst die Bits und indizieren Sie dann eine Nachschlagetabelle. Für einen 24-Bit-Wert, für den wir nur den Wert der oberen Hälfte wünschen, können wir die Daten möglicherweise um 12 Bit nach rechts verschieben und einen 12-Bit-Wert für einen Tabellenindex erhalten. Ein 12-Bit-Tabellenindex impliziert eine Tabelle mit 4096 Werten, was praktisch sein kann.

Die Technik der Indizierung in ein Array anstelle einer if-Anweisung kann verwendet werden, um zu entscheiden, welcher Zeiger verwendet werden soll. Ich sah eine Bibliothek, die Binärbäume implementierte, und anstatt zwei benannte Zeiger (pLeft und pRight oder was auch immer) zu haben, hatte ich ein Array von Zeigern der Länge 2 und verwendete die "Entscheidungsbit" -Technik, um zu entscheiden, welchem ​​ich folgen sollte. Zum Beispiel anstelle von:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

i = (x < node->value);
node = node->link[i];

Es ist eine schöne Lösung, vielleicht funktioniert es

Manoj Kashyam
quelle
Mit welchem ​​C ++ - Compiler / welcher Hardware haben Sie dies getestet und mit welchen Compileroptionen? Ich bin überrascht, dass die Originalversion nicht automatisch zu einem schönen verzweigungslosen SIMD-Code vektorisiert wurde. Haben Sie die vollständige Optimierung aktiviert?
Peter Cordes
Eine 4096-Eintrags-Nachschlagetabelle klingt verrückt. Wenn Sie herauszuschieben alle Bits, müssen Sie nicht können nur die LUT Ergebnis verwenden , wenn Sie die Zahl wieder hinzufügen möchten. Dies alles klingt nach albernen Tricks, um Ihren Compiler nicht einfach mit verzweigungslosen Techniken zu umgehen. Einfacher wäre mask = tmp < 128 : 0 : -1UL;/total += tmp & mask;
Peter Cordes