Desafío de mil millones de filas

 (morling.dev)
2 puntos por GN⁺ 2024-01-05 | 2 comentarios | Compartir por WhatsApp
  • El One Billion Row Challenge (1BRC), realizado durante todo enero de 2024, es un desafío de rendimiento para ver hasta dónde puede llegar Java procesando un archivo de texto de mil millones de filas
  • La entrada es un texto simple con formato station;temperature, pero hay que calcular la temperatura mínima, media y máxima por estación y mostrar el resultado exacto en orden alfabético por nombre
  • La implementación permite solo Java; se pueden usar distribuciones de SDKMan y builds Early Access de openjdk.net, pero se prohíben las dependencias externas
  • Los participantes envían su solución mediante un pull request al repositorio 1brc en GitHub, y pueden comparar el formato correcto y el rendimiento con la implementación base proporcionada
  • La evaluación se hace en el mismo entorno Hetzner Cloud CCX33, ejecutando cada solución 5 veces y promediando 3 resultados tras excluir el mejor y el peor registro

El reto de Java para agregar mil millones de filas lo más rápido posible

  • One Billion Row Challenge fue un desafío de rendimiento de Java realizado del 1 al 31 de enero de 2024
  • Los participantes escriben un programa en Java que lee mediciones de temperatura desde un archivo de texto y calcula la temperatura mínima, media y máxima para cada estación meteorológica
  • La clave de la dificultad está en que el archivo de entrada tiene 1,000,000,000 filas
  • La entrada tiene una estructura simple, con una medición por línea
    • Ej.: Hamburg;12.0
    • Ej.: Bulawayo;8.9
    • Ej.: Palembang;38.8
  • La salida debe ordenar los nombres de las estaciones alfabéticamente y mostrar los valores min/mean/max de cada una
    • Ej.: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Reglas de envío y entorno de ejecución

  • El objetivo es crear la implementación en Java más rápida que realice esta misma tarea
  • Para optimizar se pueden usar hilos virtuales, Vector API y SIMD, optimización de GC, compilación AOT y más
  • Las reglas básicas son las siguientes
    • La entrega debe estar escrita en Java
    • Se pueden usar las distribuciones de Java ofrecidas en SDKMan y los builds Early Access de openjdk.net
    • También se permiten builds EA de proyectos de OpenJDK como Valhalla
    • No se pueden usar dependencias externas
  • Los participantes clonan el repositorio 1brc y envían su implementación siguiendo las instrucciones del README
  • La implementación base se ofrece como referencia de comparación y para verificar el formato correcto de la respuesta
  • El envío se realiza abriendo un pull request en el repositorio upstream

Cómo se calcula el leaderboard y cómo se comparte en la comunidad

  • La evaluación se realiza en una instancia de Hetzner Cloud CCX33
    • Especificaciones: 8 dedicated vCPU, 32 GB RAM
    • El tiempo end-to-end se mide con el programa time
    • Cada entrega se ejecuta 5 veces seguidas
    • Se excluyen la ejecución más lenta y la más rápida
    • El resultado final de esa entrega es el promedio de los tiempos de las 3 ejecuciones restantes
    • El resultado se agrega al leaderboard
  • La discusión sobre técnicas de optimización continúa en la discusión del repositorio en GitHub
  • También existe una sección de Show & Tell para compartir implementaciones en otros lenguajes además de Java, donde se han publicado implementaciones 1BRC en Rust, Go, C++ y otros

Lecturas relacionadas

2 comentarios

 
GN⁺ 2024-01-05
Opiniones de Hacker News

  • La solución [0] que actualmente parece tener el mejor rendimiento no considera las colisiones de hash, así que si en el dataset hay suficientes ciudades distintas, parece que podría dar resultados incorrectos
    Me pregunto si se me está escapando algo
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • Correcto. Ayer se señaló este problema y, de hecho, dos soluciones dependían de una función hash ajustada a un dataset específico, incumpliendo la regla de que debe funcionar con todos los nombres de estaciones, pero eso se pasó por alto durante la evaluación
      Por ahora esos registros se quitaron de la tabla de posiciones, y ambos autores están corrigiendo sus envíos, así que volverán a agregarse después
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • Creo que con el siguiente enfoque se puede procesar todo en 0.3 segundos
    Como las temperaturas tienen un decimal, en el caso general bastan unos 400 valores, y como los nombres de lugares también son finitos, unos 400, se puede crear una tabla de consulta de unas 160 mil combinaciones temperatura×lugar
    Se genera automáticamente una máquina de estados que mapee esas 160 mil combinaciones al bucket único de una tabla hash, sin importar en qué posición de rotación dentro de un registro de 4 bytes estén, y en un registro de estado de 32 bits se hace en cada ciclo una consulta a la tabla de transición de estados y el XOR de los siguientes 4 bytes
    Luego solo hay que recorrer todos los datos a velocidad de memoria e incrementar el contador del estado correspondiente; como solo hay 65K estados, los contadores caben en caché
    Con AVX512, se podrían ejecutar en paralelo 512 de estas máquinas de estado de 32 bits por núcleo, así que el cómputo no debería ser el cuello de botella
    Las temperaturas altas/bajas que no mapeen a un bucket válido o los nombres de lugares desconocidos se pasan al código lento, y el manejo del mínimo/máximo también se puede resolver con ese escape, así que solo ocurriría unos pocos miles de veces
    Creo que este método podría funcionar a velocidad de memoria con un solo núcleo AVX512, así que no habría ventaja en dividirlo entre varios núcleos

    • No hace falta una tabla de consulta. Lo único que se pide es mínimo/promedio/máximo, así que todo se puede calcular en una sola pasada sin almacenar los datos
      Solo hace falta una tabla hash de 400 entradas, 3 valores de punto flotante para el mínimo, promedio y máximo en ejecución, y un entero contador para actualizar el promedio
      Incluso usando 16 bytes por nombre, todo cabe dentro de 16 KB
      El tiempo de ejecución va a estar dominado por la E/S, y luego probablemente por el parsing de JSON
    • Un solo núcleo no puede saturar el ancho de banda de memoria. Los núcleos están limitados por el paralelismo de memoria y la latencia
      La mayoría de los chips servidor x86 modernos pueden retirar 2 cargas SIMD por ciclo de reloj, así que con AVX2 a 1GHz se puede llegar a unos 32GB/s, por lo que no hace falta necesariamente AVX-512 para maximizar el ancho de banda por núcleo
      Pero si estás leyendo desde DRAM, es muy probable que te topes con el límite mucho antes, normalmente cerca de 10~16GB/s en servidores
      Mientras la mayor parte de los datos se desborde a RAM, el rendimiento de un solo núcleo caerá bastante, y en trabajos grandes de streaming casi siempre conviene el paralelismo multinúcleo
      Se puede comprobar fácilmente asignando un bloque de memoria mucho mayor que la caché L3, provocando page faults por adelantado y luego haciendo cargas vectoriales desenrolladas en un bucle ajustado (AVX2/AVX-512)
    • Como el siguiente estado siempre depende del estado anterior, no entiendo cómo se puede ejecutar en paralelo la máquina de estados
      También me pregunto cómo se interpretaría el registro de estado. Si haces XOR con 4 bytes de entrada, con nombres de lugares no esperados en realidad podría convertirse en cualquiera de los casi 4.7 mil millones de valores posibles
      Incluso con nombres esperados, si miden más de 4 bytes, ¿no harían falta varios estados para cada uno a fin de distinguirlos de otros nombres con el mismo prefijo?
    • Creo que habría que confirmar la interpretación de las reglas. No está claro si es válido un código especializado para 400 nombres de lugares conocidos pero que soporte nombres adicionales por una ruta lenta
      Las reglas dicen que, aunque el generador de datos use un conjunto fijo de nombres de estaciones, cualquier solución debe funcionar con nombres arbitrarios de estaciones en UTF-8
    • Para encontrar los nombres de lugares, al final igual hay que leer y parsear todo el archivo

  • En vez de usar un método que descarte la ejecución más lenta y la más rápida y saque el promedio de las otras tres, me parece mejor descartar las dos lentas o simplemente aceptar el valor más rápido
    No veo una razón válida para desechar un buen resultado de ejecución

    • Esto es una forma bastante estándar de medición llamada media recortada (Trimmed Mean): https://statisticsbyjim.com/basics/trimmed-mean/
    • Sí hay una razón para descartar la ejecución más rápida. Si asumes que el sistema se comporta de manera predecible y que solo se vuelve más lento por tareas en segundo plano, entonces usar la mejor ejecución puede tener sentido
      Pero si dentro del programa hay aunque sea una pequeña fuente de no determinismo, algo más común de lo que parece, el mejor tiempo puede no ser representativo
      Sobre eso, https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... es un buen texto
    • Si te parece inaceptable descartar la ejecución más rápida, me pregunto por qué sí estás de acuerdo con descartar la más lenta

  • Desde una postura estricta con las reglas, dan ganas de levantar un daemon en segundo plano en la primera ejecución, cargar todo el archivo en memoria y fijarlo ahí; luego, hacer que las ejecuciones posteriores sean prácticamente solo un escaneo lineal, incluso trayendo de antemano la caché
    También parecería posible precalcular el resultado en la primera ejecución, según hasta dónde se quiera estirar la interpretación de las reglas; incluso se podría parsear antes los números a un formato más compacto y en las siguientes ejecuciones leerlos directamente como suma acumulada
    No encaja para nada con el espíritu del concurso, pero por lo que se ve en las reglas no parece estar prohibido
    Si no te gusta el precálculo, también serían posibles trucos como ordenar la entrada por adelantado, parsearla antes o usar compresión, ordenamiento y una disposición de memoria ya ordenada
    En el extremo, hasta se podría parchear el script calculate_time para que devuelva 0 segundos y 9999 para los competidores

    • Si a los participantes se les entrega el archivo exacto que se va a usar en la competencia, sí aparece un problema real
      Desde hardcodear la respuesta en una sola línea sin siquiera leer la entrada, hasta procesarla asumiendo que no se conoce el contenido del archivo, hay como mil millones de escalones en la zona gris del precálculo
      Podría terminar siendo una competencia para decidir qué precálculo es justo y cuál no
      Por eso en las competencias de aprendizaje automático no se les muestra a los participantes el conjunto de datos final
    • Parece que esto violaría la regla
      Dice que el cálculo debe ocurrir en el momento de ejecución de la aplicación, y que no se debe procesar el archivo de medición en tiempo de build para incrustar el resultado dentro del binario
    • Según las reglas, creo que habría que especificar que cada ejecución corra en un tmpfs separado y que entre ejecuciones se eliminen todos los procesos y la caché de páginas

  • Da la impresión de que esto simplemente está atado a la velocidad del disco. Tengo dudas de que optimizaciones como SIMD o multithreading realmente hagan diferencia
    Dependerá de cuántas estaciones distintas haya y de cómo se hagan las búsquedas en el hash, pero soy escéptico de que eso sea medible frente a la E/S

    • El acceso a disco se puede paralelizar y NVMe es muy rápido, así que el cuello de botella podría estar más del lado del CPU que del disco
      Los sistemas diseñados pensando en hardware moderno aprovechan esto, y redpanda.com, donde trabajo, es un ejemplo
      El parseo ocupa una parte grande del tiempo de cómputo, y técnicas SIMD como SWAR para encontrar delimitadores pueden ayudar
      Si quieres ver una implementación elegante de este tipo de algoritmos, Stringzilla está muy bien: https://github.com/ashvardanian/StringZilla
      Sobre el punto de que después de la primera ejecución el archivo queda completamente cacheado en memoria, ya se respondió aquí: https://news.ycombinator.com/item?id=38864034
    • Depende por completo de la carga de trabajo y del hardware. Incluso un SSD de consumo puede sostener fácilmente 7 GB/s (56 Gbps) si de 2 TB solo usas 700 GB
      Un servidor normal suele tener suficientes líneas PCIe para conectar 15 SSD de ese tipo, así que el ancho de banda de E/S del servidor queda en un nivel parecido al del ancho de banda de memoria
      Los servidores más caros tienen más líneas y más rápidas, como PCIe 5.0
      Este archivo tiene mil millones de filas y comprimido ocupa alrededor de 1 GB, y después de la primera ejecución descartada queda en memoria, así que en este escenario el ancho de banda de E/S no importa
      En el repositorio de GitHub dice que son 12 GB sin comprimir, pero aun así eso confirma que el ancho de banda de E/S no importa
    • Esta charla de Daniel Lemire es interesante: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      La idea central es que rara vez el disco es el cuello de botella
    • Depende del sistema operativo y del sistema de archivos. El archivo de entrada es de unos 12 GB y se ejecuta 5 veces en una máquina con 32 GB de memoria, así que después de la primera ejecución podría quedar entero cacheado en memoria
      Por ejemplo, en Linux con ext2 es probable que todo el archivo quede cacheado tras la primera ejecución, pero con ZFS quizá no
    • Para parsear lo más rápido posible, parece claro que habría que cargar todo en RAM y procesarlo desde el final hacia atrás
      Así los números aparecen desde el dígito menos significativo al más significativo, y luego vienen el delimitador y la cadena, avanzando hasta encontrar EOF o un salto de línea

  • Según las reglas, la entrega debe funcionar correctamente para cualquier entrada, pero da la impresión de que se puede, y probablemente se debe, ajustar para la entrada específica generada por create_measurements.sh
    Por ejemplo, es fácil imaginar una entrega que use una función hash perfecta adaptada al conjunto dado de estaciones

    • Si ese requisito existe, sería sensato que los datos de prueba fueran distintos de los datos de ejemplo
      Así se evita la optimización por sobreajuste
    • Con UTF-8 se vuelve mucho más difícil. Pero si se sigue solo la letra de la regla y no su espíritu, bastaría con detectar en cuanto aparezca un byte mayor que 127 y pasar a una implementación lenta
      Un byte mayor que 127 indica un carácter UTF-8 de varios bytes

  • Por diversión, hice una comparación de velocidad entre awk y Java
    Es un script con awk -F';' que acumula por estación la suma, el conteo, el mínimo y el máximo, y al final en END calcula el promedio y lo imprime

    • Me gustaría ver una comparación de velocidad con el wrapper de datos externos de archivos de PostgreSQL: https://www.postgresql.org/docs/current/file-fdw.html
      La idea sería crear un archivo CSV como tabla externa con file_fdw y calcular MIN, AVG y MAX con GROUP BY station_name
    • Ejecutándolo con ClickHouse local da alrededor de 15.2 segundos
      En clickhouse local se lee file('measurements.txt', 'CSV', 'station String, t Float32'), se agrupa por estación para calcular min, max y avg, y se ejecuta con max_threads = 8
      La mayor parte del tiempo se va en parsear el archivo
    • Como la variable sum puede crecer bastante, conviene usar un promedio en streaming
      Por ejemplo, con algo como new_mean = ((n*old_mean)+temp)/(n+1)

  • Es un reto interesante, pero es una pena que sea solo para Java. Tengo ganas de ver cuándo la gente empiece a crear bytecode de la JVM a mano

    • Por la discusión, parece que hay envíos en varios lenguajes. Hay Go, Rust, Python, C++, etc.
      [0] https://github.com/gunnarmorling/1brc/discussions
    • O también se puede interpretar “hay que escribirlo en Java” como “hay que usar la JVM al iniciar la ejecución”, y claramente es posible lanzar otro proceso desde Java

  • Está divertido. Se siente como una convivencia después de Advent of Code
    Si se busca una comparación justa entre lenguajes, también habría que incluir make y el tiempo de compilación. No usaba Java/Maven desde hace años, pero ver que la descarga de ./mvnw clean verify ya lleva 2 minutos me recordó enseguida por qué

    • El tiempo de compilación de Java es muy rápido. Lo que estás midiendo ahora es la velocidad de Internet
      Y como herramienta de compilación incremental, Gradle es más rápido
    • Si vas a incluir el tiempo de compilación, también habría que incluir el tiempo de programación, y dividir ambos entre la cantidad de veces que el código se ejecutará a lo largo de su vida útil
      También habría que sumar una proporción adecuada del tiempo que tomó aprender a programar
      En este tipo de retos, probablemente terminaría ganando una versión muy ingenua, lo cual no solo sería poco realista sino que además iría contra el propósito del reto
    • No entiendo por qué hacen clean
      Es como tirar la caché y luego quejarse de que es lento
    • No hace falta Maven
      Dice que no se pueden usar dependencias externas

  • Hubo una tarea muy parecida en un curso de C de la Universidad Técnica Checa
    Todos los trabajos de los estudiantes se evaluaban continuamente en una tabla de posiciones, y muchos pasaban decenas de horas optimizando para conseguir puntos extra por mejores calificaciones, o básicamente puntos de estatus
 
dlehals2 2024-01-10

El primer lugar lo hizo en 6 segundos... impresionante.