Érase una vez la Optimización cómo optimizar el codigo en C

To be, or not to be, that is the question: Whether 'tis Nobler in the mind to suffer... oops, tal vez me he equivocado de blog. Este no es el blog de literatura Inglesa? Este es un blog sobre programación en C? De acuerdo, ya que estoy, solo hay que cambiar un poco la pregunta: Optimizar, o no optimizar, esa es la pregunta...

La pregunta realmente es: "Cuando escribo código tengo que hacerlo de una manera natural, o más bien instintiva (bueno, siempre y cuando se posee el instinto del programador...) o debo seguir líneas un poco abstrusas y herméticas para que el programa sea más eficiente?" Y, por supuesto, no estoy hablando de algoritmos: en este caso, está claro que un buen algoritmo es mejor que uno malo. Estoy hablando en términos de instrucciones y grupos de instrucciones.

Hagamos una premisa: ya no estamos en el año de la pera. Y considerando esto tenemos que comportarnos/actuar. Antiguamente, los ordenadores eran (respecto a los de ahora) lentos y con pocos recursos, y los compiladores eran mucho más sencillos de los actuales. Y, entonces, utilizando la palabra mágica register se podía acelerar un loop y, consiguiendo escribir un código reducido al máximo omitiendo cualquiera operación (presuntamente) superflua, se obtenían programas mucho más eficientes. ¿Y ahora? ¿Aún tiene sentido escribir código de esta manera? El compilador realmente necesita nuestra ayuda?

El asunto es complejo, y creo que necesitaremos más de un post. En este, para empezar, analizaremos un ejemplo sencillo (?), La optimización de un loop, que es, por supuesto, una parte (de hecho, La Parte) critica para el rendimiento de un programa. Comencemos:

// myFunc1()
// versión con multiplicación, array e índice
int myFunc1(int array[], int nelems)
{
    int i;
    for (i = 0; i < nelems; i++)
        array[i] = i * 2;
}

La función es muy simple, pero contiene un bucle, y si nelems es muy grande podría llegar a ser costoso. Probemos a optimizarla usando dos técnicas: la Strength Reduction y ​​la Induction Variable: Vamos a ver lo que podemos lograr a través de varios pasos:

// myFunc2()
// versión con incremento en lugar de multiplicación
int myFunc2(int array[], int nelems)
{
    int i, incr;
    for (i = 0, incr = 0; i < nelems; i++) {
        array[i] = incr;
        incr += 2;
    }
}

// myFunc3()
// versión con incremento y pointer en lugar de array
int myFunc3(int array[], int nelems)
{
    int *ptr = array;
    int i, incr;
    for (i = 0, incr = 0; i < nelems; i++, ptr++) {
        *ptr = incr;
        incr += 2 ;
    }
}

// myFunc4()
// versión con incremento, pointer y sin indice
int myFunc4(int array[], int nelems)
{
    int *ptr = array;
    int limit = nelems * 2;
    int incr;
    for (incr = 0; incr < limit; incr += 2, ptr++)
        *ptr = incr;
}

Según lo prometido y dicho, en este post no quiero limitarme a proponer técnicas de optimización sin proporcionar datos, así que he escrito un programa de prueba y, en mi ordenador, con un valor de nelems lo suficientemente grande (0xFFFFFFF) los resultados son los siguientes:

- compilación sin optimización
myFunc1 - Tiempo transcurrido: 1.720000 segundos.
myFunc2 - Tiempo transcurrido: 1.340000 segundos.
myFunc3 - Tiempo transcurrido: 1.160000 segundos.
myFunc4 - Tiempo transcurrido: 0.920000 segundos.

Por lo tanto, parece que las técnicas de optimización funcionan. Vamos a probar de compilar optimizando, o sea, dejamos que se ocupe el compilador: usaremos la opción -O2 de GCC. Veamos los nuevos resultados:

- compilación con optimización (-O2)
myFunc1 - Tiempo transcurrido: 0.940000 segundos.
myFunc2 - Tiempo transcurrido: 0.540000 segundos.
myFunc3 - Tiempo transcurrido: 0.540000 segundos.
myFunc4 - Tiempo transcurrido: 0.540000 segundos.

Ohhh, qué sorpresa! Parece que el compilador es mejor que nosotros! Con la opción-O2, la versión sin optimizar (myFunc1) se comporta más o menos como la que hemos optimizado nosotros (myFunc4) sin utilizar -O2. No es una sorpresa: simplemente significa que el compilador ha hecho (probablemente) nuestras optimizaciones manuales. También notamos que, utilizando cualquiera de las versiones optimizadas manualmente, el compilador es capaz de añadir un plus adicional de mejora.

Sólo para confundirnos más las ideas, vamos a hacer otro test, sustituyendo la multiplicación por dos con un Shift Lógico:

/ myFunc2Bis()
// versión con shift lógico en lugar de multiplicación
int myFunc2Bis(int array[], int nelems)
{
    int i;
    for (i = 0; i < nelems; i++)
        array[i] = i << 1;
}

Y vemos la velocidad sin la optimización del compilador:

- compilación sin optimización
myFunc2Bis - Tiempo transcurrido: 0.950000 segundos.

Mira, parece que con usando solo el shift logico se consigue el mismo resultado que se obtiene aplicando todas las técnicas ilustradas (myFunc4). Y si además utilizamos la opción -O2, ¿qué pasa?

- compilación con optimización (-O2)
myFunc2Bis - Tiempo transcurrido: 0.540000 segundos.

obtenemos el mismo resultado optimizado que hemos visto arriba.. Tal vez hemos descubierto el secreto del compilador...

La primera conclusión (pero seguirán otros capítulos): merece la pena transformar un código legible y claro como el de myFunc1() en uno mucho más críptico, como el de myFunc4(), simplemente porque no confiamos en el compilador? O bien, podría añadir, porque somos tan presuntuosos como para pensar que podemos hacerlo mejor que el compilador? Repito: ya no estamos en el año de la pera, y considerando esto tenemos que actuar.

Por lo visto hasta ahora, parece que la única ayudita manual que podemos dar es usar (cuando sea posible, y sólo en los puntos realmente críticos) shift logicos en lugar de multiplicaciones. En este caso, recomiendo añadir un comentario, para evitar las maldiciones de los que leen nuestro código. Y si estáis impacientes de descubrir otras informaciones útiles en la optimización, y no queréis esperar mis próximos episodios (traidores!), os sugiero la habitual ronda en Google, o leer directamente un excelente artículo (en Italiano, lo siento) del igualmente excelente Carlo Pescio.

Volveré sobre el tema, intentando agregar datos reales y trabajo de pruebas (¡habéis visto que he cumplido mi promesa!) a los estudios sólo teóricos disponibles en la red. Y si no, ¿qué hago aquí?

Hasta el próximo post.