simdjson - Analizar JSON a velocidades de GB/s

• Analiza 2.5 veces más rápido que los parsers existentes usando el conjunto de instrucciones SIMD

• Selección automática en tiempo de ejecución del parser optimizado para cada CPU: Haswell (AVX2)/Westmere (SSE4.2)/ARM64/otros 64-bit

• Soporte para validación completa de JSON y UTF-8

• Un solo archivo .h + .cpp

• Usa solo el 25% del conjunto de instrucciones frente a RapidJSON y el 50% frente a sajson

[novemberoscar]

Veo que hay varios bindings / ports

• ZippyJSON: bindings de Swift para el proyecto simdjson.

• libpy_simdjson: bindings de Python de alta velocidad para simdjson usando libpy.

• pysimdjson: bindings de Python para el proyecto simdjson.

• simdjson-rs: port para Rust.

• simdjson-rust: wrapper para Rust (bindings).

• SimdJsonSharp: versión en C# para .NET Core (bindings y port completo).

• simdjson_nodejs: bindings de Node.js para el proyecto simdjson.

• simdjson_php: bindings de PHP para el proyecto simdjson.

• simdjson_ruby: bindings de Ruby para el proyecto simdjson.

• fast_jsonparser: bindings de Ruby para el proyecto simdjson.

• simdjson-go: port para Go usando ensamblador de Golang.

rcppsimdjson: bindings de R.

[xguru]

Versión en Rust - https://github.com/simd-lite/simd-json

Contenido de la presentación del desarrollador en QCon "Parsing JSON Really Quickly: Lessons Learned"

https://www.youtube.com/watch?v=wlvKAT7SZIQ

[kunggom]

Transcripción de la charla enlazada:

https://www.infoq.com/presentations/simdjson-parser/

Me dio curiosidad cómo puede alcanzar una velocidad tan alta y lo leí; parece, literalmente, la culminación de toda clase de magia negra. Resumiendo a grandes rasgos, los puntos clave son los siguientes.

---

[Introducción]

La mayoría de las bibliotecas de parsing de JSON son más lentas que la velocidad de lectura secuencial del disco

• En mi sistema (el del ponente Daniel Lemire), la velocidad de lectura secuencial de archivos de texto grandes desde la unidad del sistema es de 2.2 GB/s, pero la velocidad de parsing de las principales bibliotecas JSON no logra seguirle el paso.

• Como era raro ver bibliotecas que superaran 1 GB/s de parsing, decidimos hacer una nosotros mismos.

• Como resultado, logramos una velocidad de procesamiento capaz de usar todo el ancho de banda del disco. Si haces las cuentas, usamos apenas 1.5 ciclos de CPU por cada byte de entrada. ¿Cómo se logró eso?

[Distintos principios]

Evitar las ramas condicionales tanto como sea posible

• Por ejemplo, incluso si a un código simple que mete números aleatorios en un arreglo le agregas un solo if para comprobar si el número es impar, se vuelve 5 veces más lento. Esto se debe a que el costo de fallar en la predicción de ramas del CPU es grande.

• Si en el código mostrado arriba eliminas el if con operaciones de bits, la velocidad casi vuelve a la normalidad.

• Si ejecutas el código repetidamente, la precisión de la predicción de ramas puede subir y la caída de rendimiento puede reducirse, pero al final eso sigue siendo un comportamiento no determinista, así que cuando entra en juego la predicción de ramas se vuelve difícil predecir o medir el rendimiento.

Usar SIMD agresivamente para aprovechar palabras más anchas

• Si usas instrucciones SIMD, puedes usar registros con palabras más anchas que 64 bits, lo que permite procesar más datos por ciclo. (Por ejemplo, SSE y NEON son de 128 bits, AVX es de 256 bits.) Por eso usaron SIMD de forma agresiva siempre que fue posible. Esa es la clave de cómo lograron usar solo 1.5 ciclos por byte de entrada.

• Para usar SIMD, recurrieron a funciones intrínsecas (intrinsic functions) dependientes del procesador. No recomiendan usar ensamblador directamente.

Evitar la asignación de memoria/objetos

• En simdjson, los datos JSON se tratan como una sola cinta larga y se reutilizan los datos. En otras palabras, no se asigna memoria por separado para cadenas o números, sino que todo se procesa en línea. Es un truco bastante común.

Medir el rendimiento constantemente

• El desarrollo estuvo guiado por benchmarks. En nuestro CI están incluidos benchmarks de rendimiento.

• Como nota, cuando haces algo intensivo para el CPU, hay que tener en cuenta que la frecuencia de operación del CPU cambia constantemente.

[Casos reales]

Ejemplo 1: validar si es UTF-8 correcto

• La tarea de validar si datos arbitrarios de entrada corresponden a code points UTF-8 válidos suele implicar varias ramas condicionales.

• Nosotros ideamos una forma de validar con SIMD si 32 bytes de datos son UTF-8 correcto en como mucho 20 ciclos, sin ramas condicionales.

• Como los bytes de UTF-8 no pueden superar el valor entero 244, basta con cargar los datos en un registro de 256 bits con una instrucción SIMD, restar a cada byte el entero 244 usando arithmetic de saturación (saturation arithmetic: una operación que limita el rango del resultado) y luego verificar simplemente que no haya valores distintos de cero.

• ¡Este método es más de 20 veces más rápido que el método que usa ramas condicionales!

Ejemplo 2: clasificar tipos de caracteres

• Para parsear JSON, hay que clasificar distintos caracteres por tipo, como comas, dos puntos, paréntesis y espacios en blanco.

• x86-64 y ARM NEON tienen instrucciones que permiten consultar de una sola vez tablas de búsqueda de 16 bytes.

• Se divide 1 byte en los 4 bits altos y los 4 bits bajos, se aplican por separado dos tablas de búsqueda preparadas de antemano y luego se hace una operación AND con los resultados.

• El código se ve sucio, pero con solo 5 instrucciones se pueden clasificar 16 caracteres sin ramas condicionales.

Ejemplo 3: detectar caracteres de escape

• ¿Se puede detectar sin ramas condicionales un carácter de escape, que se expresa anteponiendo una barra invertida (\)? En particular, también hay que manejar los casos en que aparecen barras invertidas consecutivas para escapar la propia barra invertida.

• En estos casos, hay un truco: basta con fijarse en las barras invertidas en posiciones impares.

• Si se toman como constantes bitmasks que representan posiciones pares e impares, y se aplican operaciones de bits complejas, se pueden filtrar los caracteres de escape sin usar ramas.

• Una vez filtradas las comillas escapadas, lo que queda son las comillas que indican cadenas.

• Si tomas como bitmask las posiciones de esas comillas y repites operaciones XOR, puedes obtener un bitmask que representa la posición de las cadenas. Esta parte puede resolverse con una sola instrucción en la mayoría de los procesadores.

• También hay trucos para hacer corresponder el conjunto de bits con la posición de las cadenas, pero eso se omite por falta de tiempo.

Ejemplo 4: parsear números

• Parsear números es una tarea extremadamente costosa. Al hacer un benchmark de parsing de punto flotante con una función de C bien optimizada, salió una velocidad de 0.09 GB/s, absurdamente mala. Era un cuello de botella evidente.

• La mayor parte del código para parsear números suele trabajar de a un byte a la vez. Eso de ninguna manera es rápido.

• Si tomas 8 caracteres, los conviertes en un entero de 64 bits y los metes en cierta fórmula ideada por el ponente un sábado por la noche, puedes saber si esos 8 caracteres son 8 dígitos consecutivos. Esto es especialmente importante porque mientras más dígitos tiene un número, más tiempo toma parsearlo.

• Vi que en Stack Overflow también hay snippets de código para parsear rápidamente enteros de 8 dígitos. Con SIMD se puede mejorar un poco más, pero lo importante es obtener ideas sobre esta estrategia de procesar muchos datos de una sola vez.

[Otros puntos]

Runtime dispatch

• Como el código depende mucho del hardware, terminan apareciendo funciones optimizadas para cada procesador, y hacer que en tiempo de ejecución se elija la función adecuada según el tipo de procesador fue bastante difícil.

• Puede que no se entienda de inmediato qué tenía eso de difícil, pero el problema era implementarlo de forma portable, sin depender del compilador. Algunos compiladores incluso tenían bugs, y además el lenguaje en sí no ofrece soporte para esto.

• Este punto era importante porque simdjson es una biblioteca open source de un solo archivo de cabecera, fácil de integrar en otros proyectos.

Miscelánea

• Hay wrappers para poder usarlo desde varios lenguajes.

• Existe una versión porteada a Rust, y también están en preparación ports para Go y C#, pero no hay port para Java.

• Varias de las fórmulas matemáticas usadas en este proyecto fueron ideadas junto con el coautor Geoff Langdale, y publicaron un artículo relacionado en VLDB Journal. ( https://doi.org/10.1007/s00778-019-00578-5 )

[xguru]

Wow, lo leí muy a gusto. ¡Gracias!