Eres víctima de fallos en el predictor de saltos.
¿Qué es la predicción de saltos?
Considera una bifurcación de ferrocarril.:
Imágen de Mecanismo, cortesía de Wikimedia Commons. Usado con licencia CC-By-SA 3.0 .
Supongamos que estamos en el siglo 19 - mucho antes de las comunicaciones a distancia o por radio.
Eres el operario de una bifurcación y oyes un tren que se acerca. No tienes idea alguna del camino que se supone que ha de seguir. Con lo que paras el tren para preguntar al piloto por la dirección que lleva. Y colocas las agujas en la dirección apropiada.
Los trenes, son pesados y tienen mucha inercia, con lo que les lleva mucho tiempo detenerse.
¿Hay alguna forma mejor de hacerlo? ¡Podrías adivinar la dirección a la que se dirige el tren!
- Si aciertas, el tren continua.
- Si fallas, el piloto se detiene, retrocede, y te grita que cambies las agujas. Entonces puede continuar por la otra vía.
Si aciertas siempre, el tren no tendrá que parar nunca.
Si fallas a menudo, el tren gastará mucho tiempo parando, retrocediendo y rearrancando.
Considera una sentencia if A nivel de procesador es una instrucción de salto condicional.

Tú eres el procesador y ves el salto condicional. No tienes ni idea de si saltará o no. ¿Qué hacer? Detener la ejecución y esperar a que las instrucciones anteriores terminen. Entonces continuas por la ruta correcta.
Los procesadores modernos son complicados y están muy segmentados, con lo que les lleva mucho tiempo _iniciar la ejecución_ y _detener la ejecución_.
¿Hay alguna manera mejor? ¡Adivinar si el salto se hará o no!
- Si aciertas, continuas la ejecución.
- Si fallas, te toca vaciar la unidad de ejecución y deshacer lo ejecutado tras el salto/no-salto. Entonces has de reiniciar por la otra ruta.
Si aciertas siempre, la ejecución no se interrumpe nunca.
Si fallas a menudo, dedicas mucho tiempo parando, deshaciendo la ejecución y reiniciando.
Esto es la predicción de saltos. Admito que no es la mejor analogía posible puesto que el piloto del tren podría indicar la dirección con un banderín. Pero en los ordenadores, el procesador no sabe si se ejecutará o no el salto hasta el último momento.
¿Así que qué estrategia de predicción utilizar para minimizar el número de veces que el tren debe retroceder y seguir por el otro camino? ¡Mirando un histórico! Si el tren va por la izquierda el %99 de las veces, entonces predices izquierda. Si alterna, entonces alternas tus predicciones. Si va en una dirección una de cada 3 veces, haces las mismas predicciones...
En otras palabras, intentas identificar un patrón y lo sigues. Así es más o menos como los predictores de salto funcionan.
La mayoría de programas tienen saltos condicionales que se comportan bien. Con lo que los modernos predictores de saltos tienen aciertos >%90, pero cuando se enfrentan a saltos condicionales impredecibles sin patrones reconocibles, los predictores de salto son virtualmente inútiles.
Para profundizar en el tema: "Predictor de salto" Artículo de Wikipedia.
Lo anterior nos da una pista de dónde está el problema, en la sentencia if
:
if (data[c] >= 128)
sum += data[c];
Obsérvese que los datos están uniformemente distribuidos entre 0 y 255.
Cuando los datos están ordenados, aproximadamente la primera mitad de las iteraciones no entrarán en la sentencia if
. Tras esto, siempre entrarán en la sentencia if
.
Esto es muy bueno para el predictor de saltos dado que siempre se hace el mismo tipo de salto muchas veces consecutivas.
Incluso un simple contador de saturación predecirá correctamente los saltos excepto por unas pocas iteraciones tras el cambio.
Visualización rápida:
S = Sí se salta
N = No se salta
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N S S S ... S S S ...
= NNNNNNNNNNNN ... NNNNNNNSSSSSSSSS ... SSSSSSSSSS (fácil de predecir)
Sin embargo, cuando los datos son completamente aleatorios, el predictor de saltos resulta inútil pues no puede predecir datos aleatorios.
Habrá probablemente alrededor de un %50 de predicciones fallidas. (que no es mejor que predecir al azar)
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branch = S, S, N, S, S, S, S, N, S, N, N, S, S, S, N ...
= SSNSSSSNSNNSSSN ... (completamente aleatorio - imposible de predecir)
¿Qué se puede hacer?
Si el compilador no es capaz de optimizar el salto condicional en una asignación condicional, entonces hay algunos trucos si se está dispuesto a sacrificar claridad del código por rendimiento.
Substituye:
if (data[c] >= 128)
sum += data[c];
Por:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
Esto elimina el salto condicional y lo substituye por algunas operaciones bit a bit.
(Nótese que este truco no es estrictamente equivalente a la sentencia if
original, pero en este caso, es válido para todos los valores de data[]
.)
Pruebas de rendimiento: Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release
// Salto condicional - Aleatorio
segundos = 11.777
// Salto condicional - Ordenado
segundos = 2.352
// Sin salto condicional - Aleatorio
segundos = 2.564
// Sin salto condicional - Ordenado
segundos = 2.587
Java - Netbeans 7.1.1 JDK 7 - x64
// Salto condicional - Aleatorio
segundos = 10.93293813
// Salto condicional - Ordenado
segundos = 5.643797077
// Sin salto condicional - Aleatorio
segundos = 3.113581453
// Sin salto condicional - Ordenado
segundos = 3.186068823
Observaciones:
Como regla de oro general se debe evitar saltos condicionales dependientes de datos en bucles críticos (como el de este ejemplo).
Actualización :
GCC 4.6.1 con -O3
o -ftree-vectorize
en un x64 es capaz de generar una asignación condicional. Con lo que no hay diferencia entre los datos ordenados y sin ordenar - ambos son rápidos.
VC++ 2010 es incapaz de generar asignaciones condicionales para este salto condicional incluso con /Ox
.
Intel Compiler 11 hace algo milagroso. Intercambia los dos bucles (enlace en inglés), con lo que saca el salto condicional al bucle exterior. No solo es inmune a los fallos de predicción, es el doble de rápido que lo que VC++ y GCC pueden generar. In otras palabras, ICC se ha aprovechado del bucle de prueba para vencer a la prueba de rendimiento...
Si le das al Intel Compiler el código sin salto, diréctamente lo vectoriza... y es exáctamente tan rápido como con el salto condicional (con el intercambio de bucles)
Esto muestra que incluso en compiladores modernos y maduros puede haber diferencias salvajes en su capacidad para optimizar código...
Esta respuesta es una traducción del original en inglés de Mystical