OpenCV Suma kwadratów różnic prędkości

Question

Byłem za pomocą OpenCV zrobić jakieś dopasowanie bloku i Zauważyłem to suma kwadratów kodu różnic jest bardzo szybki w porównaniu do prostego naprzód dla pętli tak:

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

Jeśli przyjrzę się kodowi źródłowemu, aby zobaczyć, gdzie dzieje się podnoszenie ciężarów, użytkownicy OpenCV mają swoje pętle do wykonywania obliczeń różnicy w kwadraturze równej 4 do kwadratu w każdej iteracji pętli. Funkcja do sprawdzania bloku wygląda następująco.

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

To wyliczenie jest dla niepodpisanych 8 bitowych liczb całkowitych. Spełniają one podobną obliczenia dla 32-bitowych pływaków w tej funkcji:

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

Zastanawiałem się, czy ktoś ma jakiś pomysł, czy złamanie pętlę się na kawałki po 4, jak to może przyspieszyć kod? Powinienem dodać, że w tym kodzie nie występuje wielowątkowość.

Answer 1

Domyślam się, że jest to prosta implementacja unrolling the loop - zapisuje 3 dodatki i 3 porównania w każdym przejściu pętli, co może być dużym oszczędności, jeśli na przykład sprawdzenie, czy len powoduje brak pamięci podręcznej. Minusem jest to, że ta optymalizacja zwiększa złożoność kodu (np. Dodatkowa pętla for na końcu, aby zakończyć pętlę dla elementów len% 4, jeśli długość nie jest równomiernie podzielna przez 4) i, oczywiście, jest to zależna od architektury optymalizacja którego wielkość poprawy będzie się różnić w zależności od sprzętu/kompilatora/etc ...

Mimo to, jest to łatwe do naśladowania w porównaniu do większości optymalizacji i prawdopodobnie spowoduje wzrost wydajności niezależnie od architektury, więc jest to niskie ryzyko, aby po prostu wrzuć to tam i miej nadzieję na najlepsze. Ponieważ OpenCV jest tak dobrze wspieranym kawałkiem kodu, jestem pewien, że ktoś wpasował się w te fragmenty kodu i stwierdził, że są tego warte - tak jak ty to zrobiłeś.

Answer 2

Istnieje jeden oczywisty optymalizacja kodu, a mianowicie:

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