En el principio fue el código máquina (I)

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á)