Estaba leyendo Niebla Agner 's manuales de optimización y me encontré con este ejemplo:
double data[LEN];
void compute()
{
const double A = 1.1, B = 2.2, C = 3.3;
int i;
for(i=0; i<LEN; i++) {
data[i] = A*i*i + B*i + C;
}
}
Agner indica que hay una forma de optimizar este código: darse cuenta de que el bucle puede evitar el uso de costosas multiplicaciones y, en su lugar, utilizar los "deltas" que se aplican por iteración.
Utilizo un trozo de papel para confirmar la teoría, primero...
...y por supuesto, tiene razón - en cada iteración del bucle podemos calcular el nuevo resultado basándonos en el anterior, añadiendo un "delta". Este delta comienza en el valor "A+B", y luego se incrementa en "2*A" en cada paso.
Así que actualizamos el código para que quede así:
void compute()
{
const double A = 1.1, B = 2.2, C = 3.3;
const double A2 = A+A;
double Z = A+B;
double Y = C;
int i;
for(i=0; i<LEN; i++) {
data[i] = Y;
Y += Z;
Z += A2;
}
}
En términos de complejidad operativa, la diferencia entre estas dos versiones de la función es realmente sorprendente. Las multiplicaciones tienen fama de ser significativamente más lentas en nuestras CPU, en comparación con las sumas. Y hemos sustituido 3 multiplicaciones y 2 sumas... ¡por sólo 2 sumas!
Así que sigo adelante y añado un bucle para ejecutar compute
muchas veces - y luego mantener el tiempo mínimo que se tardó en ejecutar:
unsigned long long ts2ns(const struct timespec *ts)
{
return ts->tv_sec * 1e9 + ts->tv_nsec;
}
int main(int argc, char *argv[])
{
unsigned long long mini = 1e9;
for (int i=0; i<1000; i++) {
struct timespec t1, t2;
clock_gettime(CLOCK_MONOTONIC_RAW, &t1);
compute();
clock_gettime(CLOCK_MONOTONIC_RAW, &t2);
unsigned long long diff = ts2ns(&t2) - ts2ns(&t1);
if (mini > diff) mini = diff;
}
printf("[-] Took: %lld ns.\n", mini);
}
Compilo las dos versiones, las ejecuto... y veo esto:
gcc -O3 -o 1 ./code1.c
gcc -O3 -o 2 ./code2.c
./1
[-] Took: 405858 ns.
./2
[-] Took: 791652 ns.
Bueno, eso es inesperado. Como informamos del tiempo mínimo de ejecución, estamos desechando el "ruido" causado por diversas partes del sistema operativo. También tuvimos cuidado de ejecutar en una máquina que no hace absolutamente nada. Y los resultados son más o menos repetibles - volver a ejecutar los dos binarios muestra que este es un resultado consistente:
for i in {1..10} ; do ./1 ; done
[-] Took: 406886 ns.
[-] Took: 413798 ns.
[-] Took: 405856 ns.
[-] Took: 405848 ns.
[-] Took: 406839 ns.
[-] Took: 405841 ns.
[-] Took: 405853 ns.
[-] Took: 405844 ns.
[-] Took: 405837 ns.
[-] Took: 406854 ns.
for i in {1..10} ; do ./2 ; done
[-] Took: 791797 ns.
[-] Took: 791643 ns.
[-] Took: 791640 ns.
[-] Took: 791636 ns.
[-] Took: 791631 ns.
[-] Took: 791642 ns.
[-] Took: 791642 ns.
[-] Took: 791640 ns.
[-] Took: 791647 ns.
[-] Took: 791639 ns.
Lo único que hay que hacer a continuación es ver qué tipo de código ha creado el compilador para cada una de las dos versiones.
objdump -d -S
muestra que la primera versión de compute
- el "tonto", pero de alguna manera rápido código - tiene un bucle que se parece a esto:
¿Y la segunda versión, optimizada, que sólo hace dos añadidos?
No sé ustedes, pero yo estoy... perplejo. La segunda versión tiene aproximadamente 4 veces menos instrucciones, siendo las dos principales sólo ESS -( addsd
). La primera versión, no sólo tiene 4 veces más instrucciones... también está llena (como era de esperar) de multiplicaciones ( mulpd
).
Confieso que no esperaba ese resultado. No porque sea fan de Agner (lo soy, pero eso es irrelevante).
¿Alguna idea de lo que me falta? ¿He cometido algún error que pueda explicar la diferencia de velocidad? Tenga en cuenta que he hecho la prueba en un Xeon W5580 y un Xeon E5-1620 - en ambas, la primera versión (tonta) es mucho más rápida que la segunda.
Para facilitar la reproducción de los resultados, existen dos gists con las dos versiones del código: Tonto pero de alguna manera más rápido y optimizado, pero de alguna manera más lento .
P.D. Por favor, no hagas comentarios sobre cuestiones de precisión en coma flotante; no es el objeto de esta pregunta.