java Warum kann ein sortiertes Array schneller verarbeitet werden als ein unsortiertes Array?



10 Answers

Zweigvorhersage

Bei einem sortierten Array sind die Bedingungsdaten data[c] >= 128 für eine Reihe von Werten zuerst false , dann true für alle späteren Werte. Das lässt sich leicht vorhersagen. Mit einem unsortierten Array bezahlen Sie die Verzweigungskosten.

java c++ performance optimization branch-prediction

Hier ist ein Stück C ++ - Code, das sehr eigenartig erscheint. 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 Anomalie der Sprache oder des Compilers sein. Also habe ich es in 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 etwas ä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 ist, weil das Array gerade erzeugt wurde.

  • Was ist los?
  • Warum kann ein sortiertes Array schneller verarbeitet werden als ein unsortiertes Array?
  • Der Code fasst einige unabhängige Begriffe zusammen und die Reihenfolge sollte keine Rolle spielen.



Wenn Sie sich für weitere Optimierungen interessieren, die mit diesem Code durchgeführt werden können, beachten Sie Folgendes:

Beginnend mit der Originalschleife:

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

Mit dem Loop-Austausch 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 if Bedingung während der Ausführung der i Schleife konstant ist. Sie können also die if Bedingung anheben:

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 reduziert werden kann, vorausgesetzt, das Gleitkommamodell lässt es zu (z. B. / fp: fast wird geworfen).

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

Dieser ist 100.000x schneller als zuvor




Ich lese gerade über diese Frage und ihre Antworten nach, und ich habe das Gefühl, dass eine Antwort fehlt.

Eine gängige Methode, um die Verzweigungsvoraussage zu beseitigen, die ich in verwalteten Sprachen als besonders gut empfunden habe, ist das Nachschlagen in einer Tabelle, anstatt eine Verzweigung zu verwenden (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 Dinge in einer ziemlich engen Schleife aus und / oder der Prozessor kann die Daten vorladen

Hintergrund und warum

Pfew, was soll das denn heißen?

Aus Prozessorsicht ist Ihr Gedächtnis langsam. Um den Geschwindigkeitsunterschied auszugleichen, bauen sie einige Caches in Ihrem Prozessor (L1 / L2-Cache) auf, die dies ausgleichen. Stellen Sie sich vor, Sie machen Ihre schönen Berechnungen und finden heraus, dass Sie ein Stück Speicher benötigen. Der Prozessor erhält seine Ladeoperation und lädt den Speicher in den Cache - und verwendet dann den Cache für die restlichen Berechnungen. Da der Speicher relativ langsam ist, verlangsamt dieses "Laden" Ihr Programm.

Wie die Verzweigungsvorhersage wurde dies in den Pentium-Prozessoren optimiert: Der Prozessor sagt voraus, dass er Daten laden muss, und versucht, diese Daten in den Cache zu laden, bevor die Operation tatsächlich den Cache erreicht. Wie wir bereits gesehen haben, läuft die Verzweigungsvorhersage manchmal furchtbar falsch - im schlimmsten Fall müssen Sie zurückgehen und tatsächlich auf einen Speicher warten, der für immer dauern wird ( mit anderen Worten: Das Versagen der Verzweigungsvorhersage ist schlecht, ein Speicher.) Laden nach einem Verzweigungsvorhersageschaden ist einfach schrecklich! ).

Wenn das Speicherzugriffsmuster vorhersagbar ist, lädt der Prozessor es in seinem schnellen Cache, und alles ist gut.

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

Einen Tisch bauen

Wir haben also herausgefunden, dass wir eine kleine Tabelle erstellen können. Als nächstes müssen Sie eine Lookup-Funktion einrichten. Suchfunktionen sind in der Regel kleine Funktionen, die ein paar grundlegende Ganzzahloperationen verwenden (und xor, shift, add, remove und vielleicht multiplizieren). Sie möchten, dass Ihre Eingabe durch die Nachschlagefunktion in eine Art "eindeutiger Schlüssel" in Ihrer Tabelle übersetzt wird, der Ihnen dann einfach die Antwort auf die Arbeit gibt, die Sie wollten.

In diesem Fall:> = 128 bedeutet, dass wir den Wert beibehalten können, <128 bedeutet, dass wir ihn loswerden. Der einfachste Weg, dies zu tun, ist die Verwendung eines 'UND': Wenn wir es behalten, UND wir 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 fortfahren und eine Tabelle mit 32768/128 Ganzzahlen erstellen und diese mit einer Null und viel füllen 7FFFFFFFF's.

Verwaltete Sprachen

Sie fragen sich vielleicht, warum dies in verwalteten Sprachen gut funktioniert. Immerhin prüfen verwaltete Sprachen die Grenzen der Arrays mit einer Verzweigung, um sicherzustellen, dass Sie nichts versauen ...

Na ja, nicht genau ... :-)

Es wurde bereits viel Arbeit geleistet, um diesen Zweig für verwaltete Sprachen zu beseitigen. 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 erfüllt wird. Zumindest wird der Microsoft-JIT-Compiler (dies wird jedoch mit Java vergleichbar sein) dies bemerken und die Prüfung vollständig entfernen. WOW - das bedeutet keine Branche. Ähnlich wird es sich mit anderen offensichtlichen Fällen befassen.

Wenn bei der Suche nach verwalteten Sprachen Probleme auftreten, müssen Sie der Suchfunktion eine & 0x[something]FFF hinzufügen, um die Begrenzungsprüfung vorhersehbar zu machen - und beobachten, wie sie schneller läuft.

Das Ergebnis dieses Falls

// 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.Next(256);

//To keep the spirit of the code in-tact 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();



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

In diesem Fall wissen wir jedoch, dass 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 7 Bits verbleiben ein 0-Bit oder ein 1-Bit, und wir möchten den Wert nur hinzufügen, wenn wir ein 1-Bit haben. Nennen wir dieses Bit das "Entscheidungsbit".

Durch Verwendung des 0/1-Werts des Entscheidungsbits als Index in einem Array 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, an der wir uns nicht interessieren. 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 Additionen, hat jedoch nie einen Verzweigungsvorhersagefehler. Es ist bei zufälligen Daten enorm schneller als bei der Version mit einer tatsächlichen if-Anweisung.

In meinen Tests war eine explizite Nachschlagetabelle etwas schneller als diese, wahrscheinlich, weil die Indizierung in eine Nachschlagetabelle etwas schneller war als die Bitverschiebung. Dies zeigt, wie mein Code die Lookup-Tabelle lutaufbaut und verwendet ( unimaginativ für "LookUp Table" im Code aufgerufen ). 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 hatte die Lookup-Tabelle nur 256 Byte, sodass sie gut in einen Cache passt und alles schnell war. Diese Technik würde nicht gut funktionieren, wenn die Daten 24-Bit-Werte hätten und wir nur die Hälfte davon wollten ... Die Nachschlagetabelle wäre viel zu groß, um praktisch zu sein. Andererseits können wir die beiden oben gezeigten Techniken kombinieren: Zuerst die Bits verschieben und dann eine Nachschlagetabelle indizieren. Bei einem 24-Bit-Wert, bei dem nur der obere Halbwert gewünscht wird, können wir die Daten möglicherweise um 12 Bit nach rechts verschieben und einen 12-Bit-Wert für einen Tabellenindex belassen. Ein 12-Bit-Tabellenindex impliziert eine Tabelle mit 4096 Werten, was praktisch sein kann.

EDIT: Eine Sache, die ich vergessen habe.

Anstatt eine ifAnweisung zu verwenden, kann die Technik des Indexierens in ein Array verwendet werden, um zu entscheiden, welcher Zeiger verwendet werden soll. Ich sah eine Bibliothek , die binären Bäume umgesetzt und anstelle von zwei genannten Zeigern mit ( pLeftund pRightoder was auch immer) hatte eine Länge-2 Array von Zeigern und verwendet , um die „Entscheidungs - Bit - Technik“ zu entscheiden , welches zu folgen. Zum Beispiel anstelle von:

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

Diese Bibliothek würde so etwas tun:

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

Hier ist ein Link zu diesem Code: Red Black Trees , ewig verwirrt




Das obige Verhalten geschieht aufgrund der Verzweigungsvorhersage.

Um die Verzweigungsvorhersage zu verstehen, muss man zunächst die Anweisungs-Pipeline verstehen :

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

Im Allgemeinen verfügen moderne Prozessoren über recht lange Pipelines, aber zur Vereinfachung betrachten wir nur diese 4 Schritte.

  1. IF - Den Befehl aus dem Speicher abrufen
  2. ID - Dekodiert die Anweisung
  3. EX - Führen Sie die Anweisung aus
  4. WB - Zurückschreiben in das CPU-Register

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

Um auf die obige Frage zurückzukommen, 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 die Anweisung B oder die Anweisung C auszuführen, muss der Prozessor warten, bis die Anweisung A nicht bis zur EX-Stufe in der Pipeline erreicht ist, da die Entscheidung, zur Anweisung B oder zur Anweisung C zu gehen, vom Ergebnis der Anweisung A abhängt. Also die Pipeline wird so aussehen.

Wenn die Bedingung wahr ist:

Wenn if-Bedingung falsch ist:

Als Ergebnis des Wartens auf das Ergebnis von Befehl A betragen die gesamten CPU-Zyklen, die in dem obigen Fall (ohne Verzweigungsvorhersage; sowohl für wahr als auch für falsch) ausgegeben wurden, 7.

Was ist also eine Branchenvorhersage?

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

Bei einer korrekten Annahme sieht die Pipeline etwa so aus:

Wenn später erkannt wird, dass die Vermutung falsch war, werden die teilweise ausgeführten Anweisungen verworfen und die Pipeline beginnt mit dem korrekten Zweig erneut, was zu einer Verzögerung führt. Die Zeit, die im Falle einer Verzweigungsfehlvorhersage vergeudet wird, ist gleich der Anzahl von Stufen in der Pipeline von der Abrufstufe bis zur Ausführungsstufe. Moderne Mikroprozessoren neigen dazu, ziemlich lange Pipelines zu haben, so dass die Verzögerung der Fehlvorhersage zwischen 10 und 20 Taktzyklen liegt. Je länger die Pipeline ist, desto größer ist der Bedarf an einem guten Branch-Prädiktor .

Im OP-Code hat der Verzweigungsvorhersager zum ersten Mal, wenn die Bedingung vorliegt, keine Informationen, um die Vorhersage zu begründen, so dass er beim ersten Mal zufällig die nächste Anweisung wählt. Später in der for-Schleife kann die Vorhersage auf der Historie basieren. Für ein Array, das aufsteigend sortiert ist, gibt es drei Möglichkeiten:

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

Nehmen wir an, der Prädiktor nimmt beim ersten Durchlauf immer den wahren Zweig an.

Im ersten Fall wird also immer der wahre Zweig verwendet, da historisch alle seine Vorhersagen korrekt sind. Im zweiten Fall wird es zunächst falsch vorhersagen, aber nach einigen Iterationen wird es richtig vorhersagen. Im dritten Fall wird es zunächst korrekt vorhergesagt, bis die Elemente weniger als 128 sind. Danach wird es für einige Zeit ausfallen, und die Korrektur selbst wird ausgeführt, wenn ein Verzweigungsvorhersagefehler in der Historie auftritt.

In all diesen Fällen ist die Anzahl der Fehler zu gering und daher müssen die teilweise ausgeführten Anweisungen nur ein paar Mal verworfen und mit dem richtigen Zweig neu gestartet werden, was zu weniger CPU-Zyklen führt.

Im Falle eines zufälligen unsortierten Arrays muss die Vorhersage jedoch die teilweise ausgeführten Anweisungen verwerfen und die meiste Zeit mit dem richtigen Zweig beginnen und im Vergleich zu dem sortierten Array mehr CPU-Zyklen bewirken.




In derselben Zeile (ich denke, dass dies in keiner Antwort hervorgehoben wurde) ist es gut zu erwähnen, dass manchmal (besonders bei Software, bei der die Leistung von Bedeutung ist - wie im Linux-Kernel) - einige if-Anweisungen wie die folgenden vorkommen:

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

oder ähnlich:

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

Sowohl likely()und unlikely()sind in der Tat Makros, die mit so etwas wie die GCC definiert sind , __builtin_expectden Compiler Einsatz Vorhersage Code , um die Bedingung unter Berücksichtigung der Informationen , die vom Benutzer zur Verfügung gestellt zu begünstigen. GCC unterstützt andere integrierte Programme, die das Verhalten des laufenden Programms ändern oder Low-Level-Anweisungen wie Löschen des Cache usw. ausgeben können. Weitere Informationen finden Sie in dieser Dokumentation zu den verfügbaren integrierten GCC-Komponenten.

Normalerweise findet man diese Art von Optimierungen hauptsächlich in Echtzeitanwendungen oder eingebetteten Systemen, bei denen die Ausführungszeit von Bedeutung ist. Wenn Sie beispielsweise nach einer Fehlerbedingung suchen, die nur 1/10000000 mal auftritt, sollten Sie den Compiler dann darüber informieren. Auf diese Weise würde die Verzweigungsvorhersage standardmäßig annehmen, dass die Bedingung falsch ist.




Das ist sicher!...

Durch die Verzweigungsvorhersage wird die Logik langsamer ausgeführt, da in Ihrem Code eine Umschaltung erfolgt! Es ist, als würden Sie eine gerade Straße oder eine Straße mit vielen Abbiegungen gehen. Die gerade Straße wird sicher schneller gemacht! ...

Wenn das Array sortiert ist, ist Ihre Bedingung im ersten Schritt falsch: data[c] >= 128und wird dann für den gesamten Weg bis zum Ende der Straße ein wahrer Wert. So kommen Sie schneller ans Ende der Logik. Auf der anderen Seite, wenn Sie ein unsortiertes Array verwenden, müssen Sie viel drehen und bearbeiten, wodurch Ihr Code sicher langsamer läuft ...

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

So programmgesteuert bewirkt die Verzweigungsvorhersage, dass der Prozess langsamer wird ...

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

1. Statisch

2. Dynamisch

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, um diese Regeln zu nutzen, sollten Sie beim Schreiben von if-else- oder switch- Anweisungen zuerst die häufigsten Fälle prüfen und schrittweise auf die wenigsten Fälle zurückgreifen. Schleifen erfordern nicht unbedingt eine spezielle Code-Reihenfolge für die statische Verzweigungsvorhersage, da normalerweise nur der Zustand des Schleifeniterators verwendet wird.




Verzweigungsvorhersage Gewinn!

Es ist wichtig zu verstehen, dass die Fehlvorhersage der Branche die Programme nicht verlangsamt. Die Kosten einer verpassten Vorhersage sind genau 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äuterung im nächsten Absatz).

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

Bei einer if-else\ switch-Anweisung muss der Ausdruck ausgewertet werden, um zu bestimmen, welcher Block ausgeführt werden soll. In dem vom Compiler generierten Assemblycode werden bedingte branch eingefügt.

Eine Verzweigungsanweisung kann dazu führen, dass ein Computer mit der Ausführung einer anderen Befehlssequenz beginnt und somit von seinem Standardverhalten der Ausführung von Anweisungen 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.

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

Visualisierung:

Nehmen wir an, Sie müssen die Route 1 oder die Route 2 auswählen. Wenn Sie darauf warten, dass Ihr Partner die Karte überprüft, haben Sie um ## angehalten und gewartet oder Sie könnten nur die Route 1 auswählen und wenn Sie Glück hatten (Route 1 ist die richtige Route), Dann müssen Sie nicht warten, bis Ihr Partner die Karte überprüft hat (Sie haben die Zeit gespart, die er für die Überprüfung der Karte benötigt hätte), andernfalls kehren Sie einfach zurück.

Während das Spülen von Pipelines superschnell ist, lohnt es sich heutzutage, dieses Spiel zu nehmen. Die Vorhersage von sortierten Daten oder von Daten, die sich langsam ändern, ist immer einfacher und besser als das Vorhersagen schneller Änderungen.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------



Es geht um die Vorhersage der Branche. Was ist es?

  • Ein Zweigprädiktor ist eine der alten Techniken zur Verbesserung der Leistung, die für moderne Architekturen noch relevant ist. Während die einfachen Vorhersagetechniken für eine schnelle Suche und Leistungseffizienz sorgen, leiden sie unter einer hohen Fehlvorhersagerate.

  • Auf der anderen Seite bieten komplexe Verzweigungsvorhersagen - entweder auf neuronaler Basis oder auf zwei Ebenen basierende Verzweigungsvorhersagen - eine bessere Vorhersagegenauigkeit, verbrauchen jedoch mehr Leistung und die Komplexität steigt exponentiell an.

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

  • Die Verzweigungsvorhersage ist im Wesentlichen ein Optimierungs- (Minimierungs-) Problem, bei dem es darauf ankommt, eine möglichst geringe Fehlrate, einen geringen Stromverbrauch und eine geringe Komplexität mit minimalen Ressourcen zu erreichen.

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 hinweist, die im Befehlsstrom vorwärts gerichtet ist.

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. dem Verzweigen zum Beginn einer Programmschleife, wenn bei einem Test am Ende der Schleife die Schleife erneut ausgeführt werden soll.

Unbedingte Verzweigungen - Dies umfasst Sprünge, Prozeduraufrufe und Rückgaben, die keine bestimmten Bedingungen haben. Beispielsweise kann eine unbedingte Sprunganweisung in der Assembler-Sprache einfach als "jmp" codiert sein, und der Befehlsstrom muss sofort an den Zielort geleitet werden, auf den die Sprunganweisung zeigt, wohingegen ein bedingter Sprung, der als "jmpne" codiert sein könnte. würde den Befehlsstrom nur umleiten, wenn das Ergebnis eines Vergleichs zweier Werte in einer vorherigen "Compare" - Anweisung zeigt, dass die Werte nicht gleich sind. (Das von der x86-Architektur verwendete segmentierte Adressierungsschema erhöht die Komplexität, da Sprünge entweder "in der Nähe" (innerhalb eines Segments) oder "weit" (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 nachfolgende Ausführungen des bedingten Verzweigungscodes verwendet.

Verweise:




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

Sie können eine Stop-Bedingung haben, anstatt nur den Wert zu überprüfen. Auf diese Weise können Sie nur die relevanten Daten durchlaufen und den Rest ignorieren.
Die Zweigvorhersage wird nur einmal verfehlt.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }





Related