java - questions - stackoverflow top question




Warum kann ein sortiertes Array schneller verarbeitet werden als ein unsortiertes Array? (14)

Hier ist ein Stück C ++ - Code, das sehr eigenartig erscheint. Aus irgendeinem seltsamen Grund macht das Sortieren der Daten auf wundersame Weise den Code fast sechsmal schneller.

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

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

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

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

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

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

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

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

Anfangs dachte ich, dies könnte nur eine Anomalie der Sprache oder des Compilers sein. Also habe ich es in Java ausprobiert.

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

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

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

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

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

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

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

Mit einem etwas ähnlichen, aber weniger extremen Ergebnis.

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

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

Der Grund, warum sich die Leistung beim der Daten drastisch verbessert, ist die Entfernung der Verzweigungsvorhersagen, wie in der Antwort von schön erklärt wird.

Nun, wenn wir uns den Code ansehen

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

Wir können herausfinden, dass die Bedeutung dieses bestimmten if... else... Ast ist, etwas hinzuzufügen, wenn eine Bedingung erfüllt ist. Diese Art von Zweig kann leicht in eine bedingte Verschiebungsanweisung umgewandelt werden, die in einem bedingten Verschiebebefehl kompiliert wird: cmovl in einem x86 System. Die Verzweigung und damit die potenzielle Verzweigungsvorhersagestrafe wird entfernt.

In C , also C++ , ist die Anweisung, die direkt (ohne Optimierung) in die Anweisung für die bedingte Verschiebung in x86 kompiliert werden soll, der ternäre Operator ... ? ... : ... ... ? ... : ... Also schreiben wir die obige Aussage in eine gleichwertige um:

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

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

Bei einem Intel Core i7 -2600K @ 3,4 GHz- und Visual Studio 2010-Release-Modus ist der Maßstab (aus Mysticial kopiertes Format):

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 robust in mehreren Tests. Wir bekommen eine große Beschleunigung, wenn das Ergebnis der Verzweigung unvorhersehbar ist, aber wir leiden etwas, wenn es vorhersehbar ist. Wenn Sie eine bedingte Verschiebung verwenden, ist die Leistung unabhängig vom Datenmuster gleich.

Schauen wir uns nun die x86 Assembly genauer an, die sie generieren. Zur Vereinfachung verwenden wir zwei Funktionen max1 und max2 .

max1 verwendet den bedingten Zweig, 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 generiert GCC -S 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

max2 verwendet aufgrund der Anweisung cmovge weniger Code. Der wahre Gewinn besteht jedoch darin, dass max2 keine max2 ( jmp , was einen erheblichen Leistungsnachteil zur Folge hätte, wenn das vorhergesagte Ergebnis nicht stimmt.

Warum ist ein bedingter Umzug besser?

In einem typischen x86 Prozessor ist die Ausführung eines Befehls in mehrere Stufen unterteilt. Grob gesagt haben wir unterschiedliche Hardware, um mit verschiedenen Phasen umzugehen. Wir müssen also nicht warten, bis eine Anweisung fertig ist, um eine neue Anweisung zu starten. Dies wird als pipelining .

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

In einem bedingten Verschiebungsfall ist der Ausführungsbefehl für die bedingte Verschiebung in mehrere Stufen unterteilt, aber die früheren Stufen wie Fetch und Decode hängen nicht vom Ergebnis der vorherigen Anweisung ab. Nur die letzten Stufen benötigen das Ergebnis. Daher warten wir einen Bruchteil der Ausführungszeit eines Befehls. Aus diesem Grund ist die Version der bedingten Bewegung langsamer als der Zweig, wenn die Vorhersage einfach ist.

Das Buch Computersysteme: Die Perspektive eines Programmierers, zweite Ausgabe, erläutert dies ausführlich. In Abschnitt 3.6.6 für bedingte Verschiebungsanweisungen , im gesamten Kapitel 4 für Prozessorarchitektur und in Abschnitt 5.11.2 finden Sie eine Sonderbehandlung für Strafen für Vorhersagen und falsche Vorhersagen .

In manchen Fällen können moderne Compiler den Code so optimieren, dass sie mit einer besseren Leistung zusammengestellt werden, in manchen Fällen ist dies nicht der Fall (der fragliche Code verwendet den systemeigenen Compiler von Visual Studio). Das Wissen um den Leistungsunterschied zwischen Verzweigung und bedingter Verschiebung, wenn unvorhersehbar, kann uns helfen, Code mit besserer Leistung zu schreiben, wenn das Szenario so komplex wird, dass der Compiler sie nicht automatisch optimieren kann.


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

Eine gängige Methode, um die Verzweigungsvoraussage zu beseitigen, die ich in verwalteten Sprachen als besonders gut empfunden habe, ist das Nachschlagen in einer Tabelle, anstatt eine Verzweigung zu verwenden (obwohl ich sie in diesem Fall nicht getestet habe).

Dieser Ansatz funktioniert im Allgemeinen, wenn:

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

Hintergrund und warum

Pfew, was soll das denn heißen?

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

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

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

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

Einen Tisch bauen

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

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

Verwaltete Sprachen

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

Na ja, nicht genau ... :-)

Es wurde bereits viel Arbeit geleistet, um diesen Zweig für verwaltete Sprachen zu beseitigen. Zum Beispiel:

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

In diesem Fall ist es für den Compiler offensichtlich, dass die Randbedingung niemals erfüllt wird. Zumindest wird der Microsoft-JIT-Compiler (dies wird jedoch mit Java vergleichbar sein) dies bemerken und die Prüfung vollständig entfernen. WOW - das bedeutet keine Branche. Ähnlich wird es sich mit anderen offensichtlichen Fällen befassen.

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

Das Ergebnis dieses Falls

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

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

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

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

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

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

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();

Zweifellos wären einige von uns an Möglichkeiten interessiert, Code zu identifizieren, der für den Zweigprädiktor der CPU problematisch ist. Das Valgrind-Tool cachegrind verfügt über einen cachegrind , der mit dem --branch-sim=yes aktiviert wird. Das Durchlaufen der Beispiele in dieser Frage, wobei die Anzahl der äußeren Schleifen auf 10000 reduziert und mit g++ kompiliert wurde, führt zu folgenden Ergebnissen:

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 von cg_annotate erzeugte zeilenweise Ausgabe cg_annotate wir für die betreffende Schleife:

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 Linie leicht identifizieren. In der unsortierten Version verursacht die if (data[c] >= 128) -Zeile Bcm falsch vorausgesagte bedingte Verzweigungen ( Bcm ) unter dem Zweigprädiktormodell von cachegrind, in der sortierten Version jedoch nur 10.006 .

Unter Linux können Sie alternativ das Leistungsindikatorsubsystem verwenden, um dieselbe Aufgabe auszuführen, jedoch mit nativer Leistung unter Verwendung von CPU-Indikatoren.

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 Quelltextanmerkungen mit Disassemblierung ausfü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 .


Sie sind ein Opfer von Verzweigungsvorhersagen .

Was ist eine Branchenvorhersage?

Betrachten Sie einen Eisenbahnknotenpunkt:

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

Nun, um der Argumentation willen, nehmen wir an, dies sei in den 1800er Jahren - vor der Fern- oder Funkverbindung.

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

Züge sind schwer und haben viel Trägheit. Sie brauchen also ewig, um anzufahren und langsamer zu 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, wird der Kapitän anhalten, sich zurücklehnen und Sie anschreien, den Schalter zu betätigen. Dann kann der andere Pfad neu gestartet werden.

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

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

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

Moderne Prozessoren sind kompliziert und verfügen über lange Pipelines. Sie brauchen also ewig, um sich aufzuwärmen und zu verlangsamen.

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

  • Wenn Sie richtig geraten haben, führen Sie die Ausführung weiter aus.
  • Wenn Sie falsch geraten haben, müssen Sie die Pipeline leeren und zum Zweig zurückkehren. Dann können Sie den anderen Pfad neu starten.

Wenn Sie jedes Mal richtig raten , muss die Ausführung nie aufhören.
Wenn Sie zu oft falsch denken , verbringen Sie viel Zeit mit Stehenbleiben, Zurücksetzen und Neustarten.

Dies ist eine Zweigvorhersage. 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 nicht, in welche Richtung sich ein Zweig bis zum letzten Moment bewegen wird.

Wie würden Sie strategisch raten, um die Anzahl der Male zu verringern, die der Zug auf den anderen Weg zurückkehren muss? Du siehst die Vergangenheit an! Wenn der Zug zu 99% nach links fährt, dann sind Sie vermutlich links. Wenn es abwechselnd ist, wechseln Sie Ihre Vermutungen ab. 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. Dies ist mehr oder weniger die Funktion von Branch-Prädiktoren.

Die meisten Anwendungen haben sich gut verhaltene Zweige. Moderne Branch-Prädiktoren erreichen also typischerweise Trefferraten von> 90%. Bei unvorhersehbaren Verzweigungen ohne erkennbare Muster sind Verzweigungsprädiktoren praktisch unbrauchbar.

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

Wie 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 eingegeben. Danach geben sie alle die if-Anweisung ein.

Dies ist für den Verzweigungsvorhersager sehr freundlich, da der Zweig viele Male in dieselbe Richtung geht. Selbst ein einfacher Sättigungszähler kann den Zweig richtig vorhersagen, mit Ausnahme der wenigen Iterationen nach dem Richtungswechsel.

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 Zweigprädiktor unbrauchbar, da er keine zufälligen Daten vorhersagen kann. Somit wird es wahrscheinlich eine Fehlvorhersage von ungefähr 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 man also machen?

Wenn der Compiler den Zweig nicht in eine bedingte Bewegung optimieren kann, können Sie einige Hacks ausprobieren, 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];

Dadurch wird die Verzweigung eliminiert und durch einige bitweise Operationen ersetzt.

(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 dem Zweig: 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 tatsächlich etwas langsamer als beim Zweig, wenn die Daten sortiert werden.

Als Faustregel gilt, dass in kritischen Schleifen datenabhängige Verzweigungen vermieden werden. (wie in diesem Beispiel)

Aktualisieren:

  • GCC 4.6.1 mit -O3 oder -ftree-vectorize auf x64 kann eine bedingte Bewegung erzeugen. Es besteht also kein Unterschied zwischen sortierten und unsortierten Daten - beide sind schnell.

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

  • Der Intel Compiler 11 hat etwas Wunderbares. Sie tauscht die beiden Schleifen aus und hebt dadurch den unvorhersehbaren Zweig zur äußeren Schleife. Es ist also nicht nur immun gegen Missverständnisse, es ist auch doppelt so schnell, wie VC ++ und GCC generieren kann! 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 ... und ist genauso schnell wie der Zweig (mit dem Loop-Interchange).

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


Zweigvorhersage

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


Das ist sicher!...

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

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

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

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

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

1. Statisch

2. Dynamisch

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

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


Eine offizielle Antwort wäre von

  1. Intel - Vermeidung der Kosten von Zweigfehlervorhersagen
  2. Intel - Branch- und Loop-Reorganisation zur Verhinderung von Missverständnissen
  3. Wissenschaftliche Arbeiten - Computer für die Architektur der Zweigvorhersage
  4. Bücher: JL Hennessy, DA Patterson: Computerarchitektur: ein quantitativer Ansatz
  5. Artikel in wissenschaftlichen Veröffentlichungen: TY Yeh, YN Patt machte eine Menge davon zu Vorhersagen der Branche.

In diesem diagram warum der Zweigprädiktor verwirrt wird.

Jedes Element im ursprünglichen Code ist ein Zufallswert

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

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

Andererseits wird der Prädiktor nach dem Sortieren zuerst in einen Zustand versetzt, in dem er stark nicht verwendet wird, und wenn sich die Werte auf den hohen Wert ändern, wird der Prädiktor in drei Durchläufen den gesamten Weg von stark nicht genommen zu stark genommen.


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

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

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

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

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

Es gibt wirklich drei verschiedene Arten von Zweigen:

Vorwärtsbedingte Verzweigungen - basierend auf einer Laufzeitbedingung wird der PC (Programmzähler) so geändert, dass er auf eine Adresse hinweist, die im Befehlsstrom vorwärts gerichtet ist.

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

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

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

Verweise:


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

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

oder ähnlich:

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

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

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


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

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

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

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

Da die Daten zwischen 0 und 255 verteilt werden, wenn das Array sortiert wird, wird um die erste Hälfte der Iterationen nicht die if-statement eingegeben (die ifAnweisung wird unten geteilt).

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

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

Lassen Sie uns etwas Benchmarking machen, um es besser zu verstehen

Die Leistung einer if-Anweisung hängt davon ab, ob ihr Zustand ein vorhersagbares Muster aufweist. Wenn die Bedingung immer wahr oder immer falsch ist, nimmt die Verzweigungsvorhersagelogik im Prozessor das Muster auf. Wenn das Muster jedoch nicht vorhersagbar ist, wird die if-Statement viel teurer.

Messen wir die Leistung dieser Schleife unter 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 " schlechtes " Wahr-Falsch-Muster kann eine if-Zählung um bis zu sechsmal langsamer machen als ein " gutes " Muster! Welches Muster gut und welches schlecht ist, hängt natürlich von den genauen Anweisungen des Compilers und dem jeweiligen Prozessor ab.

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


Das, was bereits von anderen erwähnt wurde, steckt hinter dem Rätsel Branch Predictor .

Ich versuche nicht, etwas hinzuzufügen, sondern das Konzept auf andere Weise zu erklären. Es gibt eine kurze Einführung in das Wiki, die Text und Diagramm enthält. Ich mag die folgende Erklärung, die den Branch Predictor anhand eines Diagramms intuitiv ausarbeitet.

In der Computerarchitektur ist ein Zweigprädiktor eine digitale Schaltung, die versucht zu erraten, in welche Richtung ein Zweig (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 Anweisungspipeline zu verbessern. Zweigprä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 genommen" werden und mit dem ersten Code-Zweig, der unmittelbar nach dem bedingten Sprung folgt, ausgeführt werden, oder er kann "genommen" werden und an eine andere Stelle im Programmspeicher springen, wo sich der zweite Code-Zweig 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ührungsstufe in der Befehlspipeline durchlaufen hat (siehe Fig. 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 die Verzweigungsvorhersage muss der Prozessor warten, bis der bedingte Sprungbefehl die Ausführungsphase bestanden hat, bevor der nächste Befehl in die Abrufphase in der Pipeline eintreten kann.

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

Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

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

Es werden 7 Taktzyklen benötigt, um 3 Anweisungen auszuführen.

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

Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.

Die Zeit, die im Falle einer Verzweigungsfehlvorhersage vergeudet wird, ist gleich der Anzahl von Stufen in der Pipeline von der Abrufstufe bis zur Ausführungsstufe. Moderne Mikroprozessoren neigen dazu, ziemlich lange Pipelines zu haben, so dass die Verzögerung der Fehlvorhersage zwischen 10 und 20 Taktzyklen liegt. Wenn Sie also eine Pipeline verlängern, steigt der Bedarf an erweiterten Verzweigungsvorhersagen.

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

Es ist eine ziemlich einfache Demo, die den sehr grundlegenden Teil von Branch Predictor verdeutlicht. Wenn diese Gifs störend sind, können Sie sie gerne aus der Antwort entfernen und Besucher können die Demo auch von git


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

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

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

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

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

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

Dieser Code verschwendet die Hälfte der Additionen, hat jedoch nie einen Verzweigungsvorhersagefehler. Es ist bei zufälligen Daten enorm schneller als bei der Version mit einer tatsächlichen if-Anweisung.

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

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

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

In diesem Fall hatte die Lookup-Tabelle nur 256 Byte, sodass sie gut in einen Cache passt und alles schnell war. Diese Technik würde nicht gut funktionieren, wenn die Daten 24-Bit-Werte hätten und wir nur die Hälfte davon wollten ... Die Nachschlagetabelle wäre viel zu groß, um praktisch zu sein. Andererseits können wir die beiden oben gezeigten Techniken kombinieren: Zuerst die Bits verschieben und dann eine Nachschlagetabelle indizieren. Bei einem 24-Bit-Wert, bei dem nur der obere Halbwert gewünscht wird, können wir die Daten möglicherweise um 12 Bit nach rechts verschieben und einen 12-Bit-Wert für einen Tabellenindex belassen. Ein 12-Bit-Tabellenindex impliziert eine Tabelle mit 4096 Werten, was praktisch sein kann.

EDIT: Eine Sache, die ich vergessen habe.

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

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

Diese Bibliothek würde so etwas tun:

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

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


Häufig verwendete boolesche Operationen in C ++ erzeugen viele Zweige in einem kompilierten Programm. Wenn sich diese Verzweigungen in Schleifen befinden und schwer vorhersagbar 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 überbestimmt in dem Sinne, dass alle Operatoren, die boolesche Variablen als Eingabe haben, prüfen, ob die Eingaben einen anderen Wert als 0oder haben 1, aber Operatoren, die Booleans 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 auf folgende Weise 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. Die Niederlassungen können bei falschen Vorhersagen sehr lange dauern. Die booleschen Operationen können wesentlich effizienter gestaltet werden, wenn mit Sicherheit bekannt ist, dass die Operanden keine anderen Werte als 0und haben 1. Der Grund, warum der Compiler keine solche Annahme macht, besteht darin, dass die Variablen andere Werte haben könnten, wenn sie nicht initialisiert wurden oder aus unbekannten Quellen stammen. Der obige Code kann optimiert werden, wenn aund bwurden mit gültigen Werten initialisiert oder wenn sie von Operatoren stammen, die eine boolesche Ausgabe erzeugen. 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 bitweisen Operatoren ( &und |) anstelle der booleschen Operatoren ( &&und ||) verwenden zu können. Die bitweisen Operatoren sind einzelne Anweisungen, die nur einen Taktzyklus benötigen. Der Operator OR ( |) funktioniert auch, wenn aund bandere Werte als 0oder haben 1. Der Operator AND ( &) und der Operator EXCLUSIVE OR ( ^) können inkonsistente Ergebnisse liefern, wenn die Operanden andere Werte als 0und haben 1.

~kann nicht für NICHT verwendet werden. Stattdessen können Sie ein boolesches NICHT für eine Variable erstellen, die als XOR bezeichnet wird , 0oder 1durch XOR-Verknüpfung mit 1:

bool a, b;
b = !a;

kann optimiert werden für:

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

a && bkann nicht ersetzt werden , a & bwenn bein Ausdruck, der nicht unter werden soll , wenn aist false( &&nicht beurteilen b, &wird). Ebenso a || bkann nicht mit a | bif ersetzt werden, wenn bein Ausdruck nicht ausgewertet werden asoll true.

Die Verwendung von bitweisen Operatoren ist vorteilhafter, wenn die Operanden Variablen sind, als wenn die Operanden Vergleiche wären:

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







branch-prediction