optimization - tag - ¿Por qué es lenta la instrucción de una rama de CPU?

seo image alt tag example

Question

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

Está bien, aunque ninguno de los artículos explica por qué debería hacer esto. ¿Qué ocurre exactamente cuando la 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

Oli dio una muy buena explicación de por qué la ramificación es cara: predicción de oleoductos y ramas. 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 leer más acerca de las optimizaciones de C ++ en el compilador de Microsoft here : el optimizador guiado de perfiles usa 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 "Optimización de la sucursal condicional", por ejemplo, suponiendo que la mayoría de las veces sea 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í hay una publicación de blog sobre otras optimizaciones: http://bogdangavril.wordpress.com/2011/11/02/optimizating-your-native-program/

Answer 2

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 deberían evitarse las derivaciones es porque las CPU modernas siguen una arquitectura de canalización . Esto significa que hay múltiples instrucciones secuenciales que se ejecutan simultáneamente. Pero la canalización solo se puede utilizar por completo 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 de antemano 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 cual existen ranuras de predicción de bifurcación y retardo de ramificación .

Answer 3

Debido a que la CPU adopta una 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, decodificación escenario). Está bien para las instrucciones sin control, pero hace que las cosas sean complejas cuando se ejecutan instrucciones de control como jmp o call .

Dado que la CPU no sabe cuál será la siguiente instrucción al ejecutar una instrucción jmp , utiliza técnicas de predicción de bifurcación para predecir si se tomará o no la instrucción de bifurcación (por ejemplo, una instrucción de bifurcación en un fragmento de bucle probablemente recuperará el flujo de instrucciones) a la cabeza del bucle).

Sin embargo, cuando dicha predicción falla, lo que se denomina propagación errónea de ramas , 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.