Código sin bifurcaciones en

Acerca de Código sin bifurcaciones

El concepto condicionales presenta jcc, la familia de instrucciones para bifurcar según una condición. Una 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 comprobación de la condición en tiempo de ejecución.

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

Si la predicción es correcta, la ejecución continúa como si no hubiera bifurcación. Sin embargo, si la predicción es errónea, la CPU debe descartar el trabajo realizado en la ruta prevista y reiniciar la ejecución en la correcta.

Esto se denomina predicción incorrecta de bifurcación y resulta caro, ya que conlleva un retraso.

Cuando una bifurcación es difícil de predecir, esas predicciones incorrectas se acumulan. En esos casos, a veces es preferible evitar la bifurcación por completo, de modo que se ejecuten las mismas instrucciones independientemente de la condición. El código que elige entre valores sin una jcc se denomina código sin bifurcaciones.

Hay varias formas de estructurar el código para que se bifurque con menos frecuencia, o para que las bifurcaciones que tenga sean más predecibles. En particular, x86-64 ofrece dos familias de instrucciones que se suelen usar para escribir código sin bifurcaciones.

Movimientos condicionales

La familia de instrucciones cmovcc copia el operando de origen en el destino solo si se cumple una condición concreta. De lo contrario, el destino se deja 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. Añadir e a un sufijo incluye la igualdad.
3. Añadir n niega la condición.
4. También hay variantes que se refieren a si una bandera está activada. 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 elige una de dos rutas:

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

Escrita con cmovcc, se calculan incondicionalmente ambos valores candidatos 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 bifurcaciones ejecuta siempre las mismas instrucciones. No hay ninguna jcc que el predictor pueda adivinar.

El destino de una cmovcc debe ser un registro. El origen puede ser un registro o una posició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

Asignación condicional

La familia de instrucciones setcc asigna el valor 1 al operando de destino si se cumple una condición concreta, y el valor 0 en caso contrario. El destino es siempre un operando de 8 bits.

El sufijo cc sigue la misma nomenclatura que en jcc y cmovcc. Por ejemplo, setz asigna el valor 1 al destino si ZF == 1, y el valor 0 en caso contrario.

Como el destino es de 8 bits, es habitual que setcc vaya seguida de 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

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

Cuándo usar código sin bifurcaciones

El código sin bifurcaciones no siempre es más rápido que el código con bifurcaciones. Cuando una bifurcación es muy predecible, el predictor acierta casi siempre y una jcc no cuesta prácticamente nada. El código sin bifurcaciones que sustituye a esa bifurcación 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 bifurcaciones manejan bien, así que la bifurcación sale prácticamente gratis sin importar cuántos elementos procese sum_array.

El código sin bifurcaciones merece la pena cuando la bifurcación es difícil de predecir, o cuando se requiere un tiempo de ejecución constante independientemente de las entradas.