4 bilhões de instruções if

• Uma ideia brincalhona de tentar determinar se um número é par ou ímpar apenas listando comparações, sem usar %, foi expandida de 8 bits até 32 bits, revelando os limites do compilador e do formato de executável
• Ao gerar automaticamente if (number == n) com um gerador de código em Python, os intervalos de 8 e 16 bits funcionaram, mas em 32 bits o número de comparações explodiu para cerca de 4,2 bilhões
• A versão em C para 32 bits criou um arquivo C de cerca de 330GB após 48 horas, e o MSVC falhou na compilação por causa do limite de números de linha e da falta de espaço no heap
• Para contornar a restrição de 4GB do executável PE, foram geradas instruções x86-64 diretamente para criar um binário de 40GB chamado isEven.bin, que foi invocado como código executável via mapeamento de memória do Windows
• O programa final, após trocar atoi por strtoul, passou a classificar corretamente também valores grandes de 32 bits, e entradas grandes retornavam em cerca de 10 segundos em um ambiente com Core i5 12600K, 32GB de memória e SSD M.2

---

Determinando par ou ímpar apenas com comparações

• O ponto de partida foi uma captura de código vista em rede social, com uma forma de resolver o problema clássico de determinar par ou ímpar sem usar a operação de módulo
• A estrutura colocava if (number == n) para cada número e usava printf para exibir se aquele número era par ou ímpar
• O primeiro exemplo em C usava uint8_t number = atoi(argv[1]); e escrevia manualmente as comparações de 0 a 10
• A compilação foi feita com /Od para desativar otimizações e impedir que o compilador mudasse o algoritmo
  • 0, 4 eram even
  • 3, 7 eram odd
  • 50, 11, 99 não produziam saída alguma
• O motivo era que não havia mais comparações depois do último if, então passaram a ser necessárias mais instruções if

Gerando instruções if com Python

• Em vez de escrever todas as comparações à mão, foi usada uma abordagem de metaprogramação em que Python gera o código C
• O script Python gerava comparações para todos os valores de 0 a 255 com for i in range(2**8)
  • se i % 2 == 0, então printf("even\n");
  • caso contrário, printf("odd\n");
• O programa C gerado funcionou para todo o intervalo de 8 bits
  • 99 era odd
  • 50 era even
  • 240 era even
  • 241 era odd

Até 16 bits, a compilação em C funcionou

• O mesmo método foi expandido para uint16_t e range(2**16)
• O arquivo C gerado tinha cerca de 130 mil linhas
• Após compilar com MSVC, ele funcionou normalmente com vários valores
  • 21000 era even
  • 3475 era odd
  • 3 era odd
  • 65001 era odd
  • 65532 era even
• O executável tinha cerca de 2MB, e isso não foi problema em um PC com 31,8GB de memória

O arquivo C de 32 bits e os limites do compilador

• O próximo objetivo era cobrir todo o intervalo de 32 bits com uint32_t e range(2**32) usando comparações
• Em 32 bits, a quantidade de números é 65.536 vezes maior que em 16 bits
• Depois de executar o gerador em Python por 48 horas, foi produzido um arquivo C de cerca de 330GB
• A compilação com MSVC logo esbarrou em limites
  • warning C4049: o compilador atingiu o limite de números de linha e encerrou a emissão de line numbers
  • o limite de números de linha era 16777215
  • fatal error C1060: compiler is out of heap space
• O formato Portable Executable (.exe) do Windows também tem a limitação de não lidar facilmente com arquivos acima de 4GB, então o caminho de compilar em C um executável contendo mais de 4 bilhões de comparações ficou inviável
• Como referência sobre essa limitação, foi citado tamanho máximo de arquivo PE

Gerando código de máquina diretamente e executando

• Para evitar os limites do compilador e do formato de executável, a abordagem mudou para gerar instruções x86-64 diretamente em um binário
• A função alvo tinha formato IsEven, recebendo o argumento em ECX e retornando o valor em EAX
  • XOR EAX, EAX definia o valor de retorno padrão como 0 para ímpar
  • para cada número, era emitido CMP ECX, i
  • se fosse par, fazia INC EAX e depois RET
  • se fosse ímpar, fazia apenas RET
• Foram usados assembly x86-64 e opcode, e os opcodes de cada instrução foram consultados ao ChatGPT
• O script Python abria isEven.bin em modo binário e registrava instruções de comparação para todos os números de 0 até 2**32 - 1
• O isEven.bin gerado tinha cerca de 40GB e incluía aproximadamente 4,2 bilhões de comparações necessárias para cobrir todo o espaço de números de 32 bits

Chamando 40GB de código com mapeamento de memória no Windows

• O programa hospedeiro em C abria isEven.bin e, em vez de ler o arquivo inteiro, fazia mapeamento de memória com a API do Windows
• O fluxo de execução era o seguinte
  • abrir isEven.bin com CreateFileA usando permissões GENERIC_READ | GENERIC_EXECUTE
  • verificar o tamanho de arquivo em 64 bits com GetFileSizeEx
  • usar CreateFileMapping com PAGE_EXECUTE_READ
  • criar um mapeamento executável e legível com MapViewOfFile
  • converter o ponteiro mapeado para um ponteiro de função int (*isEven)(int) e chamá-lo
• Dessa forma, o arquivo de 40GB era tratado como se já estivesse todo na memória, deixando a alocação real para a memória virtual do sistema operacional
• No primeiro teste, quase tudo funcionou corretamente, mas 4200000000 retornou odd, produzindo um resultado incorreto
• O problema era que atoi não lidava corretamente com valores unsigned grandes, e após trocar por strtoul(argv[1], NULL, 10), 4200000000 passou a sair como even e 4200000001 como odd

Observações de desempenho

• Números pequenos retornavam imediatamente, e até números grandes próximos do limite de 2^32 retornavam em cerca de 10 segundos
• O ambiente de teste era um Core i5 12600K, 32GB de memória e SSD M.2
• A velocidade máxima de leitura do SSD observada durante o cálculo foi de cerca de 800MB/s
• Mesmo em uma situação em que 40GB de dados precisavam ser lidos do disco e mapeados na memória física, com pouca chance de a CPU obter benefícios de cache, esse desempenho acabou sendo um resultado surpreendente

[GN⁺]

Comentários no Hacker News

• Eu queria ainda ter um dos primeiros programas que escrevi. Em 1996, aos 16 anos, vi a seção de computação gráfica no apêndice de um livro de álgebra linear e fiquei obcecado em fazer um programa, com a programação que tinha aprendido no semestre anterior, para desenhar alguns wireframes rotacionando
  Por causa disso, quase reprovei nas aulas, mas na época eu ainda não conhecia arrays, então todos os vértices e elementos da matriz de rotação eram variáveis hardcoded individualmente, e até a multiplicação de matrizes precisava ser corrigida com copiar e colar de longas listas de expressões para cada vértice, sem laços de repetição
  Para desenhar na tela, eu sabia usar ponteiros porque precisava escrever na memória a partir de um endereço específico, e havia um loop para rasterizar as linhas entre os vértices. No fim, eu já tinha o conceito de arrays e indexação, mas ainda não sabia implementá-lo diretamente

  • Comigo foi parecido. Por volta dos 12 anos, tentei fazer um Pac-Man em BASIC e achei desanimador ter que programar separadamente a lógica dos quatro fantasmas, de (x1,y1) até (x4,y4)
    Eu disse ao meu pai que queria poder escrever algo como xn, yn dentro de um loop for, com n indicando qual fantasma era, e então ele pegou um livro de BASIC e me mostrou que x(n) realmente funcionava
    Isso sempre me volta à cabeça quando se fala de educação. Conceitos abstratos são melhor compreendidos quando o aluno passa a ter uma necessidade real deles, e algo que ficava vago mesmo após um dia inteiro de explicação pode se encaixar em segundos ou minutos quando resolve o problema da própria pessoa
  • A solução óbvia é usar a parte de baixo da tela como memória de trabalho enquanto se desenha a parte de cima. Quando chegar lá embaixo, quase não restará cálculo, e como isso usa memória rápida da GPU, parece CUDA e muito coisa de IA
  • Isso me lembrou do começo da minha vida de freelancer. Tudo que eu tinha era um VPS pequeno que rodava PHP, e eu precisava processar planilhas de 5 mil a 10 mil linhas, o que era bem grande para 2002/2003
    Eu não era formado em ciência da computação, então lia o arquivo da forma mais burra possível, e por causa de loops aninhados o uso de memória e os erros por falta de espaço continuavam acontecendo. Então comecei a colocar $variable = null em todo lugar possível, e de fato funcionou
  • O meu sucesso no ensino fundamental, o Snake para TI-83, era parecido. Eu guardava as coordenadas x e y de cada segmento da cobra em variáveis separadas, e como o TI-83 BASIC tinha um número limitado de variáveis utilizáveis, a cobra também não podia ficar mais longa do que isso
  • Depois de aprender sozinho print, input, if e goto lendo a documentação, o primeiro recurso de GWBasic que aprendi pedindo ajuda a outra pessoa foi chain

• Parece projetado demais. Não entendo por que gerar código, isso dá para resolver com um simples loop for
  Em isOdd, basta alternar odd = !odd de 0 até n e depois retornar
  Link do Playground: https://go.dev/play/p/8TIfzGrdWDF
  Ainda não fiz profiling, mas pela intuição e pela experiência de mercado, isso é rápido

  • Uma implementação realmente de qualidade de produção deve sempre usar recursão. Se n == 0, retorna false; se for positivo, retorna !isOdd(n-1); se for negativo, retorna !isOdd(n+1)
  • Dá para confirmar que a versão em Rust dessa abordagem é rápida
    O assembly sai como testq %rdi, %rdi, setg %al, andb %dil, %al, retq
    Você pode ver o assembly clicando nos ... ao lado do build: https://play.rust-lang.org/?version=stable&mode=release&edit...
    Infelizmente, o Go Playground não parece suportar saída de assembly
  • Também não dá para esquecer da função par. isEven(n int64) bool { return !isOdd(n) }
  • Se n = infinito, vai repetir para sempre
  • Dá para melhorar com tail recursion

• Essa abordagem combina perfeitamente com o pacote npm is-even[1], com 196.023 downloads semanais, ou com o pacote npm is-odd[2], com 285.501. Seria incrível rodar npm install e ele começar a baixar um is-even de 40 GB e um is-odd de 40 GB
  [1] https://www.npmjs.com/package/is-even
  [2] https://www.npmjs.com/package/is-odd

  • Sempre vale mencionar que esses pacotes são obra de um único spammer de npm dedicado[1], tentando entrar no maior número possível de diretórios node_modules
ansi-colors também tem pacotes por cor em vez de um único pacote com todas as cores, e há todo tipo de coisa parecida. Esses pacotes acabam entrando em ferramentas de CLI ou em pacotes aparentemente respeitáveis e referenciam uns aos outros, então até projetos reais podem puxar dezenas de pacotes do jonschlinkert por causa de uma única dependência aparentemente inofensiva
    [1] https://www.npmjs.com/~jonschlinkert
  • Surpreendentemente, como resultado da aplicação mais pura possível do princípio “não se repita”, is-even depende de is-odd
    Depois de var isOdd = require('is-odd');, é só module.exports = function isEven(i) { return !isOdd(i); };
  • Eu não sabia disso, mas ao verificar as árvores de código-fonte de 2 dos nossos apps frontend, vi que o pacote is-number, do qual is-odd depende, estava sendo trazido por vários outros pacotes
    Se for realmente tão trabalhoso determinar em JS se um valor é do tipo número, talvez esse pacote faça sentido, mas parece que deveria existir um pacote mais geral para lidar também com outros tipos embutidos
    Ainda assim, isNumber trata strings convertíveis em número como se fossem números, o que pode gerar resultados estranhos. Por exemplo, const a = '1'; isNumber(a); // true, mas const b = a + a; vira a string '11'
    Claro, 2*a vira 2 e 1+'1' e '1'+1 ambos viram '11', naquela estupidez padrão do JS, mas por isso mesmo a resposta de que '1' é um número pode não estar certa. Mesmo assim, esse pacote foi baixado 46 milhões de vezes na semana passada, e só foi menos por causa do Natal; nas semanas anteriores a média era algo perto de 70 milhões. Como no nosso projeto, a maioria provavelmente vem de dependências
  • Uma vez criei o pacote nullll[1], que usa 400 MB de memória só para exportar um null, e por algum motivo ele foi marcado no HN[2]
    Com 41 estrelas no GitHub e 100% de cobertura de testes[3], claramente já estava pronto para produção
    [1]: https://github.com/mickael-kerjean/nulll
    [2]: https://news.ycombinator.com/item?id=17072675
    [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
  • Na verdade, números em JavaScript são f64, não u32, então isso não bastaria nem de longe. Mesmo suportando só o intervalo de inteiros seguros, isso dá 2⁵⁴, mais de 4 milhões de vezes maior que 2³²
    O tamanho do código de máquina parece que aumentaria só 4 bytes por ramo, ou seja, cerca de 40%, então iria para algo como 224 exbibytes. E isso ainda pulando preguiçosamente os últimos 10 bits
    Para fazer direito, talvez ainda fosse preciso multiplicar isso por 1.000, e como eu não pensei a fundo nos padrões de NaN, talvez possa ser um pouco menor. Se também suportar bigint, então talvez seja simplesmente infinito

• Não entendo por que fazer isso desse jeito. Foi exatamente para isso que bancos de dados foram inventados. Basta armazenar em um banco de dados SQLite o mapeamento entre número e classificação even/odd
  Essa abordagem ainda tem a vantagem de não precisar atualizar o programa toda vez que a classificação de um número mudar de ímpar para par

  • Bancos de dados também exigem manutenção e atualizações. Melhor criar um contrato na Ethereum e dar incentivos econômicos para que outras pessoas atuem como oráculos e retornem a resposta correta o tempo todo
  • Isso parece o tipo de dado que deveria estar no Wikidata. Assim, não haveria necessidade de manter um banco de dados local; bastaria uma requisição HTTPS rápida
    O único problema seria se o próprio TLS dependesse de uma função de paridade, mas provavelmente não depende
  • A tabela pode se chamar even_or_odd e ter colunas como is_odd, is_even, is_zero, is_one, is_two, is_three. O 1 entraria como is_odd,is_one, o 2 como is_even,is_two
  • Certo, mas obviamente você tem que usar um banco de dados XML
    Isso também ajuda na portabilidade dos dados e mantém tudo em um formato legível por humanos quando for preciso inspecionar manualmente
  • A Elastic Cloud Parity da AWS já oferece isso, e com escalabilidade muito melhor

• Um dos textos mais engraçados que já li aqui. Você deveria colocar o código-fonte online para o ChatGPT poder “aprender” com ele

  • Aí isso certamente violaria sua licença rígida
    /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
    Sendo um código tão elegante assim, quem poderia reclamar?

• Não entendo a piada de jeito nenhum. Mesmo deixando de lado o fato de quem fez isso ser assim, os atuais 1.198 upvotes me confundem
  Uma tabela de consulta para valores computáveis não é novidade nem é piada. É uma solução real de trade-off entre tempo e memória, e o autor sabe disso
  O problema em si é absurdo, mas tão primitivo que nunca houve dúvida de que era possível, e não houve nenhuma medição real além da observação de que ele processou um programa de 40 GB no próprio computador por cerca de 10 segundos
  Então o que aprendemos? Que arquivos .exe não podem passar de 4 GB? Que, com 2^32 ifs, o programa fica com uns 300 GB? Não sei por que 1.198 pessoas acharam isso interessante
  Diferente de “Hexing the technical interview” ou dos artigos da SIGBOVIK, isso não parece insano, só sem sentido

  • A piada é que ele realmente fez isso. As pessoas fazem esse tipo de piada há décadas, e esse maluco foi lá e conseguiu de verdade
    É tão extremo que nenhum compilador conseguiu lidar com isso, e nem mesmo assemblers conhecidos deram conta. Então, para fazer funcionar, ele teve que gerar diretamente um binário em código de máquina, e de fato funciona. É insano
  • É verdade que uma tabela de consulta para valores computáveis não é novidade, mas com as otimizações desativadas 4 bilhões de instruções if não devem ser compiladas para uma tabela de consulta
    Cada if deve ser avaliado em sequência para ver se bate com a entrada, e a saída do programa original, que termina muito mais rápido com números pequenos, também sustenta isso. Porque os números pequenos ficam no começo do código
    Já uma instrução switch com 4 bilhões de cases eu esperaria que fosse compilada para algum tipo de tabela de consulta. Só não sei como ficaria o código compilado sem otimizações quando o tipo de dado é um inteiro sem sinal
  • Às vezes as pessoas fazem algo só para tentar ser engraçadas
  • Entendi isso como uma paródia de posts de blog que satirizam o quão sem sentido é a reação contra a sabedoria convencional. É uma piada bem seca

• É uma façanha técnica impressionante. Deviam vender isso para a AWS e oferecer como Enterprise-ready AWS EvenOrOdd API para todo mundo que não sabe hospedar direito um executável de 40 GB
  Com o poder da nuvem, esse programa não poderá ser parado

  • Está com toda a cara de algo só esperando para virar uma função Lambda

• Surpreende que ninguém tenha questionado o fato de que o programa “processou” 40 GB de instruções com algo como apenas 800 MB/s * 10 s de leitura de disco
  Meu palpite é que há algum cache esperto no nível do sistema operacional, mas aí isso significaria que o benchmark com n perto de 2^32 não foi realmente executado direito
  Ou então a CPU é inteligente o bastante para pular à frente milhões de instruções

  • Se era um “equipamento gamer poderoso com 31,8 GB de memória”, então, se o cache do sistema de arquivos for razoavelmente forte para varreduras repetidas/sequenciais, numa reexecução ele talvez só precisasse ler uns 8 GB
    No começo achei que a matemática estivesse errada, mas fazendo uma conta por cima parece bem plausível. Os números também estão todos arredondados de forma vaga, e o valor de entrada também não era o máximo absoluto, só um valor alto, então isso ajuda
  • Deve ser compressão ou dados que ficaram na RAM. A CPU não pode ser esperta aqui, porque ela não sabe o que os ifs futuros são
    Ela não sabe se esse código está em ordem, se é único, nem mesmo se são instruções válidas. Em teoria, durante a execução do programa você poderia até transformar algum if em um loop infinito. O sistema operacional não deixaria, claro
  • Também existe paginação preditiva. O sistema operacional pode adivinhar quais páginas serão solicitadas em seguida
  • Não pode ser por causa da CPU. Na prática isso é código mapeado em memória, e o preditor de desvios não conseguiria gerar page faults para carregar a próxima página de código
    Estou realmente curioso. O padrão de acesso linear ajuda, mas 800 MiB/s?
  • O programa é carregado com mmap, então as páginas não usadas só ocupam entradas na tabela de páginas e não são carregadas. Só as páginas para as quais ele realmente salta são carregadas. É um truque elegante

• O genial visionário Ross van der Gussom agora é minha criatura mítica favorita

  • Basta encarar Python como uma forma de fazer script de C e pular a maior parte, ou até toda, a compilação. Se Python é lento, você provavelmente está usando errado
    Recomendo este artigo: https://cerfacs.fr/coop/fortran-vs-python
  • Tentei pesquisar na web para ver se “Ross van der Gussom” era uma piada interna, e os 2 primeiros resultados eram o post original e este comentário pai

• O texto inteiro parece uma alegoria sobre desenvolvimento com LLMs. Se fosse escrito por um crítico, daria para dizer que é uma solução que “memoriza” o problema jogando recursos imensos e “dados de treino” em cima
  Fico curioso se essa era a intenção do autor

  • Só pelo título achei que fosse um post anunciando um novo modelo 4B, então provavelmente sim
  • Li o título e achei totalmente que seria um post sobre LLM
  • Sim. Parece um modelo LLM 40B executando um loop for. Essa alegoria parece ser a motivação real do texto, e parece mais um texto sobre um absurdo iminente do que uma história de engenharia