Código sem ramificações em

Sobre Código sem ramificações

O conceito de condicionais apresenta o jcc, a família de instruções que permite ramificar com base numa condição. Um jcc transfere a execução para outro ponto do programa apenas se a sua condição se verificar.

No entanto, as CPUs modernas são rápidas e capazes de executar muitas instruções em paralelo. Seria demasiado dispendioso parar todo o trabalho enquanto a CPU espera por uma verificação da condição em tempo de execução.

É por isso que, internamente, a CPU não espera. Usa um previsor de ramos para adivinhar o resultado de uma condição e começa a executar especulativamente o caminho previsto.

Se a previsão estiver correta, a execução prossegue como se não houvesse ramo nenhum. No entanto, se a previsão estiver errada, a CPU tem de descartar o trabalho feito no caminho previsto e recomeçar no caminho correto.

A isto chama-se previsão de ramo incorreta e é dispendiosa, provocando um atraso.

Quando um ramo é difícil de prever, essas previsões incorretas acumulam-se. Nesses casos, por vezes é preferível evitar o ramo por completo, para que as mesmas instruções sejam executadas independentemente da condição. Ao código que escolhe entre valores sem um jcc chama-se sem ramos.

Há várias formas de estruturar o código para que ramifique menos vezes, ou para que os ramos que tem sejam mais previsíveis. Em particular, o x86-64 disponibiliza duas famílias de instruções frequentemente usadas para escrever código sem ramos.

Movimentos condicionais

A família de instruções cmovcc copia o operando de origem para o destino apenas se uma condição específica se verificar. Caso contrário, o destino fica inalterado.

O sufixo cc segue a mesma nomenclatura do jcc, com o mesmo significado:

As regras são semelhantes às do jcc:

1. l e g usam-se em comparações com sinal; b e a usam-se em comparações sem sinal.
2. Acrescentar e a um sufixo inclui a igualdade.
3. Acrescentar n nega a condição.
4. Existem também variantes que se referem ao flag estar definido. Por exemplo, cmovz e cmovc.

Considera o valor absoluto de um inteiro com sinal em rdi, devolvido em rax. Escrita com jcc, a função escolhe um de dois caminhos:

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

Escrita com cmovcc, os dois valores candidatos são calculados incondicionalmente e o movimento condicional escolhe um deles:

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

A versão sem ramos executa sempre as mesmas instruções. Não há nenhum jcc para o previsor adivinhar.

O destino de um cmovcc tem de ser um registo. A origem pode ser um registo ou uma posição de memória, mas não um valor imediato.

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

Definição condicional

A família de instruções setcc define o operando de destino como 1 se uma condição específica se verificar, e como 0 caso contrário. O destino é sempre um operando de 8 bits.

O sufixo cc segue a mesma nomenclatura do jcc e do cmovcc. Por exemplo, setz define o destino como 1 se ZF == 1 e como 0 caso contrário.

Como o destino tem 8 bits, é comum seguir setcc com um movzx quando é preciso um valor mais largo:

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

É uma construção comum para transformar o resultado de uma comparação num inteiro 0 ou 1.

Quando usar código sem ramos

O código sem ramos não é sempre mais rápido do que o código com ramos. Quando um ramo é altamente previsível, o previsor acerta quase sempre e um jcc não custa praticamente nada. O código sem ramos que substitui esse ramo é mais lento, porque executa sempre os dois cálculos candidatos.

Um contador de ciclo é o exemplo canónico. Considera uma função que soma rsi inteiros 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

É exatamente este tipo de padrão que os previsores de ramos tratam bem, pelo que o ramo não tem praticamente custo, independentemente do número de elementos que o sum_array processa.

O código sem ramos compensa quando o ramo é difícil de prever, ou quando é preciso um tempo de execução consistente independentemente dos valores de entrada.