Não passe structs maiores que 16 bytes no AMD64

• A subida de posição do benchmark related_post_gen do Neat não veio de uma otimização de alto nível, mas de uma pequena mudança de ABI: passar arrays como 3 argumentos ponteiro em vez de uma struct de 24 bytes
• Por causa da contagem de referências, o array do Neat precisa, além dos ponteiros de início e fim, de um ponteiro baseado no objeto do array; por isso, ao contrário dos 16 bytes do array de D, ele entra no caminho de passagem por memória do SystemV AMD64 ABI
• Certos aggregates com mais de 16 bytes são copiados para a pilha na chamada e depois passados por ponteiro, perdendo a vantagem da passagem por registradores e aumentando o custo de embaralhamento da pilha
• No benchmark de exemplo, passar struct Vector { double x, y, z; } como struct faz 1 bilhão de execuções levarem 12,3 segundos; passando os campos como argumentos individuais, cai para 5,3 segundos
• APIs em C precisam seguir o C ABI, mas para tipos internos do runtime da linguagem, como arrays, tuplas e sumtypes, vale a pena testar a passagem separada por campos quando passam de 16 bytes

---

Gargalo revelado no Neat

• Neat subiu algumas posições no benchmark related_post_gen
• O ganho de desempenho não veio de um novo passe de otimização de alto nível, mas de uma mudança na forma de passar arrays
  • Antes: argumento struct contendo 3 ponteiros
  • Depois: 3 ponteiros passados separadamente como argumentos
• Comparado com D, o Neat estava mais lento do que o esperado, e o profiler mostrava movimentação de grandes áreas da pilha para realizar chamadas de função
• O gargalo estava mais próximo do custo de reorganização da pilha no momento da chamada do que do cálculo em si

Por que o array do Neat tem 24 bytes

• Diferente do array de D, o Neat usa contagem de referências
• O array do Neat inclui estes 3 ponteiros
  • ponteiro de início
  • ponteiro de fim
  • ponteiro baseado no objeto do array onde a contagem de referências é armazenada
• Como 3 ponteiros somam 24 bytes, ele segue um caminho diferente nas regras de passagem de argumentos do AMD64 em relação a um array de 16 bytes com 2 ponteiros
• O motivo de o array de D ser rápido e o do Neat ser lento foi justamente ultrapassar a fronteira de 16 bytes ao chegar a 24 bytes

A fronteira de 16 bytes no SystemV AMD64 ABI

• A especificação do SystemV AMD64 ABI define que, se o tamanho de um certo aggregate ultrapassa dois eightbytes, o argumento inteiro é passado pela memória
• Para passar uma struct pela memória, o lado que faz a chamada precisa executar o seguinte
  • alocar na pilha um espaço do tamanho da struct
  • preencher esse espaço com os valores a serem passados
  • passar para a função um ponteiro para a posição dessa struct
• Nesse caso, o valor obrigatoriamente precisa estar na pilha, o que reduz a margem de otimização do LLVM
• Os valores precisam ser copiados dos registradores para a pilha, e também é preciso rastrear quais partes da pilha estão em uso e quais podem ser reutilizadas
• Foi nesse rastreamento de reutilização da pilha que o LLVM mostrou um comportamento ruim

Benchmark com vetor de 3 double

• O benchmark usa vetores com 3 campos no formato struct Vector { TYPE x, y, z; };
• TYPE é definido como double
• As duas funções fazem a mesma soma, mas diferem na forma de passagem dos argumentos
  • vector_add_struct(struct Vector left, struct Vector right) recebe structs grandes como argumentos
  • vector_add_fields(...) recebe left_x, left_y, left_z, right_x, right_y, right_z como argumentos individuais
• mode e a duração da execução são recebidos por argumentos de linha de comando para impedir que o otimizador faça constant folding do cálculo inteiro
• impl.c é compilado separadamente para evitar inlining

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• O resultado foi de 12,3 segundos na passagem por struct e 5,3 segundos na passagem separada dos campos

A diferença visível no assembly

• A versão com passagem por struct usa muitas instruções em embaralhamento da pilha
• A versão por campos leva vantagem porque os parâmetros já chegam à função em registradores SSE
• Na versão com struct, é preciso carregar os valores da pilha a cada vez
• O SystemV ABI foi pensado para passar valores por registradores sempre que possível, mas neste caso essa vantagem desaparece por causa de structs maiores que 16 bytes
• Considerando a quantidade de registradores disponíveis no AMD64, o autor avalia que ainda teria sido útil permitir passagem por valor mesmo para tipos acima de 16 bytes

Quando a situação fica parecida com cdecl

• Escrever os campos na pilha e passar um ponteiro acaba ficando parecido com o antigo ABI cdecl do x86, em que tudo era passado pela pilha
• O cdecl era conhecido por ser lento, e várias convenções de chamada surgiram para torná-lo mais rápido
• O problema aqui é que o AMD64 System V ABI, por causa do tamanho da struct, acaba se comportando como aquele antigo modelo de passagem pela pilha nesse caso

Exceções com inlining e LTO

• Em código real, funções assim podem acabar todas sendo inline
• No gcc, ao ativar LTO, a diferença de desempenho entre as duas versões desaparece
• No clang, o mesmo resultado não aparece
• Nem toda função pode ou deve ser inline

Conselho para implementadores de linguagem e otimização de API

• Ao chamar uma API em C, é preciso seguir o C ABI
• Mas, para tipos de alto nível internos de uma linguagem não-C, mesmo que pareçam structs para o backend, não é obrigatório representá-los como uma única struct
• O implementador da linguagem pode decidir diretamente como passar arrays, tuplas, sumtypes e outros tipos
• No Neat, escolheu-se passar separadamente os campos desses tipos quando excedem 16 bytes, e isso trouxe vantagem no benchmark
• Se você estiver implementando uma linguagem no AMD64 ou fazendo micro-otimização de API, vale a pena medir se dividir manualmente structs maiores que 16 bytes ajuda
• Especialmente em loops internos, a diferença de desempenho pode ser maior do que o esperado

Observação adicional: struct de double e SSE

• A pergunta é por que double, sendo da classe SSE segundo a especificação, não faz a struct ser passada por registradores SSE
• A resposta é que o motivo não é conhecido, mas na prática não é assim que ela é passada

[GN⁺]

Opiniões do Hacker News

• O problema aqui é a ABI SysV amd64. Você não precisa usar a SysV como ABI interna da linguagem. Se não estiver exposto a chamadores C SysV, dá para usar a convenção de chamada que quiser
  https://llvm.org/docs/LangRef.html#calling-conventions
  Para quem tiver curiosidade, a mudança relacionada no neatlang está aqui: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  Parece muito mais complicado do que simplesmente alterar a saída da convenção de chamada do LLVM. Talvez o autor quisesse expor esses tipos a programas em C com uma convenção de chamada determinística

  • Na verdade, dá para dizer isso da ABI como um todo. Quem programa em assembly sabe: esse é um daqueles frutos baixos em que é fácil superar o compilador
    Não siga convenções cegamente; escolha o que fizer mais sentido para a situação específica
  • A primeira pergunta que me veio à cabeça já tinha resposta. É interessante ver como tanta coisa segue ABIs e afins criadas há muito tempo
    Em especial, ABIs muitas vezes tendem para compatibilidade com CPUs mais antigas, enquanto CPUs mais novas podem ter margem para melhorar usando recursos como registradores estendidos, sem reduzir o tamanho das structs. Software ajustado para um hardware ou geração específica ficaria inutilizável em algumas máquinas, então não é tão atraente; ainda assim, seria legal ter um compilador capaz de gerar esse tipo de saída quando você quisesse otimizar o código ao extremo para os recursos de hardware do seu próprio sistema

• O custo de passagem de argumentos muitas vezes é mal compreendido, então é bom ver um texto assim. Mesmo em lugares como o Google, é comum passar objetos de 24 bytes por valor, e esse custo fica tão espalhado por todas as funções que não aparece bem em profilers

  • Passagem por valor e por referência afeta, na prática, a ABI/API, então impõe uma carga cognitiva considerável. Zig tenta não impor isso: mesmo que você “passe por valor”, o compilador pode decidir passar por referência de fato
    Mas esse tipo de pegadinha também aparece: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • “Lugares como o Google”: isso vem de experiência direta? Como ex-Googler, posso dizer com segurança que há uma diretriz para passar tudo que não seja tipo primitivo por ponteiro ou referência
    A única exceção que me vem à mente é string_view
  • É bom destacar que overheads amplamente distribuídos, como os embutidos na convenção de chamada, quase não são encontrados por profiling
  • Se você passa um objeto de 24 bytes por ponteiro em vez disso, há o trade-off de precisar desreferenciar o ponteiro quando realmente for usar o objeto. E não há garantia de que esse objeto esteja por perto
    Com azar, pode ocorrer um cache miss e você ficar esperando algo como 100 nanossegundos para trazer o objeto de 24 bytes da memória principal. Se passar o mesmo objeto diretamente, ele estará na stack, então é mais provável que esteja no cache
  • Fico curioso se a ABI de C++ também derrama objetos de 24 bytes para a stack a cada chamada. Não espero que parâmetros std::string ou std::function sejam rápidos, mas ainda assim é surpreendente

• Quando fiz a primeira transição para x64, fiquei preocupado que os objetos vec3 de graphics (3 floats) crescessem para 16 bytes em vez de sizeof()=12, então fiz muitos benchmarks no motor gráfico
  Sem surpresa, graças ao alinhamento de leituras de 8 bytes, 16 bytes era mais rápido que 12 bytes. Tanto internamente quanto na GPU. Então vec3 virou silenciosamente vec4, e vec4 continuou existindo separadamente. Como sempre, é preciso fazer benchmarks com visão do todo, não benchmarks locais

  • Há um efeito colateral muito bom: encaixa bem no tamanho do SSE. Assim dá para usar _mm_load_ps diretamente, o código fica mais limpo e a vetorização também fica muito fácil
  • Provavelmente não é muito mais rápido. E, independentemente do que você faz com esses dados, imagino que também dependa bastante da CPU
    Entendo que, com 16 bytes, muitos acessos podem virar 2x8 bytes alinhados ou 1x16 bytes, em vez de 3x4 bytes. Mas em outros acessos talvez isso aconteça menos, e também há o problema de maior pressão no cache
  • A ABI x64 também é consideravelmente melhor que a ABI x86

• Pelo senso comum, valores passados em registradores podem ser pré-carregados graças à execução especulativa, sendo mais rápidos do que escritas na stack, e manipular a stack é mais rápido do que alocar no heap
  Por isso, código spaghetti bagunçado com um monte de variáveis globais é extremamente rápido, enquanto funções recursivas elegantes ou argumentos em tuplas/structs/listas são inacreditavelmente lentos. O primeiro é muito mais fácil de otimizar para loops de assembly compactos

  • Claro, isso pressupõe que o código spaghetti implemente o mesmo algoritmo que o código elegante
    Se o código elegante for O(n) e o spaghetti for O(n^2), você pode acabar sentindo a diferença. Também é preciso considerar manutenção. Em certo sentido, compiladores existem para transformar nossas soluções elegantes em código spaghetti
  • “Passe parâmetros em registradores, não na stack” é quase senso comum, mas “parâmetros maiores que 16 bytes são sempre passados pela stack” não é tão óbvio assim
  • Algumas CPUs modernas conseguem fazer renomeação de memória, então o custo de derramar para a stack pode ficar mais barato
    Objetos globais também atrapalham otimizações do compilador

• Como referência, no MSVC o tamanho de corte é 8 bytes antes de uma struct ser passada pela stack. Isso é um detalhe de ABI, então código portável não deve depender disso
  Mas, se a função não for chamada com frequência, também não precisa se estressar tanto. Se for uma função pequena chamada com frequência, como no exemplo, deixe o compilador fazer inline do código com algo como LTO. Isso abre otimizações muito mais úteis do que passar argumentos em registradores

• Classifico textos como este como “conhecimento na medida certa para virar dor de cabeça”. Mesmo que você siga as instruções e compile separadamente para forçar o compilador a criar uma função chamável via ABI, o LTO pode desfazer esse erro
  Se você compilar este programa com LTO, ele fica dramaticamente mais rápido nos dois modos do que qualquer modo do programa sem LTO. Se o programa for sensível a desempenho, faça profiling e só depois de otimizar os gargalos até o limite é que se deve commitar algo como decompor a struct em argumentos

  • É um bom conselho, mas ainda não vi um compilador que torne visível esse tipo de coisa. Primeiro, isso fica espalhado pela base de código inteira e, a menos que por sorte vire um hotspot, também não vi um profiler que mostre o impacto
    Isso se aplica a quase todo código gerado por compilador. O Valgrind talvez consiga medir, mas um profiler por amostragem provavelmente não, e não há ferramentas que destaquem problemas de geração de código dispersos
  • Além disso, fala da importância absoluta do desempenho enquanto usa contagem de referências

• Na convenção de chamada cdecl padrão do Windows, structs maiores que 8 bytes não são passadas por registradores [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• Mesmo usando a ABI SysV amd64 no amd64, é totalmente possível passar e retornar por valor structs maiores que 16 bytes. Só é lento
  Ainda assim, muitas vezes a passagem por valor vale a pena para deixar o código mais claro. Claro que não é este caso, mas, como loeg apontou, dentro da própria linguagem dá para usar uma ABI personalizada, como fazem compiladores C++, Go, OCaml e SBCL

• No exemplo fornecido, seria possível corrigir mudando o tipo do parâmetro de “struct Vector” para “const struct Vector &” e fazendo passagem por referência, sem afetar o chamador
  Já vi muito código C++ com bugs de ponteiro que usava ponteiros sem necessidade, quando passagem por referência bastava e teria sido mais fácil e segura de usar

  • Não. Na verdade, esse é justamente o problema central aqui. Por causa da ABI, o compilador basicamente faz exatamente isso
    Como a ABI manda passar o valor por ponteiro, ele precisa ser armazenado em algum lugar para obter um ponteiro, e acontece a mesma coisa que quando você explicita const-ref. Se você transformar o valor da struct em argumentos separados, os argumentos podem ser passados em registradores
  • Quando encontrei esse problema, era código com vinte ou trinta allocas tentando passar ponteiros para byval. Toda função começava com um alloca separado para cada parâmetro passado à chamada
    Eu sempre tinha assumido, em certa medida, que o LLVM limparia bem esse tipo de coisa, mas descobri que não
  • Ainda assim, para passar um ponteiro de struct ao chamado, o compilador precisa serializar três registradores na pilha
    O benefício descrito é evitar por completo a serialização de registradores para a pilha, e isso não parece ser evitável com passagem por referência
  • Este não era um exemplo em C++, mas um exemplo em C99. Em muitos ambientes, por pura inércia, não dá para trocar livremente as ferramentas
    Se C++ for permitido, surgem muito mais opções, como argumentos por movimento para reduzir cópias

• A regra prática que sempre ouvi em C++ é: se não for um tipo primitivo, passe por referência, a menos que haja uma boa razão para passar por valor; e, se for realmente necessário, passe por ponteiro
  Isso é por causa da ABI e também para evitar construtores de cópia ou de movimento. São detalhes tediosos de baixo nível, mas, se você quer desempenho máximo em C++, precisa prestar atenção neles. Para deixar claro: isto é apenas uma otimização de desempenho; o código que passa structs funciona corretamente, só é menos rápido