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





10 Answers

Previsione del ramo

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

java c++ performance optimization branch-prediction

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.



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

A partire dal ciclo originale:

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

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

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

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

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

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

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

Quello è 100.000 volte più veloce di prima




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

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

Questo approccio funziona in generale se:

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

Sfondo e perché

Pfew, quindi cosa diavolo dovrebbe significare?

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

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

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

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

Costruire un tavolo

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

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

Lingue gestite

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

Beh, non esattamente ... :-)

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

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

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

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

Il risultato di questo caso

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

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

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

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

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

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

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

Console.ReadLine();



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 inimmaginabile lut"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 una matrice, invece di utilizzare ifun'istruzione, può essere utilizzata per decidere quale puntatore utilizzare. Ho visto una libreria che implementava alberi binari, e invece di avere due puntatori nominati ( pLefte pRighto qualsiasi altra cosa) aveva una serie di puntatori lunghezza 2 e usava la tecnica del "decision bit" 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: Red Black Trees , Eternally Confuzzled




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

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

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

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

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

Pipeline a 4 stadi in generale per 2 istruzioni.

Tornando alla domanda precedente consideriamo le seguenti istruzioni:

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

Senza la previsione del ramo, si verifica quanto segue:

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

quando la condizione restituisce true:

Quando la condizione restituisce false:

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

Allora, qual è la previsione delle filiali?

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

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

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

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

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

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

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

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

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




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

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

o allo stesso modo:

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

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

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




Certamente!...

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

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

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

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

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

1. Statico

2. Dinamico

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

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




Guadagno pronostico!

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

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

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

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

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

visualizzazione:

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

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

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



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

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

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

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

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

Ci sono davvero tre diversi tipi di rami:

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

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

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

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

Riferimenti:




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

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

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

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



Related