En una interesante discusión en el grupo de Facebook de la Comunidad .NET Tijuana surgió el tema de las microoptimizaciones, en particular el uso de evaluación en corto circuito y el ahorro de ifs «que son muy costosos al CPU».

Mi último argumento:

A lo que iba es que el short-circuit, si bien te puede ahorrar ifs, también puede darte sorpresas como brincarse validaciones de seguridad. Ha ocurrido en otros lenguajes. Yo prefiero un if explicito, que en realidad no es nada caro al CPU, a menos que no diseñes bien tus condiciones.

Entonces el autor original hace un planteamiento: ¿Cuál de los dos siguientes programas es más rápido?

Programa X:

for (int i = 0; i < 1000; i++)
{
    if (x >= 10)
    {
        x = 0;
    }
    else
    {
        x++;
    }
}

Programa Y:

int y = 0;
for (int i = 0; i < 1000; i++)
{
    y = (y + 1) % 10;
}

A simple vista podría parecer que el programa X, el que tiene ifs, es más complejo: son más líneas y se divide el flujo del programa.

Pero, como siempre, la respuesta no es tan sencilla. Entonces se abre la caja de pandora. Para poder contestar sin experimentación se requiere de un conocimiento profundo y preciso de varios comportamientos que influyen en el rendimiento de un programa. Lo mejor que podemos hacer es el experimento.

¿En realidad importa?

Compilaré los siguientes programas en C:

Programa X:

#define LIMIT 1000
int main(void) {
    int x = 0;
    for (int i = 0; i < LIMIT; i++)
    {
        if (x >= 10)
        {
            x = 0;
        }
        else
        {
            x++;
        }
    }
    return 0;
}

Programa Y:

#define LIMIT 1000
int main(void) {
    int y = 0;
    for (int i = 0; i < LIMIT; i++)
    {
        y = (y + 1) % 10;
    }
    return 0;
}

Veamos cuál es más rápido:

$ c99 -o x x.c
$ c99 -o y y.c
$ time ./x

real	0m0.001s
user	0m0.000s
sys	0m0.001s
$ time ./y

real	0m0.001s
user	0m0.000s
sys	0m0.001s

Háganle caso al renglón user. En realidad no importa a cuál le hagan caso, los resultados de los dos programas son iguales.

Evidentemente ¡ambos programas son demasiado rápidos siquiera para ser medidos a pesar de que se trata de 1,000 iteraciones! Es decir, si hay una diferencia, es claro que ésta es menor a 1 ms. Realmente no nos importa.

Sin embargo, si estamos programando un sistema de manejo masivo de información (como un DBMS), esto podría resultar en una diferencia considerable. Por eso estos sistemas se escriben en C. En esos casos no sólo basta saber si importa, sino qué tanto importa.

Aumentemos el límite a 1,000,000

Qué bueno que definí el límite en una línea independiente, así puedo usar sed para modificar los archivos y que quede de manifiesto en la salida que pego a continuación.

$ sed -i -re 's/^#define LIMIT.*$/#define LIMIT 1000000/' x.c y.c
$ 
$ cat x.c
#define LIMIT 1000000
int main(void) {
    int x = 0;
    for (int i = 0; i < LIMIT; i++)
    {
        if (x >= 10)
        {
            x = 0;
        }
        else
        {
            x++;
        }
    }
    return 0;
}

$ cat y.c
#define LIMIT 1000000
int main(void) {
    int y = 0;
    for (int i = 0; i < LIMIT; i++)
    {
        y = (y + 1) % 10;
    }
    return 0;

Nuestra modificación funcionó. El límite quedó a 1,000,000. Compilemos:

$ c99 -o x x.c
$ c99 -o y y.c

Compila correctamente. ¿Cómo quedaron los tiempos?

$ time ./x

real	0m0.005s
user	0m0.005s
sys	0m0.000s
$ time ./y

real	0m0.012s
user	0m0.012s
sys	0m0.000s

Se asoma una ligera tendencia a favor del programa X. Sin embargo es prácticamente negligible. ¡Estamos hablando de 7 ns de diferencia por iteración!

Probemos con 1,000,000,000 de iteraciones

Sin embargo, los números aún son muy chicos como para tener suficiente resolución. Cualquier pequeño efecto pasajero sobre la máquina nos podría perjudicar en la medición. Una manera barata de mejorar esto es aumentando a 1,000,000,000 de iteraciones.

$ sed -i -re 's/^#define LIMIT.*$/#define LIMIT 1000000000/' x.c y.c;
$ c99 -o x x.c
$ c99 -o y y.c
$ time ./x

real	0m2.737s
user	0m2.735s
sys	0m0.000s
$ time ./y

real	0m8.827s
user	0m8.816s
sys	0m0.000s

Ya se observan valores más medibles: la diferencia es de 6 ns por iteración. Esta diferencia radica en que entre más iteraciones, los efectos de la carga del programa desde disco (o caché de disco), segmentación de memoria e inicialización de las librerías se reducen en comparación.

Niveles de optimización en los compiladores

GCC soporta varios niveles de optimización ¡y vaya que tienen efecto! ¿Qué pasa si medimos el tiempo de ejecución de los programas con 1,000,000,000 de iteraciones utilizando diferentes niveles de mágicas optimizaciones del compilador?

Para compilarlos probaremos las banderas -O0, -O1, -O2, -O3, -Ofast y -Os. Por ejemplo, para compilar con el nivel de optimización 1, usaríamos la siguiente instrucción:

$ c99 -O1 -o x x.c

Estos son los resultados, medidos en segundos:

Nivel -O	X	Y
0	2.734	8.806
1	1.450	0.339
2	0.000	0.000
3	0.000	0.000
fast	0.000	0.000
s	0.000	0.000

Dos observaciones interesantes:

1. En -O1, el programa Y funciona más rápido que el programa X.
2. A partir de -O2 ¡el tiempo se desploma a cero!

Pero no todo es tan simple…

Los compiladores son muy astutos, parte 1

Comparemos el código generado por -O0 contra el código generado por -O2 para el programa X:

$ c99 -O0 -o x x.c
$ gdb -batch -ex 'file x' -ex 'disassemble main'
Dump of assembler code for function main:
   0x00000000004004ed <+0>:	push   %rbp
   0x00000000004004ee <+1>:	mov    %rsp,%rbp
   0x00000000004004f1 <+4>:	movl   $0x0,-0x8(%rbp)
   0x00000000004004f8 <+11>:	movl   $0x0,-0x4(%rbp)
   0x00000000004004ff <+18>:	jmp    0x400518 <main+43>
   0x0000000000400501 <+20>:	cmpl   $0x9,-0x8(%rbp)
   0x0000000000400505 <+24>:	jle    0x400510 <main+35>
   0x0000000000400507 <+26>:	movl   $0x0,-0x8(%rbp)
   0x000000000040050e <+33>:	jmp    0x400514 <main+39>
   0x0000000000400510 <+35>:	addl   $0x1,-0x8(%rbp)
   0x0000000000400514 <+39>:	addl   $0x1,-0x4(%rbp)
   0x0000000000400518 <+43>:	cmpl   $0x3b9ac9ff,-0x4(%rbp)
   0x000000000040051f <+50>:	jle    0x400501 <main+20>
   0x0000000000400521 <+52>:	mov    $0x0,%eax
   0x0000000000400526 <+57>:	pop    %rbp
   0x0000000000400527 <+58>:	retq   
End of assembler dump.
$ 
$ c99 -O2 -o x x.c
$ gdb -batch -ex 'file x' -ex 'disassemble main'
Dump of assembler code for function main:
   0x0000000000400400 <+0>:	xor    %eax,%eax
   0x0000000000400402 <+2>:	retq   
End of assembler dump.

¡¿DAFUQ?! ¡¿En serio?! ¿El compilador cambió todo el código que escribimos con el sudor de nuestra frente, por dos míseras instrucciones?

Pues sí, resulta que el compilador observó que nuestro cómputo no sirve de nada porque de todos modos estamos regresando 0 en la línea return 0, así que todo nuestro código no tiene efecto observable. Por eso lo toma, lo tira a la basura y nosotros seguimos observando exactamente el mismo resultado: el correcto.

Los compiladores son muy astutos, parte 2

Hagamos el mismo análisis, comparando el código generado por -O0 contra el código generado por -O2, ahora para el programa Y:

$ c99 -O0 -o y y.c
$ gdb -batch -ex 'file y' -ex 'disassemble main'
Dump of assembler code for function main:
   0x00000000004004ed <+0>:	push   %rbp
   0x00000000004004ee <+1>:	mov    %rsp,%rbp
   0x00000000004004f1 <+4>:	movl   $0x0,-0x8(%rbp)
   0x00000000004004f8 <+11>:	movl   $0x0,-0x4(%rbp)
   0x00000000004004ff <+18>:	jmp    0x400536 <main+73>
   0x0000000000400501 <+20>:	mov    -0x8(%rbp),%eax
   0x0000000000400504 <+23>:	lea    0x1(%rax),%ecx
   0x0000000000400507 <+26>:	mov    $0x66666667,%edx
   0x000000000040050c <+31>:	mov    %ecx,%eax
   0x000000000040050e <+33>:	imul   %edx
   0x0000000000400510 <+35>:	sar    $0x2,%edx
   0x0000000000400513 <+38>:	mov    %ecx,%eax
   0x0000000000400515 <+40>:	sar    $0x1f,%eax
   0x0000000000400518 <+43>:	sub    %eax,%edx
   0x000000000040051a <+45>:	mov    %edx,%eax
   0x000000000040051c <+47>:	mov    %eax,-0x8(%rbp)
   0x000000000040051f <+50>:	mov    -0x8(%rbp),%edx
   0x0000000000400522 <+53>:	mov    %edx,%eax
   0x0000000000400524 <+55>:	shl    $0x2,%eax
   0x0000000000400527 <+58>:	add    %edx,%eax
   0x0000000000400529 <+60>:	add    %eax,%eax
   0x000000000040052b <+62>:	sub    %eax,%ecx
   0x000000000040052d <+64>:	mov    %ecx,%eax
   0x000000000040052f <+66>:	mov    %eax,-0x8(%rbp)
   0x0000000000400532 <+69>:	addl   $0x1,-0x4(%rbp)
   0x0000000000400536 <+73>:	cmpl   $0x3b9ac9ff,-0x4(%rbp)
   0x000000000040053d <+80>:	jle    0x400501 <main+20>
   0x000000000040053f <+82>:	mov    $0x0,%eax
   0x0000000000400544 <+87>:	pop    %rbp
   0x0000000000400545 <+88>:	retq   
End of assembler dump.
$ 
$ c99 -O2 -o y y.c
$ gdb -batch -ex 'file y' -ex 'disassemble main'
Dump of assembler code for function main:
   0x0000000000400400 <+0>:	xor    %eax,%eax
   0x0000000000400402 <+2>:	retq   
End of assembler dump.

No sólo ocurre lo mismo, sino que además llama la atención la línea marcada en negritas:

0x000000000040050e <+33>:	imul   %edx

A pesar de no utilizar optimizaciones, el compilador sabe que, para calcular el módulo, usar la operación DIV tomaría más ciclos de reloj que seguir un algoritmo basado en multiplicaciones enteras, y sabe que eso es cierto en este caso y en esta arquitectura.

Otro ejemplo de una optimización común: cuando hablamos de una variable x que es entera positiva, la expresión x / 2 suele ser convertida en x >> 1.

¿Cómo evitar que nuestro código sea eliminado?

Simplemente es cuestión de usar el valor. Podríamos imprimirlo en pantalla, pero para mantener limpio el desensamblaje mejor cambiemos return 0 por return x o return y según corresponda:

$ sed -i -re "s/return 0;/return x;/" x.c
$ sed -i -re "s/return 0;/return y;/" y.c
$ cat x.c
#define LIMIT 1000000000
int main(void) {
    int x = 0;
    for (int i = 0; i < LIMIT; i++)
    {
        if (x >= 10)
        {
            x = 0;
        }
        else
        {
            x++;
        }
    }
    return x;
}

$ cat y.c
#define LIMIT 1000000000
int main(void) {
    int y = 0;
    for (int i = 0; i < LIMIT; i++)
    {
        y = (y + 1) % 10;
    }
    return y;
}

Bien, nuestro código fuente está correcto. Compilemos con -O3:

$ c99 -O3 -o x x.c
$ c99 -O3 -o y y.c

Compiló correctamente. Verifiquemos en el código generado:

$ gdb -batch -ex 'file x' -ex 'disassemble main'
Dump of assembler code for function main:
   0x0000000000400400 <+0>:	mov    $0x3b9aca00,%edx
   0x0000000000400405 <+5>:	xor    %eax,%eax
   0x0000000000400407 <+7>:	xor    %esi,%esi
   0x0000000000400409 <+9>:	nopl   0x0(%rax)
   0x0000000000400410 <+16>:	lea    0x1(%rax),%ecx
   0x0000000000400413 <+19>:	cmp    $0x9,%eax
   0x0000000000400416 <+22>:	mov    %ecx,%eax
   0x0000000000400418 <+24>:	cmovg  %esi,%eax
   0x000000000040041b <+27>:	sub    $0x1,%edx
   0x000000000040041e <+30>:	jne    0x400410 <main+16>
   0x0000000000400420 <+32>:	repz retq 
End of assembler dump.
$ gdb -batch -ex 'file y' -ex 'disassemble main'
Dump of assembler code for function main:
   0x0000000000400400 <+0>:	mov    $0x3b9aca00,%esi
   0x0000000000400405 <+5>:	xor    %edx,%edx
   0x0000000000400407 <+7>:	mov    $0x66666667,%edi
   0x000000000040040c <+12>:	nopl   0x0(%rax)
   0x0000000000400410 <+16>:	lea    0x1(%rdx),%ecx
   0x0000000000400413 <+19>:	mov    %ecx,%eax
   0x0000000000400415 <+21>:	imul   %edi
   0x0000000000400417 <+23>:	mov    %ecx,%eax
   0x0000000000400419 <+25>:	sar    $0x1f,%eax
   0x000000000040041c <+28>:	sar    $0x2,%edx
   0x000000000040041f <+31>:	sub    %eax,%edx
   0x0000000000400421 <+33>:	lea    (%rdx,%rdx,4),%eax
   0x0000000000400424 <+36>:	add    %eax,%eax
   0x0000000000400426 <+38>:	sub    %eax,%ecx
   0x0000000000400428 <+40>:	sub    $0x1,%esi
   0x000000000040042b <+43>:	mov    %ecx,%edx
   0x000000000040042d <+45>:	jne    0x400410 <main+16>
   0x000000000040042f <+47>:	mov    %ecx,%eax
   0x0000000000400431 <+49>:	retq   
End of assembler dump.

Claramente el código ya no está siendo eliminado.

$ time ./x

real	0m1.460s
user	0m1.458s
sys	0m0.000s
$ time ./y

real	0m4.188s
user	0m4.180s
sys	0m0.004s

El resultado: ~3 ns de diferencia por iteración en -O3.

La nueva tabla completa de resultados entre los diferentes niveles de optimización, medidos en segundos:

-O	X	Y
0	2.729	8.810
1	1.455	4.188
2	1.455	4.180
3	1.458	4.180
fast	1.458	4.185
s	1.451	5.688

¡Tenemos un ganador!

Observaciones interesantes: A diferencia de los resultados que obtuvimos en la primera tabla, donde el código usaba return 0, en esta ocasión el programa Y ya no gana ni siquiera en -O1. En realidad no es que fuera más óptimo anteriormente, sino que el compilador alcanzaba a descartarlo mejor por el uso de return 0.

Conclusiones

Las conclusiones te tocan a ti. 🙂

Actualización

Después de hacer la publicación caí en cuenta de que olvidé mencionar algunos detalles importantes:

1. El sistema donde se probó es un Intel(R) Xeon(R) CPU X5472 @ 3.00GHz de 8 núcleos con memoria ECC. Nunca vi que se usara más de un solo núcleo. Los invito a repetir las pruebas en sus laptops y Raspberry Pi. Raspberry Pi es ARM, hay que tomarlo en consideración.
2. GCC no fue lo suficientemente inteligente para detectar que sólo estábamos trabajando con constantes y haber reducido el programa a una asignación directa con complejidad O(1).
3. Es importante considerar que los dos programas probados no son equivalentes. X arroja 10, Y arroja 0. Para hacer una comparación justa entre dos programas es importante que el resultado sea el mismo. Aparentemente, el motivo del planteamiento era probar brutamente if contra bloques sin if. El motivo es que, en la vida real, las adecuaciones que se necesitarían para garantizar el resultado afectarían la complejidad del programa; se supone que uno es una refactorización del otro. En este caso sí importa cuidar los nanosegundos puesto que se trata de una medición.
4. El propósito de esta publicación es dejar en claro que la velocidad de un programa es muy variable y que depende de muchos factores, como del lenguaje, del compilador, de la arquitectura en la que corre el programa, del modelo exacto de microprocesador, incluso de la manera en como hacemos nuestra prueba, pero sobre todo, del algoritmo. La microoptimización sólo tiene sentido en casos muy particulares.