22 Domanda: Perché l'elaborazione di un array ordinato è più rapida rispetto all'elaborazione di un array non ordinato?

domanda creata a Tue, Jun 4, 2019 12:00 AM

Ecco un pezzo di codice C ++ che mostra un comportamento 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 pensavo che questo potesse essere solo un linguaggio o un'anomalia del compilatore, quindi l'ho provato con 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 simile ma meno estremo.


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

  • Che cosa sta succedendo?
  • Perché l'elaborazione di un array ordinato è più veloce rispetto all'elaborazione di un array non ordinato? Il codice riassume alcuni termini indipendenti, quindi l'ordine non dovrebbe avere importanza.
23151
  1. Solo per la cronaca. Su Windows /VS2017 /i7-6700K 4GHz non c'è differenza tra due versioni. Ci vogliono 0,6 secondi per entrambi i casi. Se il numero di iterazioni nel loop esterno è aumentato di 10 volte, il tempo di esecuzione aumenta di 10 volte in 6 secondi in entrambi i casi.
    2017-11-15 20: 45: 37Z
  2. @ user194715: qualsiasi compilatore che usi un cmov o altra implementazione senza ramo (come l'auto-vettorizzazione con pcmpgtd) avrà prestazioni che non dipendono dai dati di alcuna CPU. Ma se è ramoso, sarà ordinabile in base a qualsiasi CPU con un'esecuzione speculativa out-of-order. (Anche le CPU ad alto rendimento in ordine utilizzano la previsione del ramo per evitare bolle di recupero /decodifica sui rami presi, la penalità di errore è minore).
    2017-12-26 07: 14: 57Z
  3. @ KyleMit ha qualcosa a che fare con entrambi? Non ho letto molto su entrambi
    2018-01-10 06: 26: 02Z
  4. @ mohitmun, entrambi questi difetti di sicurezza rientrano in un'ampia categoria di vulnerabilità classificate come " branch target injection "attacchi
    2018-01-10 14: 26: 37Z
  5. 22 risposte                              22                         

    Sei una vittima della previsione del ramo fallita.


    Che cos'è Predizione di ramo?

    Considera uno svincolo ferroviario:

     Immagine che mostra un nodo ferroviario Immagine di Mecanismo, tramite Wikimedia Commons. Utilizzato sotto la licenza CC-By-SA 3.0 .

    Ora per il gusto di argomentare, supponiamo che questo sia tornato nel 1800 - prima della lunga distanza o della 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 poi imposti lo switch in modo appropriato.

    I treni sono pesanti e hanno molta inerzia. Quindi impiegano un'eternità per avviarsi 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 ​​strong>, thIl treno non dovrà mai fermarsi.
    Se indovina troppo spesso , il treno impiegherà molto tempo per fermarsi, eseguire il backup e riavviare.


    Considera un'istruzione if: a livello di processore, è un'istruzione branch:

    Schermata del codice compilato contenente un'istruzione if

    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 pipeline lunghe. Quindi impiegano un'eternità per "scaldarsi" e "rallentare".

    C'è un modo migliore? Indovina in quale direzione andrà il ramo!

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

    Se indovini giusto ogni volta ​​strong>, l'esecuzione non dovrà mai interrompersi.
    Se indovina troppo spesso , passi molto tempo a rallentare, a rallentare e a riavviare.


    Questa è una previsione di ramo. 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, in che modo indovinerai strategicamente per ridurre al minimo 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 un modo ogni tre volte, indovina lo stesso ...

    In altre parole, provi a identificare un pattern e seguilo. Questo è più o meno come funzionano i predittori di ramo.

    La maggior parte delle applicazioni ha rami ben educati. Pertanto, i predittori di succursali moderni raggiungeranno generalmente i tassi di successo di > 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 in alto, il colpevole è questa frase if:

     
    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. Successivamente, entreranno tutti nella dichiarazione 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 eccetto per le poche iterazioni dopo che ha cambiato 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 una supposizione casuale).

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

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

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

    Benchmark: 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: esiste 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 empirica generale è di evitare la ramificazione dipendente dai dati nei loop critici (come in questo esempio).


    Aggiornamento:

    • GCC 4.6.1 con -O3 o -ftree-vectorize su x64 è in grado di generare uno spostamento 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 C ++ Compiler (ICC) 11 fa qualcosa di miracoloso. È interscambii due cicli , 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 ciclo di test per sconfiggere il benchmark ...

    • Se si fornisce al compilatore Intel il codice senza diramazione, è appena fuori destra per vettorializzare ... ed è altrettanto veloce come con il ramo (con lo scambio di loop).

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

        
    30295
    2019-05-27 12: 42: 11Z
    1. @ Mysticial Per evitare lo spostamento hack potresti scrivere qualcosa come int t=-((data[c]>=128)) per generare la maschera. Anche questo dovrebbe essere più veloce. Sarebbe interessante sapere se il compilatore è abbastanza intelligente da inserire una mossa condizionale o meno.
      2012-06-27 16: 47: 51Z
    2. @ phonetagger Dai un'occhiata a questa domanda di follow-up: stackoverflow.com/questions/11276291/... Intel Compiler è arrivato abbastanza vicino per eliminare completamente il ciclo esterno.
      2012-07-10 17: 08: 39Z
    3. @ Novelocrat Solo la metà è corretta. Spostare un 1 nel bit del segno quando è zero è effettivamente UB. Questo perché ha overflow di interi con segno. Ma spostare 1 su un bit di segno è IB. Spostando a destra un numero intero con segno negativo è IB. Puoi entrare nell'argomento che quel C /C ++ non richiede che il bit più in alto sia l'indicatore del segno. Ma i dettagli di implementazione sono IB.
      2013-08-18 21: 04: 38Z
    4. @ Mysticial Grazie mille per il collegamento. Sembra promettente. Lo farò comunque. Un'ultima richiesta. Ci dispiace, ma per favore non importa, potresti dirmi come potresti fare questo int t = (data[c] - 128) >> 31; sum += ~t & data[c]; per sostituire la condizione originale se sopra?
      2014-03-08 20: 05: 22Z
    5. La grammatica in me vuole che pensi che questo dovrebbe leggere "... vittima della previsione del ramo fallire ure " piuttosto che solo ".. . vittima del fallimento della previsione del ramo. "
      2015-06-27 11: 35: 58Z

    Previsione filiale.

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

        
    3907
    2016-08-05 07: 53: 10Z
    1. La previsione dei branch funziona meglio su array ordinati rispetto a array con pattern diversi? Ad esempio, per l'array - > {10, 5, 20, 10, 40, 20, ...} l'elemento successivo nell'array dal modello è 80. Questo tipo di array verrà accelerato dalla previsione del ramo in cui l'elemento successivo è 80 qui se il modello è seguito? O di solito aiuta solo con array ordinati?
      2014-09-23 18: 58: 12Z
    2. Quindi praticamente tutto ciò che ho imparato convenzionalmente su big-O è fuori dalla finestra? È meglio sostenere un costo di smistamento rispetto a un costo di ramificazione?
      2014-10-30 07: 51: 58Z
    3. @ AgrimPathak Dipende. Per input non troppo grandi, un algoritmo con una complessità più elevata è più veloce di un algoritmo con complessità inferiore quando le costanti sono più piccole per l'algoritmo con maggiore complessità. Dove il punto di pareggio può essere difficile da prevedere. Inoltre, confronta questo , la località è importante. Big-O è importante, ma non è l'unico criterio per le prestazioni.
      2014-10-30 10: 14: 12Z
    4. Quando si verifica la previsione dei branch? Quando la lingua saprà che l'array è ordinato? Sto pensando a una situazione di array che assomiglia a: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? questo oscuro 3 aumenterà il tempo di esecuzione? Sarà lungo come array non ordinato?
      2014-11-09 13: 37: 18Z
    5. @ La previsione di FilipBartuzi Branch avviene nel processore, sotto il livello di lingua (ma il linguaggio può offrire modi per dire al compilatore cosa è probabile, quindi il compilatore può emettere il codice adatto a tale). Nel tuo esempio, l'out-of-order 3 condurrà a una errata interpretazione del ramo (per condizioni appropriate, dove 3 dà un risultato diverso da 1000), e quindi l'elaborazione di tale array richiederà probabilmente un paio di dozzina o cento nanosecondi più a lungo di un array ordinati, quasi mai visibili. Quanto costa il tempo è alto tasso di mispredictions, un errore di battitura per 1000 non è molto.
      2014-11-09 13: 49: 37Z

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

    Ora, se guardiamo il codice

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

    possiamo scoprire che il significato di questo particolare ramo if... else... è aggiungere qualcosa quando una condizione è soddisfatta. Questo tipo di ramo può essere facilmente trasformato in un'istruzione spostamento 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 si 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;
    

    Pur mantenendo la leggibilità, possiamo controllare il fattore di accelerazione.

    Su Intel Core i7 -2600K a 3,4 GHz e in modalità di rilascio di Visual Studio 2010 , il punto di riferimento è (formato copiato da Mysticial):

    86

     
    //  Branch - Random
    seconds = 8.885
    
    //  Branch - Sorted
    seconds = 1.528
    
    //  Branchless - Random
    seconds = 3.716
    
    //  Branchless - Sorted
    seconds = 3.71
    

    64

     
    //  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. Infatti, 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à, utilizziamo due funzioni max1 e max2.

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

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

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

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

    Su una macchina x86-64, GCC -S genera l'assieme 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 utilizza molto meno codice a causa dell'uso dell'istruzione cmovge. Ma il vero vantaggio è che max2 non prevede salti derivati, jmp, che comporterebbero una penalizzazione significativa delle prestazioni se il risultato previsto non è corretto.

    Quindi perché una mossa condizionale ha prestazioni migliori?

    In un tipico processore x86, 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 pipeline .

    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 necessitano 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 della cruscach quando la previsione è facile.

    Il libro Computer Systems: A Programmer's Perspective, seconda edizione spiega questo in dettaglio. Puoi consultare la Sezione 3.6.6 per Istruzioni di spostamento condizionale , l'intero Capitolo 4 per Architettura del processore , e la Sezione 5.11.2 per un trattamento speciale per Predizione dei rami e Misprediction sanzioni .

    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 il ramo e lo spostamento condizionale quando imprevedibile può aiutarci a scrivere codice con prestazioni migliori quando lo scenario diventa così complesso che il compilatore non può ottimizzarlo automaticamente.

        
    3144
    2019-05-27 12: 50: 22Z
    1. Non esiste un livello di ottimizzazione predefinito a meno che non si aggiunga -O alle righe di comando GCC. (E non puoi avere un inglese peggiore del mio;)
      2012-06-28 14: 04: 45Z
    2. Trovo difficile credere che il compilatore possa ottimizzare l'operatore ternario meglio di quanto possa fare l'if-statement equivalente. Hai dimostrato che GCC ottimizza l'operatore ternario a una mossa condizionale; tu non ho mostrato che non fa esattamente la stessa cosa per l'if-statement. Infatti, secondo Mystical sopra, GCC fa ottimizza l'if-statement su una mossa condizionale, il che renderebbe questa risposta completamente errata.
      2012-06-30 15: 29: 23Z
    3. @ WiSaGaN Il codice non dimostra nulla, perché le tue due parti di codice vengono compilate con lo stesso codice macchina. È di fondamentale importanza che le persone non abbiano l'idea che in qualche modo l'istruzione if nel tuo esempio sia diversa dal terenario nel tuo esempio. È vero che possiedi la somiglianza nel tuo ultimo paragrafo, ma ciò non cancella il fatto che il resto dell'esempio è dannoso.
      2012-10-11 03: 12: 02Z
    4. @ WiSaGaN Il mio downvote si trasformerebbe definitivamente in un upvote se hai modificato la risposta per rimuovere l'esempio ingannevole -O0 e per mostrare la differenza in ottimizzato asm sui tuoi due testicoli.
      2012-10-11 04: 13: 03Z
    5. @ UpAndAdam Al momento del test, VS2010 non può ottimizzare il ramo originale in una mossa condizionale anche quando si specifica un livello di ottimizzazione elevato, mentre gcc può.
      2013-09-14 15: 18: 02Z

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

    A partire dal loop 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 in:

     
    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 durante l'esecuzione del ciclo i, quindi puoi sollevare il if:

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

    Quindi, vedi che il ciclo interno può essere collassato in una singola espressione, supponendo che il modello a virgola mobile lo consenta (per esempio, viene lanciato /fp:fast)

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

    Quello è 100.000 volte più veloce di prima.

        
    2159
    2019-05-27 12: 51: 33Z
    1. Se vuoi imbrogliare, puoi anche prendere la moltiplicazione al di fuori del ciclo e fare sum * = 100000 dopo il ciclo.
      2012-10-11 01: 48: 01Z
    2. @ Michael - Credo che questo esempio sia in realtà un esempio di loop-invariant (LIH) e NON loop swap . In questo caso, l'intero ciclo interno è indipendente dal loop esterno e può quindi essere sollevato dall'esterno loop, dopo di che il risultato viene semplicemente moltiplicato per una somma superiore a i di un'unità = 1e 5. Non fa alcuna differenza per il risultato finale, ma volevo semplicemente impostare il record direttamente dal momento che questa è una pagina così frequentata.
      2013-03-04 12: 59: 11Z
    3. Anche se non nel semplice spirito dei cicli di scambio, il if interno a questo punto potrebbe essere convertito in: sum += (data[j] >= 128) ? data[j] * 100000 : 0; che il compilatore potrebbe essere in grado di ridurre a cmovge o equivalente.
      2013-05-15 11: 57: 16Z
    4. Il ciclo esterno serve a rendere il tempo impiegato dal loop interno abbastanza grande per il profilo. Allora, perché dovresti fare un ciclo di scambio. Alla fine, quel loop verrà comunque rimosso.
      2016-06-22 15: 45: 19Z
    5. @ saurabheights: domanda errata: perché il compilatore NON esegue il ciclo di swap. Microbenchmarks è difficile;)
      2016-12-29 13: 58: 53Z

    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 ramo, abilitato usando il flag --branch-sim=yes. Eseguendolo sugli esempi in questa domanda, con il numero di cicli esterni ridotti a 10000 e compilato con g++, si ottengono questi risultati:

    Ordinato:

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

    Celebrita:

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

    Drill down nell'output line-by-line prodotto da cg_annotate vediamo il ciclo in questione:

    Ordinato:

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

    Celebrita:

     
              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 smistata la linea if (data[c] >= 128) sta causando 164.050.007 rami condizionali erroneamente detti (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 i contatori della CPU.

     
    perf stat ./sumtest_sorted
    

    Ordinato:

     
     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
    

    Celebrita:

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

    Vedi il tutorial sul rendimento per ulteriori dettagli.

        
    1800
    2012-10-18 19: 20: 21Z
    1. Questo è spaventoso, nella lista non ordinata, ci dovrebbe essere il 50% di possibilità di colpire l'add. In qualche modo la previsione del ramo ha solo un tasso di errore del 25%, come può fare meglio del 50% di perdere?
      2013-12-09 04: 00: 09Z
    2. @ tall.b.lo: Il 25% è di tutti i rami - ci sono due rami nel ciclo, uno per data[c] >= 128 (che ha una percentuale di errore del 50% come suggerito) e una per la condizione di loop c < arraySize che ha una percentuale di errore di ~ 0%.
      2013-12-09 04: 29: 25Z

    Ho appena letto 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. si tratta di una piccola tabella e potrebbe essere memorizzata nella cache del processore e
    2. stai eseguendo le cose in un ciclo piuttosto stretto e /o il processore può precaricare i dati.

    Sfondo e perché

    Dal punto di vista del processore, la tua memoria è lenta. Per compensare la differenza di velocità, un paio di cache sono integrate nel processore (L1/Cache L2). 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 'carico' 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 - nel peggiore dei casi è necessario tornare indietro e attendere effettivamente un carico di memoria, operazione che durerà per sempre ( 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 pattern di accesso alla memoria è prevedibile, il processore lo caricherà nella sua cache veloce e tutto andrà bene.

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

    Costruire una tabella

    Quindi abbiamo capito che possiamo creare un piccolo tavolo. 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). Vuoi che il tuo contributo venga tradotto dalla funzione di ricerca su una "chiave unica" nella tua tabella, che ti dà semplicemente la risposta di tutto il lavoro che volevi che facesse.

    In questo caso: > = 128 significa che possiamo mantenere il valore, < 128 significa che ci sbarazziamo di esso. Il modo più semplice per farlo è usare un 'AND': se lo teniamo, noi e lui con 7FFFFFFF; se vogliamo sbarazzarci di esso, noi di AND lo 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 di 7FFFFFFFF.

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

    Bene, non esattamente ...: -)

    C'è stato un bel po 'di lavoro sull'eliminazione di questo ramo per le lingue gestite. Ad 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 hai problemi con le ricerche nelle lingue gestite - la chiave è aggiungere un & 0x[something]FFF alla tua funzione di ricerca per rendere prevedibile il controllo dei confini - e guardarlo andare più veloce.

    Il risultato di questo caso

     
    // Generate data
    int arraySize = 32768;
    int[] data = new int[arraySize];
    
    Random random = new Random(0);
    for (int c = 0; c < arraySize; ++c)
    {
        data[c] = random.Next(256);
    }
    
    /*To keep the spirit of the code intact, 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();
    
        
    1259
    2019-01-16 04: 47: 21Z
    1. Vuoi bypassare il predittore del ramo, perché? È un'ottimizzazione.
      2013-04-24 17: 50: 33Z
    2. Perché nessun ramo è meglio di un ramo :-) In molte situazioni questo è semplicemente molto più veloce ... se stai ottimizzando, ne vale sicuramente la pena provare. Lo usano anche un po 'in F.ex. graphics.stanford.edu/~seander/bithacks.html
      2013-04-24 21: 57: 13Z
    3. In generale le tabelle di ricerca possono essere veloci, ma hai eseguito i test per questa particolare condizione? Avrai ancora una condizione di ramo nel tuo codice, solo ora verrà spostata nella parte di generazione della tabella di ricerca. Ancora non otterresti il ​​tuo potenziamento
      2013-12-19 21: 45: 03Z
    4. @ Zain se vuoi davvero sapere ... Sì: 15 secondi con il ramo e 10 con la mia versione. Indipendentemente da ciò, è una tecnica utile per sapere in entrambi i modi.
      2013-12-20 18: 57: 29Z
    5. Perché non sum += lookup[data[j]] dove lookup è un array con256 voci, le prime a zero e le ultime a essere uguale all'indice?
      2014-03-12 12: 17: 49Z

    Poiché i dati vengono distribuiti tra 0 e 255 quando l'array è ordinato, intorno alla prima metà delle iterazioni non verrà inserito lo stato if (l'istruzione if è condivisa di seguito).

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

    La domanda è: cosa rende l'istruzione sopra 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 in quale direzione un ramo (ad 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

    Le prestazioni di un documento if dipendono 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 statement if 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 loop con diversi pattern 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 pattern " cattivo " true-false può rendere una dichiarazione if fino a sei volte più lenta di un pattern " buono "! Ovviamente, quale modello è buono e quale è cattivo dipende dalle esatte istruzioni generate dal compilatore e dal processore specifico.

    Quindi non ci sono dubbi sull'impatto della previsione dei rami sulle prestazioni!

        
    1129
    2019-02-27 10: 58: 32Z
    1. Non visualizzi i tempi del pattern TF "casuale".
      2013-02-23 02: 31: 21Z
    2. @ MooingDuck 'Causa non farà alcuna differenza - quel valore può essere qualsiasi cosa, ma sarà ancora nei limiti di queste soglie. Allora perché mostrare un valore casuale quando conosci già i limiti? Anche se sono d'accordo sul fatto che tu possa mostrarne uno per completezza, e 'solo per il gusto di farlo'.
      2016-03-28 12: 58: 51Z
    3. @ cst1992: In questo momento il suo timing più lento è TTFFTTFFTTFF, che sembra, per il mio occhio umano, abbastanza prevedibile. Il casuale è intrinsecamente imprevedibile, quindi è del tutto possibile che sia ancora più lento, e quindi al di fuori dei limiti qui mostrati. OTOH, potrebbe essere che TTFFTTFF colpisca perfettamente il caso patologico. Non posso dire, dal momento che non ha mostrato i tempi per caso.
      2016-03-28 18: 27: 16Z
    4. @ MooingDuck Per un occhio umano, "TTFFTTFFTTFF" è una sequenza prevedibile, ma quello di cui stiamo parlando è il comportamento del predittore di ramo incorporato in una CPU. Il predittore di branche non è un riconoscimento di pattern di livello AI; è molto semplice. Quando si alternano solo rami non predice bene. Nella maggior parte del codice, i rami si comportano quasi sempre; considera un ciclo che viene eseguito migliaia di volte. Il ramo alla fine del loop torna all'inizio del ciclo 999 volte, quindi la millesima volta fa qualcosa di diverso. Un predittore di ramo molto semplice funziona bene, di solito.
      21-07-2017 21: 07: 37Z
    5. @ steveha: Penso che tu stia facendo ipotesi su come funziona il predittore del ramo CPU, e non sono d'accordo con questa metodologia. Non so quanto sia avanzato quel predittore di branche, ma credo che sia molto più avanzato di te. Probabilmente hai ragione, ma le misure sarebbero sicuramente buone.
      21-07-2016 21: 10: 18Z

    Un modo per evitare il branch prerrori di edizione è quello di costruire 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 i valori > = 128. Ciò significa che possiamo facilmente estrarre un singolo bit che ci dirà se vogliamo un valore o no: spostando i dati sui 7 bit corretti, restiamo con 0 bit o 1 bit e vogliamo aggiungere il valore solo quando abbiamo 1 bit. Chiamiamo questo bit il "bit di decisione".

    Usando il valore 0/1 del bit di decisione come indice in un array, possiamo creare 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 sui dati casuali rispetto alla versione con una dichiarazione 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 lut in modo inaspettato per "Tabella LookUp" 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 stata 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 della metà 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.

    La tecnica di indicizzazione in una matrice, invece di utilizzare un'istruzione if, può essere utilizzata per decidere quale puntatore utilizzare. 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 lunghezza 2 e usava la tecnica del "bit di decisione" per decidere quale seguire. Ad esempio, anziché:

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

    questa libreria farebbe qualcosa del tipo:

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

    Ecco un link a questo codice: Red Black Trees , Eternamente confuso

        
    1051
    2019-05-27 13: 08: 32Z
    1. A destra, puoi anche usare il bit direttamente e moltiplicare (data[c]>>7 - che è discusso anche qui da qualche parte); Ho intenzionalmente lasciato fuori questa soluzione, ma ovviamente hai ragione. Solo una piccola nota: la regola empirica delle tabelle di ricerca è che se si adatta a 4KB (a causa della memorizzazione nella cache), funzionerà - preferibilmente rendere la tabella più piccola possibile. Per le lingue gestite lo spingo a 64 KB, per linguaggi di basso livello come C ++ e C, probabilmente lo riconsidererei (è solo la mia esperienza). Dal typeof(int) = 4, proverei ad attenermi a un massimo di 10 bit.
      2013-07-29 12: 05: 24Z
    2. Penso che l'indicizzazione con il valore 0/1 sarà probabilmente più veloce di un multiplo intero, ma suppongo che se le prestazioni sono davvero critiche dovresti profilarle. Sono d'accordo sul fatto che piccole tabelle di ricerca siano essenziali per evitare la pressione della cache, ma chiaramente se hai una cache più grande puoi farla franca con una tabella di ricerca più grande, quindi il 4KB è più una regola empirica che una regola complessa. Penso che intendessi sizeof(int) == 4? Questo sarebbe vero per 32-bit. Il mio cellulare di due anni ha una cache L1 da 32KB, quindi potrebbe funzionare anche una tabella di ricerca 4K, soprattutto se i valori di ricerca erano un byte anziché un int.
      2013-07-29 22: 02: 13Z
    3. Forse mi manca qualcosa ma nel tuo j è uguale a 0 o 1 metodo perché non devi semplicemente moltiplicare il valore per j prima di aggiungerlo invece di usare l'indicizzazione dell'array (probabilmente dovrebbe essere moltiplicato per 1-j anziché j)
      2014-03-04 15: 38: 24Z
    4. @ steveha La moltiplicazione dovrebbe essere più veloce, ho provato a cercarlo nei libri Intel, ma non sono riuscito a trovarlo ... in entrambi i casi, anche il benchmark mi dàqui.
      2014-03-18 08: 45: 05Z
    5. @ steveha P.S .: un'altra possibile risposta sarebbe int c = data[j]; sum += c & -(c >> 7); che non richiede alcuna moltiplicazione.
      2014-03-18 08: 52: 11Z

    Nel caso ordinato, puoi fare di meglio che fare affidamento sulla previsione dei rami o su qualsiasi 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 (utilizzando Lg(arraySize) = 15 confronti), quindi fare una scala accumulo 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 fornisce una soluzione approssimativa per entrambi ordinati o non ordinati è: sum= 3137536; (assumendo una distribuzione veramente uniforme, 16384 campioni con valore atteso 191,5) : -)

        
    950
    2019-05-11 11: 31: 12Z
    1. sum= 3137536 - intelligente. Questo ovviamente non è il punto della domanda. La domanda riguarda chiaramente la spiegazione di caratteristiche di prestazione sorprendenti. Sono incline a dire che l'aggiunta di fare std::partition invece di std::sort è preziosa. Anche se la domanda reale si estende a qualcosa di più del semplice benchmark dato.
      2013-07-24 16: 31: 30Z
    2. @ DeadMG: questa non è la ricerca dicotomica standard per una determinata chiave, ma una ricerca per l'indice di partizionamento; richiede un solo confronto per iterazione. Ma non fare affidamento su questo codice, non l'ho verificato. Se sei interessato a una corretta implementazione garantita, fammi sapere.
      2013-07-24 20: 37: 31Z

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

    Per comprendere la previsione delle diramazioni, devi 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, leggi questo esempio su Wikipedia .

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

    1. IF: recupera le istruzioni dalla memoria   
    2. ID - Decodifica l'istruzione   
    3. EX - Esegue l'istruzione   
    4. WB - Scrivi di nuovo nel registro della CPU

    Conduttura a 4 stadi in generale per 2 istruzioni. Conduttura a 4 stadi in generale

    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 all'istruzione C dipende dal risultato dell'istruzione A. Quindi la pipeline sarà simile a questa.

    quando la condizione restituisce true: inserisci la descrizione dell'immagine qui

    Se la condizione restituisce false: inserisci la descrizione dell'immagine qui

    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 true sia per false) sono 7.

    Che cos'è la previsione delle filiali?

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

    In caso di ipotesi corretta, la pipeline è simile a questa: inserisci la descrizione dell'immagine qui

    Se in seguito 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 microprocessori moderni 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 di 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 elementi nuovi di avvio 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. Dopo di ciò, fallirà per un po 'di tempo e sarà corretto quando vedrà un errore di previsione del ramo 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 in 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 produrre più cicli CPU rispetto alla matrice ordinata.

        
    774
    2018-04-10 20: 13: 26Z
    1. come vengono eseguite due istruzioni insieme? questo è fatto con core CPU separati o l'istruzione della pipeline è integrata nel singolo core della cpu?
      2017-10-11 14: 49: 42Z
    2. @ M.kazemAkhgary È tutto all'interno di un nucleo logico. Se sei interessato, questo è ben descritto ad esempio in Manuale per gli sviluppatori di software Intel
      2017-11-03 07: 45: 12Z

    Una risposta ufficiale potrebbe essere

    1. Intel - Evitare il costo della mispredicione delle filiali
    2. Intel - Riorganizzazione di rami e loop per prevenire i malintenzionati
    3. Documenti scientifici - architettura dei computer di previsione delle branche
    4. Libri: J.L. Hennessy, D.A. Patterson: architettura del computer: un approccio quantitativo
    5. Articoli su pubblicazioni scientifiche: T.Y. Yeh, Y.N. Patt ha fatto molti di questi su previsioni di ramo.

    Puoi anche vedere da questo delizioso diagramma perché il predittore di branchi si confonde.

     diagramma di stato a 2 bit

    Ogni elemento nel codice originale è un valore casuale

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

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

    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.


    678
    2017-01-31 11: 39: 33Z

    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 le seguenti:  

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

    o allo stesso modo:

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

    Sia il likely() che il unlikely() sono in effetti delle macro definite usando qualcosa come il __builtin_expect del GCC per 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. Vedi 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 informarne il compilatore? In questo modo, per impostazione predefinita, la previsione del ramo presuppone che la condizione sia falsa.

        
    645
    2016-10-28 10: 28: 11Z

    Le operazioni booleane usate frequentemente in C ++ generano molte ramificazioni nel programma compilato. Se questi rami sono all'interno di cicli e sono difficili da prevedere, possono rallentare notevolmente l'esecuzione. Le variabili booleane vengono memorizzate come numeri interi a 8 bit con il valore 0 per false e 1 per 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 0 o 1, ma gli operatori che hanno booleani come output non possono produrre altro valore di 0 o 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 è tipicamente 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 0 e 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 precedente può essere ottimizzato se a e b sono stati inizializzati su valori validi o se provengono da operatori che producono output booleano. Il codice ottimizzato ha questo aspetto:

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

    char viene utilizzato al posto di bool per poter utilizzare gli operatori bit a 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 a e b hanno valori diversi da 0 o 1. L'operatore AND (&) e l'operatore EXCLUSIVO (^) possono fornire risultati incoerenti se gli operandi hanno valori diversi da 0 e 1.

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

     
    bool a, b;
    b = !a;
    

    può essere ottimizzato per:

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

    a && b non può essere sostituito con a & b se b è un'espressione che non dovrebbe essere valutata se a è false (&& non valuterà b, & sarà). Allo stesso modo, a || b non può essere sostituito con a | b se b è un'espressione che non dovrebbe essere valutata se 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 esistapect l'espressione && per generare molte errate previsioni dei rami).

        
    614
    2019-05-30 16: 34: 26Z

    Questo è sicuro! ...

    La previsione del ramo rallenta la logica, a causa dello switching 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, hai bisogno di molte trasformazioni ed elaborazioni che facciano rallentare il tuo codice di sicuro ...

    Guarda l'immagine che ho creato per te qui sotto. Quale strada sta per finire più velocemente?

     Branch Prediction

    Quindi, a livello di codice, la previsione dei rami causa un rallentamento del processo ...

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

    1. Static

    2. Dinamico

     Branch Prediction

      

    La previsione del ramo statico viene utilizzata la prima volta dal microprocessore   si incontra un ramo condizionale e la previsione del ramo dinamico è   utilizzato per le esecuzioni successive del codice filiale condizionale.

         

    Per scrivere efficacemente il tuo codice per approfittare di questi   regole, quando scrivi le istruzioni if-else o switch , controlla di più   prima i casi comuni e procedono progressivamente verso il meno comune.   I loop non richiedono necessariamente alcun ordine speciale di codice per   previsione del ramo statico, come unica condizione dell'iter iteratore   è normalmente usato.

        
    289
    2018-05-03 06: 35: 51Z

    Questa domanda ha già ricevuto una risposta eccellente molte volte. Vorrei tuttavia attirare l'attenzione del gruppo su un'altra interessante analisi.

    Recentemente questo esempio (modificato leggermente) è stato usato anche come un modo per dimostrare come un 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 trascorre la maggior parte del suo tempo sia in ordinata che in ampli; caso non ordinato. Infine, il pezzo mostra anche come usare una caratteristica poco conosciuta dell'HAL (Hardware Abstraction Layer) per determinare quanta parte della mis- tipazione delle branche sta accadendo nel caso non ordinato.

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

        
    266
    2017-01-17 18: 02: 31Z
    1. Questo è un articolo molto interessante (in effetti, ho appena letto tutto), ma come risponde alla domanda?
      2018-03-16 12: 47: 19Z
    2. @ PeterMortensen Sono un po 'sconcertato dalla tua domanda. Per esempio qui c'è una linea rilevante da quella parte: When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. L'autore sta cercando di discutere la profilazione nel contesto del codice postato qui e nel processo cercando di spiegare perché il caso ordinato è molto più veloce.
      2018-03-16 15: 37: 16Z

    Come ciò che è già stato menzionato da altri, ciò che sta dietro al mistero è Predictor ramo .

    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 del computer, un predittore di ramo è un   circuito digitale che cerca di indovinare da che parte un ramo (ad esempio un   se-allora-altra struttura) andrà prima che questo sia noto per certo. Il   scopo del predittore del ramo è quello di migliorare il flusso nel   pipeline di istruzioni. I predittori di ramo svolgono un ruolo fondamentale in   ottenendo alte prestazioni efficaci in molte pipeline moderne   architetture a microprocessore come x86.

         

    La ramificazione bidirezionale viene solitamente implementata con un salto condizionato   istruzioni. Un salto condizionato può essere "non preso" e continuare   esecuzione con il primo ramo di codice che segue immediatamente   dopo il salto condizionale, o può essere "preso" e saltare a   posto diverso nella memoria del programma in cui si trova il secondo ramo del codice   immagazzinato. Non è noto per certo se un salto condizionale sarà   preso o non preso fino a quando la condizione è stata calcolata e il   il salto condizionale ha superato la fase di esecuzione nell'istruzione   gasdotto (vedi figura 1).

     figura 1

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

    1. Senza il predittore di ramo.
      

    Senza la previsione del ramo, il processore dovrebbe attendere fino al   l'istruzione di salto condizionale ha superato la fase di esecuzione prima del   la prossima istruzione può 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 andare nella pipeline fino a quando non viene eseguita l'istruzione di salto condizionale.

     senza predittore di ramo

    Ci vorranno 9 cicli di clock per completare 3 istruzioni.

    1. Usa il Predictor del ramo e non fare un salto condizionale. Supponiamo che il predetto sia non prendendo il salto condizionale.

     inserisci la descrizione dell'immagine qui

    Ci vorranno 7 cicli di clock per completare 3 istruzioni.

    1. Utilizza il Predittore di rami e fai un salto condizionale. Supponiamo che il predetto sia non prendendo il salto condizionale.

     inserisci la descrizione dell'immagine qui

    Ci vorranno 9 cicli di clock per completare 3 istruzioni.

      

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

    Come puoi vedere, sembra che non abbiamo un motivo per non utilizzare Branch Predictor.

    È una demo abbastanza semplice che chiarisce la parte fondamentale di Branch Predictor. Se quei gif sono fastidiosi, non esitate a rimuoverli dalla risposta e i visitatori possono anche ottenere la demo da BranchPredictorDemo

        
    183
    2019-06-04 16: 20: 33Z

    Guadagno pronostico delle branchie!

    È importante capire che il malinteso dei rami 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'è un'istruzione if-else \switch, l'espressione deve essere valutata per determinare quale blocco deve essere eseguito. Nel codice assembly generatodal compilatore, vengono inserite le istruzioni condizionali branch .

    Un'istruzione branch può far sì che un computer inizi a eseguire una sequenza di istruzioni diversa e quindi devia dal suo comportamento predefinito delle istruzioni di esecuzione nell'ordine (cioè se l'espressione è falsa, il programma salta il codice del blocco if) in base ad alcuni condizione, 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 blocco if 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 potresti scegliere il percorso1 e se sei stato fortunato (il percorso 1 è corretto percorso), quindi non dovevi aspettare che il tuo partner controllasse la mappa (hai salvato il tempo che gli sarebbe occorso per controllare la mappa), altrimenti tornerai indietro.

    Mentre lo svuotamento delle condotte è velocissimo, 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  \--------------------------------
    
        
    172
    2018-03-16 12: 30: 45Z

    Riguarda la 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 neurali o varianti di prediction branch a due livelli, forniscono una migliore accuratezza della previsione, ma consumano più potenza e la complessità aumenta esponenzialmente.

    • Oltre a questo, nelle tecniche di predizione complessa il tempo necessario 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 di branch è essenzialmente un problema di ottimizzazione (minimizzazione) in cui l'enfasi è posta su un tasso di mancato tasso minimo, basso consumo energetico e bassa complessità con risorse minime.

    Esistono in realtà tre diversi tipi di filiali:

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

    Rami condizionali precedenti : il PC viene modificato in modo che punti 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.

    Rami incondizionati : include salti, chiamate di procedure e resi senza condizioni specifiche. 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 "compare" 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 predizione dei rami.) p>

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

    References:

    116
    2018-03-16 10: 57: 23Z

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

    È possibile avere una condizione di arresto invece di 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), may be in some other part of the code
     std::sort(data, data + arraySize, std::greater<int>());
    
     for (unsigned c = 0; c < arraySize; ++c) {
           if (data[c] < 128) {
                  break;
           }
           sum += data[c];               
     }
    
        
    110
    2019-03-05 09: 58: 40Z
    1. Giusto, ma il costo di installazione di ordinare l'array è O (N log N), quindi interrompere in anticipo non ti aiuta se l'unico motivo per cui stai ordinando l'array è essere in grado di rompere presto. Se, tuttavia, hai altri motivi per preordinare l'array, allora sì, questo è prezioso.
      2018-11-06 12: 28: 29Z
    2. @ LukeHutchison buona osservazione; si prega di vedere la mia risposta qui sotto per una presa diversa.
      2019-02-27 11: 47: 22Z
    3. Dipende quante volte si ordinano i dati rispetto a quante volte si loop su di esso. L'ordinamento in questo esempio è solo un esempio, non deve essere prima del ciclo
      2019-02-27 12: 23: 22Z
    4. Sì, questo è esattamente il punto che ho fatto nel mio primo commento :-) Dici "La previsione del ramo mancherà solo una volta." Ma non si contano i fallimenti di predizione di ramo O (N log N) all'interno dell'algoritmo di ordinamento, che in realtà è maggiore delle mancate previsioni di ramo O (N) nel caso non ordinato. Quindi è necessario utilizzare l'interezza dei dati ordinati O (log N) per pareggiare in pareggio (probabilmente in realtà più vicino a O (10 log N), a seconda dell'algoritmo di ordinamento, ad esempio per quicksort, a causa di errori di cache - mergesort è più coerente con la cache, quindi è necessario avvicinarsi agli usi O (2 log N) per pareggiare in pareggio.)
      2019-02-28 12: 28: 14Z
    5. Un ottimizzazione significativa sarebbe di fare solo "mezzo quicksort", ordinando solo gli elementi inferiori al valore di pivot di destinazione di 127 (assumendo tutto meno di o uguale a il pivot viene ordinato dopo il pivot). Una volta raggiunto il pivot, somma gli elementi prima del pivot. Questo dovrebbe essere eseguito nel tempo di avvio O (N) anziché in O (N log N), anche se ci saranno ancora molti errori di previsione del ramo, probabilmente dell'ordine di O (5 N) in base ai numeri che ho dato prima, dal è un mezzo quicksort.
      2019-02-28 12: 34: 48Z

    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
    
        
    106
    2018-05-14 14: 01: 18Z
    1. Stai dicendo che ogni istruzione può essere condizionata? Quindi, più istruzioni con il suffisso GE potrebbero essere eseguite in sequenza, senza cambiare il valore di R3 tra?
      2018-05-14 14: 04: 03Z
    2. Sì, corretto, ogni istruzione può essere condizionata da ARM, almeno nei set di istruzioni a 32 e 64 bit. C'è un campo di condizioni dedicato a 4 bit. Puoi averediverse istruzioni di seguito con la stessa condizione, ma ad un certo punto, se la possibilità che la condizione sia falsa non è trascurabile, allora è più efficiente aggiungere un ramo.
      2018-05-15 17: 06: 42Z
    3. L'altra innovazione in ARM è l'aggiunta del suffisso dell'istruzione S, anche opzionale su (quasi) tutte le istruzioni, che se assente, impedisce alle istruzioni di modificare i bit di stato (con l'eccezione dell'istruzione CMP, il cui compito è impostare bit di stato, quindi non ha bisogno del suffisso S). Ciò consente di evitare le istruzioni CMP in molti casi, purché il confronto sia con zero o simile (ad esempio SUBS R0, R0, # 1 imposterà il bit Z (Zero) quando R0 raggiunge zero). Le condizioni e il suffisso S hanno zero costi generali. È un bel ISA.
      2018-05-15 17: 06: 54Z
    4. Non aggiungere il suffisso S ti permette di avere diverse istruzioni condizionali di fila senza preoccuparti che uno di loro possa cambiare i bit di stato, che altrimenti potrebbero avere l'effetto collaterale di saltando il resto delle istruzioni condizionali.
      2018-05-15 17: 08: 22Z

    Le matrici ordinate vengono elaborate più velocemente di una matrice non ordinata, a causa di un fenomeno chiamato previsione delle diramazioni.

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

    Effettuare una previsione errata 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. Una previsione errata comporta la ripetizione dello stesso passo, fino a quando si verifica una previsione corretta.

    La risposta alla tua domanda è molto semplice.

    In una matrice non ordinata, il computer fa più previsioni, portando a una maggiore possibilità di errori. Considerando che, in un array ordinato, il computer fa meno previsioni, riducendo la possibilità di errori. Fare più previsioni richiede più tempo.

    Matrice ordinata: strada dritta     ____________________________________________________________________________________     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -     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 nel computer, e spero che questo ti abbia aiutato a capire meglio.


    Inoltre, desidero citare @Simon_Weaver dai commenti:

      

    Non fa meno previsioni - fa meno previsioni sbagliate. Deve ancora prevedere ogni volta attraverso il loop ...

        
    96
    2019-05-27 12: 47: 18Z
    1. "In parole semplici" - Trovo che la tua spiegazione sia meno semplice dell'altra con i treni e molto meno accurata di una qualsiasi altra risposta, sebbene Non sono un principiante. Sono molto curioso del perché ci siano così tanti upvotes, forse uno dei futuri uptot può dirmi?
      2018-07-04 13: 54: 21Z
    2. @ Sinatr probabilmente è basato sull'opinione pubblica, io stesso l'ho trovato abbastanza buono da svaligiarlo, non è accurato come altri esempi, questo è il punto: dare via il risposta (come possiamo tutti concordare che la previsione delle branche è coinvolta qui) senza che i lettori debbano fare delle spiegazioni tecniche come facevano gli altri (molto bene). E penso che l'abbia fatto abbastanza bene.
      2018-07-09 12: 45: 50Z
    3. Non fa meno previsioni - fa meno previsioni sbagliate, ma deve sempre prevedere per ogni ciclo.
      2018-07-16 01: 28: 03Z
    4. Oh tuo corretto, mio ​​male, grazie @Simon_Weaver, lo correggo tra qualche tempo, o per favore puoi modificarlo e poi lo approverò , grazie in anticipo ...
      2018-07-16 05: 52: 47Z

    L'assunto da altre risposte che è necessario ordinare i dati non è corretto.

    Il seguente codice non ordina l'intero array, ma solo i segmenti di 200 elementi di esso, e quindi esegue il più veloce.

    L'ordinamento delle sole sezioni k completa la preelaborazione in tempo lineare anziché n.log(n).

     
    #include <algorithm>
    #include <ctime>
    #include <iostream>
    
    int main() {
        int data[32768]; const int l = sizeof data / sizeof data[0];
    
        for (unsigned c = 0; c < l; ++c)
            data[c] = std::rand() % 256;
    
        // sort 200-element segments, not the whole array
        for (unsigned c = 0; c + 200 <= l; c += 200)
            std::sort(&data[c], &data[c + 200]);
    
        clock_t start = clock();
        long long sum = 0;
    
        for (unsigned i = 0; i < 100000; ++i) {
            for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }
    
        std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
        std::cout << "sum = " << sum << std::endl;
    }
    

    Ciò "dimostra" anche che non ha nulla a che fare con alcun problema algoritmico come l'ordinamento, ed è in effetti una previsione di ramo.

        
    17
    2019-02-28 15: 24: 59Z
    1. Non vedo davvero come questo provi qualcosa? L'unica cosa che hai mostrato è che "non fare tutto il lavoro di smistamento dell'intero array richiede meno tempo rispetto all'ordinamento dell'intero array". La tua affermazione che questo "è anche più veloce" dipende molto dall'architettura. Vedi la mia risposta su come funziona su ARM. PS puoi rendere il tuo codice più veloce su architetture non ARM inserendo la sommatoria all'interno del ciclo di blocchi di 200 elementi, ordinando al contrario, e quindi usando il suggerimento di Yochai Timmer di interrompere una volta ottenuto un valore fuori intervallo. In questo modo, ogni sommatoria dei blocchi di 200 elementi può essere terminata anticipatamente.
      2019-02-28 12: 18: 29Z
    2. @ LukeHutchison La dimostrazione è per l'OP, non per un risponditore ben informato come te. Per l'OP ciò annulla l'ipotesi che l'ordinamento abbia a che fare con l'elaborazione più veloce (vedi la formulazione del titolo della domanda). "Esegue il più veloce" in senso algoritmico su un'architettura per scopi generali - ARM è un caso speciale. Il suggerimento di Yochai Timmer è un'ottimizzazione ponderata, che non è algoritmica in senso ampio. Inoltre, in generale, le persone farebbero qualcosa in entrambi i casi veri e falsi, quindi la modifica di Yochai non si applicherebbe & probabilmente qualcosa di più significativo della somma.
      2019-02-28 15: 21: 15Z
fonte posta Qui