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


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.

21644
2018-06-27 13:51


origine


risposte:


Sei una vittima di previsione del ramo  fallire.


Cos'è la previsione delle filiali?

Prendi in considerazione un nodo ferroviario:

Licensed Image Immagine  da Mecanismo, via Wikimedia Commons. Usato sotto il CC-By-SA 3.0  licenza.

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.

C'è 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.


Prendi in considerazione un'istruzione if:  A livello di processore, è un'istruzione di ramo:

image2

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

C'è 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 indovini troppo spesso , passi 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 va 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 di 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 la filiale:  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 una mossa 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. esso interscambia 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 ...


28559
2018-06-27 13:56



Previsione del ramo

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


3634
2018-06-27 13:54



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 in Mysticial La risposta.

Ora, se guardiamo il codice

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

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

In C, quindi C++, la dichiarazione, 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.

Su un Intel Core i7 -2600K @ 3.4 GHz e 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 esaminando il x86 assemblaggio 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'assemblaggio qui sotto.

: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 delle istruzioni cmovge. Ma il vero vantaggio è questo max2 non coinvolge salti di rami, jmp, che comporterebbe una penalità significativa in termini di prestazioni se il risultato previsto non è corretto.

Quindi perché una mossa condizionale ha un rendimento migliore?

In un tipico x86 processore, l'esecuzione di un'istruzione è divisa 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 movimento condizionale di esecuzione è divisa in più fasi, ma le fasi precedenti come Fetch e Decodenon dipende 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  lo spiega in dettaglio. È possibile consultare la sezione 3.6.6 per Istruzioni di spostamento condizionale , intero capitolo 4 per Architettura del processore e Sezione 5.11.2 per un trattamento speciale per Predizione della successione e penalità in caso di maledizione .

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.


2957
2018-06-28 02:14



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 if condizionale è costante per tutta l'esecuzione del i loop, in modo da poter sollevare il if su:

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


2022
2017-07-03 02:25



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 branch-predictor, abilitato usando il --branch-sim=yes bandiera. Eseguendolo sopra gli esempi in questa domanda, con il numero di cicli esterni ridotti a 10000 e compilati con g++, dà 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%   )

Drilling down 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 non ordinata il if (data[c] >= 128) linea causa 164.050.007 rami condizionali erroneamente Bcm) nel modello predittore di branch di cachegrind, mentre sta causando solo 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)
...

Vedere il tutorial sulle prestazioni  per ulteriori dettagli.


1686
2017-10-12 05:53



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 delle filiali a volte è terribilmente sbagliata - nella peggiore delle ipotesi è necessario tornare indietro e attendere effettivamente un carico di memoria, che richiederà un tempo infinito ( in altre parole: la previsione del ramo fallita è cattiva, un carico di memoria dopo un errore di previsione del 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 tua funzione di ricerca per rendere prevedibile il controllo del limite e guardarlo andare 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();

1157
2018-04-24 06:26



Poiché i dati vengono distribuiti tra 0 e 255 quando l'array è ordinato, intorno alla prima metà delle iterazioni non verrà inserito il if-statamento (il if la dichiarazione è 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 ramo è un circuito digitale che tenta di indovinare da che parte un ramo (ad es if-then-else struttura) andrà prima che questo sia noto per certo. 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

Le prestazioni di un iflo stato 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, il ifla dichiarazione sarà molto più costosa.

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

A " cattivo "Il modello vero falso può fare un if-statamento fino a sei volte più lento di un " bene "Modello! 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!


1032
2018-02-15 07:24



Un modo per evitare errori di previsione delle diramazioni è creare una tabella di ricerca e indicizzarla utilizzando i dati. Stefan de Bruijn ne ha discusso nella sua risposta.

Ma in questo caso, sappiamo che i valori sono nell'intervallo [0, 255] e ci interessano solo valori> = 128. Ciò significa che possiamo facilmente estrarre un singolo bit che ci dirà se vogliamo o meno un valore: spostando i dati a destra 7 bit, siamo lasciati con un bit 0 o un 1 bit, e vogliamo solo aggiungere il valore quando abbiamo un 1 bit. Chiamiamo questo bit il "bit di decisione".

Usando il valore 0/1 del bit di decisione come un indice in un array, possiamo creare un codice che sarà ugualmente veloce se i dati sono ordinati o non ordinati. Il nostro codice aggiungerà sempre un valore, ma quando il bit di decisione è 0, aggiungeremo il valore da qualche parte a cui non interessa. Ecco il codice:

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

Questo codice spreca metà degli add, ma non ha mai avuto un errore di previsione del ramo. È tremendamente più veloce su dati casuali rispetto alla versione con un'istruzione if effettiva.

Ma nei miei test, una tabella di ricerca esplicita era leggermente più veloce di questa, probabilmente perché l'indicizzazione in una tabella di ricerca era leggermente più veloce dello spostamento dei bit. Questo mostra come il mio codice si configura e usa la tabella di ricerca (chiamata in modo inequivocabile lutper "LookUp Table" nel codice). Ecco il codice C ++:

// 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 questo caso, la tabella di ricerca era a soli 256 byte, quindi si adattava bene in una cache e tutto era veloce. Questa tecnica non funzionerebbe bene se i dati fossero valori a 24 bit e volevamo solo metà di essi ... la tabella di ricerca sarebbe troppo grande per essere pratica. D'altra parte, possiamo combinare le due tecniche mostrate sopra: prima spostate i bit, quindi indicizzate una tabella di ricerca. Per un valore a 24 bit che vogliamo solo il valore medio superiore, potremmo potenzialmente spostare i dati a destra di 12 bit e lasciare un valore a 12 bit per un indice di tabella. Un indice di tabella a 12 bit implica una tabella di 4096 valori, che potrebbe essere pratico.

EDIT: Una cosa che ho dimenticato di inserire.

La tecnica di indicizzazione in un array, invece di usare un if dichiarazione, può essere usato per decidere quale puntatore usare. Ho visto una libreria che implementava alberi binari e invece di avere due puntatori nominati ( pLeft e pRight o qualsiasi altra cosa) aveva una serie di puntatori di lunghezza 2 e utilizzava la tecnica del "bit di decisione" per decidere quale seguire. Ad esempio, invece di:

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

questa libreria farebbe qualcosa come:

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

Ecco un link a questo codice: Alberi neri rossi , Eternamente confuso


960
2017-07-22 08:29



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.

In effetti, l'array è partizionato in una zona contigua con data < 128 e un altro con data >= 128. Quindi dovresti trovare il punto di partizione con una ricerca dicotomica (usando Lg(arraySize) = 15 confronti), quindi effettuare 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ù veloce, che dà un approssimativo  soluzione per entrambi ordinati o non ordinati è: sum= 3137536; (assumendo una distribuzione veramente uniforme, 16384 campioni con valore atteso 191,5) :-)


881
2017-07-24 07:57



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

Per comprendere la previsione delle branche, è necessario prima capire Pipeline di 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. 4-stage pipeline in general

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: enter image description here

Quando la condizione restituisce false: enter image description here

Come risultato dell'attesa per il risultato dell'istruzione A, i cicli totali della CPU trascorsi 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: enter image description here

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ù lungo è il gasdotto, maggiore è la necessità di un bene 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.


696
2017-07-03 15:35