Por petición popular (de una sóla persona) inicio aquí una serie de entradas sobre diferentes aspectos de la optimización de programas: ¿Qué cosas funcionan y cuáles no? ¿cuándo es necesario optimizar a mano y cuándo es mejor dejar que el compilador lo haga por tí? etc.
Me da que no es este un tema popular, entre otras cosas porque la historia nos dice que, debido a los cambios en el hardware, lo que era una optimización ayer, ahora resulta que es más lento que un código menos trabajado. La sensación es que el esfuerzo es fútil. De hecho ese es uno de los temas que pienso tocar en el futuro: ¿Por qué el paralelismo y las jerarquías de memoria (registros->caches->RAM->Disco) no son meros caprichos de la tecnología actual, sino que hay leyes físicas fundamentales que garantizan que vamos a tenerlas en el futuro?
El tema de hoy comenzó, precisamente, como una pregunta referente a la memoria: ¿cuándo es preferible guardar unos cálculos en memoria para no tener que rehacerlos?
La respuesta es muy compleja y totalmente caso-dependiente. Existen reglas generales, pero cada caso concreto tiene sus diferentes problemas.
Por lo tanto, vamos a considerar el caso concreto, relacionado con un
programa de ajedrez:
const int UP = 8;
inline int Sign(int color)
{ return (1 - (color * 2)); } // White sign is +1, Black sign is -1
inline int Ahead(int color)
{ return (Sign(color) * UP); } // UP is -8, DOWN is +8
Supongamos que la función
Ahead se llama muchas veces siendo
color un valor que sólo admite los valores 0 y 1. ¿Es más rápido precalcular un array
ahead de dos valores?
En este caso creo que la respuesta es clara. Los cálculos son extremadamente sencillos y pueden hacerse sobre registros, así que ni hablar de precálculos. Aunque para dos únicos valores es seguro que la cache se utilizaría eficientemente, acceder a registros es más rápido que acceder a cache.
Sin embargo aún quedan algunas preguntas por responder:
- ¿Los inline hacen algo?
- ¿Se conseguiría alguna ganancia optimizando a mano Ahead y sign?
Para responder a esas preguntas lo mejor es recurrir al código máquina.
 |
| La solución está aquí |
|
|
Para ver el código que genera el compilador escribí el siguiente programa:
int main()
{
int b=rand() & 1; // Me aseguro de que b=0,1
int a=Ahead(b) ;
printf("Hello world %i !\n", a);
return 0;
}
El
rand() es necesario porque si ponemos una constante literal el compilador no se molesta en incluir las funciones y llama a
printf con el valor calculado en tiempo de compilación. El
printf es necesario porque si no usamos el valor de
a, el compilador no se molesta en incluir
nada.
El código máquina generado por
gcc con la máxima optimización (-O3), pero sin más florituras es:
sub rsp,0x8
call 0x400470 <rand@plt> // Llama a rand()
and eax,0x1 // b = rand() & 1
mov esi,0x4006bc // N.P.I.
mov edi,0x1 // N.P.I.
neg eax // eax = -b
add eax,eax // eax = eax+eax = -2*b
lea edx,[rax*8+0x8] // edx = 8*eax+8 = 8 - 16*b
xor eax,eax // eax = 0
call 0x400460 <__printf_chk@plt> // Llama a printf
xor eax,eax
add rsp,0x8
ret
La parte del programa donde se hace la "llamada" a
Ahead son simplemente tres instrucciones en código máquina que realizan la operación a = 8 - 16*b.
Se pueden hacer muchos comentarios respecto al código y la cantidad de trucos que usa:
1. Se da cuenta de que la llamada combinada a las dos funciones se puede simplificar como:
Ahead(color) = (1 - (color * 2)) * UP = 8 - 16*color
2. Aprovecha que teníamos
color en
eax y lo suma consigo mismo para obtener el doble de una forma rápida y sin necesidad de parámetros adicionales.
3. Usa la instrucción
lea (load effective address) como un truco para obtener un cálculo aritmético. Esta función suele usarse para calcular punteros y moverse por un array (índice +
offset), pero aquí se usa para hacer un cálculo. Desconozco si es posible escoger cualquier multiplicador o si hay sólo unos cuantos a elegir (lo que explicaría por qué no hace simplemente
[rax*16+0x8]).
En resumen, reto a cualquiera a que escriba un código máquina más eficiente que el que genera el compilador para este caso.
Un detalle interesante es que, en este caso, si hubiéramos usado un array, los "cálculos" necesarios para acceder a los elementos son casi igual de complicados que el cálculo en sí.
Respecto a la otra pregunta: pues no, el
gcc genera el mismo código. Da igual si hemos puesto la directiva
inline o no.
(Continuará)
