Prestazioni di trasmissione da size_t a double

Question

TL; DR: Perché la moltiplicazione/fusione dei dati in size_t è lenta e perché varia in base alla piattaforma?

Sto riscontrando alcuni problemi di prestazioni che non comprendo completamente. Il contesto è un frame grabber della telecamera in cui un'immagine Uint16_t 128x128 viene letta e post-elaborata ad una velocità di diversi 100 Hz.

Nella postelaborazione viene generato un istogramma frame->histo che è di uint32_t e dispone di thismaxval = 2^16 elementi, in pratica vengono calcolati tutti i valori di intensità. Utilizzando questo istogramma calcolo la somma e somma squadrato

double sum=0, sumsquared=0; 
size_t thismaxval = 1 << 16; 

for(size_t i = 0; i < thismaxval; i++) { 
    sum += (double)i * frame->histo[i]; 
    sumsquared += (double)(i * i) * frame->histo[i]; 
} 

profilatura il codice con profilo Mi sono le seguenti (campioni, percentuale, codice):

58228 32.1263 : sum += (double)i * frame->histo[i]; 
116760 64.4204 : sumsquared += (double)(i * i) * frame->histo[i]; 

o, la prima linea riprende 32 % del tempo della CPU, la seconda riga del 64%.

Ho fatto un po 'di benchmark e sembra che il tipo di dati/casting sia problematico. Quando cambio il codice in

uint_fast64_t isum=0, isumsquared=0; 

for(uint_fast32_t i = 0; i < thismaxval; i++) { 
    isum += i * frame->histo[i]; 
    isumsquared += (i * i) * frame->histo[i]; 
} 

esegue ~ 10 volte più veloce. Tuttavia, questo successo in termini di prestazioni varia anche a seconda della piattaforma. Sulla workstation, una CPU Core i7 950 @ 3,07 GHz, il codice è 10 volte più veloce. Sul mio Macbook8,1, che ha un processore Intel Core i7 Sandy Bridge da 2.7 GHz (2620M), il codice è solo 2x più veloce.

Ora mi chiedo:

1. Perché il codice originale in modo lento e facilmente accelerato?
2. Perché varia così tanto per piattaforma?

Aggiornamento:

ho compilato il codice precedente con

g++ -O3 -Wall cast_test.cc -o cast_test 

Update2:

Ho eseguito il codice ottimizzato attraverso un profiler (Instruments su Mac, come Shark) e ha trovato due cose:

1) Il ciclo stesso richiede in alcuni casi una notevole quantità di tempo. thismaxval è di tipo size_t.

1. for(size_t i = 0; i < thismaxval; i++) prende il 17% del mio tempo di esecuzione totale
2. for(uint_fast32_t i = 0; i < thismaxval; i++) prende 3,5%
3. for(int i = 0; i < thismaxval; i++) non compare nel profiler, presumo che sia inferiore a 0.1%

2) I tipi di dati e la materia colata come segue:

1. sumsquared += (double)(i * i) * histo[i]; 15% (con size_t i)
2. sumsquared += (double)(i * i) * histo[i]; 36% (con uint_fast32_t i)
3. isumsquared += (i * i) * histo[i]; 13% (con uint_fast32_t i , uint_fast64_t isumsquared)
4. isumsquared += (i * i) * histo[i]; 11% (con int i, uint_fast64_t isumsquared)

Sorprendentemente, int è più veloce di uint_fast32_t?

Update4:

ho incontrato qualche altro test con diversi tipi di dati e compilatori diversi, su una macchina. I risultati sono i seguenti.

Per testd 0 - 2, il codice relativo è

for(loop_t i = 0; i < thismaxval; i++) 
     sumsquared += (double)(i * i) * histo[i]; 

con sumsquared un doppio, e loop_tsize_t, uint_fast32_t e int per test 0, 1 e 2.

Per i test 3-- 5 il codice è

for(loop_t i = 0; i < thismaxval; i++) 
     isumsquared += (i * i) * histo[i]; 

con isumsquared di tipo uint_fast64_t e loop_t nuovo size_t, uint_fast32_t e int per test 3, 4 e 5.

I compilatori ho usato sono 4.2.1 gcc, gcc 4.4.7, gcc 4.6.3 e 4.7.0 gcc. I tempi sono in percentuale del tempo totale della CPU del codice, quindi mostrano le prestazioni relative, non assolute (sebbene il tempo di esecuzione fosse abbastanza costante a 21 secondi). Il tempo di CPU è per entrambe le due linee, perché non sono sicuro che il profiler abbia correttamente separato le due linee di codice.

 
gcc: 4.2.1 4.4.7 4.6.3 4.7.0 
---------------------------------- 
test 0: 21.85 25.15 22.05 21.85 
test 1: 21.9 25.05 22  22 
test 2: 26.35 25.1 21.95 19.2 
test 3: 7.15 8.35 18.55 19.95 
test 4: 11.1 8.45 7.35 7.1 
test 5: 7.1 7.8 6.9 7.05 

o:

Sulla base di questo, sembra che casting è costoso, indipendentemente dal tipo integer che uso.

Inoltre, sembra che gcc 4.6 e 4.7 non siano in grado di ottimizzare correttamente il ciclo 3 (size_t e uint_fast64_t).

Answer 1

Per le vostre domande originali:

1. Il codice è lento perché coinvolge la conversione da intero a tipi di dati float. Ecco perché è facilmente accelerato quando si utilizza anche un tipo di dati intero per le variabili di somma perché non richiede più una conversione float .
2. La differenza è il risultato di diversi fattori .Ad esempio, dipende dall'efficienza con cui una piattaforma è in grado di eseguire una conversione int-> float. Inoltre questa conversione potrebbe anche compromettere le ottimizzazioni interne del processore nel programma motore di previsione e di previsione, cache, ... e anche le funzioni di parallelizzazione interne dei processori possono avere un'enorme influenza nei calcoli di tali .

Per le ulteriori domande:

• "Sorprendentemente int è più veloce di uint_fast32_t"? Qual è il sizeof (size_t) e sizeof (int) sulla tua piattaforma? Un'ipotesi che posso fare è che entrambi sono probabilmente a 64 bit e quindi un cast a 32 bit non solo può darti degli errori di calcolo ma include anche una penalità diversa per il casting .

In generale, cercare di evitare i cast visibili e nascosti nel miglior modo possibile se questi non sono realmente necessari. Ad esempio, prova a scoprire quale tipo di dati reale è nascosto dietro "size_t" sul tuo ambiente (gcc) e usa quello per la variabile loop. Nel tuo esempio il quadrato di uint non può essere un tipo di dati float quindi non ha senso usare il doppio qui. Attenersi ai tipi interi per ottenere le massime prestazioni.

Answer 2

su x86, la conversione di uint64_t a virgola mobile è più lento perché ci sono solo le istruzioni per convertire int64_t, int32_t e int16_t. int16_t e in modalità 32-bit int64_t può essere convertito solo utilizzando le istruzioni x87, non SSE.

Convertendo uint64_t a virgola mobile, GCC 4.2.1 converte il valore come se fosse un int64_t e poi aggiunge 2 se era negativo per compensare. (Quando si utilizza il x87, su Windows e * BSD o se è stato modificato il controllo di precisione, attenzione che la conversione ignora controllo di precisione ma l'aggiunta la rispetta.)

Un uint32_t è prima esteso a int64_t.

Durante la conversione di numeri interi a 64 bit in modalità a 32 bit su processori con determinate funzionalità a 64 bit, un problema di inoltro da magazzino a carico può causare stalli. Il numero intero a 64 bit viene scritto come due valori a 32 bit e riletto come un valore a 64 bit. Questo può essere molto brutto se la conversione fa parte di una lunga catena di dipendenze (non in questo caso).