OpenCV suma de diferencias al cuadrado acelerar

Question

He estado usando el OPENCV hacer algo de coincidencia de bloques y me he dado cuenta de que es la suma de las diferencias al cuadrado código es muy rápido en comparación con una recta hacia adelante para el bucle de esta manera:

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

Si miro el código fuente para ver dónde ocurre el trabajo pesado, las personas OpenCV tienen sus bucles for para hacer cálculos de 4 diferencias cuadradas a la vez en cada iteración del ciclo. La función para hacer la coincidencia de bloque se ve así.

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

Este cálculo es para enteros de 8 bits sin signo. Llevan a cabo un cálculo similar para la flota de 32 bits en esta función:

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

Me preguntaba si alguien tenía alguna idea de si romper un bucle en trozos de 4 les gusta esto podría acelerar el código? Debo añadir que no hay multithreading en este código.

Answer 1

Mi conjetura es que esto es sólo una implementación sencilla de unrolling the loop - se ahorra 3 adiciones y 3 se comparan en cada pasada del bucle, que puede ser un gran ahorro si, por ejemplo, comprobar len implica una pérdida de caché. La desventaja es que esta optimización agrega complejidad de código (por ejemplo, el bucle for adicional al final para terminar el bucle para los elementos de len% 4 que quedan si la longitud no es divisible por 4) y, por supuesto, es una optimización dependiente de la arquitectura cuya magnitud de mejora variará según el hardware/compilador/etc ...

Aún así, es sencillo de seguir en comparación con la mayoría de las optimizaciones y probablemente resultará en algún tipo de aumento de rendimiento independientemente de la arquitectura, por lo que es de bajo riesgo solo tirarlo allí y esperar lo mejor. Como OpenCV es una porción de código tan bien respaldada, estoy seguro de que alguien armó estos trozos de código y descubrió que valía la pena, como tú mismo has hecho.

Answer 2

Hay una optimización evidente de su código, a saber:

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