Introducción al concurso 1BRC
- En el concurso 1BRC, se preveía que, después de procesar a los "sospechosos habituales", el cuello de botella sería parsear las temperaturas desde un archivo CSV.
- Las temperaturas podían aparecer en cuatro formatos:
-XX.X, -X.X, X.X y XX.X, y al principio se usaba una llamada a la biblioteca Double.parseDouble().
- Sin embargo, pronto aparecieron soluciones personalizadas, y una de ellas parecía ser un método optimizado con solo dos bifurcaciones y sin bucles.
- Luego, la solución presentada por Quân Anh Mai (@merykitty) encendió el hashtag #1BRC en Twitter. Esta solución usaba una sola lectura de archivo y ningún
if.
Análisis del SWAR casi mágico de merykitty
- El código de merykitty está compuesto por solo 18 operaciones ALU e incluye una única llamada a una función de bajo nivel,
numberOfTrailingZeros().
- El número
long de entrada contiene 8 bytes del CSV, y la salida es una temperatura en forma entera (10 veces la temperatura real).
- Esta técnica se conoce como "SIMD Within A Register" (SWAR) y usa registros e instrucciones estándar del CPU.
- El código pasa por etapas como detectar si el número es negativo, eliminar el carácter de signo, encontrar la posición del punto decimal, alinear el contenido con una plantilla, convertir caracteres ASCII en valores numéricos, multiplicar cada dígito por su peso y sumarlos todos, y aplicar el signo.
- Todos estos pasos se realizan usando únicamente operaciones ALU.
Conclusión
- Cómo merykitty pudo lograr todo esto por su cuenta en apenas unos días es el verdadero misterio que ningún post de blog puede explicar.
- QuestDB es de código abierto y ofrece inserción rápida de datos y análisis SQL bajo la licencia Apache 2.0.
Opinión de GN⁺
- Este artículo muestra la complejidad y creatividad de la técnica SWAR diseñada para resolver un simple problema de parseo de temperaturas. Resalta el poder de las operaciones de bits y la importancia de la optimización en programación.
- Este tipo de enfoque puede ser un caso interesante, especialmente para ingenieros de software principiantes interesados en programación de sistemas o en el desarrollo de aplicaciones sensibles al rendimiento.
- Para profundizar la comprensión sobre operaciones de bits y optimización, puede ser útil buscar competencias de programación en línea o tutoriales que traten temas o problemas relacionados.
- Se necesita más investigación sobre cómo esta técnica puede aplicarse en entornos industriales reales y sobre qué otras bases de datos o sistemas usan técnicas de optimización similares.
- Al adoptar sistemas como QuestDB, conviene considerar no solo las mejoras de rendimiento, sino también otros factores como la mantenibilidad, la legibilidad del código y el soporte técnico a largo plazo.
1 comentarios
Comentarios en Hacker News
Resumen de los comentarios de Hacker News relacionados con el artículo de simdjson:
Interpretación del contexto del código: la solución presentada es sobresaliente, pero requiere asumir que los datos están bien estructurados. La verificación eficiente de errores y las funciones de recuperación tienen mucho valor en parsers con experiencia.
Técnica de parseo de números: multiplicar cada bitfield numérico por su correspondiente potencia de 10 y luego usar MUL para hacer shift/suma es una técnica conocida. Ver el blog de Lemire.
Explicación de SWAR (SIMD Within A Register): hay muchos ejemplos de implementación de rutinas SWAR eficientes en Java/Scala usando var handles de vista de arreglos de bytes.
Definición breve de SWAR: "SIMD Within A Register" realiza operaciones SIMD dentro de un solo registro.
Pregunta sobre el cuello de botella de I/O en BRC (Branchless Ray Casting): no se entiende por qué la CPU sería el cuello de botella.
Experiencia usando SWAR en 68000: era posible procesar 4 bytes en paralelo de una sola vez, pero manejar el overflow era complicado. Le encantó mucho este artículo.
Espacio de estados y superoptimizador: pregunta sobre si existe un superoptimizador que produzca resultados similares, dado que el espacio de estados es pequeño.
Instrucciones AVX y soporte SIMD en Java: este algoritmo podría ejecutarse con paralelismo de 32x usando instrucciones AVX, pero es una lástima que Java no soporte bien el uso de CPU SIMD salvo en ciertos casos.
Comprensión de la manipulación de bits: este artículo le ayudó a entender la manipulación de bits mejor que cualquier otro anterior, y agradece al autor por presentar una solución en Java para el reto 1BRC.