OpenCV somma delle differenze al quadrato accelerare

Question

Sto usando l'OpenCV a fare un po 'di corrispondenza del blocco e ho notato che è somma di codice differenze al quadrato è molto veloce rispetto ad un dritto in avanti per ciclo come questo:

int SSD = 0; 
for(int i =0; i < arraySize; i++) 
    SSD += (array1[i] - array2[i])*(array1[i] - array2[i]); 

Se osservo il codice sorgente per vedere dove avviene il sollevamento pesante, gli utenti di OpenCV hanno cicli di differenza di 4 quadrati alla volta in ciascuna iterazione del ciclo. La funzione per eseguire la corrispondenza dei blocchi è simile a questa.

int64 
icvCmpBlocksL2_8u_C1(const uchar * vec1, const uchar * vec2, int len) 
{ 
int i, s = 0; 
int64 sum = 0; 

for(i = 0; i <= len - 4; i += 4) 
{ 
    int v = vec1[i] - vec2[i]; 
    int e = v * v; 

    v = vec1[i + 1] - vec2[i + 1]; 
    e += v * v; 
    v = vec1[i + 2] - vec2[i + 2]; 
    e += v * v; 
    v = vec1[i + 3] - vec2[i + 3]; 
    e += v * v; 
    sum += e; 
} 

for(; i < len; i++) 
{ 
    int v = vec1[i] - vec2[i]; 

    s += v * v; 
} 

return sum + s; 
} 

Questo calcolo è per interi a 8 bit senza segno. Essi svolgono un calcolo simile per carri a 32 bit in questa funzione:

double 
icvCmpBlocksL2_32f_C1(const float *vec1, const float *vec2, int len) 
{ 
double sum = 0; 
int i; 

for(i = 0; i <= len - 4; i += 4) 
{ 
    double v0 = vec1[i] - vec2[i]; 
    double v1 = vec1[i + 1] - vec2[i + 1]; 
    double v2 = vec1[i + 2] - vec2[i + 2]; 
    double v3 = vec1[i + 3] - vec2[i + 3]; 

    sum += v0 * v0 + v1 * v1 + v2 * v2 + v3 * v3; 
} 
for(; i < len; i++) 
{ 
    double v = vec1[i] - vec2[i]; 

    sum += v * v; 
} 
return sum; 
} 

Mi chiedevo se qualcuno avesse qualche idea se la rottura di un anello in blocchi di 4 come questo potrebbe accelerare il codice? Devo aggiungere che non c'è il multithreading che si verifica in questo codice.

Answer 1

La mia ipotesi è che questa è solo un'implementazione semplice di unrolling the loop - salva 3 aggiunte e 3 confronti su ogni passaggio del ciclo, che può essere un grande risparmio se, ad esempio, il controllo di len comporta un errore di cache. Il rovescio della medaglia è che questa ottimizzazione aggiunge complessità al codice (ad esempio, il ciclo aggiuntivo alla fine per terminare il ciclo per gli oggetti len% 4 rimasti se la lunghezza non è equamente divisibile per 4) e, naturalmente, è un'ottimizzazione dipendente dall'architettura la cui entità di miglioramento varierà in base all'hardware/compilatore/ecc ...

Tuttavia, è semplice da seguire rispetto alla maggior parte delle ottimizzazioni e probabilmente porterà a un qualche tipo di aumento delle prestazioni indipendentemente dall'architettura, quindi è a basso rischio solo per buttalo lì e spera per il meglio. Dal momento che OpenCV è un pezzo di codice così ben supportato, sono sicuro che qualcuno ha strumentato questi pezzi di codice e li ha trovati a valere la pena - come tu stesso hai fatto.

Answer 2

C'è un evidente ottimizzazione del codice, vale a dire:

int SSD = 0; 
for(int i = 0; i < arraySize; i++) 
{ 
    int v = array1[i] - array2[i]; 
    SSD += v * v; 
}