- Messaggi
- 2,332
- Reazioni
- 1,928
- Punteggio
- 134
Costrutti condizionali: IF e branch prediction (1/2)
Indice degli argomenti:
1. Prefazione
Non di rado ho letto confronti tra if e switch, in molti casi forzati, in quanto equiparati l'un l'altro - consigliando anche l'utilizzo indistinto in base al gusto o alla semplicità di lettura di uno piuttosto che dell'altro. In questa prima parte di articolo ci occuperemo dell'IF ed in particolare porremo la nostra attenzione sul branch prediction. La seconda parte tratterà invece lo switch, mettendo quindi in luce le differenze tra i due costrutti.
I compilatori utilizzati sono esattamente:
Gli eseguibili prodotti avranno come architettura target x86.
2. Introduzione
La CPU è dotata tra le altre cose di una o più pipelines; attualmente le pipelines hanno circa 14 stadi. Eviterò di soffermarmi sulla pipeline, in quanto al di fuori dagli scopi dell'articolo, pertanto mi limiterò solo a dire che grazie alle pipelines la CPU è in grado di eseguire più istruzioni in un determinato periodo di tempo. Ogni stadio della CPU si occupa di un'operazione distinta dalle altre, quindi ad esempio mentre avviene la decodifica di un'istruzione un'altra viene già elaborata. Ciò permette di aumentare un parametro noto come throughput (eg. la quantità di dati elaborati in un dato momento).
Va da sè che per ottenere questa efficienza le istruzioni vengono caricate prima dell'esecuzione stessa; questo purtroppo introduce in certi casi alcuni problemi. Nel caso di un salto condizionato (un IF ad esempio), la CPU deve determinare quali istruzioni caricare: quelle nel corpo del ciclo, o quelle che seguono il blocco? Insomma, l'esito della condizione verificata dall'IF, sarà vera o falsa?
Gli algoritmi di brench prediction servono a questo. Con il progredire della tecnologia sono stati migliorati ed approcci nuovi vengono introdotti; si passa dallo static brench prediction, al dynamic brench prediction, sino ad arrivare alle reti neurali. L'argomento è interessante, ma l'aspetto interessante è capire che impatto ha sul sistema.
La percentuale di successo varia in base alla tecnica utilizzata, ma il fallimento non è così raro in determinati casi; quando i dati sono casuali e non vi è un criterio ben definito il brench prediction solitamente fallisce. Il fallimento del brench prediction - che consiste nel caricamento di istruzioni di un IF o nel loro mancato caricamento a seconda dell'errore di previsione - causa lo svuotamento della pipeline, con un conseguente ritardo dovendo ricaricare l'istruzione corretta e procedendo con l'elaborazione.
A questo punto è lecito chiedersi quanto i processori moderni soffrono davvero il brench prediction. Possibile che il codice che scriviamo, ed un if, possa avere conseguenze così "caotiche"?
Come esempio, si considerino il seguente sorgente:
C++
In pratica: riempio un array con 100.000 valori generati in maniera pseudo-casuale compresi tra 0 e 1000. Poi sommo solo i valori >= a 500. Nell'altra simulazione, ordino l'array utilizzato in precedenza e poi richiamo la funzione di somma. La funzione di somma è chiaramente quella che causa dispendio in termini di tempo (100.000 * 100.000 = 10.000.000.000 di cicli).
Sotto spoiler l'output (ottenuto senza flags di ottimizzazione con G++).
3. IF
A basso livello, l'if presente nel codice, è trasformato in:
E' d'uopo una spiegazione del codice, così da avere una comprensione più chiara su ciò che avviene. L'istruzione CMP (Compare) esegue un confronto tra il valore contenuto nel registro EAX ed il valore immediato 0x1F3 (499d); il confronto avviene eseguendo una sottrazione e scartando il risultato. In accordo al risultato ottenuto vengono settati opportuni bit nel registro EFLAGS. Tali bit vengono verificati da alcune istruzioni: in quasi tutti i casi si tratta delle Jxx, dove xx assume valori differenti in base al tipo di salto richiesto. Sono tutte istruzioni di salto condizionato (condizionato appunto dal valore dei flags interessati); Jxx è la forma generica. Nel caso di specie si tratta di JLE (Jump If Lower or Equals, Salta se è minore o uguale).
La condizione in assembly viene notoriamente "ribaltata" rispetto all'alto livello (noi avevamo infatti scritto >= 500, e non <= 499). Nell'iterazione illustrata il valore di EAX è maggiore, infatti viene eseguito il corpo dell'if (chi utilizza Ollydbg l'avrà sicuramente notato subito dal fatto che la freccia che indica a quale indirizzo avverrebbe il salto presenta colore grigio e non rosso, ad indicare che "jump is taken").
L'istruzione successiva alla JLE legge sullo stack locale il valore contenuto in LOCAL.5. Come si evince dall'istruzione sopra alla JMP, questa locazione (variabile locale), è il contatore del ciclo (infatti viene incrementata di una unità sempre).
Questo valore viene letto in quanto fornisce l'indice attuale (che nel codice è indicato con j, la variabile del ciclo) che viene poi moltiplicato per 4 ([EAX*4]) così da ottenere l'offset attuale nell'array.
ARG.1 è l'offset iniziale dell'array (il primo argomento della funzione); questo viene trasferito in EAX e poi sommato a EDX (l'offset calcolato in precedenza). A questo punto si accede alla locazione e si legge il valore (equivalente, ad alto livello, di numbers[j]).
Quanto si è visto riguarda codice generato da G++. Guardiamo quindi come tratta quel codice Microsoft Compiler.
Il compilatore di casa Microsoft si comporta diversamente, come si evince dallo screenshot. In questo caso EAX contiene l'indice; ECX è l'offset alla base dell'array e con la CMP si vede un indirizzamento che utilizza [base*indice+spiazzamento]. L'indice a cui si accede è la locazione dell'array; il confronto avviene con 0x1F4 (500d) ed il salto dell'istruzione successiva si verifica se il valore è minore di 500.
A questo punto viene assegnato a EDX l'indice attuale (j, nel codice); ad EAX viene assegnato l'offset alla base dell'array e ad ECX viene assegnata una variabile locale, LOCAL.3 (la variabile che memorizza la somma). A questo punto avviene la somma il cui risultato è salvato in ECX per essere assegnato successivamente alla variabile somma; il JMP successivo salta alla condizione del for.
Forse i meno pratici si chiederanno perchè effettuare la somma in questo modo, utilizzando ECX per memorizzare il risultato precedente e sommare il nuovo valore, per riassegnare ancora. La risposta è semplice: non si può fare. Un'operazione tra due operandi di memoria non è permessa (non esiste l'opcode).
Ora il modo in cui un IF viene valutato penso sia abbastanza chiaro: si tratta di utilizzare un'istruzione che effettui un confronto, come CMP, e che setti quindi dei bit nel registro dei flags (EFLAGS); a questo punto l'istruzione di salto sulla base del valore assunto dai bit decide se effettuare o no un salto; in caso positivo si dice "is taken" in caso negativo "not taken".
Ciò che causa i problemi dei quali si è diffusamente discusso sopra è proprio il CMP: il risultato dell'operazione è sicuro solo una volta eseguito; in fase di prefetch la CPU può solo affidarsi ad uno degli algoritmi per la predizione del flusso e sperare di non aver sbagliato.
Prima di proseguire con il nuovo paragrafo, ho pensato di lasciare un minimo di spazio all'operatore ternario.
3.1 L'operatore ternario
L'operatore ternario, (condition) ? true : false, è un modo elegante per scrivere quello che sarebbe altrimenti un if-else classico. Nel caso di specie è inutile, e pure controproducente. Sostituendo infatti l'if con:
otteniamo:
Parte del codice risulta inalterata. Tuttavia ora è un if-else e non più un if, quindi viene aggiunto un JMP al termine dell'if per saltare mov eax=0. Utilizzando il costrutto if-else il codice è invece identico a quanto mostrato sopra (il compilatore riconosce l'inutilità di una somma con il secondo operando a 0, quindi evita il blocco else).
4. La causa...
Il codice è stato pensato appositamente per creare una situazione piuttosto estrema ed evidenziare l'impatto che gli IF e le predizioni errate hanno sul codice.
Estraendo un campione dall'universo sul quale operiamo (l'array), ci troviamo d'innanzi ad una situazione simile alla presente:
Se consideriamo che l'algoritmo opera una scelta usando il valore 500, che si trova a metà del range di valori, osserviamo che la probabilità di considerare un valore < a 500 è esattamente uguale a quella di considerarne uno maggiore (di 500). Quindi la probabilità è del 50%:
Dove I indica un valore Inferiore a 500, ed S uno superiore.
Considerando la distribuzione sopra illustrata, risulta evidente la difficoltà nel prendere la decisione corretta.
5. ...ed il rimedio
Il rimedio spesso è a carico del compilatore,ma il programmatore spesse volte può semplificare le operazioni che sta eseguendo. Il tempo di calcolo della sola funzione sumAbove500() è Θ(n2),quindi un tempo tutt'altro che ottimale.
Un problema come quello evidenziato nel primo codice si può risolvere utilizzando alcuni accorgimenti. Il primo al quale si pensa quando si deve di fatto cercare un valore in un array... è ordinare l'array. Inserendo infatti l'inserimento prima della funzione sumAbove, i tempi di calcolo saranno notevolmente inferiori.
Di seguito l'output:
Grazie al sorting ora la distribuzione dei valori sarà composta in questo modo:
IIIIIIIIIIIIIIIIII.....SSSSSSSSSSSSS
Ne consegue che la predizione ora è attuabile con una probabilità di successo nettamente superiore a prima (ed i tempi lo attestano).
6. Soluzioni ottimali
Trovo corretto riportare anche soluzioni migliori, seppur non direttamente collegate ad un'agevolazione della predizione. Si tratta infatti della rimozione della stessa; nel primo caso, l'algoritmo precedente della funzione sumAbove verrà ottimizzato temporalmente, trasformando il suo tempo in Θ(n). La tecnica è nota come hoisting, o loop-invariant code motion, e come detto anche nel rispettivo paragrafo, è utilizzata in fase di ottimizzazione dai compilatori (quando riescono e quando è possibile). Preciso solo si tratti di una delle tante tecniche di ottimizzazione.
Nel secondo invece verrà utilizzato dell'assembly inline, compilando con CL.exe (Microsoft Compiler), per evitare l'if; sempre in questo paragrafo verrà anche visto come approssimare l'if utilizzando operazioni bitwise.
6.1. Loop-invariant code motion (invariante di ciclo)
La tecnica utilizzata è una di quelle utilizzate dai compilatori per ottimizzare il codice (che noi scriviamo), e nota come hoisting, o loop-invariant code motion. E' abbastanza semplice: si tratta di spostare al di fuori di un loop istruzioni che non si ha la necessità di avere all'interno, eseguendole quindi un numero inferiore di volte. La si può applicare ad operazioni matematiche o anche ad un if.
Mostro i passaggi logici per attuare questa trasformazione, utilizzando la funzione in questione:
Credo sia saltato all'occhio a molti di voi: i cicli in questo caso paiono inutili, scritti in questo modo. Si può quindi spostare l'if al di fuori del ciclo, senza intaccare i calcoli ma usando sempre i come indice:
Il tempi di seguito riportati fanno riferimento alla funzione con complessità quadratica e quella mostrata qui sopra:
Non riporto gli altri tempi, in quanto la tendenza risulta chiara; sto omettendo anche di specificare il compilatore utilizzato, in quanto le differenze sono irrisorie.
La versione mostrata in precedenza tuttavia mette in risalto l'inutilità dell'inner loop: ed è qui che viene applichiamo un passaggio successivo, rimuovendo l'inner loop.
Il tempi di calcolo che seguono, utilizzano l'invariante appena mostrata e la funzione originale in tempo quadratico che utilizza però il sorting:
Il guadagno in termini di tempo in questo caso è unicamente da imputare alla complessità dell'algoritmo: se utilizzassimo la versione con sorting con l'algoritmo in complessità lineare, i risultati sarebbero pressochè identici.
6.2. Operatori bitwise ed assembly-inline
E' possibile ottenere buoni risultati percorrendo anche altre strade, nonostante la precedente fosse ottimale. Se nel caso precedente la riduzione (azzeramento) dei tempi era da imputare alla complessità dell'algoritmo, in questo caso invece si andrà ad agire unicamente sul branch prediction, o meglio, sul branch mis-prediction rimuovendolo, senza tuttavia modificare quella che è la complessità dell'algoritmo.
Il primo caso analizzato è il rimpiazzo di un IF utilizzando operazioni sui bit; nel secondo invece si agirà utilizzando assembly-inline.
Consideriamo l'if in questione:
Analizzando il problema sappiamo che: la somma del valore in posizione J avviene solo se detto valore è >= a 500; ma è anche vero che lo stesso risultato lo otterremmo sommando 0 quando il valore è < di 500, così da non alterare il risultato.
Possiamo quindi sommare sempre, indipendentemente dal fatto che il valore sia inferiore o superiore a 500. Per comodità, come esempio prendiamo un valore più piccolo, come 10, considerando quindi il range 0..20.
Come si può sapere se un valore è inferiore o superiore? Si può sottrarre il valore considerato con quello centrale, 10. Come valori di esempio utilizzeremo 5 e 16.
n = 5 - 10 = -5
n = 16 - 10 = 6
E' lapalissiano, e lo era anche prima della sottrazione, che il numero > di 10 ha come risultato un valore positivo; viceversa quello inferiore a 10. Sulla base di questa considerazione, possiamo pensare di rappresentare i valori positivi con lo 0 ed i valori negativi con -1. Per comprendere il motivo si consideri la rappresentazione binaria dei risultati:
-5 = 11111011b
6 = 00000110b
Ciò che si può fare è applicare una maschera al valore originale, utilizzando un AND bit a bit e sfruttare proprio la numerazione: applicando uno shift a destra del valore -5 di 7bit, otteniamo -1 (11111111 in binario); applicando uno shift a destra di 7 posizioni del valore 6 otteniamo 0 (00000000 in binario). Considerando che lo scopo nel nostro caso è sommare i valori maggiori di 10, possiamo usare il valore di output precedente, negarlo applicando il complemento a 1, ed utilizzare poi un AND sul valore originale.
Per comprendere meglio il procedimento, riporto tutte le operazioni necessarie:
n = (5 - 10) >> 7 = -1
sum += ~n & 5
L'ultima operazione, ~n & 5, produrrà come risultato: ~(-1) % 5 = 0 & 5 = 0.
n = (16 - 10) >> 7 = 0
sum += ~n & 6
In questo caso avremo: ~(0) & 6 = -1 & 6 = 6.
Le uniche differenze tra questo esempio ed il caso proposto dall'algoritmo sono il numero centrale, 500, che andrà a sostituire il 10 di questo esempio, ed il numero di bit dello shift che passeranno da 7 a 31 (essendo valori a 32bit).
La funzione è quindi riportata di seguito:
Senza quindi modificare la complessità dell'algoritmo, otteniamo i seguenti risultati (Microsoft Compiler, ma di nuovo, i tempi sono analoghi):
La versione ordinata offre ovviamente tempi migliori, ma era lecito aspettarselo. L'if in quel caso non costituisce un problema; inoltre vengono eseguite meno istruzioni rispetto alla versione bitwise. Ripensate però alla versione senza ordinamento: i tempi sono comunque migliorati di 1/2 circa.
Il secondo esempio sulla rimozione del branch prediction (evitando il branch-misprediction) è quello che trovo anche più interessante: si tratta di utilizzare assembly-inline ed in particolare l'istruzione CMOVcc, dove 'cc' viene sostituito da E, NE, GE etc. In sostanza funziona in questo modo: l'istruzione CMP si occupa di settare i flags in accordo con il risultato dell'operazione; l'istruzione CMOV esegue, come da acronimo, un Conditional Move. Utilizzando CMOVE, ad esempio, l'assegnamento avviene solo se i due valori "comparati" (con il CMP precedente) sono uguali.
Procediamo direttamente con il codice che andremo ad utilizzare in seguito:
Utilizzo una variabile temporanea per memorizzare il valore; come prima istruzione lo XOR, che azzera il registro EAX. Ad EBX viene assegnata la variabile t, che successivamente viene comparata con il valore 500. L'utilizzo di CMOVGE consente di assegnare il valore di ebx al registro eax solo se il valore di ebx è >= a 500.
Si evita così il bisogno di predire il risultato in quanto l'istruzione da caricare, al di là dell'esito della CMOVGE, sarà l'istruzione successiva alla stessa.
Questi i tempi ottenuti dopo aver compilato con Microsoft Compiler.
In questo caso come si può notare i tempi sono relativamente simili; si tratta di una differenza di ~0.5s, importante, ma comunque molto più vicina al risultato del sorting rispetto all'utilizzo di operazioni sui bit.
7. Ottimizzazione automatica
Il titolo del paragrafo è forse un pò forzato: si tratta delle ottimizzazioni eseguite dal compilatore, a patto che sia il programmatore ad attuarle. Prenderemo ancora in considerazione entrambi i compilatori citati in precedenza, ma questa volta utilizzando i flags per l'ottimizzazione del codice.
Questa volta, al contrario delle precedenti, inizieremo dai tempi; nel primo caso abbiamo cl.exe (Microsoft), con il flags di ottimizzazione /O2 (ottimizza la velocità); nel secondo G++ con il flags di ottimizzazione -O2 (come Microsoft, ottimizza la velocità).
Microsoft Compiler:
G++
La versione asm-inline ho preferito mantenerla nel precedente output, ma solo come paragone con gli altri risultati (e perchè guarderemo che accade in fase di generazione del codice).
Osservando solo i risultati con e senza sorting, si notano tempistiche differenti da un compilatore all'altro. Vale quindi la pena capire in quale modo viene utilizzato dal compilatore. Inizieremo da cl.exe (Microsoft).
La prima cosa che salta all'occhio è che la funzione viene inserita inline e lo si evince da quel commento "Somma" al termine dello screnshot.
Questa parte di codice in particolare è significativa: si tratta difatti del corpo della funzione sumAbove500(). La prima riga è uno spostamento dati tra uno spiazzamento (memoria) ed un registro. In questo caso si tratta dello stack (vi è un segment override prefix, SS, ad indicarlo). La locazione puntata fa uso di indice, base e spiazzamento; l'utilizzo stesso dell'indice - il valore 4 - fa già capire che quella locazione è in realtà una posizione dell'array: l'indice è EDX, e la moltiplicazione è dovuta al fatto che i dati sono a 32bit (4byte).
Al registro ECX viene assegnato il valore 0x4E20 che in decimale è 20.000. Proseguendo si trova un CMP tra il valore EAX e 0x1F4, che in decimale è il numero 500. Si tratta dell'IF interno ai due cicli; infatti l'istruzione successiva è JL (Jump if less); quando non si verifica il salto il valore è maggiore di 500, e quindi avviene la somma. Da notare le 5 istruzioni che seguono: ADD ESI, EAX. Quello che stiamo analizzando viene chiamato "loop-unrolling", ed è un'altra delle tecniche di ottimizzazione.
Il funzionamento è relativamente semplice: si tratta di ridurre il numero delle iterazioni, ripetendo le istruzioni del corpo del ciclo. Dopo alle ADD troviamo una SUB tra ECX ed il numero 1; prima del loop era stato assegnato infatti il valore 20.000 ad ECX. Questo significa che il ciclo - come appare dalla JNE al seguito - va da 500 a 0. Ripetendo la somma 5 volte, ed eseguendo 1/5 delle iterazioni - 20.000 al posto delle 100.000 - si ottiene ottimizzazione.
Successivamente al JNE, troviamo INC EDX, che avvalora l'ipotesi iniziale: EDX è infatti l'indice usato nell'array. Il CMP alla penultima riga verifica che il valore di EDX (l'indice) sia inferiore (JB, istruzione successiva) del numero 100.000, che è infatti il ciclo esterno.
Le istruzioni che seguono, quelle che fanno uso dei registri XMM, possiamo ignorarle; basti sapere che una delle CALL effettua una chiamata alla funzione QueryPerformanceCounter (KERNEL32); si tratta di un timestamp che viene poi utilizzato per il calcolo del tempo. Le altre istruzioni effettuano una conversione tra un valore double word intero ed uno in floating point a precisione doppia.
Osserviamo ora che output produce G++.
La porzione che ci interessa particolarmente è questa:
SS:[ARG.1] è l'array, mentre [ARG.2] - che vediamo nello screenshot sopra - è la dimensione dell'array, e viene assegnata al registro EDI. Alla prima istruzione riportata, si vede l'assegnamento del valore [ARG.1] a EAX. Questa è la base dell'array. Il modo di procedere come si nota differisce rispetto all'altro compilatore: notiamo infatti l'istruzione LEA ESI,[EDI*4+EAX]. Sapendo che EAX contiene la base dell'array, e EDI è la dimensione, moltiplicando EDI*4 e sommando la base dell'array otteniamo l'ultimo elemento; è bene notare che viene assegnato l'indirizzo e non il valore puntato.
Lo XOR del registro EAX con sè stesso equivale a MOV EAX, 0; ha però il pregio di essere più performante (e richiede meno byte per codificare l'istruzione).
Si arriva quindi al ciclo: viene assegnato l'offset ARG.1 a EDX; ad ECX viene assegnato il valore puntato da EDX, e questo è il loop interno. Per mezzo di LEA viene calcolata la somma tra ECX ed EAX. E qui è necessario fare attenzione: ECX contiene il primo elemento del vettore, essendo la prima iterazione, mentre EAX contiene 0 (è stato azzerato in precedenza). La somma produrrà quindi come risultato il valore di ECX. Questo valore viene assegnato quindi ad EBX; successivamente viene testato il valore di ECX con 0x1F4 (500, in decimale): se il valore è >= 500, allora EBX viene assegnato ad EAX. Come si nota anche G++ rimuove l'if.
Per comprendere meglio ciò che accade: supponiamo che il valore di ECX fosse >= di 500, e che quindi EBX sia stato assegnato ad EAX. L'istruzione successiva incrementa EDX di 4; EDX punta al prossimo elemento dell'array. Viene quindi testato con l'ultimo contenuto in ESI e se gli indirizzi corrispondono il ciclo termina; in caso contrario il loop si ripete. Ora ad ECX viene assegnata la prossima locazione; ad EBX viene assegnato come valore (valore, non indirizzo) la somma tra ECX ed EAX. In pratica EAX contiene la somma, ed ECX il valore attuale. Il valore attuale viene sempre sommato sfruttando LEA e memorizzato temporaneamente in EBX. Se il valore di ECX è => di 500, allora viene assegnato al registro EAX. In questo modo EAX conterrà sempre la somma finale.
La lentezza rispetto al compilato con Microsoft è dovuta principalmente al non srotolare il ciclo (loop-unrolling).
8. Conclusione
Voglio precisare che i risultati ottenuti sopra non devono portare a conclusioni affrettate: vi possono essere altre ottimizzazioni, altre porzioni di codice, molto meglio ottimizzate da G++ rispetto al compilatore di Microsoft.
La prima parte dell'articolo termina qui. La seconda tratterà del secondo costrutto condizionale, lo switch.
PS. come nei precedenti casi, se avete domande, ponete pure li sotto. :) In caso di errori grammaticali o imprecisioni, chiedo venia, e segnalatemeli pure.
Indice degli argomenti:
- Prefazione
- Introduzione
- IF
- L'operatore ternario
- La causa
- Il rimedio
- Soluzioni ottimali
- Loop-invariant code motion
- Operazioni bitwise ed assembly inline
- Ottimizzazione automatica
- Conclusione
1. Prefazione
Non di rado ho letto confronti tra if e switch, in molti casi forzati, in quanto equiparati l'un l'altro - consigliando anche l'utilizzo indistinto in base al gusto o alla semplicità di lettura di uno piuttosto che dell'altro. In questa prima parte di articolo ci occuperemo dell'IF ed in particolare porremo la nostra attenzione sul branch prediction. La seconda parte tratterà invece lo switch, mettendo quindi in luce le differenze tra i due costrutti.
I compilatori utilizzati sono esattamente:
- Microsoft (R) C/C++ Optimizing Compiler versione 19.10.25019 per x86
- MinGw, g++ version 6.2.0
Gli eseguibili prodotti avranno come architettura target x86.
2. Introduzione
La CPU è dotata tra le altre cose di una o più pipelines; attualmente le pipelines hanno circa 14 stadi. Eviterò di soffermarmi sulla pipeline, in quanto al di fuori dagli scopi dell'articolo, pertanto mi limiterò solo a dire che grazie alle pipelines la CPU è in grado di eseguire più istruzioni in un determinato periodo di tempo. Ogni stadio della CPU si occupa di un'operazione distinta dalle altre, quindi ad esempio mentre avviene la decodifica di un'istruzione un'altra viene già elaborata. Ciò permette di aumentare un parametro noto come throughput (eg. la quantità di dati elaborati in un dato momento).
Va da sè che per ottenere questa efficienza le istruzioni vengono caricate prima dell'esecuzione stessa; questo purtroppo introduce in certi casi alcuni problemi. Nel caso di un salto condizionato (un IF ad esempio), la CPU deve determinare quali istruzioni caricare: quelle nel corpo del ciclo, o quelle che seguono il blocco? Insomma, l'esito della condizione verificata dall'IF, sarà vera o falsa?
Gli algoritmi di brench prediction servono a questo. Con il progredire della tecnologia sono stati migliorati ed approcci nuovi vengono introdotti; si passa dallo static brench prediction, al dynamic brench prediction, sino ad arrivare alle reti neurali. L'argomento è interessante, ma l'aspetto interessante è capire che impatto ha sul sistema.
La percentuale di successo varia in base alla tecnica utilizzata, ma il fallimento non è così raro in determinati casi; quando i dati sono casuali e non vi è un criterio ben definito il brench prediction solitamente fallisce. Il fallimento del brench prediction - che consiste nel caricamento di istruzioni di un IF o nel loro mancato caricamento a seconda dell'errore di previsione - causa lo svuotamento della pipeline, con un conseguente ritardo dovendo ricaricare l'istruzione corretta e procedendo con l'elaborazione.
A questo punto è lecito chiedersi quanto i processori moderni soffrono davvero il brench prediction. Possibile che il codice che scriviamo, ed un if, possa avere conseguenze così "caotiche"?
Come esempio, si considerino il seguente sorgente:
C++
Codice:
#include <algorithm>
#include <ctime>
#include <iostream>
unsigned long sumAbove500(int numbers[], const unsigned int size)
{
unsigned long sum = 0;
for (unsigned int i = 0; i < size; i++)
{
for (unsigned int j = 0; j < size; j++)
{
if (numbers[j] >= 500)
sum += numbers[j];
}
}
return sum;
}
int main()
{
const unsigned int size = 100000;
int numbers[size];
srand (time(NULL));
// Quantita' di test da eseguire
for(int i=0; i<10; i++)
{
// Popolo l'array
int k = 0;
while(k++ < size) numbers[k] = std::rand() % 1000;
//
// Inizio dei Test
//
std::cout << "------------ Test #" << (i+1) << " ---------------\n";
std::cout << "Senza Sorting:\n";
clock_t start = clock();
unsigned long sum = sumAbove500(numbers, size);
double executionTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << "\t" << executionTime << "s\n";
std::cout << "\tsomma = " << sum << "\n";
}
}In pratica: riempio un array con 100.000 valori generati in maniera pseudo-casuale compresi tra 0 e 1000. Poi sommo solo i valori >= a 500. Nell'altra simulazione, ordino l'array utilizzato in precedenza e poi richiamo la funzione di somma. La funzione di somma è chiaramente quella che causa dispendio in termini di tempo (100.000 * 100.000 = 10.000.000.000 di cicli).
Sotto spoiler l'output (ottenuto senza flags di ottimizzazione con G++).
Codice:
------------ Test #1 ---------------
Senza Sorting:
76.542s
somma = 877790848
------------------------------------
------------ Test #2 ---------------
Senza Sorting:
77.06s
somma = 2365423552
------------------------------------
------------ Test #3 ---------------
Senza Sorting:
78.489s
somma = 3678092736
------------------------------------
------------ Test #4 ---------------
Senza Sorting:
80.717s
somma = 2481987072
------------------------------------
------------ Test #5 ---------------
Senza Sorting:
79.775s
somma = 914390848
------------------------------------
------------ Test #6 ---------------
Senza Sorting:
77.247s
somma = 3920954368
------------------------------------
------------ Test #7 ---------------
Senza Sorting:
77.57s
somma = 1505121664
------------------------------------
------------ Test #8 ---------------
Senza Sorting:
77.046s
somma = 495088960
------------------------------------
------------ Test #9 ---------------
Senza Sorting:
78.196s
somma = 263090848
------------------------------------
------------ Test #10 ---------------
Senza Sorting:
78.303s
somma = 1985658144
------------------------------------3. IF
A basso livello, l'if presente nel codice, è trasformato in:
Codice:
g++ costrutti.cpp -o costrutti
E' d'uopo una spiegazione del codice, così da avere una comprensione più chiara su ciò che avviene. L'istruzione CMP (Compare) esegue un confronto tra il valore contenuto nel registro EAX ed il valore immediato 0x1F3 (499d); il confronto avviene eseguendo una sottrazione e scartando il risultato. In accordo al risultato ottenuto vengono settati opportuni bit nel registro EFLAGS. Tali bit vengono verificati da alcune istruzioni: in quasi tutti i casi si tratta delle Jxx, dove xx assume valori differenti in base al tipo di salto richiesto. Sono tutte istruzioni di salto condizionato (condizionato appunto dal valore dei flags interessati); Jxx è la forma generica. Nel caso di specie si tratta di JLE (Jump If Lower or Equals, Salta se è minore o uguale).
La condizione in assembly viene notoriamente "ribaltata" rispetto all'alto livello (noi avevamo infatti scritto >= 500, e non <= 499). Nell'iterazione illustrata il valore di EAX è maggiore, infatti viene eseguito il corpo dell'if (chi utilizza Ollydbg l'avrà sicuramente notato subito dal fatto che la freccia che indica a quale indirizzo avverrebbe il salto presenta colore grigio e non rosso, ad indicare che "jump is taken").
L'istruzione successiva alla JLE legge sullo stack locale il valore contenuto in LOCAL.5. Come si evince dall'istruzione sopra alla JMP, questa locazione (variabile locale), è il contatore del ciclo (infatti viene incrementata di una unità sempre).
Questo valore viene letto in quanto fornisce l'indice attuale (che nel codice è indicato con j, la variabile del ciclo) che viene poi moltiplicato per 4 ([EAX*4]) così da ottenere l'offset attuale nell'array.
ARG.1 è l'offset iniziale dell'array (il primo argomento della funzione); questo viene trasferito in EAX e poi sommato a EDX (l'offset calcolato in precedenza). A questo punto si accede alla locazione e si legge il valore (equivalente, ad alto livello, di numbers[j]).
Quanto si è visto riguarda codice generato da G++. Guardiamo quindi come tratta quel codice Microsoft Compiler.
Codice:
cl costrutti.cpp /EHsc
Il compilatore di casa Microsoft si comporta diversamente, come si evince dallo screenshot. In questo caso EAX contiene l'indice; ECX è l'offset alla base dell'array e con la CMP si vede un indirizzamento che utilizza [base*indice+spiazzamento]. L'indice a cui si accede è la locazione dell'array; il confronto avviene con 0x1F4 (500d) ed il salto dell'istruzione successiva si verifica se il valore è minore di 500.
A questo punto viene assegnato a EDX l'indice attuale (j, nel codice); ad EAX viene assegnato l'offset alla base dell'array e ad ECX viene assegnata una variabile locale, LOCAL.3 (la variabile che memorizza la somma). A questo punto avviene la somma il cui risultato è salvato in ECX per essere assegnato successivamente alla variabile somma; il JMP successivo salta alla condizione del for.
Forse i meno pratici si chiederanno perchè effettuare la somma in questo modo, utilizzando ECX per memorizzare il risultato precedente e sommare il nuovo valore, per riassegnare ancora. La risposta è semplice: non si può fare. Un'operazione tra due operandi di memoria non è permessa (non esiste l'opcode).
Ora il modo in cui un IF viene valutato penso sia abbastanza chiaro: si tratta di utilizzare un'istruzione che effettui un confronto, come CMP, e che setti quindi dei bit nel registro dei flags (EFLAGS); a questo punto l'istruzione di salto sulla base del valore assunto dai bit decide se effettuare o no un salto; in caso positivo si dice "is taken" in caso negativo "not taken".
Ciò che causa i problemi dei quali si è diffusamente discusso sopra è proprio il CMP: il risultato dell'operazione è sicuro solo una volta eseguito; in fase di prefetch la CPU può solo affidarsi ad uno degli algoritmi per la predizione del flusso e sperare di non aver sbagliato.
Prima di proseguire con il nuovo paragrafo, ho pensato di lasciare un minimo di spazio all'operatore ternario.
3.1 L'operatore ternario
L'operatore ternario, (condition) ? true : false, è un modo elegante per scrivere quello che sarebbe altrimenti un if-else classico. Nel caso di specie è inutile, e pure controproducente. Sostituendo infatti l'if con:
C:
sum+= (numbers[j] >= 500) ? numbers[j] : 0;otteniamo:
Codice:
g++ costrutti.cpp -o costrutti
Parte del codice risulta inalterata. Tuttavia ora è un if-else e non più un if, quindi viene aggiunto un JMP al termine dell'if per saltare mov eax=0. Utilizzando il costrutto if-else il codice è invece identico a quanto mostrato sopra (il compilatore riconosce l'inutilità di una somma con il secondo operando a 0, quindi evita il blocco else).
4. La causa...
Il codice è stato pensato appositamente per creare una situazione piuttosto estrema ed evidenziare l'impatto che gli IF e le predizioni errate hanno sul codice.
Estraendo un campione dall'universo sul quale operiamo (l'array), ci troviamo d'innanzi ad una situazione simile alla presente:
Codice:
0, 41, 467, 334, 500, 169, 724, 478, 358, 962, 464, 705, 145, 281, 827, 961, 491, 995, 942, 827Se consideriamo che l'algoritmo opera una scelta usando il valore 500, che si trova a metà del range di valori, osserviamo che la probabilità di considerare un valore < a 500 è esattamente uguale a quella di considerarne uno maggiore (di 500). Quindi la probabilità è del 50%:
| 0 | 41 | 467 | 334 | 500 | 169 | 724 | 478 | 358 | 962 | 464 | 705 | 145 | 281 | 827 | 961 | 491 | 995 | 942 | 827 |
| I | I | I | I | S | I | S | I | I | S | I | S | I | I | S | S | I | S | S | S |
Dove I indica un valore Inferiore a 500, ed S uno superiore.
Considerando la distribuzione sopra illustrata, risulta evidente la difficoltà nel prendere la decisione corretta.
5. ...ed il rimedio
Il rimedio spesso è a carico del compilatore,ma il programmatore spesse volte può semplificare le operazioni che sta eseguendo. Il tempo di calcolo della sola funzione sumAbove500() è Θ(n2),quindi un tempo tutt'altro che ottimale.
Un problema come quello evidenziato nel primo codice si può risolvere utilizzando alcuni accorgimenti. Il primo al quale si pensa quando si deve di fatto cercare un valore in un array... è ordinare l'array. Inserendo infatti l'inserimento prima della funzione sumAbove, i tempi di calcolo saranno notevolmente inferiori.
C:
std::sort(numbers, numbers + sizeDi seguito l'output:
Codice:
------------ Test #1 ---------------
Senza Sorting:
78.792s
somma = 2869856256
Con sorting:
19.779s
somma = 2869856256
------------------------------------
------------ Test #2 ---------------
Senza Sorting:
78.621s
somma = 2611825440
Con sorting:
19.742s
somma = 2611825440
------------------------------------
------------ Test #3 ---------------
Senza Sorting:
78.552s
somma = 831723552
Con sorting:
18.884s
somma = 831723552
------------------------------------
------------ Test #4 ---------------
Senza Sorting:
75.434s
somma = 3673923552
Con sorting:
18.657s
somma = 3673923552
------------------------------------
------------ Test #5 ---------------
Senza Sorting:
74.499s
somma = 2192287072
Con sorting:
18.96s
somma = 2192287072
------------------------------------
------------ Test #6 ---------------
Senza Sorting:
76.374s
somma = 3250323552
Con sorting:
19.369s
somma = 3250323552
------------------------------------
------------ Test #7 ---------------
Senza Sorting:
76.25s
somma = 424321664
Con sorting:
19.079s
somma = 424321664
------------------------------------
------------ Test #8 ---------------
Senza Sorting:
75.225s
somma = 2314488960
Con sorting:
19.078s
somma = 2314488960
------------------------------------
------------ Test #9 ---------------
Senza Sorting:
76.322s
somma = 2849023552
Con sorting:
19.055s
somma = 2849023552
------------------------------------
------------ Test #10 ---------------
Senza Sorting:
76.957s
somma = 2321158144
Con sorting:
20.194s
somma = 2321158144
------------------------------------Grazie al sorting ora la distribuzione dei valori sarà composta in questo modo:
IIIIIIIIIIIIIIIIII.....SSSSSSSSSSSSS
Ne consegue che la predizione ora è attuabile con una probabilità di successo nettamente superiore a prima (ed i tempi lo attestano).
6. Soluzioni ottimali
Trovo corretto riportare anche soluzioni migliori, seppur non direttamente collegate ad un'agevolazione della predizione. Si tratta infatti della rimozione della stessa; nel primo caso, l'algoritmo precedente della funzione sumAbove verrà ottimizzato temporalmente, trasformando il suo tempo in Θ(n). La tecnica è nota come hoisting, o loop-invariant code motion, e come detto anche nel rispettivo paragrafo, è utilizzata in fase di ottimizzazione dai compilatori (quando riescono e quando è possibile). Preciso solo si tratti di una delle tante tecniche di ottimizzazione.
Nel secondo invece verrà utilizzato dell'assembly inline, compilando con CL.exe (Microsoft Compiler), per evitare l'if; sempre in questo paragrafo verrà anche visto come approssimare l'if utilizzando operazioni bitwise.
6.1. Loop-invariant code motion (invariante di ciclo)
La tecnica utilizzata è una di quelle utilizzate dai compilatori per ottimizzare il codice (che noi scriviamo), e nota come hoisting, o loop-invariant code motion. E' abbastanza semplice: si tratta di spostare al di fuori di un loop istruzioni che non si ha la necessità di avere all'interno, eseguendole quindi un numero inferiore di volte. La si può applicare ad operazioni matematiche o anche ad un if.
Mostro i passaggi logici per attuare questa trasformazione, utilizzando la funzione in questione:
C:
unsigned long sumAbove500(int numbers[], const unsigned int size)
{
unsigned long sum = 0;
for (unsigned int i = 0; i < size; i++)
{
for (unsigned int j = 0; j < size; j++)
{
if (numbers[j] >= 500)
sum += numbers[j];
}
}
return sum;
}Credo sia saltato all'occhio a molti di voi: i cicli in questo caso paiono inutili, scritti in questo modo. Si può quindi spostare l'if al di fuori del ciclo, senza intaccare i calcoli ma usando sempre i come indice:
C:
unsigned long sumAbove500_2(int numbers[], const unsigned int size)
{
unsigned long sum = 0;
for (unsigned int i = 0; i < size; i++)
{
if (numbers[i] >= 500)
{
for (unsigned int j = 0; j < size; j++)
{
sum += numbers[i];
}
}
}
return sum;
}Il tempi di seguito riportati fanno riferimento alla funzione con complessità quadratica e quella mostrata qui sopra:
Codice:
------------ Test #1 ---------------
Senza Sorting:
74.261s
somma = 4185090848
Con sorting:
11.615s
somma = 4185090848
------------------------------------
------------ Test #2 ---------------
Senza Sorting:
75.067s
somma = 544156256
Con sorting:
11.405s
somma = 544156256
------------------------------------Non riporto gli altri tempi, in quanto la tendenza risulta chiara; sto omettendo anche di specificare il compilatore utilizzato, in quanto le differenze sono irrisorie.
La versione mostrata in precedenza tuttavia mette in risalto l'inutilità dell'inner loop: ed è qui che viene applichiamo un passaggio successivo, rimuovendo l'inner loop.
C:
unsigned long sumAbove500Invariant(int numbers[], const unsigned int size)
{
unsigned long sum = 0;
for (unsigned int i = 0; i < size; i++)
{
if (numbers[i] >= 500)
{
sum += numbers[i] * size;
}
}
return sum;
}Il tempi di calcolo che seguono, utilizzano l'invariante appena mostrata e la funzione originale in tempo quadratico che utilizza però il sorting:
Codice:
------------ Test #1 ---------------
Senza Sorting:
0.001s
somma (invariante) = 3442490848
Con sorting:
20.69s
somma = 3442490848
------------------------------------
------------ Test #2 ---------------
Senza Sorting:
0.001s
somma (invariante) = 217225440
Con sorting:
20.498s
somma = 217225440
------------------------------------
------------ Test #3 ---------------
Senza Sorting:
0.001s
somma (invariante) = 1768860032
Con sorting:
20.563s
somma = 1768860032
------------------------------------
------------ Test #4 ---------------
Senza Sorting:
0.001s
somma (invariante) = 1844323552
Con sorting:
20.582s
somma = 1844323552
------------------------------------
------------ Test #5 ---------------
Senza Sorting:
0.001s
somma (invariante) = 3421788960
Con sorting:
20.518s
somma = 3421788960
------------------------------------
------------ Test #6 ---------------
Senza Sorting:
0.001s
somma (invariante) = 3456925440
Con sorting:
20.435s
somma = 3456925440
------------------------------------
------------ Test #7 ---------------
Senza Sorting:
0.001s
somma (invariante) = 2718658144
Con sorting:
20.581s
somma = 2718658144
------------------------------------
------------ Test #8 ---------------
Senza Sorting:
0.001s
somma (invariante) = 1820192736
Con sorting:
20.655s
somma = 1820192736
------------------------------------
------------ Test #9 ---------------
Senza Sorting:
0s
somma (invariante) = 3142921664
Con sorting:
20.563s
somma = 3142921664
------------------------------------
------------ Test #10 ---------------
Senza Sorting:
0.001s
somma (invariante) = 3389990848
Con sorting:
20.613s
somma = 3389990848
------------------------------------Il guadagno in termini di tempo in questo caso è unicamente da imputare alla complessità dell'algoritmo: se utilizzassimo la versione con sorting con l'algoritmo in complessità lineare, i risultati sarebbero pressochè identici.
6.2. Operatori bitwise ed assembly-inline
E' possibile ottenere buoni risultati percorrendo anche altre strade, nonostante la precedente fosse ottimale. Se nel caso precedente la riduzione (azzeramento) dei tempi era da imputare alla complessità dell'algoritmo, in questo caso invece si andrà ad agire unicamente sul branch prediction, o meglio, sul branch mis-prediction rimuovendolo, senza tuttavia modificare quella che è la complessità dell'algoritmo.
Il primo caso analizzato è il rimpiazzo di un IF utilizzando operazioni sui bit; nel secondo invece si agirà utilizzando assembly-inline.
Consideriamo l'if in questione:
C:
if (numbers[j] >= 500) sum += numbers[j]Analizzando il problema sappiamo che: la somma del valore in posizione J avviene solo se detto valore è >= a 500; ma è anche vero che lo stesso risultato lo otterremmo sommando 0 quando il valore è < di 500, così da non alterare il risultato.
Possiamo quindi sommare sempre, indipendentemente dal fatto che il valore sia inferiore o superiore a 500. Per comodità, come esempio prendiamo un valore più piccolo, come 10, considerando quindi il range 0..20.
Come si può sapere se un valore è inferiore o superiore? Si può sottrarre il valore considerato con quello centrale, 10. Come valori di esempio utilizzeremo 5 e 16.
n = 5 - 10 = -5
n = 16 - 10 = 6
E' lapalissiano, e lo era anche prima della sottrazione, che il numero > di 10 ha come risultato un valore positivo; viceversa quello inferiore a 10. Sulla base di questa considerazione, possiamo pensare di rappresentare i valori positivi con lo 0 ed i valori negativi con -1. Per comprendere il motivo si consideri la rappresentazione binaria dei risultati:
-5 = 11111011b
6 = 00000110b
Ciò che si può fare è applicare una maschera al valore originale, utilizzando un AND bit a bit e sfruttare proprio la numerazione: applicando uno shift a destra del valore -5 di 7bit, otteniamo -1 (11111111 in binario); applicando uno shift a destra di 7 posizioni del valore 6 otteniamo 0 (00000000 in binario). Considerando che lo scopo nel nostro caso è sommare i valori maggiori di 10, possiamo usare il valore di output precedente, negarlo applicando il complemento a 1, ed utilizzare poi un AND sul valore originale.
Per comprendere meglio il procedimento, riporto tutte le operazioni necessarie:
n = (5 - 10) >> 7 = -1
sum += ~n & 5
L'ultima operazione, ~n & 5, produrrà come risultato: ~(-1) % 5 = 0 & 5 = 0.
n = (16 - 10) >> 7 = 0
sum += ~n & 6
In questo caso avremo: ~(0) & 6 = -1 & 6 = 6.
Le uniche differenze tra questo esempio ed il caso proposto dall'algoritmo sono il numero centrale, 500, che andrà a sostituire il 10 di questo esempio, ed il numero di bit dello shift che passeranno da 7 a 31 (essendo valori a 32bit).
La funzione è quindi riportata di seguito:
C:
unsigned long sumAbove500Bitwise(int numbers[], const unsigned int size)
{
unsigned long sum = 0;
for (unsigned int i = 0; i < size; i++)
{
for (unsigned int j = 0; j < size; j++)
{
int temp = (numbers[j] - 500) >> 31;
sum += ~temp & numbers[j];
}
}
return sum;
}Senza quindi modificare la complessità dell'algoritmo, otteniamo i seguenti risultati (Microsoft Compiler, ma di nuovo, i tempi sono analoghi):
Codice:
------------ Test #1 ---------------
Con Bitwise (originale):
27.696s
somma = 988856256
Con sorting (originale):
20.5s
somma = 988856256
------------------------------------
------------ Test #2 ---------------
Con Bitwise (originale):
27.914s
somma = 3034123552
Con sorting (originale):
21.307s
somma = 3034123552
------------------------------------
------------ Test #3 ---------------
Con Bitwise (originale):
28.69s
somma = 2290588960
Con sorting (originale):
20.904s
somma = 2290588960
------------------------------------
------------ Test #4 ---------------
Con Bitwise (originale):
29.173s
somma = 2955692736
Con sorting (originale):
22.449s
somma = 2955692736
------------------------------------
------------ Test #5 ---------------
Con Bitwise (originale):
28.191s
somma = 4198690848
Con sorting (originale):
21.325s
somma = 4198690848
------------------------------------
------------ Test #6 ---------------
Con Bitwise (originale):
28.49s
somma = 1056023552
Con sorting (originale):
21.48s
somma = 1056023552
------------------------------------
------------ Test #7 ---------------
Con Bitwise (originale):
28.626s
somma = 2196560032
Con sorting (originale):
20.733s
somma = 2196560032
------------------------------------
------------ Test #8 ---------------
Con Bitwise (originale):
28.933s
somma = 2168121664
Con sorting (originale):
21.514s
somma = 2168121664
------------------------------------
------------ Test #9 ---------------
Con Bitwise (originale):
28.973s
somma = 2818458144
Con sorting (originale):
21.157s
somma = 2818458144
------------------------------------
------------ Test #10 ---------------
Con Bitwise (originale):
28.179s
somma = 2037454368
Con sorting (originale):
21.958s
somma = 2037454368
------------------------------------La versione ordinata offre ovviamente tempi migliori, ma era lecito aspettarselo. L'if in quel caso non costituisce un problema; inoltre vengono eseguite meno istruzioni rispetto alla versione bitwise. Ripensate però alla versione senza ordinamento: i tempi sono comunque migliorati di 1/2 circa.
Il secondo esempio sulla rimozione del branch prediction (evitando il branch-misprediction) è quello che trovo anche più interessante: si tratta di utilizzare assembly-inline ed in particolare l'istruzione CMOVcc, dove 'cc' viene sostituito da E, NE, GE etc. In sostanza funziona in questo modo: l'istruzione CMP si occupa di settare i flags in accordo con il risultato dell'operazione; l'istruzione CMOV esegue, come da acronimo, un Conditional Move. Utilizzando CMOVE, ad esempio, l'assegnamento avviene solo se i due valori "comparati" (con il CMP precedente) sono uguali.
Procediamo direttamente con il codice che andremo ad utilizzare in seguito:
Codice:
int t = numbers[j];
__asm{
xor eax, eax
mov ebx, t
cmp ebx, 500
cmovge eax, ebx
add sum, eax
}Utilizzo una variabile temporanea per memorizzare il valore; come prima istruzione lo XOR, che azzera il registro EAX. Ad EBX viene assegnata la variabile t, che successivamente viene comparata con il valore 500. L'utilizzo di CMOVGE consente di assegnare il valore di ebx al registro eax solo se il valore di ebx è >= a 500.
Si evita così il bisogno di predire il risultato in quanto l'istruzione da caricare, al di là dell'esito della CMOVGE, sarà l'istruzione successiva alla stessa.
Questi i tempi ottenuti dopo aver compilato con Microsoft Compiler.
Codice:
Asm-inline (originale):
18.696s
somma = 3489754368
Con sorting (originale):
18.215s
somma = 3489754368
------------------------------------
Asm-inline (originale):
18.653s
somma = 295792736
Con sorting (originale):
18.283s
somma = 295792736
------------------------------------
Asm-inline (originale):
18.592s
somma = 1364323552
Con sorting (originale):
18.199s
somma = 1364323552
------------------------------------
Asm-inline (originale):
18.573s
somma = 1438123552
Con sorting (originale):
18.217s
somma = 1438123552
------------------------------------
Asm-inline (originale):
18.585s
somma = 2369025440
Con sorting (originale):
18.184s
somma = 2369025440
------------------------------------
Asm-inline (originale):
18.578s
somma = 904887072
Con sorting (originale):
18.206s
somma = 904887072
------------------------------------
Asm-inline (originale):
18.575s
somma = 4016225440
Con sorting (originale):
18.184s
somma = 4016225440
------------------------------------
Asm-inline (originale):
18.585s
somma = 3827023552
Con sorting (originale):
18.197s
somma = 3827023552
------------------------------------
Asm-inline (originale):
19.547s
somma = 2108290848
Con sorting (originale):
20.64s
somma = 2108290848
------------------------------------
Asm-inline (originale):
19.689s
somma = 1327487072
Con sorting (originale):
18.278s
somma = 1327487072
------------------------------------In questo caso come si può notare i tempi sono relativamente simili; si tratta di una differenza di ~0.5s, importante, ma comunque molto più vicina al risultato del sorting rispetto all'utilizzo di operazioni sui bit.
7. Ottimizzazione automatica
Il titolo del paragrafo è forse un pò forzato: si tratta delle ottimizzazioni eseguite dal compilatore, a patto che sia il programmatore ad attuarle. Prenderemo ancora in considerazione entrambi i compilatori citati in precedenza, ma questa volta utilizzando i flags per l'ottimizzazione del codice.
Questa volta, al contrario delle precedenti, inizieremo dai tempi; nel primo caso abbiamo cl.exe (Microsoft), con il flags di ottimizzazione /O2 (ottimizza la velocità); nel secondo G++ con il flags di ottimizzazione -O2 (come Microsoft, ottimizza la velocità).
Microsoft Compiler:
Codice:
------------ Test #1 ---------------
Senza sorting (originale):
2.041s
somma = 1150625440
Asm-inline (originale):
15.124s
somma = 1150625440
Con sorting (originale):
2.048s
somma = 1150625440
------------------------------------
------------ Test #2 ---------------
Senza sorting (originale):
2.022s
somma = 3045388960
Asm-inline (originale):
15.117s
somma = 3045388960
Con sorting (originale):
2.067s
somma = 3045388960
------------------------------------
------------ Test #3 ---------------
Senza sorting (originale):
2.017s
somma = 3321858144
Asm-inline (originale):
15.317s
somma = 3321858144
Con sorting (originale):
2.139s
somma = 3321858144
------------------------------------
------------ Test #4 ---------------
Senza sorting (originale):
2.057s
somma = 3835025440
Asm-inline (originale):
15.247s
somma = 3835025440
Con sorting (originale):
2.138s
somma = 3835025440
------------------------------------
------------ Test #5 ---------------
Senza sorting (originale):
2.075s
somma = 908258144
Asm-inline (originale):
15.377s
somma = 908258144
Con sorting (originale):
2.135s
somma = 908258144
------------------------------------
------------ Test #6 ---------------
Senza sorting (originale):
2.103s
somma = 2128221664
Asm-inline (originale):
15.333s
somma = 2128221664
Con sorting (originale):
2.128s
somma = 2128221664
------------------------------------
------------ Test #7 ---------------
Senza sorting (originale):
2.063s
somma = 1942321664
Asm-inline (originale):
15.53s
somma = 1942321664
Con sorting (originale):
2.203s
somma = 1942321664
------------------------------------
------------ Test #8 ---------------
Senza sorting (originale):
2.076s
somma = 3376888960
Asm-inline (originale):
15.366s
somma = 3376888960
Con sorting (originale):
2.122s
somma = 3376888960
------------------------------------
------------ Test #9 ---------------
Senza sorting (originale):
2.042s
somma = 4068390848
Asm-inline (originale):
15.223s
somma = 4068390848
Con sorting (originale):
2.121s
somma = 4068390848
------------------------------------
------------ Test #10 ---------------
Senza sorting (originale):
2.02s
somma = 1096154368
Asm-inline (originale):
15.607s
somma = 1096154368
Con sorting (originale):
2.117s
somma = 1096154368
------------------------------------G++
Codice:
------------ Test #1 ---------------
Senza sorting (originale):
5.797s
somma = 194358144
Con sorting (originale):
5.782s
somma = 194358144
------------------------------------
------------ Test #2 ---------------
Senza sorting (originale):
5.782s
somma = 4160656256
Con sorting (originale):
5.782s
somma = 4160656256
------------------------------------
------------ Test #3 ---------------
Senza sorting (originale):
5.782s
somma = 3715488960
Con sorting (originale):
5.907s
somma = 3715488960
------------------------------------
------------ Test #4 ---------------
Senza sorting (originale):
5.907s
somma = 1160825440
Con sorting (originale):
5.954s
somma = 1160825440
------------------------------------
------------ Test #5 ---------------
Senza sorting (originale):
6.001s
somma = 461458144
Con sorting (originale):
5.985s
somma = 461458144
------------------------------------
------------ Test #6 ---------------
Senza sorting (originale):
5.97s
somma = 1273994624
Con sorting (originale):
5.985s
somma = 1273994624
------------------------------------
------------ Test #7 ---------------
Senza sorting (originale):
5.938s
somma = 70088960
Con sorting (originale):
6.016s
somma = 70088960
------------------------------------
------------ Test #8 ---------------
Senza sorting (originale):
5.923s
somma = 878654368
Con sorting (originale):
5.954s
somma = 878654368
------------------------------------
------------ Test #9 ---------------
Senza sorting (originale):
5.97s
somma = 1409354368
Con sorting (originale):
5.892s
somma = 1409354368
------------------------------------
------------ Test #10 ---------------
Senza sorting (originale):
5.906s
somma = 3158023552
Con sorting (originale):
5.892s
somma = 3158023552
------------------------------------La versione asm-inline ho preferito mantenerla nel precedente output, ma solo come paragone con gli altri risultati (e perchè guarderemo che accade in fase di generazione del codice).
Osservando solo i risultati con e senza sorting, si notano tempistiche differenti da un compilatore all'altro. Vale quindi la pena capire in quale modo viene utilizzato dal compilatore. Inizieremo da cl.exe (Microsoft).
La prima cosa che salta all'occhio è che la funzione viene inserita inline e lo si evince da quel commento "Somma" al termine dello screnshot.
Codice:
CPU Disasm
Address Hex dump Command Comments
013A51C0 > /8B4494 38 MOV EAX,DWORD PTR SS:[EDX*4+ESP+38]
013A51C4 . |B9 204E0000 MOV ECX,4E20
013A51C9 . |0F1F80 000000 NOP DWORD PTR DS:[EAX]
013A51D0 > |3D F4010000 CMP EAX,1F4
013A51D5 . |7C 0A JL SHORT 013A51E1
013A51D7 . |03F0 ADD ESI,EAX
013A51D9 . |03F0 ADD ESI,EAX
013A51DB . |03F0 ADD ESI,EAX
013A51DD . |03F0 ADD ESI,EAX
013A51DF . |03F0 ADD ESI,EAX
013A51E1 > |83E9 01 SUB ECX,1
013A51E4 .^|75 EA JNE SHORT 013A51D0
013A51E6 . |42 INC EDX
013A51E7 . |81FA A0860100 CMP EDX,186A0
013A51ED .^\72 D1 JB SHORT 013A51C0Questa parte di codice in particolare è significativa: si tratta difatti del corpo della funzione sumAbove500(). La prima riga è uno spostamento dati tra uno spiazzamento (memoria) ed un registro. In questo caso si tratta dello stack (vi è un segment override prefix, SS, ad indicarlo). La locazione puntata fa uso di indice, base e spiazzamento; l'utilizzo stesso dell'indice - il valore 4 - fa già capire che quella locazione è in realtà una posizione dell'array: l'indice è EDX, e la moltiplicazione è dovuta al fatto che i dati sono a 32bit (4byte).
Al registro ECX viene assegnato il valore 0x4E20 che in decimale è 20.000. Proseguendo si trova un CMP tra il valore EAX e 0x1F4, che in decimale è il numero 500. Si tratta dell'IF interno ai due cicli; infatti l'istruzione successiva è JL (Jump if less); quando non si verifica il salto il valore è maggiore di 500, e quindi avviene la somma. Da notare le 5 istruzioni che seguono: ADD ESI, EAX. Quello che stiamo analizzando viene chiamato "loop-unrolling", ed è un'altra delle tecniche di ottimizzazione.
Il funzionamento è relativamente semplice: si tratta di ridurre il numero delle iterazioni, ripetendo le istruzioni del corpo del ciclo. Dopo alle ADD troviamo una SUB tra ECX ed il numero 1; prima del loop era stato assegnato infatti il valore 20.000 ad ECX. Questo significa che il ciclo - come appare dalla JNE al seguito - va da 500 a 0. Ripetendo la somma 5 volte, ed eseguendo 1/5 delle iterazioni - 20.000 al posto delle 100.000 - si ottiene ottimizzazione.
Successivamente al JNE, troviamo INC EDX, che avvalora l'ipotesi iniziale: EDX è infatti l'indice usato nell'array. Il CMP alla penultima riga verifica che il valore di EDX (l'indice) sia inferiore (JB, istruzione successiva) del numero 100.000, che è infatti il ciclo esterno.
Le istruzioni che seguono, quelle che fanno uso dei registri XMM, possiamo ignorarle; basti sapere che una delle CALL effettua una chiamata alla funzione QueryPerformanceCounter (KERNEL32); si tratta di un timestamp che viene poi utilizzato per il calcolo del tempo. Le altre istruzioni effettuano una conversione tra un valore double word intero ed uno in floating point a precisione doppia.
Osserviamo ora che output produce G++.
La porzione che ci interessa particolarmente è questa:
Codice:
asm[/FONT]]
CPU Disasm
Address Hex dump Command Comments
0040171B |. 8B4424 30 MOV EAX,DWORD PTR SS:[ARG.1]
0040171F |. 31ED XOR EBP,EBP
00401721 |. 8D34B8 LEA ESI,[EDI*4+EAX]
00401724 |. 31C0 XOR EAX,EAX
00401726 |. 8D76 00 LEA ESI,[ESI]
00401729 |. 8DBC27 000000 LEA EDI,[EDI]
00401730 |> 8B5424 30 /MOV EDX,DWORD PTR SS:[ARG.1]
00401734 |> 8B0A |/MOV ECX,DWORD PTR DS:[EDX]
00401736 |. 8D1C08 ||LEA EBX,[ECX+EAX]
00401739 |. 81F9 F4010000 ||CMP ECX,1F4
0040173F |. 0F4DC3 ||CMOVGE EAX,EBX
00401742 |. 83C2 04 ||ADD EDX,4
00401745 |. 39F2 ||CMP EDX,ESI
00401747 |.^ 75 EB |\JNE SHORT 00401734
00401749 |. 83C5 01 |ADD EBP,1
0040174C |. 39EF |CMP EDI,EBP
0040174E |.^ 75 E0 \JNE SHORT 00401730SS:[ARG.1] è l'array, mentre [ARG.2] - che vediamo nello screenshot sopra - è la dimensione dell'array, e viene assegnata al registro EDI. Alla prima istruzione riportata, si vede l'assegnamento del valore [ARG.1] a EAX. Questa è la base dell'array. Il modo di procedere come si nota differisce rispetto all'altro compilatore: notiamo infatti l'istruzione LEA ESI,[EDI*4+EAX]. Sapendo che EAX contiene la base dell'array, e EDI è la dimensione, moltiplicando EDI*4 e sommando la base dell'array otteniamo l'ultimo elemento; è bene notare che viene assegnato l'indirizzo e non il valore puntato.
Lo XOR del registro EAX con sè stesso equivale a MOV EAX, 0; ha però il pregio di essere più performante (e richiede meno byte per codificare l'istruzione).
Si arriva quindi al ciclo: viene assegnato l'offset ARG.1 a EDX; ad ECX viene assegnato il valore puntato da EDX, e questo è il loop interno. Per mezzo di LEA viene calcolata la somma tra ECX ed EAX. E qui è necessario fare attenzione: ECX contiene il primo elemento del vettore, essendo la prima iterazione, mentre EAX contiene 0 (è stato azzerato in precedenza). La somma produrrà quindi come risultato il valore di ECX. Questo valore viene assegnato quindi ad EBX; successivamente viene testato il valore di ECX con 0x1F4 (500, in decimale): se il valore è >= 500, allora EBX viene assegnato ad EAX. Come si nota anche G++ rimuove l'if.
Per comprendere meglio ciò che accade: supponiamo che il valore di ECX fosse >= di 500, e che quindi EBX sia stato assegnato ad EAX. L'istruzione successiva incrementa EDX di 4; EDX punta al prossimo elemento dell'array. Viene quindi testato con l'ultimo contenuto in ESI e se gli indirizzi corrispondono il ciclo termina; in caso contrario il loop si ripete. Ora ad ECX viene assegnata la prossima locazione; ad EBX viene assegnato come valore (valore, non indirizzo) la somma tra ECX ed EAX. In pratica EAX contiene la somma, ed ECX il valore attuale. Il valore attuale viene sempre sommato sfruttando LEA e memorizzato temporaneamente in EBX. Se il valore di ECX è => di 500, allora viene assegnato al registro EAX. In questo modo EAX conterrà sempre la somma finale.
La lentezza rispetto al compilato con Microsoft è dovuta principalmente al non srotolare il ciclo (loop-unrolling).
8. Conclusione
Voglio precisare che i risultati ottenuti sopra non devono portare a conclusioni affrettate: vi possono essere altre ottimizzazioni, altre porzioni di codice, molto meglio ottimizzate da G++ rispetto al compilatore di Microsoft.
La prima parte dell'articolo termina qui. La seconda tratterà del secondo costrutto condizionale, lo switch.
PS. come nei precedenti casi, se avete domande, ponete pure li sotto. :) In caso di errori grammaticali o imprecisioni, chiedo venia, e segnalatemeli pure.
