4 bilhões de instruções if

4 bilhões de instruções if

• Ao pesquisar redes sociais recentemente, encontrei este screenshot dentro de um trem.
• Este código é um exemplo perfeito de trade-off entre tempo e memória.
• A ideia era implementar isso em C para aumentar o desempenho.

Estrutura do código

• Foi escrito um código em C para determinar se um número é par ou ímpar.
• Ele foi compilado com as otimizações desativadas.
• Funciona normalmente para números de 0 a 10, mas apresenta problemas para valores maiores.

Metaprogramação

• Usou-se Python para fazer metaprogramação das instruções if.
• Foi gerado um programa para determinar paridade em inteiros de 8 bits.

Expansão para 16 bits

• O programa foi expandido da mesma forma para inteiros de 16 bits.
• Foi gerado e compilado um arquivo C com cerca de 130 mil linhas.

Desafio dos 32 bits

• Houve uma tentativa de expandir o programa para inteiros de 32 bits.
• Foi gerado um arquivo C de 330 GB, mas o compilador falhou por falta de espaço no heap.
• Devido aos limites do formato Portable Executable, não foi possível lidar com arquivos maiores que 4 GB.

Escrevendo código de máquina diretamente

• A função IsEven foi escrita diretamente em assembly x86-64.
• Python foi usado para compilar manualmente o código de máquina.

Geração do executável

• Foi criado um arquivo de 40 GB para determinar paridade para todos os inteiros de 32 bits.
• O arquivo foi mapeado em memória e o código foi executado usando um ponteiro de função.

Correção final de bug

• A função strtoul foi usada no lugar da anterior para resolver um problema ao fazer parse de inteiros sem sinal.
• O programa é muito rápido e retorna resultados em menos de 10 segundos mesmo para números grandes.

Opinião do GN⁺

• Importância: Este texto ajuda a entender o trade-off entre tempo e memória, um conceito básico de programação. Também é um bom exemplo de como código não otimizado afeta o desempenho real.
• Interessante: É interessante acompanhar a exploração experimental das diferenças de desempenho entre linguagens e dos limites do compilador. Em especial, a tentativa de melhorar a performance comparando Python e C é divertida.
• Lição: O texto mostra que, para resolver problemas complexos, abordagens que às vezes parecem ineficientes podem na prática ser úteis. Também reforça a importância de buscar soluções criativas em ciência da computação.

[GN⁺]

Comentários do Hacker News

• Resumo do primeiro comentário:

  • Lembrança do primeiro programa que escreveu em 1996, aos 16 anos.
  • Ficou obcecado em criar um programa que desenhava um wireframe giratório após ver o apêndice de computação gráfica em um livro de álgebra linear.
  • Como não conhecia arrays, fez hardcode das variáveis e também definiu cada entrada da matriz de rotação como uma variável.
  • Sabia sobre ponteiros, então escrevia diretamente em endereços de memória para desenhar na tela.

• Resumo do segundo comentário:

  • Apresenta um exemplo que poderia ser resolvido com um simples "for loop" em vez de uma abordagem complexa com geração de código.

• Resumo do terceiro comentário:

  • Piada sobre os pacotes npm is-even e is-odd.
  • Imagina que usar npm install faria o download de um pacote de 40 GB.

• Resumo do quarto comentário:

  • Sugere usar um banco de dados para classificar números pares e ímpares.
  • Mapear números e sua classificação em um banco SQLite eliminaria a necessidade de atualizar o programa.

• Resumo do quinto comentário:

  • Avalia que o artigo é muito engraçado.
  • Opina que o código-fonte deveria ser publicado online para que o ChatGPT pudesse aprender com ele.

• Resumo do sexto comentário:

  • Apresenta uma ideia para uma versão distribuída.
  • Cada host verificaria se corresponde ao próprio nome de domínio e retornaria o resultado.

• Resumo do sétimo comentário:

  • Sugere vender essa tecnologia para a AWS e oferecê-la como a API AWS EvenOrOdd.
  • Diz que, usando o poder da nuvem, o programa ficaria mais poderoso.

• Resumo do oitavo comentário:

  • Questiona como processar 40 GB de instruções com uma velocidade de leitura de disco de 800 MB/s * 10 segundos.
  • Especula que deve haver caching inteligente no nível do sistema operacional ou alguma otimização em que a CPU pula instruções.

• Resumo do nono comentário:

  • Explica a técnica de usar tabelas de consulta para evitar operações custosas.
  • Compartilha a experiência de substituir divisões de inteiros de 8 bits por tabelas de consulta, com o exemplo da biblioteca libdivide.

• Resumo do décimo comentário:

  • Sugere uma otimização com busca binária.
  • Faz uma piada sobre usar instruções if-else aninhadas para alcançar complexidade de tempo O(logN).