java - trovare - Perché è più veloce elaborare una matrice ordinata rispetto a una matrice non ordinata?




programma c massimo e minimo (14)

Ecco un pezzo di codice C ++ che sembra molto particolare. Per qualche strana ragione, l'ordinamento miracolosamente dei dati rende il codice quasi sei volte più veloce.

#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;
}
  • Senza std::sort(data, data + arraySize); , il codice viene eseguito in 11.54 secondi.
  • Con i dati ordinati, il codice viene eseguito in 1,93 secondi.

Inizialmente, ho pensato che questa potrebbe essere solo una lingua o un'anomalia del compilatore. Così l'ho provato in Java.

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

Con un risultato un po 'simile ma meno estremo.

Il mio primo pensiero fu che l'ordinamento porta i dati nella cache, ma poi ho pensato a quanto fosse sciocco perché l'array era appena stato generato.

  • Cosa sta succedendo?
  • Perché è più veloce elaborare una matrice ordinata rispetto a una matrice non ordinata?
  • Il codice riassume alcuni termini indipendenti e l'ordine non dovrebbe avere importanza.

https://code.i-harness.com


Dato che i dati sono distribuiti tra 0 e 255 quando l'array è ordinato, intorno alla prima metà delle iterazioni non verrà inserito l' if statement (l'istruzione if è condivisa di seguito).

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

La domanda è: cosa rende la dichiarazione precedente non eseguita in alcuni casi come nel caso dei dati ordinati? Arriva il "predittore del ramo". Un predittore di branche è un circuito digitale che cerca di indovinare in quale direzione un ramo (per esempio una struttura if-then-else ) andrà prima che questo sia noto con certezza. Lo scopo del predittore di branca è di migliorare il flusso nella pipeline di istruzioni. I predittori di ramo svolgono un ruolo fondamentale nel raggiungimento di alte prestazioni efficaci!

Facciamo un po 'di benchmark per comprenderlo meglio

La performance di un ifdocumento dipende dal fatto che la sua condizione abbia uno schema prevedibile. Se la condizione è sempre vera o sempre falsa, la logica di predizione del ramo nel processore preleverà il modello. D'altra parte, se il modello è imprevedibile, lo ifstumento sarà molto più costoso.

Misuriamo le prestazioni di questo ciclo con condizioni diverse:

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

Ecco i tempi del ciclo con diversi modelli true-false:

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

Un modello " cattivo " vero e falso può rendere una ifdichiarazione fino a sei volte più lenta di un modello " buono "! Ovviamente, quale modello è buono e quale è cattivo dipende dalle esatte istruzioni generate dal compilatore e dallo specifico processore.

Quindi non vi è alcun dubbio sull'impatto della previsione del ramo sulle prestazioni!


Ho appena letto su questa domanda e le sue risposte, e sento che manca una risposta.

Un metodo comune per eliminare la previsione di branch che ho trovato particolarmente utile nei linguaggi gestiti è una ricerca di tabelle invece di usare un ramo (anche se in questo caso non l'ho testato).

Questo approccio funziona in generale se:

  1. È una tabella piccola ed è probabile che venga memorizzata nella cache del processore
  2. Stai eseguendo le cose in un ciclo piuttosto stretto e / o il processore può precaricare i dati

Sfondo e perché

Pfew, quindi cosa diavolo dovrebbe significare?

Dal punto di vista del processore, la tua memoria è lenta. Per compensare la differenza di velocità, creano un paio di cache nel processore (cache L1 / L2) che compensano ciò. Quindi immagina che stai facendo i tuoi bei calcoli e capisci che hai bisogno di un pezzo di memoria. Il processore avrà il suo funzionamento 'carica' e caricherà il pezzo di memoria nella cache - e quindi utilizzerà la cache per fare il resto dei calcoli. Poiché la memoria è relativamente lenta, questo "caricamento" rallenterà il tuo programma.

Come la previsione del ramo, questo è stato ottimizzato nei processori Pentium: il processore prevede che è necessario caricare un pezzo di dati e tenta di caricarlo nella cache prima che l'operazione colpisca effettivamente la cache. Come abbiamo già visto, la previsione del ramo a volte diventa terribilmente sbagliata - nel peggiore dei casi è necessario tornare indietro e attendere effettivamente un carico di memoria, che richiederà un tempo indefinito ( in altre parole: la previsione del ramo fallita è cattiva, una memoria caricare dopo un errore di previsione ramo è semplicemente orribile! ).

Fortunatamente per noi, se il modello di accesso alla memoria è prevedibile, il processore lo caricherà nella sua cache veloce e tutto andrà bene.

La prima cosa che dobbiamo sapere è ciò che è piccolo ? Mentre generalmente più piccolo è meglio, una regola empirica è di attenersi a tabelle di ricerca con dimensioni <= 4096 byte. Come limite superiore: se la tua tabella di ricerca è più grande di 64 KB probabilmente vale la pena riconsiderare.

Costruire un tavolo

Quindi abbiamo capito che possiamo creare un tavolino. La prossima cosa da fare è ottenere una funzione di ricerca sul posto. Le funzioni di ricerca sono in genere piccole funzioni che utilizzano un paio di operazioni di base integer (e, o, xor, shift, aggiungi, rimuovi e forse moltiplica). Si desidera che il proprio input venga tradotto dalla funzione di ricerca su una "chiave univoca" nella propria tabella, che quindi fornisce semplicemente la risposta di tutto il lavoro che si desidera eseguire.

In questo caso:> = 128 significa che possiamo mantenere il valore, <128 significa che ci liberiamo di esso. Il modo più semplice per farlo è usare un 'AND': se lo teniamo, noi e lui con 7FFFFFFF; se vogliamo liberarcene, we AND it con 0. Notate anche che 128 è una potenza di 2 - quindi possiamo andare avanti e creare una tabella di numeri interi 32768/128 e riempirla con uno zero e un sacco di 7FFFFFFFF di.

Lingue gestite

Potresti chiederti perché questo funziona bene nelle lingue gestite. Dopo tutto, le lingue gestite controllano i confini degli array con un ramo per assicurarti di non rovinare ...

Beh, non esattamente ... :-)

C'è stato un bel po 'di lavoro sull'eliminazione di questo ramo per le lingue gestite. Per esempio:

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

In questo caso, è ovvio al compilatore che la condizione al contorno non verrà mai colpita. Almeno il compilatore Microsoft JIT (ma mi aspetto che Java faccia cose simili) lo noterà e rimuoverà del tutto il controllo. WOW - questo significa nessun ramo. Allo stesso modo, si occuperà di altri casi ovvi.

Se si riscontrano problemi con le ricerche nelle lingue gestite, la chiave è aggiungere un & 0x[something]FFF alla propria funzione di ricerca per rendere prevedibile il controllo dei limiti e osservarlo più veloce.

Il risultato di questo caso

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

Se sei curioso di ulteriori ottimizzazioni che possono essere fatte per questo codice, considera questo:

A partire dal ciclo originale:

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

Con lo scambio di loop, possiamo tranquillamente cambiare questo loop per:

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

Quindi, puoi vedere che il condizionale if è costante durante l'esecuzione del ciclo i , così puoi issare il if fuori:

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

Quindi, si vede che il ciclo interno può essere collassato in una singola espressione, assumendo che il modello a virgola mobile lo consenta (per esempio, / fp: veloce);

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

Quello è 100.000 volte più veloce di prima


Senza dubbio alcuni di noi sarebbero interessati ai modi di identificare il codice che è problematico per il predittore di ramo della CPU. Lo strumento Valgrind cachegrind ha un simulatore di predittore di branche, abilitato usando il --branch-sim=yes . Eseguendolo sopra gli esempi in questa domanda, con il numero di cicli esterni ridotti a 10000 e compilati con g++ , si ottengono questi risultati:

Smistato:

==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%   )

Unsorted:

==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_annotate nell'output line-by-line prodotto da cg_annotate vediamo il ciclo in questione:

Smistato:

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

Unsorted:

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

Questo ti permette di identificare facilmente la linea problematica - nella versione unsorted la riga if (data[c] >= 128) sta causando 164,050,007 rami condizionali erroneamente predicati (Bcm) nel modello predittore di branch di cachegrind, mentre sta solo causando 10.006 nella versione ordinata .

In alternativa, su Linux è possibile utilizzare il sottosistema dei contatori delle prestazioni per eseguire la stessa attività, ma con prestazioni native utilizzando contatori CPU.

perf stat ./sumtest_sorted

Smistato:

 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

Unsorted:

 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

Può anche fare annotazione del codice sorgente con il disassemblaggio.

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

Guarda il tutorial sul rendimento per maggiori dettagli.


Previsione del ramo

Con una matrice ordinata, i data[c] >= 128 sulla condizione data[c] >= 128 sono prima false per una serie di valori, quindi diventano true per tutti i valori successivi. È facile da prevedere. Con una matrice non ordinata, si paga il costo della ramificazione.


Sei vittima del fallimento della previsione del ramo .

Cos'è la previsione delle filiali?

Prendi in considerazione un nodo ferroviario:

di Mecanismo, via Wikimedia Commons. Utilizzato con la licenza CC-By-SA 3.0 .

Ora per il gusto di argomentare, supponiamo che questo sia tornato nel 1800 - prima di una lunga distanza o di una comunicazione radio.

Sei l'operatore di un incrocio e senti arrivare un treno. Non hai idea di che cosa dovrebbe andare. Si ferma il treno per chiedere all'autista la direzione che vogliono. E quindi si imposta l'interruttore in modo appropriato.

I treni sono pesanti e hanno molta inerzia. Quindi impiegano un'eternità per iniziare e rallentare.

Esiste un modo migliore? Indovina in quale direzione andrà il treno!

  • Se hai indovinato, continua.
  • Se hai indovinato, il capitano si fermerà, eseguirà il backup e ti urlerà di lanciare l'interruttore. Quindi può riavviare l'altro percorso.

Se indovini giusto ogni volta , il treno non dovrà mai fermarsi.
Se indovini troppo spesso , il treno impiegherà molto tempo per fermarsi, fare retromarcia e ripartire.

Considera un'istruzione if: al livello del processore, è un'istruzione branch:

Sei un processore e vedi un ramo. Non hai idea di dove andrà. cosa fai? Interrompi l'esecuzione e attendi fino al completamento delle istruzioni precedenti. Quindi prosegui lungo il percorso corretto.

I processori moderni sono complicati e hanno lunghe condutture. Quindi impiegano un'eternità per "riscaldarsi" e "rallentare".

Esiste un modo migliore? Indovina in quale direzione andrà il ramo!

  • Se hai indovinato, continui a farlo.
  • Se hai indovinato, devi lavare la tubazione e tornare al ramo. Quindi puoi riavviare l'altro percorso.

Se indovini giusto ogni volta , l'esecuzione non dovrà mai fermarsi.
Se indovina troppo spesso , trascorri molto tempo a rallentare, a rallentare e a riavviare.

Questa è la previsione delle filiali. Ammetto che non è la migliore analogia poiché il treno potrebbe semplicemente segnalare la direzione con una bandiera. Ma nei computer, il processore non sa in quale direzione un ramo andrà fino all'ultimo momento.

Quindi, come indurrebbe strategicamente a minimizzare il numero di volte in cui il treno deve tornare indietro e percorrere l'altro percorso? Guardi la storia passata! Se il treno passa a sinistra il 99% delle volte, allora indovina a sinistra. Se si alterna, allora si alternano le ipotesi. Se va in un modo ogni 3 volte, indovina lo stesso ...

In altre parole, si tenta di identificare un modello e seguirlo. Questo è più o meno come funzionano i predittori di ramo.

La maggior parte delle applicazioni ha rami ben educati. Pertanto, i predittori di ramo moderni raggiungeranno in genere tassi di successo> 90%. Ma di fronte a rami imprevedibili senza schemi riconoscibili, i predittori di ramo sono praticamente inutili.

Ulteriori letture: articolo "Predittore di rami" su Wikipedia .

Come accennato dall'alto, il colpevole è questa affermazione se:

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

Si noti che i dati sono equamente distribuiti tra 0 e 255. Quando i dati sono ordinati, all'incirca la prima metà delle iterazioni non entrerà nell'istruzione if. Dopo di ciò, entreranno tutti nell'istruzione if.

Questo è molto amichevole per il predittore del ramo poiché il ramo consecutivamente va nella stessa direzione molte volte. Anche un semplice contatore di saturazione predice correttamente il ramo tranne le poche iterazioni dopo che esso cambia direzione.

Visualizzazione rapida:

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)

Tuttavia, quando i dati sono completamente casuali, il predittore di ramo è reso inutile perché non può prevedere dati casuali. Quindi ci sarà probabilmente una misprediction di circa il 50%. (non meglio di indovinare casualmente)

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)

Quindi cosa si può fare?

Se il compilatore non è in grado di ottimizzare il ramo in una mossa condizionale, puoi provare alcuni hack se sei disposto a sacrificare la leggibilità per le prestazioni.

Sostituire:

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

con:

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

Ciò elimina il ramo e lo sostituisce con alcune operazioni bit a bit.

(Si noti che questo hack non è strettamente equivalente all'istruzione if originale, ma in questo caso è valido per tutti i valori di input dei data[] .)

Benchmarks: Core i7 920 @ 3,5 GHz

C ++ - Visual Studio 2010 - x64 Release

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

osservazioni:

  • Con il ramo: c'è un'enorme differenza tra i dati ordinati e non ordinati.
  • Con l'Hack: non c'è differenza tra dati ordinati e non ordinati.
  • Nel caso C ++, l'hack è in realtà un po 'più lento rispetto al branch quando i dati sono ordinati.

Una regola generale è quella di evitare la ramificazione dipendente dai dati nei loop critici. (come in questo esempio)

Aggiornare:

  • GCC 4.6.1 con -O3 o -ftree-vectorize su x64 è in grado di generare un movimento condizionale. Quindi non vi è alcuna differenza tra i dati ordinati e non ordinati - entrambi sono veloci.

  • VC ++ 2010 non è in grado di generare spostamenti condizionali per questo ramo anche sotto /Ox .

  • Intel Compiler 11 fa qualcosa di miracoloso. Intercambia i due anelli , sollevando in tal modo il ramo imprevedibile verso l'anello esterno. Quindi non solo è immune alle previsioni errate, ma è anche il doppio di qualsiasi altro VC ++ e GCC possano generare! In altre parole, ICC ha approfittato del test-loop per sconfiggere il benchmark ...

  • Se si fornisce al compilatore Intel il codice senza diramazione, esso lo rende perfettamente adatto a destra ... ed è altrettanto veloce come con il ramo (con lo scambio di loop).

Questo dimostra che anche i compilatori moderni maturi possono variare notevolmente nella loro capacità di ottimizzare il codice ...


Il comportamento sopra riportato sta accadendo a causa della previsione Branch.

Per comprendere la previsione delle diramazioni, è necessario prima capire la pipeline delle istruzioni :

Qualsiasi istruzione è suddivisa in una sequenza di passaggi in modo che i diversi passaggi possano essere eseguiti contemporaneamente in parallelo. Questa tecnica è nota come pipeline di istruzioni e viene utilizzata per aumentare il throughput nei processori moderni. Per capirlo meglio, per favore vedi questo esempio su Wikipedia .

In generale, i processori moderni hanno pipeline piuttosto lunghe, ma per comodità consideriamo solo questi 4 passaggi.

  1. IF: recupera l'istruzione dalla memoria
  2. ID: decodifica l'istruzione
  3. EX - Esegui l'istruzione
  4. WB - Scrivi di nuovo al registro della CPU

Pipeline a 4 stadi in generale per 2 istruzioni.

Tornando alla domanda precedente consideriamo le seguenti istruzioni:

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

Senza la previsione del ramo, si verifica quanto segue:

Per eseguire l'istruzione B o l'istruzione C il processore dovrà attendere che l'istruzione A non arrivi fino allo stadio EX nella pipeline, poiché la decisione di andare all'istruzione B o l'istruzione C dipende dal risultato dell'istruzione A. Quindi la pipeline sarà simile a questo.

quando la condizione restituisce true:

Quando la condizione restituisce false:

Come risultato dell'attesa per il risultato dell'istruzione A, i cicli totali della CPU spesi nel caso precedente (senza previsione del ramo, sia per vero che per falso) sono 7.

Allora, qual è la previsione delle filiali?

Il predittore di ramo tenterà di indovinare in che direzione andrà un ramo (una struttura if-then-else) prima che questo sia noto. Non aspetterà che l'istruzione A raggiunga lo stadio EX della pipeline, ma indovina la decisione e passa a quella istruzione (B o C nel caso del nostro esempio).

In caso di ipotesi corretta, la pipeline è simile a questa:

Se successivamente viene rilevato che l'ipotesi è sbagliata, le istruzioni parzialmente eseguite vengono scartate e la pipeline si avvia con il ramo corretto, con un ritardo. Il tempo che viene sprecato in caso di misprediction di un ramo è uguale al numero di stadi nella pipeline dalla fase di recupero alla fase di esecuzione. I moderni microprocessori tendono ad avere condutture piuttosto lunghe in modo che il ritardo di errore sia compreso tra 10 e 20 cicli di clock. Più lunga è la pipeline, maggiore è la necessità di un buon predittore di ramo .

Nel codice dell'OP, la prima volta quando il condizionale, il predittore del ramo non ha alcuna informazione per basare la previsione, quindi la prima volta sceglierà in modo casuale l'istruzione successiva. Più avanti nel ciclo for, può basare la previsione sulla storia. Per un array ordinato in ordine crescente, ci sono tre possibilità:

  1. Tutti gli elementi sono meno di 128
  2. Tutti gli elementi sono maggiori di 128
  3. Alcuni nuovi elementi di partenza sono inferiori a 128 e successivamente diventano maggiori di 128

Supponiamo che il predittore assumerà sempre il ramo vero alla prima esecuzione.

Quindi nel primo caso prenderà sempre il ramo vero poiché storicamente tutte le sue previsioni sono corrette. Nel secondo caso, inizialmente prevarrà, ma dopo alcune iterazioni, predicherà correttamente. Nel 3 ° caso, inizialmente prevarrà correttamente fino a quando gli elementi saranno inferiori a 128. Dopodiché fallirà per un po 'di tempo e sarà corretto quando vedrà un errore di previsione dei rami nella storia.

In tutti questi casi l'errore sarà troppo ridotto di numero e, di conseguenza, solo poche volte sarà necessario scartare le istruzioni parzialmente eseguite e ricominciare con il ramo corretto, con un conseguente minor numero di cicli della CPU.

Ma nel caso di un array casuale non ordinato, la previsione dovrà scartare le istruzioni parzialmente eseguite e ricominciare con il ramo corretto la maggior parte del tempo e portare a più cicli della CPU rispetto alla matrice ordinata.


Le matrici ordinate vengono elaborate più rapidamente di una matrice non ordinata, a causa di fenomeni chiamati previsione dei rami.

Il predittore di ramo è un circuito digitale (nell'architettura dei computer) che tenta di prevedere in che direzione andrà un ramo, migliorando il flusso nella pipeline di istruzioni. Il circuito / computer prevede il prossimo passo e lo esegue.

Fare una previsione sbagliata porta a tornare al passaggio precedente e all'esecuzione con un'altra previsione. Supponendo che la previsione sia corretta, il codice continuerà con il passaggio successivo. La previsione errata risulta nel ripetere lo stesso passo, fino a quando si verifica la previsione corretta.

La risposta alla tua domanda è molto semplice.

In una matrice non ordinata, il computer esegue più previsioni, portando a una maggiore possibilità di errori. Mentre, in ordine, il computer fa meno pronostici riducendo la possibilità di errori. Fare più previsioni richiede più tempo.

Matrice ordinata: Straight Road

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Matrice non ordinata: strada curva

______   ________
|     |__|

Predizione del ramo: indovinare / prevedere quale strada è diritta e seguirla senza controllo

___________________________________________ Straight road
 |_________________________________________|Longer road

Sebbene entrambe le strade raggiungano la stessa destinazione, la strada diritta è più breve e l'altra è più lunga. Se poi scegli l'altro per sbaglio, non puoi tornare indietro e così perderai un po 'di tempo extra se scegli la strada più lunga. Questo è simile a ciò che accade sul computer, e spero che questo ti abbia aiutato a capire meglio.

Aggiornamento: Dopo quello che @Simon_Weaver ha detto, voglio aggiungere un altro fatto che ... "non fa meno previsioni - fa meno previsioni sbagliate e deve ancora prevedere per ogni volta attraverso il ciclo."


Nella stessa linea (penso che questo non sia stato evidenziato da nessuna risposta) è bene menzionare che a volte (specialmente nel software in cui le prestazioni sono importanti, come nel kernel di Linux) si possono trovare alcune affermazioni come la seguente:

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

o allo stesso modo:

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

Entrambi likely()e unlikely()sono infatti macro che vengono definite utilizzando qualcosa come GCC __builtin_expectper aiutare il compilatore a inserire il codice di previsione per favorire la condizione tenendo conto delle informazioni fornite dall'utente. GCC supporta altri builtin che potrebbero modificare il comportamento del programma in esecuzione o emettere istruzioni di basso livello come svuotare la cache, ecc. Vedere questa documentazione che passa attraverso i builtin del GCC disponibili.

Normalmente questo tipo di ottimizzazioni si trova principalmente in applicazioni hard-real-time o in sistemi embedded in cui il tempo di esecuzione è importante ed è fondamentale. Ad esempio, se stai verificando qualche condizione di errore che accade solo 1/10000000 volte, allora perché non informare il compilatore su questo? In questo modo, per impostazione predefinita, la previsione del ramo assumerebbe che la condizione sia falsa.


Oltre al fatto che la previsione del ramo può rallentare, un array ordinato ha un altro vantaggio:

È possibile avere una condizione di arresto anziché semplicemente controllare il valore, in questo modo si circoscrive solo i dati rilevanti e si ignora il resto.
La previsione del ramo mancherà solo una volta.

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

Una risposta ufficiale sarebbe da

  1. Intel - Evitare il costo della mispredicione dei rami
  2. Intel: riorganizzazione di segmenti e loop per prevenire i malintenzionati
  3. Documenti scientifici - architettura dei computer di previsione delle filiali
  4. Libri: JL Hennessy, DA Patterson: Architettura del computer: un approccio quantitativo
  5. Articoli in pubblicazioni scientifiche: TY Yeh, YN Patt ne ha fatti molti sulle previsioni di ramo.

Puoi anche vedere da questo delizioso diagram perché il predittore del ramo si confonde.

Ogni elemento nel codice originale è un valore casuale

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

quindi il predittore cambierà i lati come il std::rand()colpo.

D'altra parte, una volta che è stato ordinato, il predittore si muoverà prima in uno stato fortemente non preso e quando i valori cambiano al valore alto il predittore sarà in tre passaggi attraverso il cambiamento da fortemente non preso a fortemente preso.


Come quello che è già stato detto da altri, ciò che sta dietro al mistero è Branch Predictor .

Non sto cercando di aggiungere qualcosa, ma di spiegare il concetto in un altro modo. C'è un'introduzione concisa sul wiki che contiene testo e diagramma. Mi piace la spiegazione qui sotto che utilizza un diagramma per elaborare intuitivamente il Predictor del ramo.

Nell'architettura dei computer, un predittore di ramo è un circuito digitale che cerca di indovinare in quale direzione un ramo (ad esempio una struttura if-then-else) andrà prima che questo sia noto. Lo scopo del predittore di branca è di migliorare il flusso nella pipeline di istruzioni. I predittori di ramo svolgono un ruolo fondamentale nel raggiungimento di alte prestazioni efficaci in molte moderne architetture a microprocessore con pipeline come x86.

La ramificazione bidirezionale viene solitamente implementata con un'istruzione di salto condizionale. Un salto condizionato può essere "non preso" e continuare l'esecuzione con il primo ramo di codice che segue immediatamente dopo il salto condizionato, oppure può essere "preso" e passare a un altro punto nella memoria di programma dove il secondo ramo di codice è immagazzinato. Non è noto con certezza se un salto condizionato sarà preso o non preso fino a quando la condizione non sarà stata calcolata e il salto condizionato ha superato la fase di esecuzione nella pipeline di istruzioni (vedi figura 1).

In base allo scenario descritto, ho scritto una demo di animazione per mostrare come le istruzioni vengono eseguite in una pipeline in diverse situazioni.

  1. Senza il Predictor del ramo.

Senza la previsione delle diramazioni, il processore dovrebbe attendere che l'istruzione di salto condizionale abbia passato lo stadio di esecuzione prima che l'istruzione successiva possa entrare nella fase di recupero nella pipeline.

L'esempio contiene tre istruzioni e la prima è un'istruzione di salto condizionale. Le ultime due istruzioni possono entrare nella pipeline fino a quando non viene eseguita l'istruzione di salto condizionale.

Ci vorranno 9 cicli di clock per 3 istruzioni da completare.

  1. Usa Branch Predictor e non fare un salto condizionale. Supponiamo che la previsione non stia prendendo il salto condizionale.

Ci vorranno 7 cicli di clock per 3 istruzioni da completare.

  1. Usa Branch Predictor e fai un salto condizionale. Supponiamo che la previsione non stia prendendo il salto condizionale.

Ci vorranno 9 cicli di clock per 3 istruzioni da completare.

Il tempo che viene sprecato in caso di misprediction di un ramo è uguale al numero di stadi nella pipeline dalla fase di recupero alla fase di esecuzione. I moderni microprocessori tendono ad avere condutture piuttosto lunghe in modo che il ritardo di errore sia compreso tra 10 e 20 cicli di clock. Di conseguenza, rendendo la pipeline più lunga aumenta la necessità di un predittore di ramo più avanzato.

Come puoi vedere, sembra che non abbiamo una ragione per non utilizzare Branch Predictor.

È una demo abbastanza semplice che chiarisce la parte fondamentale di Branch Predictor. Se quelle gif sono fastidiose, non esitate a rimuoverle dalla risposta e i visitatori possono anche ottenere la demo da git


Questa domanda è già stata risolta in modo eccellente molte volte. Vorrei tuttavia attirare l'attenzione del gruppo su un'altra interessante analisi.

Recentemente questo esempio (leggermente modificato) è stato usato anche come un modo per dimostrare come un pezzo di codice può essere profilato all'interno del programma stesso su Windows. Lungo la strada, l'autore mostra anche come utilizzare i risultati per determinare dove il codice sta spendendo la maggior parte del suo tempo in entrambi i casi ordinati e non ordinati. Infine, il pezzo mostra anche come utilizzare una caratteristica poco conosciuta dell'HAL (Hardware Abstraction Layer) per determinare quanta discordanza di rami si sta verificando nel caso non ordinato.

Il link è qui: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm


Su ARM, non è necessario alcun ramo, poiché ogni istruzione ha un campo di condizioni a 4 bit, che viene testato a costo zero. Questo elimina la necessità di rami brevi, e non ci sarebbe alcun colpo di predizione di ramo. Pertanto, la versione ordinata sarebbe più lenta della versione non ordinata su ARM, a causa del sovraccarico extra di ordinamento. Il ciclo interno sarebbe simile al seguente:

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




branch-prediction