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




c++ performance optimization branch-prediction (18)

Si tratta della previsione delle filiali. Che cos'è?

  • Un predittore di ramo è una delle antiche tecniche di miglioramento delle prestazioni che trova ancora rilevanza nelle architetture moderne. Mentre le semplici tecniche di predizione forniscono una rapida ricerca e efficienza energetica soffrono di un alto tasso di errore di lettura.

  • D'altra parte, le previsioni di branch complesse - o basate su neurale o varianti di predizione di ramo su due livelli - forniscono una migliore accuratezza di previsione, ma consumano più potenza e la complessità aumenta esponenzialmente.

  • In aggiunta a ciò, nelle tecniche di previsione complesse il tempo impiegato per prevedere i rami è di per sé molto elevato, da 2 a 5 cicli, che è paragonabile al tempo di esecuzione dei rami effettivi.

  • La previsione del ramo è essenzialmente un problema di ottimizzazione (minimizzazione) in cui l'enfasi è posta su un tasso di mancato tasso minimo, un basso consumo energetico e una bassa complessità con risorse minime.

Ci sono davvero tre diversi tipi di rami:

Inoltra rami condizionali - in base a una condizione di runtime, il PC (contatore del programma) viene modificato in modo che punti a un indirizzo in avanti nel flusso di istruzioni.

Rami condizionali all'indietro : il PC viene modificato in modo che punti all'indietro nel flusso di istruzioni. Il ramo si basa su alcune condizioni, come il diramazione all'indietro all'inizio di un ciclo del programma quando un test alla fine del ciclo indica che il ciclo deve essere eseguito nuovamente.

Filiali incondizionate - questo include salti, chiamate di procedure e ritorni che non hanno una condizione specifica. Ad esempio, un'istruzione di salto incondizionata potrebbe essere codificata in linguaggio assembly semplicemente come "jmp" e il flusso di istruzioni deve essere immediatamente indirizzato alla posizione di destinazione indicata dall'istruzione di salto, mentre un salto condizionato che potrebbe essere codificato come "jmpne" reindirizza il flusso di istruzioni solo se il risultato di un confronto di due valori in una precedente istruzione di "confronto" mostra che i valori non sono uguali. (Lo schema di indirizzamento segmentato utilizzato dall'architettura x86 aggiunge ulteriore complessità, poiché i salti possono essere "vicini" (all'interno di un segmento) o "lontani" (al di fuori del segmento). Ogni tipo ha effetti diversi sugli algoritmi di previsione dei rami.)

Predizione di ramo statico / dinamico : la previsione di ramo statico viene utilizzata dal microprocessore la prima volta che viene rilevato un ramo condizionale e la previsione di ramo dinamico viene utilizzata per le esecuzioni successive del codice di ramo condizionale.

Riferimenti:

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.

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!


Le operazioni booleane usate frequentemente in C ++ producono molti rami nel programma compilato. Se questi rami sono all'interno di cicli e sono difficili da prevedere, possono rallentare notevolmente l'esecuzione. Le variabili booleane sono memorizzate come numeri interi a 8 bit con il valore 0per falsee 1per true.

Le variabili booleane sono sovradeterminate nel senso che tutti gli operatori che hanno variabili booleane come input verificano se gli input hanno un valore diverso da 0o 1, ma gli operatori che hanno booleani come output non possono produrre altro valore di 0o 1. Ciò rende le operazioni con le variabili booleane come input meno efficienti del necessario. Considera un esempio:

bool a, b, c, d;
c = a && b;
d = a || b;

Questo è in genere implementato dal compilatore nel modo seguente:

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

Questo codice è tutt'altro che ottimale. I rami possono richiedere molto tempo in caso di previsioni errate. Le operazioni booleane possono essere rese molto più efficienti se è noto con certezza che gli operandi non hanno altri valori di 0e 1. Il motivo per cui il compilatore non fa una tale ipotesi è che le variabili potrebbero avere altri valori se non sono inizializzate o provengono da fonti sconosciute. Il codice sopra può essere ottimizzato se ae bsono stati inizializzati su valori validi o se provengono da operatori che producono output booleano. Il codice ottimizzato si presenta così:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charviene utilizzato al posto di boolper consentire di utilizzare gli operatori bit per bit ( &e |) anziché gli operatori booleani ( &&e ||). Gli operatori bit a bit sono istruzioni singole che richiedono solo un ciclo di clock. L'operatore OR ( |) funziona anche se ae bha valori diversi da 0o 1. L'operatore AND ( &) e l'operatore EXCLUSIVE OR ( ^) possono fornire risultati incoerenti se gli operandi hanno valori diversi da 0e 1.

~non può essere usato per NOT. Invece, puoi creare un NOT booleano su una variabile che è nota 0o 1XOR con 1:

bool a, b;
b = !a;

può essere ottimizzato per:

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

a && bnon può essere sostituito con a & bse bè un'espressione che non dovrebbe essere valutata se aè false( &&non valuterà b, &sarà). Allo stesso modo, a || bnon può essere sostituito a | bse bè un'espressione che non dovrebbe essere valutata se lo aè true.

L'utilizzo di operatori bit a bit è più vantaggioso se gli operandi sono variabili rispetto a se gli operandi sono confronti:

bool a; double x, y, z;
a = x > y && z < 5.0;

è ottimale nella maggior parte dei casi (a meno che non si preveda che l' &&espressione generi molte errate previsioni di ramo).


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.


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


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.


Nel caso ordinato, puoi fare meglio che fare affidamento sulla previsione dei rami o su un trucco di confronto senza ramo: rimuovi completamente il ramo.

Infatti, l'array è partizionato in una zona contigua con data < 128e un altro con data >= 128. Quindi dovresti trovare il punto di partizione con una ricerca dicotomica (usando i Lg(arraySize) = 15confronti), quindi fare un accumulo diretto da quel punto.

Qualcosa come (non selezionato)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

o, leggermente più offuscato

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Un approccio ancora più rapido, che fornisce una soluzione approssimata per entrambi ordinati o non ordinati è: sum= 3137536;(assumendo una distribuzione veramente uniforme, 16384 campioni con valore atteso 191,5) :-)


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

Certamente!...

La previsione dei branch rallenta la logica, a causa della commutazione che avviene nel tuo codice! È come se steste andando su una strada dritta o su una strada con molte svolte, di sicuro la scala sarà fatta più veloce! ...

Se l'array è ordinato, la tua condizione è falsa al primo passaggio data[c] >= 128:, quindi diventa un valore vero per tutto il percorso fino alla fine della strada. Ecco come si arriva alla fine della logica più velocemente. D'altra parte, usando un array non ordinato, è necessario un sacco di svolte e di processi che rendono il tuo codice più lento di sicuro ...

Guarda l'immagine che ho creato per te qui sotto. Quale strada sarà finita più velocemente?

Quindi, a livello di programmazione, la previsione delle branchie rallenta il processo ...

Inoltre, è bene sapere che abbiamo due tipi di previsioni di branch che influenzeranno il tuo codice in modo diverso:

1. Statico

2. Dinamico

La previsione del ramo statico viene utilizzata dal microprocessore la prima volta che viene rilevato un ramo condizionale e viene utilizzata la previsione del ramo dinamico per le esecuzioni successive del codice filiale condizionale.

Per scrivere in modo efficace il tuo codice per sfruttare queste regole, quando scrivi le istruzioni if-else o switch , verifica prima i casi più comuni e procedi progressivamente verso il meno comune. I loop non richiedono necessariamente un ordinamento di codice speciale per la previsione del ramo statico, in quanto viene utilizzata normalmente solo la condizione dell'iter iteratore.


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


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


Il motivo per cui le prestazioni migliorano drasticamente quando i dati sono ordinati è che la penalità di predizione del ramo viene rimossa, come spiegato splendidamente nella risposta di .

Ora, se guardiamo il codice

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

possiamo scoprire che il significato di questo particolare if... else... ramo è aggiungere qualcosa quando una condizione è soddisfatta. Questo tipo di ramo può essere facilmente trasformato in un'istruzione di movimento condizionale , che verrebbe compilata in un'istruzione di movimento condizionale: cmovl , in un sistema x86 . Il ramo e quindi la penalità di predizione del ramo potenziale vengono rimossi.

In C , quindi C++ , l'istruzione, che compilerebbe direttamente (senza alcuna ottimizzazione) nell'istruzione di movimento condizionale in x86 , è l'operatore ternario ... ? ... : ... ... ? ... : ... Quindi riscriviamo l'affermazione precedente in una equivalente:

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

Mantenendo la leggibilità, possiamo controllare il fattore di accelerazione.

In un Intel Core i7 -2600K a 3,4 GHz e in Visual Studio 2010 Release Mode, il benchmark è (formato copiato da Mysticial):

X 86

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

Il risultato è robusto in più test. Otteniamo una grande accelerazione quando il risultato del ramo è imprevedibile, ma soffriamo un po 'quando è prevedibile. In effetti, quando si utilizza una mossa condizionale, le prestazioni sono le stesse indipendentemente dal modello di dati.

Ora esaminiamo più da vicino l'analisi dell'assieme x86 che generano. Per semplicità, usiamo due funzioni max1 e max2 .

max1 usa il ramo condizionale if... else ... :

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

max2 usa l'operatore ternario ... ? ... : ... ... ? ... : ... :

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

Su una macchina x86-64, GCC -S genera l'assembly di seguito.

: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 usa molto meno codice a causa dell'uso di cmovge di istruzioni. Ma il vero vantaggio è che max2 non prevede salti max2 , jmp , che comporterebbero una penalizzazione significativa delle prestazioni se il risultato previsto non è corretto.

Quindi perché una mossa condizionale ha un rendimento migliore?

In un tipico processore x86 , l'esecuzione di un'istruzione è suddivisa in più fasi. Approssimativamente, abbiamo diversi hardware per gestire le diverse fasi. Quindi non dobbiamo aspettare che un'istruzione finisca per avviarne una nuova. Questo è chiamato pipelining .

In un caso di diramazione, la seguente istruzione è determinata dalla precedente, quindi non possiamo eseguire il pipelining. Dobbiamo aspettare o prevedere.

In un caso di movimento condizionale, l'istruzione di spostamento condizionale di esecuzione è divisa in più fasi, ma le fasi precedenti come Fetch e Decode non dipendono dal risultato dell'istruzione precedente; solo le ultime fasi hanno bisogno del risultato. Quindi, aspettiamo una frazione del tempo di esecuzione di una istruzione. Questo è il motivo per cui la versione con spostamento condizionale è più lenta del ramo quando la previsione è semplice.

Il libro Computer Systems: A Programmer's Perspective, seconda edizione spiega questo in dettaglio. È possibile consultare la Sezione 3.6.6 per le Istruzioni di spostamento condizionale , l'intero Capitolo 4 per l' architettura del processore e la Sezione 5.11.2 per un trattamento speciale per le penalità di previsione e di stima errata .

A volte, alcuni compilatori moderni possono ottimizzare il nostro codice all'assemblaggio con prestazioni migliori, a volte alcuni compilatori non possono (il codice in questione utilizza il compilatore nativo di Visual Studio). Conoscere la differenza di prestazioni tra ramo e mossa condizionale quando imprevedibile può aiutarci a scrivere codice con prestazioni migliori quando lo scenario diventa così complesso che il compilatore non può ottimizzarlo automaticamente.


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

Guadagno pronostico!

È importante capire che il malinteso del ramo non rallenta i programmi. Il costo di una previsione mancata è come se la previsione delle branch non esistesse e si aspettava che la valutazione dell'espressione decidesse quale codice eseguire (ulteriori spiegazioni nel paragrafo successivo).

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

Ogni volta che c'è una if-else\ switchistruzione, l'espressione deve essere valutata per determinare quale blocco deve essere eseguito. Nel codice assembly generato dal compilatore, vengono inserite le istruzioni del branch condizionale .

Un'istruzione branch può far sì che un computer inizi a eseguire una sequenza di istruzioni diversa e quindi si discosti dal suo comportamento predefinito delle istruzioni di esecuzione nell'ordine (cioè se l'espressione è falsa, il programma salta il codice del ifblocco) a seconda di alcune condizioni, che è la valutazione dell'espressione nel nostro caso.

Detto questo, il compilatore cerca di prevedere l'esito prima che venga effettivamente valutato. Recupererà le istruzioni dal ifblocco e se l'espressione risulta vera, allora meraviglioso! Abbiamo guadagnato il tempo necessario per valutarlo e fatto progressi nel codice; in caso contrario, stiamo eseguendo il codice sbagliato, la pipeline viene svuotata e viene eseguito il blocco corretto.

visualizzazione:

Supponiamo che tu debba scegliere il percorso 1 o il percorso 2. In attesa che il tuo partner controlli la mappa, ti sei fermato a ## e hai aspettato, oppure puoi scegliere il percorso1 e se sei stato fortunato (l'itinerario 1 è il percorso corretto), poi fantastico non hai dovuto aspettare che il tuo partner controllasse la mappa (hai salvato il tempo che gli sarebbe occorso per controllare la mappa), altrimenti tornerai indietro.

Mentre le linee di scarico sono super veloci, oggi vale la pena scommettere su questa scommessa. La previsione di dati ordinati o di dati che cambiano lentamente è sempre più facile e migliore della previsione di modifiche veloci.

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

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


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


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.


La pura speculazione è che stai usando un terminale che tenta di eseguire il word-wrapping piuttosto che il character-wrapping e tratta B come un carattere word ma # come un carattere non-word. Quindi quando raggiunge la fine di una linea e cerca un posto in cui interrompere la linea, vede un # quasi immediatamente e felicemente si spezza lì; mentre con la B , deve continuare a cercare più a lungo e può avere più testo da avvolgere (che può essere costoso su alcuni terminali, ad esempio, l'output di backspaces, quindi l'output degli spazi per sovrascrivere le lettere che vengono spostate).

Ma questa è pura speculazione.







java c++ performance optimization branch-prediction