El desafío de mil millones de filas

Artículo original ↗ Discusión en Hacker News ↗

Un “Desafío de mil millones de filas” centrado en Java para calcular el mínimo/promedio/máximo de temperaturas a partir de un archivo de texto de 12 GB y 1.000 millones de líneas se ha convertido en una muestra de ajuste extremo del rendimiento y conocimiento de sistemas. Los participantes debaten si la tarea está limitada por I/O o por CPU, alternando técnicas como mapeo de memoria, análisis numérico personalizado, SIMD, multi-threading y el aprovechamiento del comportamiento de la caché de páginas del SO, mientras también discuten métodos de benchmarking justos y reglas que prohíben trucos específicos del conjunto de datos. Muchos contrastan Java optimizado a mano con C, Rust, SQL, bases de datos, awk y pandas, usando el ejercicio para explorar cómo se comportan el hardware moderno, los runtimes y las herramientas de procesamiento de datos bajo cargas pesadas, pero conceptualmente simples.

Alcance del desafío y lenguajes

  • Aunque se presenta como un desafío de Java, muchos participantes comentan y comparten implementaciones en C/C++, Rust, Go, .NET, Python, Perl, Awk, R, SQL, ClickHouse, DuckDB, Pinot y otros.
  • Algunos desearían que otros lenguajes de JVM estuvieran permitidos oficialmente, mientras que otros señalan que la regla de “sin dependencias externas” excluye cosas como Hadoop o Pandas.

IO, caché y estrategias de acceso a archivos

  • Un tema central es si la tarea está limitada por IO o por CPU.
  • Como el archivo de 12 GB se ejecuta 5 veces en una máquina de 32 GB y las cachés no se vacían, las ejecuciones posteriores operan efectivamente desde la caché de páginas, lo que convierte el análisis y la agregación en el principal cuello de botella.
  • Estrategias debatidas: leer en RAM frente a mmap, IO con búfer frente a O_DIRECT, io_uring, búferes pequeños de tamaño fijo y cómo manejar líneas que cruzan límites de fragmentos.
  • Algunos argumentan que apoyarse en la política de caché del SO hace que el benchmark sea menos “puro”; otros dicen que refleja implementaciones reales.

Restricciones de corrección y preocupaciones por sobreajuste

  • Los nombres de estación deben ser UTF-8 arbitrario (sin ;), de hasta 100 caracteres; las temperaturas van de −99.9 a 99.9 con exactamente un decimal.
  • Esto permite aritmética entera (escalando por 10) y un análisis más simple que el de punto flotante completo.
  • Se descubrió que varias soluciones rápidas usaban incorrectamente funciones hash o dependían del conjunto de datos específico y fueron eliminadas; hay debate sobre qué cuenta como “sobreajuste” injusto.
  • Surgen ideas de aleatorización del conjunto de datos o semillas ocultas para evitar ajustar una solución a un solo archivo.

Debate sobre la metodología del benchmark

  • El organizador descarta la ejecución más rápida y la más lenta de 5 y promedia las 3 del medio.
  • Unos sostienen que el tiempo mínimo refleja mejor el potencial algorítmico sin ruido.
  • Otros responden que las medias recortadas aproximan mejor el rendimiento real bajo ruido del sistema, contención de máquinas virtuales y efectos del GC.

Estrategias algorítmicas y de implementación

  • Sugerencias comunes: procesamiento en flujo con agregados por estación, temperaturas enteras, análisis numérico hecho a mano, SIMD para búsqueda de delimitadores y parsing, minimizar asignaciones y diseñar con cuidado la hash map.
  • Algunos exploran ideas exóticas como máquinas de estados personalizadas, hash perfectos o analizadores SIMD especializados con estado, aunque se debate su viabilidad.

Uso de bases de datos y motores analíticos

  • Varios participantes demuestran que motores SQL (PostgreSQL, ClickHouse, DuckDB, Pinot, kdb+/q) resuelven la consulta de forma muy concisa pero a menudo más lenta, especialmente al incluir la ingestión.
  • Hay discusión sobre el crecimiento del almacenamiento, estrategias de índices, trucos con arrays, planes de consulta paralelos y COPY frente a INSERT para cargas masivas.

Java, herramientas de build y comparaciones de lenguajes

  • Las opiniones sobre Java están divididas: algunos elogian su rendimiento y herramientas; otros se quejan de la verbosidad y la repetición.
  • Largas subtramas comparan Maven, Gradle y las herramientas de Cargo/Go, el comportamiento de la compilación incremental y la percepción de lentitud en las compilaciones.
  • Algunos señalan que, aunque los lenguajes de bajo nivel pueden ser los más rápidos, un Java ingenuo a menudo supera a un C/C++ ingenuo gracias a valores predeterminados más seguros y a las optimizaciones del JIT.