¿Por qué es lenta una instrucción de bifurcación de CPU?

Question

Desde que comencé a programar, he leído en todo lugar para evitar a toda costa las ramas derrochadoras.

Eso está bien, aunque ninguno de los artículos explica por qué debería hacer esto. ¿Qué sucede exactamente cuando el CPU decodifica una instrucción de bifurcación y decide hacer un salto? ¿Y cuál es la "cosa" que lo hace más lento que otras instrucciones (como la suma)?

Answer 1

Una instrucción de bifurcación no es inherentemente más lenta que cualquier otra instrucción.

Sin embargo, la razón por la que escuchaste que las ramas deberían evitarse es porque las CPU modernas siguen un pipeline architecture. Esto significa que hay múltiples instrucciones secuenciales que se ejecutan simultáneamente. Pero la canalización solo se puede utilizar completamente si es capaz de leer la siguiente instrucción de la memoria en cada ciclo, lo que a su vez significa que necesita saber qué instrucción leer.

En una rama condicional, generalmente no se sabe con anticipación qué camino tomará. Entonces, cuando esto sucede, la CPU tiene que detenerse hasta que la decisión se haya resuelto y descarta todo lo que está detrás de la instrucción de bifurcación. Esto reduce la utilización y, por lo tanto, el rendimiento.

Esta es la razón por la que existen cosas como branch prediction y branch delay slots.

Answer 2

Dado que la CPU adopta la tubería para ejecutar instrucciones, lo que significa que cuando una instrucción previa se está ejecutando en algún momento (por ejemplo, leyendo valores de registros), la siguiente instrucción se ejecutará al mismo tiempo, pero en otra etapa (por ejemplo, etapa de decodificación). Está bien para las instrucciones que no son de control, pero hace que las cosas sean complejas cuando se ejecutan las instrucciones de control como jmp o call.

Desde la CPU no sabe cuál será la siguiente instrucción al ejecutar una instrucción jmp, utiliza branch prediction técnicas para predecir si se tomará o no la instrucción de salto (Por ejemplo, una instrucción de salto en un fragmento de bucle probable que tome la flujo de instrucción de vuelta a la cabeza del bucle).

Sin embargo, cuando dicha predicción falla, que se llama branch misprediction, tendrá un impacto en el rendimiento de la ejecución. Dado que la tubería después de la derivación debe descartarse, y volver a empezar desde la instrucción correcta.

Answer 3

Oli dio una muy buena explicación de por qué la ramificación es costosa: predicción de oleoductos y bifurcaciones. Sin embargo, quiero agregar que no debería preocuparse demasiado por el problema, ya que los compiladores modernos optimizarán el código y una optimización reduce las ramificaciones.

Puede obtener más información sobre las optimizaciones de C++ en el compilador de Microsoft here: el optimizador guiado de perfiles utiliza la información de tiempo de ejecución (es decir, qué partes del código son las más utilizadas) para optimizar su código. La aceleración está en el rango del 20%.

Una de las operaciones es "condicional optimización del Poder", por ejemplo - si se asume la mayor parte del tiempo i es 6 - esto es más rápido:

if (i==6) 
{ 
    //... 
} 

else 
{ 
    switch (i) 
    { 
     case 1: // 
     case 2: // 
     //... 
    } 
} 

que:

switch (i) 
{ 
    case 1: // 
    //... 
    case 6: // 
    case 7: // 
} 

Aquí es una Publicación de blog sobre otras optimizaciones: http://bogdangavril.wordpress.com/2011/11/02/optimizating-your-native-program/