O Desafio das Um Bilhão de Linhas

Artigo original ↗ Discussão no Hacker News ↗

Um “One Billion Row Challenge” centrado em Java para calcular min/média/max de temperaturas a partir de um arquivo de texto de 12 GB com 1 bilhão de linhas tornou-se uma vitrine para ajuste extremo de desempenho e conhecimento de sistemas. Os participantes debatem se a tarefa é limitada por I/O ou CPU, trocando técnicas como memory mapping, parsing numérico personalizado, SIMD, multi-threading e o aproveitamento do comportamento do page cache do sistema operacional, ao mesmo tempo em que discutem métodos justos de benchmark e regras que proíbem truques específicos do conjunto de dados. Muitos comparam Java otimizado manualmente com C, Rust, bancos SQL, awk e pandas, usando o exercício para explorar como hardware moderno, runtimes e ferramentas de processamento de dados se comportam sob cargas pesadas, porém conceitualmente simples.

Escopo do desafio e linguagens

  • Embora seja apresentado como um desafio de Java, muitos participantes discutem e compartilham implementações em C/C++, Rust, Go, .NET, Python, Perl, Awk, R, SQL, ClickHouse, DuckDB, Pinot e outras.
  • Alguns gostariam que outras linguagens da JVM fossem permitidas oficialmente, enquanto outros observam que a regra de “sem dependências externas” exclui coisas como Hadoop ou Pandas.

IO, cache e estratégias de acesso a arquivos

  • Um tema central é saber se a tarefa é limitada por IO ou por CPU.
  • Como o arquivo de 12 GB é executado 5 vezes em uma máquina de 32 GB e os caches não são esvaziados, as execuções posteriores efetivamente operam a partir do page cache, tornando o parsing e a agregação o principal gargalo.
  • Abordagens debatidas: ler para a RAM vs mmap, IO com buffer vs O_DIRECT, io_uring, buffers pequenos fixos e o tratamento de linhas que cruzam limites de blocos.
  • Alguns argumentam que depender da política de cache do sistema operacional torna o benchmark menos “puro”; outros dizem que isso reflete implantações reais.

Restrições de correção e preocupações com overfitting

  • Os nomes das estações devem ser UTF-8 arbitrário (sem ;), com até 100 caracteres; as temperaturas variam de −99.9 a 99.9, com exatamente uma casa decimal.
  • Isso permite aritmética inteira (escala por 10) e parsing mais simples do que ponto flutuante completo.
  • Várias soluções rápidas foram descobertas usando incorretamente funções de hash ou dependendo do conjunto de dados específico, e foram removidas; há debate sobre o que conta como “overfitting” injusto.
  • Surgem ideias de randomização do conjunto de dados ou seeds ocultas para evitar ajustes a um único arquivo.

Debate sobre metodologia de benchmark

  • O organizador descarta o mais rápido e o mais lento de 5 execuções e faz a média das 3 do meio.
  • Um lado argumenta que o tempo mínimo reflete melhor o potencial algorítmico sem ruído.
  • Outros respondem que médias aparadas aproximam melhor o desempenho no mundo real sob ruído do sistema, contenção de VM e efeitos de GC.

Estratégias algorítmicas e de implementação

  • Sugestões comuns: processamento em streaming com agregados por estação, temperaturas inteiras, parsing numérico escrito manualmente, SIMD para busca de delimitadores e parsing, minimização de alocações e projeto cuidadoso de hash map.
  • Alguns exploram ideias mais exóticas como máquinas de estado personalizadas, hashes perfeitos ou parsers especializados e stateful com SIMD, embora a viabilidade seja debatida.

Uso de bancos de dados e motores de análise

  • Vários participantes demonstram motores SQL (PostgreSQL, ClickHouse, DuckDB, Pinot, kdb+/q) resolvendo a consulta de forma muito concisa, mas muitas vezes mais lentamente, especialmente incluindo ingestão.
  • Há discussão sobre inchaço de armazenamento, estratégias de índices, truques com arrays, planos de consulta paralelos e COPY vs INSERT para carregamento em massa.

Java, ferramentas de build e comparações entre linguagens

  • As opiniões sobre Java são mistas: alguns elogiam seu desempenho e ferramentas; outros reclamam da verbosidade e do boilerplate.
  • Longas subthreads comparam Maven vs Gradle vs ferramentas de Cargo/Go, comportamento de compilação incremental e a percepção de lentidão no build.
  • Alguns observam que, embora linguagens de baixo nível possam ser as mais rápidas, Java ingênuo muitas vezes supera C/C++ ingênuo por padrões mais seguros e otimizações do JIT.