FizzBuzz a 55 GiB/s (2021)

 (codegolf.stackexchange.com)
5 pontos por GN⁺ 2023-07-04 | 1 comentários | Compartilhar no WhatsApp
  • High throughput Fizz Buzz, do Code Golf Stack Exchange, é um experimento de desempenho que compete para ver quão rápido é possível gerar a saída do FizzBuzz e enviá-la por um pipe, pontuando pela taxa de transferência de <program> | pv > /dev/null
  • A saída válida deve ser ASCII simples, usar quebras de linha \n, ter Fizz/Buzz/FizzBuzz corretos, continuar até pelo menos 2^58 ou ser praticamente infinita, e o truque de bytes nulos detectado apenas pelo pv é proibido
  • As principais implementações abandonam loops com % 3, % 5 e printf, reduzindo gargalos com desenrolamento do padrão de 15 linhas, processamento de números de largura fixa, buffers grandes, paralelização e saída zero-copy
  • A resposta em assembly x86-64+AVX2 destacada pressupõe Linux e AVX2 e combina vmsplice, cache L2, huge pages e um interpretador de bytecode de FizzBuzz para registrar cerca de 61 GiB/s
  • Os resultados variam muito conforme CPU, pipe buffer, versão do pv, CPU affinity e configurações de mitigation; na máquina do autor da pergunta, a maior pontuação ficou com a implementação em C++ de David Frank, cerca de 1,7 Tb/s

Limites de throughput levados ao extremo com FizzBuzz

  • O ponto principal não é o problema FizzBuzz, mas descobrir o que vira gargalo primeiro em uma geração de texto muito simples: cálculo de CPU, cópia de memória, I/O por pipe ou fronteira com o kernel
  • A implementação ingênua em C usada como referência utiliza % 3, % 5 e printf, e entrega cerca de 170 MiB/s em uma máquina comum
  • O autor da pergunta já tinha visto implementações acima de 3 GiB/s na mesma máquina e queria que a comunidade explorasse limites de throughput ainda maiores
  • A pontuação foi medida no desktop do autor da pergunta
    • AMD 5950x, 16C/32T
    • 64 GB de RAM a 3200 MHz
    • CPU mitigations desativadas
  • A tabela por linguagem inclui asm 60,8 GiB/s, C 20,9 GiB/s, Julia 15,5 GiB/s, Go 6,8 GiB/s, Java 5,8 GiB/s, Rust 3,4 GiB/s, Ruby 1,7 GiB/s, Python 0,5 GiB/s, entre outras
  • A resposta em assembly x86-64+AVX2 de ais523 mira desempenho máximo em thread única e registrou cerca de 31 GiB/s na máquina do autor, e cerca de 61 GiB/s no agregado do autor da pergunta
  • A implementação em C++ de David Frank registrou, segundo o corpo da pergunta, a maior pontuação atual, cerca de 1,7 Terabit/s; outra implementação separada em C++20 afirma ter alcançado 283 GB/s em um AMD Ryzen 9 7700X

Regras de saída e condições do benchmark

  • As condições para uma saída válida são exigentes
    • A saída deve ser exatamente FizzBuzz
    • Deve ter 1 byte por caractere ASCII
    • Apenas \n é permitido como quebra de linha
    • \r\n não é permitido
    • A saída deve continuar até um número muito grande, pelo menos 2^58
  • O próprio método de benchmark também afeta o throughput
    • Discute-se que pv e o Linux pipe buffer usam, por padrão, buffers de 64 K
    • Dependendo da alocação em CPU sibling cores, o caminho pelo cache L2 entre o programa gerador e o programa consumidor pode mudar
    • É possível forçar a alocação de CPU com taskset para fazer comparações

Como a implementação em assembly otimiza

  • O ponto central da implementação em assembly é reduzir o custo de copiar a saída, mais do que o custo de cálculo
    • Usar write aumenta o custo de copiar do espaço de usuário para o espaço do kernel
    • O autor escreve que trocar para uma versão baseada em write reduz o desempenho para um quinto
    • Com vmsplice, o pipe passa a referenciar o buffer do programa, reduzindo cópias
  • O cálculo do FizzBuzz é dividido em 3 etapas
    • A primeira etapa codifica a string inicial diretamente
    • A segunda etapa processa números de 2 a 5 dígitos com rotinas AVX2 relativamente diretas
    • A terceira etapa processa a faixa de 6 a 18 dígitos com um interpretador de bytecode de FizzBuzz
  • O loop principal da terceira etapa mira 64 bytes de saída a cada 4 ciclos de clock
    • 1 byte de bytecode gera 1 byte de saída
    • Ele carrega 32 bytes de bytecode e produz 32 bytes de saída com vpshufb, vpsubb e outras instruções
    • Os números das linhas são tratados com aproximações e correções no bytecode, evitando fazer a conversão numérica comum a cada linha
  • Essa implementação é altamente dependente da plataforma
    • Requer uma versão não muito antiga do Linux
    • Requer um processador x86-64 com suporte a AVX2
    • Emite erro na inicialização se a saída padrão não for um pipe
    • O autor afirma que ela pode produzir saída incorreta em algumas configurações de pipe que envolvem splice

Estratégias comuns adotadas por implementações em outras linguagens

  • Implementações em C, Go, Java, Rust, Python, Julia, Ruby e C# repetem direções de otimização parecidas
    • Desenrolam o padrão de 15 linhas do FizzBuzz
    • Reduzem a quantidade de conversões para strings numéricas
    • Acumulam a saída em buffers grandes
    • Paralelizam o trabalho de geração com threads ou goroutines
    • Usam barrier, channel, queue ou mutex para preservar a ordem da saída
  • É difícil tratar esse resultado como uma simples comparação de “desempenho de linguagem”
    • Versão do pv, tamanho do pipe, disponibilidade de vmsplice, CPU affinity, huge pages, otimizações do compilador e inlining de memcpy alteram muito o throughput
    • Algumas respostas têm comentários dizendo que são rápidas em determinadas máquinas, mas que os mesmos números não foram reproduzidos em outros ambientes

Escopo não coberto

  • As notas de entrada indicam que alguns source chunks foram omitidos por limites de tamanho e custo, portanto o texto não cobre integralmente todas as 46 respostas nem todo o código e comentários
  • O escopo omitido pode incluir algumas submissões por linguagem, corpos longos de código, logs detalhados de tuning e discussões nos comentários

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-04
Comentários do Hacker News

  • O mais impressionante é que o Linux consegue manter os dados enviados por pipe de um programa para outro apenas no cache L2, sem tocar a memória principal
    É uma arquitetura de sistemas impressionante ver várias partes comuns do kernel Linux se encaixando para tornar esse caminho rápido possível
    Fico curioso se algo assim também seria possível com as portas Mach do Mac OSX ou com os Named Pipes do Windows

    • Se o cache da CPU usa tags de endereço físico e as tabelas de páginas dos dois processos compartilham a mesma página física, então, a menos que o sistema operacional limpe ou invalide explicitamente o cache durante a troca de contexto, a CPU permite que qualquer um dos processos use o conteúdo em cache
    • Esse é um dos muitos motivos pelos quais toda a indústria de high-frequency trading roda em Linux

  • Fazendo jus ao nome de usuário “ais523 - high effort answers”, ele deixou um comentário extremamente caprichado mesmo para quem não conseguiu executar o programa, e a conclusão foi esta
    “Provavelmente o programa acabou sendo compilado com ASLR ativado. Nesse caso, o linker dinâmico não respeita o alinhamento de 4MiB do segmento BSS, o que na prática ignora meu .align, e isso parece ser a causa do bug”

    • Só sei que, se essa pessoa se candidatar à mesma vaga que eu, eu não teria a menor chance. É o leet coder definitivo

  • Sempre rio ao ver este comentário cada vez que esse post reaparece
    “@chx: Eu já tenho uma dissertação de mestrado. Isso foi mais difícil. – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Fiz implementações simples sem otimização em Rust, Python3 e C. Usei apenas if/else/while simples e saída padrão
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Queria saber se alguém entende por que o desempenho do Rust fica numa faixa parecida com a do Python3. Eu esperava algo mais próximo de C

    • A função print do Rust pega um lock por padrão. Isso é por segurança; C não faz isso. Mais detalhes na documentação do Rust: https://doc.rust-lang.org/std/macro.print.html
      Para obter desempenho parecido com C, provavelmente será preciso lidar com esse lock manualmente
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      E também ajustar o tamanho do buffer da saída padrão para combinar com o de C
    • É um post antigo, mas pode ajudar
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C e Python usam bufferização adaptativa na saída padrão. Se o destino da saída for um terminal, eles fazem flush a cada quebra de linha; caso contrário, só fazem flush quando o buffer interno enche
      Em um programa em C que conta números com 1ms de latência, a segunda coluna é o tempo decorrido desde o read() anterior
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      Dá para ver que tudo foi gravado de uma vez. Se você alocar um terminal, sai linha por linha
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      O Rust não tem esse comportamento adaptativo na saída, então sempre se comporta como no segundo resultado, independentemente de ser terminal ou não
      Tecnicamente, ele sempre envolve a saída padrão em um LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html) e faz flush sempre que encontra uma escrita com quebra de linha. Para maximizar a taxa de transferência, é preciso agrupar várias linhas escrevendo algo como um BufWriter
    • Rust precisa ser compilado com --release, e C com -O3
    • Quase certamente está limitado pela saída. Muito provavelmente é um problema de bufferização ou de lock

  • Fico curioso sobre o quão rápido seria se tudo tivesse sido escrito em assembly
    No desenvolvimento de áudio, é muito comum escrever código DSP em assembly

    • O motivo de isso ser rápido não é simplesmente por ser assembly. Isso é necessário para essa solução, mas de forma alguma é condição suficiente
      É preciso combinar pesquisa extrema de algoritmos, conhecimento profundo de chamadas de sistema do Linux e otimizações específicas de cada plataforma para que isso seja possível. Nas palavras do próprio autor, Alex Smith:
      “@chx: eu já tenho uma dissertação de mestrado. Isso foi mais difícil.”
      Está em um nível completamente diferente de algo que se resolve só com “é só fazer em assembly”
    • Mesmo que tudo tivesse sido escrito apenas em Java, ainda teria sido melhor do que o jeito atual de enfiar o Chrome dentro de uma instância de Python e rodar um servidor web em JavaScript para renderizar documentos
    • No fim, acabaria como a história de Geoworks do Steve Yegge
      “Certo. Eu estudava na University of Washington e fui trabalhar numa empresa chamada Geoworks, onde passei 5 anos programando em assembly. Nós, da Geoworks, escrevemos o sistema operacional inteiro, bibliotecas, drivers, apps, enfim, o desktop OS inteiro em assembly. Era assembly de 8086! E nem era um assembly bom! Só tinha quatro registradores! Se contar o 386, tinha também o registrador si. Era horrível.
      Na verdade, nós gostávamos bastante. Era assembly orientado a objetos. É impressionante como a pessoa consegue se convencer a gostar de alguma coisa, e essa é a verdadeira ironia de tudo isso. Para nós, C++ era o ápice da decadência romana. Era como vomitar para conseguir comer mais. Eles tinham IF! Nós tínhamos jump CX zero! Eles tinham ‘objetos’. Nós também tínhamos, mas eles tinham sintaxe para isso. Parecia uma fraqueza inacreditável. E, naquela época, sabíamos que conseguíamos produzir código mais rápido do que qualquer compilador, e de fato conseguíamos!
      Então o que aconteceu? A empresa faliu. Por quê? Provavelmente vou discordar de todo mundo da Geoworks nisso. Na verdade, sei que talvez eu seja o único que acredita nisso. Mas foi porque escrevemos 15 milhões de linhas de assembly 8086. Tínhamos ferramentas realmente boas, de classe mundial, pode acreditar. É absolutamente necessário ter isso. Mas chega um momento em que…
      O problema é o seguinte: imagine uma formiga tentando atravessar o chão do porta-malas em linha reta. Ela não consegue ir em linha reta. Nós sabemos disso porque temos uma visão mais ampla. Dá para ver a formiga andando por aí, fazendo otimizações locais em torno daquela pedrinha, e agora indo para o outro lado.
      Era exatamente assim quando escrevíamos um sistema enorme em assembly. No fim, a Microsoft lançou uma plataforma para dispositivos móveis muito mais rápida que a nossa. Entrei com o depurador e pensei: ‘O que é isso? Por que está acontecendo? A renderização está muito lenta, está engasgando’. Fui ver e, toda vez que a tela era atualizada, alguma barra de título era renderizada 140 vezes. E não era só a barra de título. Tudo estava sendo chamado várias vezes.
      Porque já não conseguíamos mais enxergar como o sistema funcionava!
      Sistemas pequenos não são apenas mais fáceis de otimizar; eles podem ser otimizados. Quero dizer que a otimização global é possível.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • Assembly está distante demais do código-fonte escrito hoje para sequer ser algo realista de se considerar. Ainda assim, dá para imaginar o quanto tudo poderia ser mais rápido se as empresas de software realmente se importassem com desempenho
      Algo como 99% dos sites e softwares de hoje provavelmente conseguiria pelo menos 50% de ganho de velocidade com mudanças básicas, só prestando um pouco de atenção ao desempenho da aplicação. Coisas como cache correto, otimização de assets, substituir bibliotecas terceiras inchadas por chamadas nativas básicas que façam a mesma coisa, e configuração adequada de servidor e banco de dados
      Também parece possível que, em alguns anos, a IA ofereça otimização com um clique no repositório, aplicando boas práticas ou reescrevendo o código original em assembly rápido
    • Um detalhe que muita gente deixa passar quando fala que linguagens mais primitivas produzem programas mais rápidos é que, se avançar um pouquinho na codificação já for doloroso, você se esforça muito para implementar o mínimo possível
      Restrições de recursos podem trazer clareza de foco

  • Embora este experimento seja divertido e instrutivo, ele parece ter uma pequena falha. Em vez de avaliar quão rápido um problema complexo é resolvido, ele testa principalmente uma questão periférica: a eficiência de tirar memória de um processo e passá-la para outro
    Então parece que o segundo processo continua escrevendo no console ou em um arquivo, mas tecnicamente não é isso que acontece. Executar pv >/dev/null é, em essência, quase o mesmo que não fazer nada, e a chamada de sistema write retorna quase imediatamente
    vmsplice é algo equivalente a memória compartilhada, no sentido de permitir que outro processo acesse o buffer/memória de um processo. Como os requisitos iniciais da competição provavelmente eram ambíguos, não parece claro se isso seria aceitável pelas regras

    • Dá para rolar para cima até a pergunta original e verificar se os requisitos iniciais eram ambíguos, e também confirmar pelo histórico de edições que eles não mudaram depois que o desafio começou
      “Escreva um programa FizzBuzz. Execute-o. Direcione a saída com | pv > /dev/null. Quanto maior o throughput, melhor.”
      “A saída do programa deve ser um fizzbuzz válido e correto. Não vale trapacear inserindo bytes nulos entre saídas válidas. Tipo bytes nulos que não aparecem no console, mas entram na medição de throughput do pv.”
      E vmsplice(2) de fato produz um fluxo de bytes no pipe da saída padrão, que o pv(1) pode fazer splice para /dev/null ou o cat(1) pode copiar para o terminal
      Esta não foi a única submissão a usar vmsplice(2). Outros participantes também descobriram que isso está longe de ser uma solução mágica. Mesmo depois de atravessar a barreira de E/S, ainda sobra muito trabalho para gerar as páginas de saída o mais rápido possível
    • Acho que “a eficiência de tirar memória de um processo e passá-la para outro” quase sempre é o problema inteiro
      A maior parte do código fica limitada por memória e E/S. Mesmo problemas complexos normalmente emperram na velocidade de mover dados de um lugar para outro; raramente emperram no cálculo em si. Mesmo passando o dia otimizando assembly de GPU, nos raros casos em que o gargalo é computação, depois de otimizar isso o gargalo vira memória
    • Não concordo. Sem antes fazer uma boa quantidade de otimizações específicas de FizzBuzz, você nem chega ao ponto em que o gargalo é “a eficiência de tirar memória de um processo e passá-la para outro”
      Por exemplo, existe uma representação de bits inteligente que faz com que o carry decimal aconteça naturalmente
      Os requisitos iniciais da competição também não eram particularmente ambíguos nesse ponto. Eles dizem explicitamente para medir o throughput com | pv > /dev/null, e também dizem isto:
      “Também são permitidas otimizações / assembly específicas de arquitetura. Isto não é uma competição de verdade. Eu só quero ver as pessoas levando o fizz buzz ao limite, mesmo que funcione apenas em um ambiente/plataforma especializado.”
    • E/S é literalmente algo que todo programa precisa fazer. Em hardware moderno, 99% do código acaba tendo gargalo aí. Mover bytes de um lugar para outro é indispensável e relativamente lento
      Entender como lidar bem com E/S de memória e E/S de arquivo em termos de desempenho é uma habilidade relevante para todo programa e todo programador

  • Dizem para salvar como fizzbuzz.S, mas fiquei curioso sobre a diferença entre as extensões .S e .s

    • O S maiúsculo executa primeiro o pré-processador
      Segundo a página de manual:
      file.s
      código assembler
      file.S
      file.sx
      código assembler que precisa de pré-processamento
    • Se bem me lembro, tradicionalmente a diferença era se a entrada passava pelo pré-processador (.S) ou não (.s)
      Não sei se ainda há alguma diferença nas toolchains modernas
    • Na convenção com a qual estou acostumado, .S é usado para arquivos de assembly escritos por humanos, normalmente rastreados no git, e .s para assembly gerado por máquina que pode ser sobrescrito se necessário
    • GCC e afins não sobrescrevem .S, mas se você pedir para gerar assembly (por exemplo, gcc -S xyz.c), ele sobrescreve .s

  • Post anterior:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • No começo eu li 55 GiB/s FritzBox. FritzBox é um roteador popular na Europa germanófona
    Meu ISP também tuitou na semana passada sobre uma caixa OPNSense[1] com suporte a 60 GiB/s que estará disponível em breve
    [1] https://twitter.com/init7/status/1674920410889043973

    • Estou usando um DEC750 com a memória expandida para 16GB. Foi um ótimo equipamento: roteador silencioso, com suporte a 10GbE, WireGuard a 2.3GbE e consumo em idle de só 8W, parecido com o de um cable modem, então não pretendo trocá-lo antes de 2030~2035
      Também deixo um adaptador USB WiFi conectado, para que certas VLANs entrem em failover se o cabo cair, usando o celular para manter a conectividade crítica do trabalho
      Não é barato, mas se você quer hardware de verdade enquanto apoia financeiramente o projeto OPNSense, é difícil contestar os equipamentos da Deciso. Eles são eficientes em consumo, usam componentes focados em durabilidade e simplesmente funcionam bem
      É bom ver a linha comercial ficando mais poderosa