c++ - ¿Por qué cambiar el orden de estas instrucciones afecta significativamente el rendimiento?

optimization

Question

Para una tarea en la escuela, estoy realizando una operación intensiva en una gran variedad de números. Mientras evaluaba una versión de un solo hilo que operaba en toda la matriz y comparaba mis resultados con los de mis compañeros, noté un comportamiento extraño.

La función es la siguiente:

int compute (char a[], int start, int end) {
int sum = 0;
int min = a[start];
int max = a[start];
for (int i = start; i < end; i++) {
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
int cube = a[i] * a[i] * a[i];
sum += cube;
}
return sum;
}

Pero el programa de mi compañero de clase se ejecuta constantemente más rápido, a menudo mucho más rápido. Su código es idéntico, excepto por el orden de las instrucciones en el cuerpo del bucle:

for (int i = start; i < end; i++) {
int cube = a[i] * a[i] * a[i];
sum += cube;
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
}

Aquí está la salida que compara el tiempo de ejecución de cada versión con una matriz de entrada de tamaño 1,000,000,000 (inicializado con bytes firmados al azar):

Min/max first:
sum = 5445493143089, min = -128, max = 127
Completed in 1.050268 sec
Product-sum first:
sum = 5445493143089, min = -128, max = 127
Completed in 1.010639 sec

Hemos inspeccionado el ensamblaje generado para ambas versiones y hemos observado las mismas instrucciones presentes, simplemente ordenadas de manera diferente. Que yo sepa, esto no debería tener un efecto tan significativo como lo hace, pero podría estar equivocado. (También notamos que los registros utilizados diferían enormemente, pero esto dudo especialmente que debería tener un efecto).

Nos encontramos con este comportamiento cuando -std=c11 tanto para C ( -std=c11 ) como para C ++ ( -std=c++11 ).

¿Por qué el orden de esas líneas afecta en gran medida el comportamiento del programa secuencial? También estamos comparando una versión paralela de la operación, y en contraste, su comportamiento casi no cambia. Busqué en el reordenamiento de memoria como un posible culpable, pero ese no parece ser el problema ya que la versión paralela prácticamente no se ve afectada (y de todos modos no hay superposición en las particiones).

Pruebas intensivas de espalda con espalda que demuestran el comportamiento. La suma de productos es siempre más rápida que min / max, incluso en alternancia y permitiendo el almacenamiento en caché.

Answer 1

Podría ser tan simple como la predicción de salto del procesador funciona mejor con los saltos condicionales en la parte inferior del bucle ...

Answer 2

Si ponemos saltos explícitos en el código, puede ver que el que tiene las condicionales al final puede evitar un salto la mayor parte del tiempo. Esto es similar al código que realmente será generado por el compilador.

Primera forma, min / max primero:

 int i = lo;
goto start;
loop:
i++;
start:
if (!(i < hi)) goto end;
if (!(a[i] > ret.max)) goto label1;
ret.max = a[i];
label1:
if (!(a[i] < ret.min)) goto label2;
ret.min = a[i];
label2:
long long square = a[i] * a[i];
ret.sum += square;
goto loop;
end:

Segunda forma, min / max ultima

 int i = lo;
goto start;
loop:
i++;
start:
if (!(i < hi)) goto end;
long long square = a[i] * a[i];
ret.sum += square;
if (!(a[i] > ret.max)) goto label1;
ret.max = a[i];
label1:
if (!(a[i] < ret.min)) goto loop;
ret.min = a[i];
goto loop;
end: