Frage Warum ist es schneller, ein sortiertes Array als ein unsortiertes Array zu verarbeiten?


Hier ist ein Stück C ++ - Code, der sehr merkwürdig 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);, der Code läuft 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 es in Java versucht.

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

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

21647
2018-06-27 13:51


Ursprung


Antworten:


Du bist ein Opfer von Verzweigungsvorhersage Scheitern.


Was ist Branchennachfrage?

Betrachten Sie einen Eisenbahnknotenpunkt:

Licensed Image Bild von Mecanismo, über Wikimedia Commons. Verwendet unter der CC-Von-SA 3.0 Lizenz.

Nehmen wir nun an, dass dies in den 1800er Jahren der Fall ist - vor der Fern- oder Funkkommunikation.

Sie sind der Betreiber einer Kreuzung und Sie hören einen Zug kommen. Du hast keine Ahnung, wohin es gehen soll. Sie stoppen den Zug, um den Fahrer zu fragen, welche Richtung er möchte. Und dann stellst du den Schalter entsprechend ein.

Die Züge sind schwer und haben eine große Trägheit. Es dauert also ewig, um zu starten und zu verlangsamen.

Gibt es einen besseren Weg? Sie raten, in welche Richtung der Zug fährt!

  • Wenn Sie richtig geraten haben, geht es weiter.
  • Wenn Sie falsch geraten haben, wird der Captain anhalten, zurück gehen und Sie anschreien, den Schalter umzuschalten. Dann kann es den anderen Pfad neu starten.

Wenn Sie jedes Mal richtig ratenDer Zug wird niemals anhalten müssen.
Wenn Sie zu oft falsch geratenDer Zug wird viel Zeit damit verbringen, anzuhalten, zu sichern und neu zu starten.


Betrachten Sie eine if-Anweisung: Auf der Prozessor-Ebene handelt es sich um eine Verzweigungsinstruktion:

image2

Sie sind ein Prozessor und Sie sehen einen Zweig. Du hast keine Ahnung, wohin es gehen wird. Wie geht's? Sie stoppen die Ausführung und warten, bis die vorherigen Anweisungen abgeschlossen sind. Dann gehst du den richtigen Weg weiter.

Moderne Prozessoren sind kompliziert und haben lange Pipelines. So dauert es ewig, bis sie sich "aufwärmen" und "verlangsamen".

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 zurück zum Zweig rollen. Dann können Sie den anderen Pfad neu starten.

Wenn Sie jedes Mal richtig ratenDie Ausführung wird niemals aufhören müssen.
Wenn Sie zu oft falsch geratenSie verbringen viel Zeit damit, abzuwürgen, zurückzurollen und neu zu starten.


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

Wie würdest du strategisch raten, um die Anzahl der Fahrten zu minimieren, die der Zug zurücklegen muss? Du schaust auf die Vergangenheit! Wenn der Zug 99% der Zeit nach links fährt, dann raten Sie links. Wenn es sich ändert, wechseln Sie Ihre Vermutungen ab. Wenn es alle 3 Male in eine Richtung geht, erraten Sie dasselbe ...

Mit anderen Worten, Sie versuchen ein Muster zu identifizieren und folgen ihm. Dies ist mehr oder weniger wie Branch Prädiktoren arbeiten.

Die meisten Anwendungen haben gut benannte Zweige. Moderne Branch Prädiktoren erreichen daher typischerweise Trefferquoten von> 90%. Bei unvorhersehbaren Verzweigungen ohne erkennbare Muster sind Branch Prädiktoren praktisch nutzlos.

Weiterführende Literatur: "Branch Prädiktor" Artikel auf Wikipedia.


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

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

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

Dies ist sehr freundlich zum Verzweigungsprädiktor, da die Verzweigung aufeinanderfolgend mehrmals in dieselbe Richtung geht. Selbst ein einfacher sättigender Zähler wird den Zweig mit Ausnahme der wenigen Iterationen, nachdem er die Richtung wechselt, korrekt vorhersagen.

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 Verzweigungsvorhersager unbrauchbar, da er keine Zufallsdaten vorhersagen kann. Somit wird es wahrscheinlich 50% Fehleinschätzung geben. (nicht besser als Zufallsraten)

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 die Verzweigung nicht in eine bedingte Bewegung 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 beseitigt die Verzweigung und ersetzt sie durch einige bitweise Operationen.

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

Benchmarks: Core i7 920 bei 3,5 GHz

C ++ - Visual Studio 2010 - x 64-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 Filiale: Es gibt einen großen Unterschied zwischen den sortierten und unsortierten Daten.
  • Mit dem Hack: Es gibt keinen Unterschied zwischen sortierten und unsortierten Daten.
  • Im C ++ - Fall ist der Hack bei der Sortierung etwas langsamer als bei der Verzweigung.

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


Aktualisieren:

  • GCC 4.6.1 mit -O3 oder -ftree-vectorize Auf x64 kann eine bedingte Bewegung erzeugt werden. Es gibt also keinen Unterschied zwischen den sortierten und unsortierten Daten - beide sind schnell.

  • VC ++ 2010 kann keine bedingten Verschiebungen für diese Verzweigung generieren, auch nicht unter /Ox.

  • Intel Compiler 11 tut etwas Wunderbares. Es tauscht die zwei Schleifen ausund dadurch den unberechenbaren Zweig zur äußeren Schleife hochziehen. Es ist also nicht nur immun gegen Fehleinschätzungen, es ist auch doppelt so schnell wie alles, was VC ++ und GCC erzeugen können! Mit anderen Worten, ICC nutzte den Test-Loop, um den Benchmark zu besiegen ...

  • Wenn Sie dem Intel Compiler den Branchless-Code geben, vektorisiert er ihn einfach ... und ist genauso schnell wie mit der Verzweigung (mit dem Loop-Austausch).

Dies zeigt, dass selbst erfahrene, moderne Compiler sehr unterschiedlich in ihrer Fähigkeit sind, Code zu optimieren ...


28564
2018-06-27 13:56



Verzweigungsvorhersage

Bei einem sortierten Array die Bedingung data[c] >= 128 ist zuerst false für einen Streak von Werten, dann wird true für alle späteren Werte. Das ist leicht vorherzusagen. Bei einem unsortierten Array bezahlen Sie die Verzweigungskosten.


3635
2018-06-27 13:54



Der Grund, warum sich die Leistung beim Sortieren der Daten drastisch verbessert, liegt darin, dass der Strafschaden für die Verzweigungsvorhersage entfernt wird, wie in Mystik's Antwort.

Nun, wenn wir uns den Code anschauen

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

wir können das die Bedeutung dieses Besonderen finden if... else... Zweig ist etwas hinzuzufügen, wenn eine Bedingung erfüllt ist. Diese Art der Verzweigung kann leicht in eine umgewandelt werden bedingter Umzug Anweisung, die in eine bedingte Move-Anweisung kompiliert würde: cmovl, in einem (n x86 System. Die Verzweigung und somit die potentielle Verzweigungsvorhersage-Strafe wird entfernt.

Im Cso C++, die Anweisung, die direkt (ohne jegliche Optimierung) in den bedingten Verschiebebefehl in kompilieren würde x86, ist der ternäre Operator ... ? ... : .... Also schreiben wir die obige Aussage in eine äquivalente um:

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

Während die Lesbarkeit erhalten bleibt, können wir den Beschleunigungsfaktor überprüfen.

Auf einem Intel Kern i7-2600K @ 3,4 GHz und Visual Studio 2010 Release-Modus, der Benchmark ist (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 bekommen eine große Beschleunigung, wenn das Verzweigungsergebnis unvorhersehbar ist, aber wir leiden ein wenig, wenn es vorhersehbar ist. Bei einer bedingten Bewegung ist die Leistung unabhängig vom Datenmuster gleich.

Jetzt schauen wir uns genauer an, indem wir die x86 Montage erzeugen sie. Der Einfachheit halber verwenden wir zwei Funktionen max1 und max2.

max1 verwendet die bedingte Verzweigung if... else ...:

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

max2 verwendet den ternären Operator ... ? ... : ...:

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

Auf einer x86-64-Maschine GCC -S generiert die Baugruppe unten.

: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

max2 verwendet viel weniger Code aufgrund der Verwendung von Anweisungen cmovge. Aber der wahre Gewinn ist das max2 beinhaltet keine Verzweigungssprünge, jmp, die eine erhebliche Leistungseinbuße haben würde, wenn das vorhergesagte Ergebnis nicht richtig ist.

Warum funktioniert eine bedingte Bewegung besser?

In einem typischen x86 Prozessor ist die Ausführung eines Befehls in mehrere Stufen unterteilt. Grob haben wir unterschiedliche Hardware, um mit verschiedenen Stufen umzugehen. Wir müssen also nicht auf eine Anweisung warten, um einen neuen zu beginnen. Das nennt man Pipelining.

In einem Verzweigungsfall wird der folgende Befehl durch den vorhergehenden bestimmt, so dass wir kein Pipelining durchführen können. Wir müssen entweder warten oder vorhersagen.

In einem bedingten Bewegungsfall ist der Ausführungsbedingungs-Bewegungsbefehl in mehrere Stufen unterteilt, aber die früheren Stufen mögen Fetch und Decode hängt nicht vom Ergebnis der vorherigen Anweisung ab; nur die letzten Stufen brauchen das Ergebnis. Daher warten wir einen Bruchteil der Ausführungszeit einer Anweisung ab. Aus diesem Grund ist die Version mit bedingter Verschiebung langsamer als die Verzweigung, wenn die Vorhersage einfach ist.

Das Buch Computersysteme: Eine Perspektive des Programmierers, zweite Ausgabe erklärt das im Detail. Sie können Abschnitt 3.6.6 nachsehen Anweisungen zum bedingten Verschieben, ganzes Kapitel 4 für Prozessor Architekturund Abschnitt 5.11.2 für eine spezielle Behandlung für Branch Prediction und Misprediction Strafen.

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


2958
2018-06-28 02:14



Wenn Sie noch mehr Optimierungen für diesen Code wünschen, 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 Loop-Austausch können wir diese Schleife sicher zu:

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 conditional ist während der gesamten Ausführung konstant i Schleife, so können Sie die hissen if aus:

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

Dann können Sie sehen, dass die innere Schleife zu einem einzigen Ausdruck zusammengefasst werden kann, vorausgesetzt, dass das Fließkommamodell dies zulässt (/ fp: fast wird zum Beispiel geworfen).

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

Dieser ist 100.000 mal schneller als zuvor


2024
2017-07-03 02:25



Zweifellos würden einige von uns daran interessiert sein, Code zu identifizieren, der für den Verzweigungsprädiktor der CPU problematisch ist. Das Valgrind-Werkzeug cachegrind hat einen Verzweigungs-Prädiktor-Simulator, der durch Verwendung des --branch-sim=yes Flagge. Führen Sie es über die Beispiele in dieser Frage, mit der Anzahl der äußeren Schleifen auf 10000 reduziert und kompiliert mit g++, gibt diese 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%   )

Drilldown in die Zeile für Zeile produziert von cg_annotate wir sehen für die Schleife in Frage:

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

Damit können Sie die problematische Zeile leicht identifizieren - in der unsortierten Version der if (data[c] >= 128) Linie verursacht 164.050.007 falsch vorhergesagte bedingte Verzweigungen (Bcm) unter dem Branch-Prädiktor-Modell von cachegrind, während es in der sortierten Version nur 10.006 verursacht.


Alternativ können Sie unter Linux das Leistungsindikator-Subsystem verwenden, um die gleiche Aufgabe auszuführen, jedoch mit nativer Leistung unter Verwendung von CPU-Zählern.

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 Quelltext-Annotation mit Disassembly 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)
...

Sehen das Performance-Tutorial für mehr Details.


1687
2017-10-12 05:53



Ich lese gerade diese Frage und ihre Antworten auf, und ich fühle, dass eine Antwort fehlt.

Eine gängige Methode zur Beseitigung der Verzweigungsvorhersage, die in verwalteten Sprachen besonders gut funktioniert, ist eine Tabellensuche, 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 laufen Dinge in einer ziemlich engen Schleife und / oder der Prozessor kann die Daten vorladen

Hintergrund und warum

Pfau, was soll das denn bedeuten?

Aus Prozessorsicht ist Ihr Speicher langsam. Um den Unterschied in der Geschwindigkeit auszugleichen, bauen sie einige Caches in Ihrem Prozessor (L1 / L2-Cache) ein, die das kompensieren. Stellen Sie sich vor, dass Sie Ihre Berechnungen durchführen und herausfinden, dass Sie ein Gedächtnis brauchen. Der Prozessor erhält seine "Lade" -Operation und lädt das Stück Speicher in den Cache - und verwendet dann den Cache, um den Rest der Berechnungen auszuführen. Da der Speicher relativ langsam ist, verlangsamt diese "Last" Ihr Programm.

Wie bei der Verzweigungsvorhersage wurde dies in den Pentium-Prozessoren optimiert: Der Prozessor sagt voraus, dass er ein Stück Daten laden muss und versucht, diesen in den Cache zu laden, bevor die Operation tatsächlich den Cache erreicht. Wie wir bereits gesehen haben, geht die Verzweigungsprognose manchmal furchtbar schief - im schlimmsten Fall müssen Sie zurückgehen und tatsächlich auf eine Speicherlast warten, die ewig dauern wird (Mit anderen Worten: Eine fehlerhafte Verzweigungsvorhersage ist schlecht, eine Speicherlast nach einer Verzweigungsvorhersage ist einfach schrecklich!).

Zum Glück für uns, wenn das Speicherzugriffsmuster vorhersehbar ist, wird der Prozessor es in seinem schnellen Cache laden und alles ist gut.

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

Erstellen einer Tabelle

Wir haben also herausgefunden, dass wir eine kleine Tabelle erstellen können. Als nächstes muss eine Nachschlagefunktion eingerichtet werden. Suchfunktionen sind normalerweise kleine Funktionen, die ein paar einfache Integer-Operationen verwenden (und, oder, xor, shift, add, remove und vielleicht multiplizieren). Sie möchten, dass Ihre Eingabe von der Lookup-Funktion in eine Art "eindeutigen Schlüssel" in Ihrer Tabelle übersetzt wird, der Ihnen dann einfach die Antwort auf alle Arbeiten gibt, die Sie ausführen wollten.

In diesem Fall:> = 128 bedeutet, dass wir den Wert behalten können, <128 bedeutet, dass wir ihn loswerden. Der einfachste Weg, dies zu tun, ist mit einem "UND": Wenn wir es behalten, wir UND es mit 7FFFFFFF; wenn wir es loswerden wollen, wir UND es mit 0. Bemerke auch, dass 128 eine Potenz von 2 ist - also können wir weitergehen und eine Tabelle von 32768/128 ganzen Zahlen machen und sie mit einer Null und einer Menge davon füllen 7FFFFFFFFs.

Verwaltete Sprachen

Sie werden sich vielleicht fragen, warum dies in verwalteten Sprachen gut funktioniert. Schließlich überprüfen verwaltete Sprachen die Grenzen der Arrays mit einer Verzweigung, um sicherzustellen, dass Sie nicht versauen ...

Nun, nicht genau ... :-)

Es hat einiges an Arbeit getan, diesen Zweig für verwaltete Sprachen zu eliminieren. Beispielsweise:

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 erwarte, dass Java ähnliche Dinge tut) wird dies bemerken und den Scheck ganz entfernen. WOW - das bedeutet keine Branche. Ähnlich wird es sich mit anderen offensichtlichen Fällen befassen.

Wenn Sie Probleme mit Suchvorgängen in verwalteten Sprachen haben, müssen Sie einen hinzufügen & 0x[something]FFFzu Ihrer Lookup-Funktion, um die Grenzkontrolle vorhersehbar zu machen - und sehen Sie, wie sie schneller läuft.

Das Ergebnis dieses Falles

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

1158
2018-04-24 06:26



Da die Daten bei der Sortierung des Arrays zwischen 0 und 255 verteilt sind, wird die erste Hälfte der Iterationen nicht in die if(das if Aussage wird unten geteilt).

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

Die Frage ist: Was bewirkt, dass die obige Anweisung in bestimmten Fällen nicht wie bei sortierten Daten ausgeführt wird? Hier kommt der "Branch Prädiktor". Ein Verzweigungsvorhersager ist eine digitale Schaltung, die versucht zu erraten, auf welche Weise eine Verzweigung (z. B. ein if-then-else Struktur) wird gehen, bevor dies sicher bekannt ist. Der Zweck des Verzweigungsprädiktors besteht darin, den Fluss in der Befehlspipeline zu verbessern. Branch Prädiktoren spielen eine entscheidende Rolle beim Erreichen einer hohen effektiven Leistung!

Lassen Sie uns einige Bankmarkierungen machen, um es besser zu verstehen

Die Leistung eines ifDie Aussage hängt davon ab, ob ihr Zustand vorhersagbar ist. Wenn die Bedingung immer wahr oder immer falsch ist, nimmt die Verzweigungsvorhersagelogik im Prozessor das Muster auf. Auf der anderen Seite, wenn das Muster unvorhersehbar ist, die ifDie Aussage wird viel teurer sein.

Messen wir die Leistung dieser Schleife mit verschiedenen Bedingungen:

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 "Schlecht"True-False-Muster kann eine machen if- bis zu sechs Mal langsamer als ein "gut" Muster! Natürlich, welches Muster gut ist und welches schlecht ist, hängt von den genauen Anweisungen ab, die vom Compiler und vom spezifischen Prozessor erzeugt werden.

Es besteht also kein Zweifel über die Auswirkung der Verzweigungsvorhersage auf die Leistung!


1033
2018-02-15 07:24



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

Aber in diesem Fall wissen wir, dass Werte im Bereich [0, 255] liegen und wir interessieren uns nur für Werte> = 128. Das heißt, wir können leicht ein einzelnes Bit extrahieren, das uns sagt, ob wir einen Wert haben wollen oder nicht: durch Verschieben die Daten nach rechts 7 Bits, wir sind mit einem 0 Bit oder einem 1 Bit übrig, und wir wollen nur den Wert hinzufügen, wenn wir ein 1 Bit haben. Nennen wir dieses Bit das "Entscheidungsbit".

Indem wir den 0/1-Wert des Entscheidungsbits als Index in ein Array verwenden, können wir einen Code erstellen, der genauso schnell ist, ob die Daten sortiert oder nicht sortiert sind. Unser Code wird immer einen Wert hinzufügen, aber wenn das Entscheidungsbit 0 ist, werden wir den Wert hinzufügen, den wir 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 Adds, hat jedoch nie einen Fehler bei der Verzweigungsvorhersage. Es ist enorm viel schneller auf zufällige Daten als die Version mit einer tatsächlichen if-Anweisung.

Aber 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 Nachschlagetabelle einrichtet und verwendet (phantasielos genannt) lut für "LookUp Table" im Code). 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 Bytes groß, also passt sie 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 von ihnen wollten ... die Nachschlagetabelle wäre viel zu groß, um praktisch zu sein. Auf der anderen Seite können wir die zwei oben gezeigten Techniken kombinieren: zuerst die Bits verschieben und dann eine Nachschlagetabelle indizieren. Bei einem 24-Bit-Wert, der nur den Wert der oberen Hälfte haben soll, könnten 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.

EDIT: Eine Sache habe ich vergessen zu setzen.

Die Technik des Indizierens in ein Array, anstatt ein if Anweisung kann verwendet werden, um zu entscheiden, welcher Zeiger verwendet werden soll. Ich sah eine Bibliothek, die binäre Bäume implementiert, und anstatt zwei benannte Zeiger (pLeft und pRight oder was auch immer) hatte ein Längen-2-Array von Zeigern und verwendete die "Entscheidungsbit" -Technik, um zu entscheiden, welcher zu folgen ist. Zum Beispiel, anstatt:

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

Diese Bibliothek würde so etwas wie Folgendes tun:

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

Hier ist ein Link zu diesem Code: Rote schwarze Bäume, Ewig verwirrt


961
2017-07-22 08:29