Este artículo técnico explica cómo un bucle aparentemente óptimo en C puede acelerarse hasta cuatro veces introduciendo una rama condicional que, sobre el papel, parece innecesaria. El autor trabajaba en un compresor específico de dominio cuyo algoritmo principal consiste en encontrar el camino más corto en una retícula: para cada símbolo se calcula la mejor codificación siguiente y, recorriendo esas referencias, se obtiene el orden óptimo de codificación.
El cuello de botella no estaba en el núcleo denso del algoritmo, cuidadosamente vectorizado con instrucciones SSE (__m128i), sino en un segundo bucle aparentemente trivial: j = next_j[i][j], que se compila en un único mov. Aunque en los años 80 esa sería la forma más rápida posible, en CPUs modernos el rendimiento depende del paralelismo a nivel de instrucción. El problema es que cada iteración necesita el valor de j calculado en la anterior, lo que convierte el bucle en latencia-bound en lugar de throughput-bound.
La solución propuesta es contraintuitiva: añadir un if (j != next_j[i][j]) para que la CPU prediga que la condición es falsa y especule que j no cambia. Cuando la predicción falla, el predictor de saltos deshace las escrituras especulativas erróneas. El reto es que el compilador, al ver que la variable j vive en un registro, considera el if redundante y lo elimina con una pasada de eliminación de subexpresiones comunes. Para engañarlo, el autor recurre a un cast a volatile que hace creer al optimizador que la lectura y la escritura son independientes.
El resultado, medido en un benchmark sintético, es una aceleración de aproximadamente cuatro veces. El artículo también menciona una alternativa estructural —sustituir el array de 8 elementos por un valor y una máscara de bits— que haría el if semánticamente necesario, aunque probablemente más lenta en x86.