Código sin bifurcaciones en

Acerca de Código sin bifurcaciones

El concepto de condicionales presenta jcc, la familia de instrucciones para ramificar según una condición. Un jcc transfiere la ejecución a otro punto del programa solo si se cumple su condición.

Sin embargo, las CPU modernas son rápidas y capaces de ejecutar muchas instrucciones en paralelo. Sería demasiado costoso detener todo el trabajo mientras la CPU espera una verificación de condición en tiempo de ejecución.

Por eso, internamente, la CPU no espera. Usa un predictor de ramas para adivinar el resultado de una condición y comienza a ejecutar especulativamente la ruta predicha.

Si la predicción es correcta, la ejecución continúa como si no hubiera una rama. Sin embargo, si la predicción es incorrecta, la CPU debe descartar el trabajo realizado en la ruta predicha y reiniciar en la correcta.

Esto se conoce como predicción incorrecta de rama y es costoso, ya que conlleva un retraso.

Cuando una rama es difícil de predecir, esas predicciones incorrectas se acumulan. En esos casos, a veces es preferible evitar la rama por completo, de modo que las mismas instrucciones se ejecuten sin importar la condición. El código que selecciona entre valores sin un jcc se llama sin ramas.

Hay varias formas de estructurar el código para que se ramifique menos, o para que las ramas que sí tenga sean más predecibles. En particular, x86-64 proporciona dos familias de instrucciones que se usan comúnmente para escribir código sin ramas.

Movimientos condicionales

La familia de instrucciones cmovcc copia el operando de origen en el destino solo si se cumple una condición específica. De lo contrario, el destino queda sin cambios.

El sufijo cc sigue la misma nomenclatura que en jcc, con el mismo significado:

Las reglas son similares a las de jcc:

1. l y g se usan para comparaciones con signo; b y a se usan para comparaciones sin signo.
2. Agregar e a un sufijo incluye la igualdad.
3. Agregar n niega la condición.
4. También hay variantes que hacen referencia a que la bandera esté establecida. Por ejemplo, cmovz y cmovc.

Considera el valor absoluto de un entero con signo en rdi, devuelto en rax. Escrita con jcc, la función selecciona uno de dos caminos:

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

Escrita con cmovcc, ambos valores candidatos se calculan incondicionalmente y el movimiento condicional elige uno:

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

La versión sin ramas siempre ejecuta las mismas instrucciones. No hay ningún jcc que el predictor tenga que adivinar.

El destino de un cmovcc debe ser un registro. La fuente puede ser un registro o una ubicación de memoria, pero no un inmediato.

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

Establecimiento condicional

La familia de instrucciones setcc establece el operando de destino en 1 si se cumple una condición específica, y en 0 de lo contrario. El destino siempre es un operando de 8 bits.

El sufijo cc sigue la misma nomenclatura que en jcc y cmovcc. Por ejemplo, setz establece el destino en 1 si ZF == 1 y en 0 de lo contrario.

Como el destino es de 8 bits, es común seguir setcc con un movzx cuando se necesita un valor más ancho:

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

Este es un patrón habitual para convertir el resultado de una comparación en un entero 0 o 1.

Cuándo usar código sin ramas

El código sin ramas no siempre es más rápido que el código con ramas. Cuando una rama es muy predecible, el predictor acierta casi siempre y jcc prácticamente no cuesta nada. El código sin ramas que reemplaza una rama así es más lento, porque siempre ejecuta ambos cálculos candidatos.

Un contador de bucle es el ejemplo canónico. Considera una función que suma rsi enteros de 64 bits a partir de rdi:

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

Este es exactamente el tipo de patrón que los predictores de ramas manejan bien, así que la rama es prácticamente gratis sin importar cuántos elementos procese sum_array.

El código sin ramas vale la pena cuando la rama es difícil de predecir, o cuando se requiere un tiempo consistente sin importar las entradas.