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

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.

Sie sind ein Opfer des Fehlschlags der Zweigvorhersage.

Was ist Zweigvorhersage?

Betrachten Sie 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:

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

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.

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.

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.

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 .

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

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!

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

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) :-)

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.

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:

Wann, wenn die Bedingung false zurückgibt:

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:

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.

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.

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.

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.

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

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?

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

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.

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

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

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.

Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

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

Es dauert 7 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

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

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

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  \--------------------------------

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.

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:

• Verzweigungsprädiktor

• Eine Demonstration der Selbstprofilierung

• Überprüfung der Zweigvorhersage

• Verzweigungsvorhersage

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];               
 }

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

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.

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.

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.

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.

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