Por que evitar a “otimização” de movimento condicional com `mix()` + `step()` em shaders

• Em shaders de GPU, código que escolhe valores com operador ternário ou um if simples normalmente não é tratado como desvio condicional, mas como movimento condicional (select)
• Mesmo trocando por step() e mascaramento aritmético, não existe um desvio para eliminar, então a própria premissa da chamada otimização de remoção de branch está errada
• Na saída dos compiladores da AMD e da Microsoft aparecem instruções de comparação e máscara/movimento condicional, sem sinais de instruções de salto ou branch
• A versão com step() cria máscaras 0.0/1.0 e depois compõe o resultado com multiplicações e somas, aumentando operações desnecessárias em relação ao código que faz movimento condicional direto
• Branches de GPU que pulam grandes blocos de cálculo de acordo com a condição continuam sendo úteis, mas para seleção simples de valores é mais seguro verificar o código de máquina gerado

---

Seleção simples de valores não é branch de GPU

• A função de exemplo snap45() calcula x = abs(v.x) a partir do vetor de entrada e depois usa dois operadores ternários para retornar um entre três resultados vec2
• A mesma lógica continua válida se for escrita com um if comum
• A “otimização” problemática é trocar o operador ternário por step() e composição por pesos
  • w0, w1, w2 são criados com step()
  • res0, res1, res2 são calculados individualmente
  • O resultado final é composto com w0*res0 + w1*res1 + w2*res2
• Essa transformação parte do equívoco de que o código original gera um branch condicional
• A simples seleção de valores em registradores não altera o ponteiro de instrução, nem causa falha de predição, flush de pipeline ou invalidação do cache de instruções
• Branches reais na GPU ainda podem ser rápidos e úteis quando servem para pular grandes blocos de cálculo conforme a condição
• Porém, em casos como o do exemplo, em que só se escolhe um valor simples ou resultado de cálculo, dá para considerar que o código de máquina gerado não cria branch

A diferença mostrada pela saída do compilador

• O código GLSL original com operador ternário é transformado pelo compilador da AMD em comparações e instruções de máscara condicional
  • Comparação: v_cmp_gt_f32, v_cmp_ngt_f32
  • Máscara condicional: v_cndmask_b32
• A saída do compilador da Microsoft mostra a mesma estrutura
  • Comparação: lt
  • Movimento condicional: movc
• Em ambas as saídas dos compiladores não há instruções de jump/branch

Por que a abordagem com step() fica mais cara

• A abordagem baseada em step() primeiro cria máscaras 0.0 ou 1.0 por meio de movimento condicional e depois mascara vários resultados candidatos com multiplicações e somas
• O código original faz diretamente o movimento condicional do valor necessário, então desperdiça menos do que a abordagem com step(), que adiciona geração de máscara e composição aritmética
• Em diferentes hardwares, a versão baseada em step() pode ser medida como muito mais lenta que a versão original
• Algumas chamadas abs() em GLSL no código de exemplo entram como modificador de instrução, e não como instrução separada da GPU; nesses casos, a chamada abs() pode ser considerada praticamente gratuita
• Recomendar float a = mix(b, c, step(y, x)); como otimização de float a = x < y ? b : c; é uma abordagem equivocada

[GN⁺]

Opiniões no Hacker News

• A conclusão do TFA parece correta, mas o argumento teria ficado mais forte se tivesse mostrado o código gerado nas duas versões, em vez de mostrar só o resultado da geração de código da versão melhor
  No trecho citado, o texto diz que “a versão que afirma estar otimizada é muito mais lenta que a versão original… desperdiça duas multiplicações e uma ou duas adições… vamos ver o código de máquina gerado”, mas na prática mostra apenas a versão boa, sem multiplicações nem adições
  Isso só prova que a versão boa é aceitável; ainda não prova que a versão ruim é pior

  • O ponto central é que a condicional não gerou um desvio real
    Mesmo que mostrassem o código gerado da outra versão, provavelmente só daria para ver que ele é mais longo; como também não seria esperado que ela gerasse um desvio, talvez não tivesse grande valor
  • O código gerado para RDNA 1 está aqui: https://shader-playground.timjones.io/5d3ece620f45091678dcee...

• Seria bom haver uma forma clara de saber quando um if força um desvio real e quando não força
  O motivo de as pessoas usarem mix/lerp, que podem até ser mais caros, é o medo de acabar gerando um desvio, mesmo aceitando um pouco de overhead
  É ótimo que o código mais claro, como v = x > y ? a : b;, funcione bem na prática, mas dá insegurança o fato de a mesma sintaxe de if às vezes ser um desvio e às vezes não
  Em contextos em que realmente não pode haver desvio, eu gostaria que branch-if e um if sem desvio fossem palavras-chave diferentes; a palavra-chave sem desvio deveria fazer a compilação falhar se o compilador não conseguisse gerá-la sem desvio, enquanto a palavra-chave com desvio deveria emitir um aviso se fosse possível gerá-la sem desvio

  • Por trás disso está a documentação confusa da NVIDIA e dos compiladores cg/CUDA
    No começo, para não assustar programadores, eles esconderam o modelo de execução e o explicaram por meio da abstração de “threads”; depois, na divulgação de GPUs, continuaram usando ideias como “há uma quantidade enorme de threads CUDA”
    Como resultado, surgiu uma mitologia estranha em torno da programação para GPU
    Na prática, muitas vezes é bom que o código tenha desvios, e o desvio em si é rápido
    O problema é que lanes SIMD não podem se separar, cada uma indo para um desvio diferente; por isso, em vez de gerar desvios, o compilador emite o código dos dois lados e mascara o resultado conforme a condição
    Assim, cálculos baseados em entradas do shader, vértices, índices de compute shader etc. não fazem desvios reais; eles são executados sequencialmente com mascaramento
    No exemplo do TFA também, os dois valores do operador ? são calculados, e condicionais sobre valores SIMD geralmente funcionam da mesma forma
    Pode surgir um desvio de atalho para pular rapidamente o cálculo quando todas as lanes têm o mesmo valor, mas em geral tanto o lado verdadeiro quanto o falso são calculados
    Apenas condicionais baseadas em registradores escalares, isto é, constantes de shader ou valores uniform, geram desvios reais, e esses desvios são muito rápidos
  • Em CPUs escalares acontece a mesma coisa
    Por exemplo, a instrução CMOV foi introduzida no core P6 em 1995
    Desvios também são caros em arquiteturas escalares, e o compilador tenta ao máximo decidir quando usar uma estratégia alternativa
    Às vezes ele erra, mas não erra com tanta frequência
  • Em GPUs, é melhor pensar quase ao contrário
    Movimento condicional é o padrão, e um desvio real só é uma otimização de desempenho possível quando é um desvio uniform, em que o workgroup inteiro segue a mesma direção
  • Dá para imaginar este exemplo: a = f(z); b = g(z); v = x > y ? a : b;
    Se as chamadas a f() e g() forem relativamente caras, decidir entre emitir código condicional ou calcular ambos e depois selecionar vira uma questão de trade-off
    Não é uma escolha simples; quem decide é o compilador
  • Seria interessante se linguagens de shader tivessem um recurso assim
    Todas as funções no código poderiam ser distinguidas como com desvio/sem desvio, como se fossem “coloridas”; uma função marcada como sem desvio exigiria que if fosse compilado como movimento condicional e só poderia chamar outras funções sem desvio

• Uma boa parte do mito de que “desvios em GPU são lentos” vem do fato de que, na época antiga do PlayStation 3, eles realmente eram bem lentos
  O PS3 tinha uma GPU NVIDIA RSX e, pela documentação, lembro que um desvio levava 6 ciclos, mas medições reais sempre davam mais lento que isso
  Isso acontecia até em desvios totalmente coerentes, em que todas as threads do warp seguiam o mesmo caminho; desvios incoerentes eram ainda mais lentos, porque a instrução IFEH levava 6 ciclos e a GPU tinha de executar os dois lados do desvio
  Acho que o mito, que persiste até hoje, de que “desvios em GPU são lentos” começou aí
  Em GPUs atuais, desvios — especialmente os coerentes — são bem baratos

  • Quando alguém fala apenas “desvio”, deve-se entender que está falando de desvio incoerente
    O overhead do mecanismo de desvio pode ter diminuído hoje, mas a limitação física de que a vazão dos dois lados do desvio cai na proporção de threads ativas continua a mesma
    Se os dois lados do desvio forem executados e tiverem o mesmo comprimento de instruções, o desempenho médio dos dois lados cai pelo menos pela metade
    Por isso a crença de que desvios em GPU são lentos persiste, e na prática está correta
    Se possível, vale a pena se esforçar mais para reformular o problema sem desvios
  • Desvios coerentes são quase “de graça”, mas as instruções extras aumentam a pressão sobre registradores
    O principal motivo para evitar desvios dinâmicos não é o desvio em si ser inerentemente lento, e sim algo mais próximo disso

• Essa otimização para evitar ramificações já foi eficaz em algum momento
  Já fiz profiling no Xbox 360 e em GPUs integradas Intel antigas, mas hoje o correto é não fazer mais isso
  Extração de bits e outras operações com inteiros são parecidas
  Antes era mais rápido emular com matemática de ponto flutuante, mas agora todas as GPUs têm operações inteiras rápidas

  • Fico curioso até que ponto é verdade que “agora todas as GPUs têm operações inteiras rápidas”
    Por exemplo, olhando para a ISA RDNA2, a arquitetura do PS5 e do Xbox Series S|X, parece que para inteiros só aparecem instruções escalares de 32 bits
    [0] https://www.amd.com/content/dam/amd/en/documents/radeon-tech...
  • Pelo menos em GPUs “grandes” isso não é um problema tão grande quanto antigamente, mas este texto, na verdade, não é sobre evitar ramificações em si
    O código apresentado já é código sem ramificações
    Parece que quem dá esse conselho julga se há código com branch apenas olhando se existe na fonte alguma construção que parece uma condicional, e acha que está evitando isso como uma otimização

• Este artigo também é relacionado: https://medium.com/@jasonbooth_86226/branching-on-a-gpu-18bf...
  “Se você perguntar na internet como escrever branches em uma GPU, podem falar como se você estivesse abrindo os portões do inferno para deixar demônios entrarem. Vão dizer que isso deve ser evitado a qualquer custo, e que dá para evitar com operadores ternários ou truques matemáticos estranhos como step(). A maior parte desse conselho é, na melhor das hipóteses, ultrapassada; em muitos casos, simplesmente errada. Vamos corrigir isso.”

• Processadores mudam, e compiladores também mudam
  Se esses detalhes importam, o melhor é distribuir várias variantes e escolher em tempo de execução a versão mais rápida
  Como já disse algumas vezes antes, já removi assembly escrito à mão e troquei por C comum, ou código parecido, tornando tudo muito mais rápido
  Talvez aquele assembly fosse mais rápido 10 ou 20 anos atrás, mas agora a situação mudou

  • Acho muito complicado descobrir em tempo de execução qual é a versão mais rápida de um shader
    Na prática, não conheço bem jogos ou engines que façam isso
    Em princípio, pode ser possível
    A maioria das APIs, como D3D, GL e Vulkan, expõe contadores de desempenho, e embora a confiabilidade varie conforme o fornecedor, dá para criar uma cena de teste representativa e reproduzi-la várias vezes para medir otimizações
    Mas muitos jogos usam cenas geradas dinamicamente e shaders gerados dinamicamente, então o número de combinações a testar pode virar um obstáculo
    Talvez seja preciso pedir ao usuário que espere até o benchmark terminar
    Se você tiver o hardware, pode medir antecipadamente em várias gerações de GPUs de cada fornecedor e hardcodar apenas as decisões importantes, mas não conheço bem uma infraestrutura existente desse tipo
  • Curiosamente, o driver da NVIDIA faz algo assim em certa medida
    Ele intercepta shaders de jogos e os substitui por shaders customizados otimizados pela NVIDIA
    Por isso aparecem frases como “otimização para o jogo X, roda 40% mais rápido” nos changelogs dos drivers da NVIDIA
  • Se for só adicionar mais um shader, tudo bem, mas em APIs gráficas “modernas” às vezes são necessárias milhares de permutações para o mesmo shader, e cada variante adicionada dobra esse número
    Também não dá para gastar tempo infinito em cada shader
    Faça profiling no hardware que interessa; se a abordagem escolhida for mais lenta em algum processador hipotético do futuro, paciência
    O melhor é torcer para que esse processador seja rápido o bastante para isso não virar um problema

• Parece que o erro e a confusão que este texto tenta corrigir também estão se repetindo aqui
  O texto não afirma que desvio condicional é grátis
  Na minha leitura, ele também não é um texto sobre o custo de desempenho de código com branch
  O ponto do texto é que a lógica condicional na forma apresentada não é compilada como código com desvio condicional
  E que não devemos continuar espalhando conselhos nocivos que tentam mascarar à força toda expressão condicional visível
  Quanto a código com branch de verdade, é evidente que executar código com branch é mais complexo
  Não existe branch grátis, e evitar branches dentro do razoável provavelmente torna qualquer código mais rápido
  Felizmente, o código original já era código sem ramificações
  Como sempre, não há uma métrica universal que diga se uma otimização vale a pena
  [0] Aqui, “visível” é importante. Refere-se a casos em que a pessoa não se importa com o código gerado, apenas com o fato de o código-fonte não parecer uma condicional
  [1] Claro que não foi sorte. Imagino que alguém tenha enviado ao IQ uma sugestão de melhoria para código de shader que parecia óbvia, mas estava errada

• Então por que o compilador não é inteligente o bastante para perceber que a versão “otimizada” é o mesmo código?
  Ele não deveria entender step() e otimizar separadamente os casos step() = 0.0 e step() == 1.0?
  Pelo menos uma multiplicação poderia ser eliminada, então normalmente isso pareceria sempre vantajoso, mesmo que acabasse virando um load/store condicional ou outra coisa

  • Na prática, talvez seja assim mesmo
    É bem possível que alguns compiladores façam essa otimização em alguns casos, mas também é perfeitamente possível escrever uma versão que o compilador não entenda
  • Outro problema da otimização é que tentar todas as possibilidades não pode levar tempo demais
    A maior parte da otimização acontece no driver, e trabalhos que demoram demais aparecem como engasgos na compilação de shaders
    Não posso dizer se esta otimização específica acontece ou não na prática, mas é um fator que sempre precisa ser considerado

• O motivo de a versão “otimizada” em questão ser mais lenta é que a função step() na prática é implementada mais ou menos assim:
  float step( float x, float y ) { return x < y ? 1.0 : 0.0; }
  Como saber se uma função do OpenGL chama uma primitiva da GPU ou se é emulada?

  • O único jeito é, como no texto original, compilar o shader, fazer a desmontagem e ler o assembly
    Já fiz isso muitas vezes com shaders HLSL e aprendi bastante sobre o conjunto de instruções virtual
    Por exemplo, é interessante que a GPU tem uma instrução sincos, mas funções trigonométricas inversas são emuladas durante a compilação
  • Por que você precisaria saber depende do objetivo
    Se desempenho for importante, talvez você precise saber
    Mas o simples fato de step ser implementada como uma função de biblioteca sobre uma condicional, e não como uma instrução dedicada, não diz por si só qual será o desempenho em comparação com uma instrução dedicada; então não há motivo para se prender demais à implementação em si
    Se a curiosidade for sobre a arquitetura da GPU, veja a desmontagem, código de drivers open source, LLVM e a documentação da ISA
  • Fora funções que você esperaria ver em assembly no estilo PC, nunca vi a GPU ter primitivas especiais
    Sempre que olho shaders decompilados, em geral eles se parecem com o que eu imaginaria em C
    Especificações como OpenGL definem o comportamento de muitas funções embutidas, e a implementação atende a essa especificação usando instruções de assembly padrão
    Dá para procurar sites online que decompilam para várias arquiteturas
  • É uma boa pergunta que aparece com frequência em programação em geral, e também é um dos principais motivos para medir primeiro ao otimizar
    Normalmente você não precisa saber nem se preocupar com como uma função embutida foi implementada
    Se você está se preocupando com isso, provavelmente está pensando em otimização; nesse caso, a resposta é “meça e veja o que é melhor”
  • Acho que o ponto que me confundiu é que “desvio” tem um significado mais bem definido e mais específico de hardware do que o sentido em que aprendi crescendo
    No sentido que aprendi, uma condicional é um desvio
    No nível de código de máquina, como o fluxo de controle é escolhido em tempo de execução, um salto condicional é, por definição, um desvio
    Usar step() não transforma lógica em aritmética; a meu ver, só esconde a lógica dentro de uma chamada de função de biblioteca
    O fato de step() ser uma função embutida ou uma função que aparece em artigos de matemática não muda isso
    Em matemática, a definição de step() também é literalmente uma condicional
    Para otimizar de verdade sem condicionais, você precisa escolher uma função contínua parecida com o resultado desejado e ajustar parâmetros para chegar o mais perto possível do objetivo
    Normalmente, você escolhe um polinômio, roda um método padrão de aproximação iterativa e acaba com uma f(x) sem desvios, contendo apenas somas, multiplicações e constantes “estranhamente específicas”
    Não entendo muito bem a parte em que o autor afirma com força que movimentação condicional não é um “desvio”
    O fato de abs() não virar uma instrução de GPU, mas descer como modificador de instrução e sair de graça, acontece porque a representação de complemento de dois dos inteiros e a representação de ponto flutuante IEEE-754 permitem tratar o bit de sinal como o bit mais significativo
    Por isso, abs() termina simplesmente zerando sempre o bit mais significativo, ou mascarando-o na instrução que faz a leitura
    Mas step(), uma operação ternária arbitrária e, até onde sei, instruções de movimentação condicional não são esses casos especiais
    Coisas básicas como abs(), sqrt() e funções trigonométricas estão mais perto de conhecimento padrão; quanto ao resto, fico em dúvida se isso realmente importa
    step() inevitavelmente precisa ter uma condição em algum lugar; seja você fazendo diretamente, entregando para uma biblioteca ou deixando para o hardware, a natureza fundamental disso não muda

• Já caí nessa armadilha
  Claude e ChatGPT também costumam sugerir isso como otimização
  Mas toda vez que medi, o desempenho piorou, às vezes bastante

  • Não é algo estranho
    LLMs apenas repetem o que existe no corpus de treinamento
    Se a maior parte da internet recomenda conteúdo errado, como essa “otimização” por movimentação condicional, a LLM também vai recomendar isso
  • LLMs repetem o que as pessoas na internet dizem, e as pessoas erram com frequência