20% más de velocidad en el procesamiento de cadenas de serde_json

 (purplesyringa.moe)
2 puntos por GN⁺ 2024-08-25 | 1 comentarios | Compartir por WhatsApp
  • serde_json, usado como el parser JSON predeterminado de facto en el ecosistema Rust, logró mejoras de rendimiento de 10%, 23% y 32% en benchmarks con muchas cadenas solo con pequeñas optimizaciones internas
  • El cálculo de la posición de errores dejó de recorrer directamente el inicio de la cadena y pasó a usar memchr para encontrar el número de líneas y el último salto de línea, reduciendo la brecha de la ruta de error, que era más de 2 veces más lenta que la ruta exitosa
  • El bucle principal del parsing de cadenas dejó de buscar por separado \, " y caracteres de control, y pasó a verificarlos de una sola vez con SWAR, logrando baja latencia en cadenas cortas incluso sin SIMD real
  • La decodificación de escapes \u redujo ramas y costo de shift con LUT, enteros con signo y tablas con desplazamiento previo, y el parsing del JSON de la versión rusa de War and Peace subió de 284 MB/s a 344 MB/s
  • Después, el cuello de botella pasó a ser la codificación UTF-8, que se resolvió con generación manual de UTF-8 para evitar los costos de inicialización y copia de char::encode_utf8 y Vec::extend_from_slice, llevando el mismo benchmark hasta 374 MB/s

Por qué optimizar serde_json tiene tanto impacto

  • serde es el framework de serialización y deserialización más representativo de Rust, y serde_json se usa ampliamente como la combinación oficial para trabajar con JSON
  • Al momento de la publicación, serde_json tenía 26,916 dependencias inversas, mientras que simd-json tenía 66
  • Con este nivel de uso, incluso pequeñas mejoras internas en serde_json pueden acumular un efecto importante en todo el ecosistema Rust
  • En un contexto donde muchos usuarios no cambian fácilmente a otro parser JSON, las optimizaciones de bajo riesgo dentro de la librería existente son prácticas

Cálculo de posición de errores: de un bucle simple a memchr

  • En benchmarks de la ruta de error, serde_json era más de 2 veces más lento que la ruta exitosa sobre los mismos datos
    • En los datasets canada, citm_catalog y twitter, la ruta de error era entre -48% y -77% más lenta que la ruta exitosa
  • El cuello de botella era la función position_of_index(), que convierte un índice a line/column para formatear mensajes de error
    • La implementación anterior recorría self.slice[..i] byte por byte y actualizaba line y column cada vez que encontraba \n
  • Al dividir el cálculo en dos pasos se pudo aplicar memchr
    • Contar cuántos \n hay en self.slice[..i] para obtener el número de línea con base 0
    • Encontrar la posición del último \n y restarla de i para obtener la columna
  • memchr ofrece implementaciones optimizadas para buscar y contar un solo carácter, y usa SIMD internamente
  • Después de integrarse PR #1160, el rendimiento de la ruta de error mejoró mucho
    • En canada DOM, la ruta de error subió de 122 MB/s a 216 MB/s
    • En citm_catalog struct, subió de 195 MB/s a 736 MB/s
    • La ruta de error seguía siendo más lenta que la exitosa, pero la brecha se redujo

Búsqueda de escapes en cadenas: encontrar tres condiciones a la vez

  • El bucle principal anterior del parsing de cadenas avanzaba por bytes no escapados mirando la tabla ESCAPE
    • En una cadena JSON, los escapes que deben procesarse son \, " y los caracteres de control ASCII de 0x1F o menos
    • Según la especificación JSON, los caracteres de control no están permitidos dentro de una cadena
  • El primer intento usó memchr2 para encontrar primero \ o ", y después verificar por separado los caracteres de control
    • Eso hacía que la cadena se recorriera dos veces, una rápida y otra lenta, y terminó siendo más lento que antes
    • Vectorizar solo la mitad y dejar el resto como código escalar no produjo una mejora total
  • El segundo intento combinó memchr2 con SIMD manual para comprobar la ausencia de caracteres de control
    • En cadenas cortas, el costo de llamar a la función de selección en tiempo de ejecución era una carga
    • En cadenas largas, seguía existiendo el problema de leer la memoria dos veces
  • La implementación final se ordenó en torno a encontrar \, " y caracteres de control en una sola pasada

Implementación de un procesamiento cercano a SIMD con SWAR

  • Para no introducir código SIMD específico por plataforma, se usó la técnica SWAR (SIMD Within A Register)
    • En lugar de SIMD de 128 bits, se trata una palabra de 64 bits como 8 bytes
    • Con operaciones de bits se verifica al mismo tiempo si cada byte cumple la condición
  • La verificación de caracteres de control reescribió la condición c >= 0 && c < 0x20 en forma de operaciones de bits
    • En grupos de 8 bytes, se comprueba con una máscara de la forma !c & (c - 0x2020202020202020) & 0x8080808080808080
    • Aunque el borrow de una resta de 64 bits puede propagarse a bytes superiores, eso no afecta el objetivo de encontrar el carácter de control más cercano
  • \ y " también se verifican de forma similar y se combinan en una sola expresión
    • La expresión completa consta de 9 operaciones de bits
    • En SIMD x86 harían falta 7 operaciones, así que el throughput es menor, pero en cadenas cortas importa más la latencia
  • En json-benchmark, este código SWAR fue más eficiente que el código SIMD real
  • En cadenas demasiado cortas, SWAR puede ser más lento que el código escalar
    • Se observó una regresión alrededor de cadenas de 5 caracteres
    • Para proteger patrones comunes como la cadena vacía "" y escapes consecutivos \r\n, \uD801\uDC37, se comprueba antes de entrar al bucle SWAR si el primer carácter es un escape
  • Los resultados de la optimización de búsqueda de cadenas variaron según el dataset
    • twitter struct pasó de 638 MB/s a 785 MB/s, un +23%
    • twitter DOM pasó de 305 MB/s a 335 MB/s, un +10%
    • citm_catalog struct pasó de 865 MB/s a 905 MB/s, un +5%
    • Las cadenas vacías seguían siendo hasta 2% más lentas en ciertos microbenchmarks

Optimización de la decodificación de escapes Unicode

  • serde_json maneja tanto cadenas Unicode sin procesar como escapes \u
    • Por ejemplo: "🥺" y "\ud83e\udd7a"
  • La decodificación hexadecimal anterior usaba una LUT de 256 entradas para mapear cada carácter a un valor entre 0 y 15
    • Procesaba '0'..='9', 'A'..='F' y 'a'..='f'
    • Los caracteres inválidos se marcaban con un valor centinela
  • Un escape \u lee 4 dígitos hexadecimales, así que el enfoque anterior incluía shift, suma, comparación y rama condicional en cada iteración
  • La implementación mejorada ya no devolvía error en cada paso del bucle, sino que procesaba los 4 dígitos y verificaba la validez al final
  • La versión final usa una LUT [i8; 256] donde los dígitos inválidos valen -1, y calcula sobre un entero de 32 bits
    • En éxito, el resultado no es negativo; en fallo, sí lo es
    • En x86, la carga desde memoria y la extensión de signo pueden combinarse en movsx
  • Para reducir la latencia de shift, se usan dos tablas
    • HEX0: valor original
    • HEX1: tabla con el valor desplazado 4 bits a la izquierda de antemano
  • Se reorganizó en una implementación decode_four_hex_digits() con unrolling explícito y claro del bucle
  • Con esta optimización, el rendimiento al parsear la versión JSON-encoded de War and Peace en ruso subió de 284 MB/s a 344 MB/s, una mejora de 21%

Cuello de botella en UTF-8 y generación manual

  • Después de optimizar la decodificación de escapes Unicode, el cuello de botella se desplazó a la codificación UTF-8
  • UTF-8 codifica un codepoint en 1 a 4 bytes según su longitud
    • 1 byte: 0xxxxxxx
    • 2 bytes: 110xxxxx 10xxxxxx
    • 3 bytes: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • char::encode_utf8 de la biblioteca estándar de Rust escribe sobre un buffer &mut [u8], así que el buffer ya debe contener valores u8 válidos
    • No se puede escribir directamente sobre un buffer sin inicializar
    • Como UTF-8 es de longitud variable, a LLVM le cuesta eliminar la zeroization innecesaria
  • serde_json lo manejaba con scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
    • En teoría, usar un buffer local [0u8; 4] podía ayudar al análisis de alias
    • En la práctica, por la copia de longitud variable de 1 a 4 bytes, LLVM terminaba generando una llamada a memcpy
  • Para evitar llamadas a memset y memcpy, se generó UTF-8 directamente
    • El algoritmo en sí es simple, pero requirió unsafe
    • Junto con algunos cambios menores, el benchmark de War and Peace mejoró adicionalmente de 344 MB/s a 374 MB/s, otro +9%

Resultado final

  • En benchmarks JSON con muchas cadenas, el rendimiento de serde_json mejoró en 10%, 23% y 32% respectivamente
  • Como muchos datos JSON contienen muchas cadenas, estas optimizaciones pueden impactar de forma amplia el código Rust que usa serde_json
  • Las mejoras se lograron eliminando secuencialmente distintos cuellos de botella, como el cálculo de posición de errores, la búsqueda de escapes en cadenas, la decodificación de escapes Unicode y la codificación UTF-8

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-08-25
Opiniones en Hacker News

  • Los trucos con UTF-8 me inquietan bastante, porque he visto demasiados ataques que confunden parsers
    Uso serde más por su correctitud que por velocidad, así que espero que lo hayan fuzzed hasta el final con un montón de strings UTF-8 inválidos

    • Por suerte, la estructura de UTF-8 es muy simple comparada con la de un parser promedio
      Eso no significa que no haya bugs, pero el estado interno del parser no debería ser grande y las pruebas exhaustivas también parecen posibles
    • Este es justamente el tipo de área donde me gustaría ver los resultados de correr un fuzzer
    • ¿Puedes mencionar algún caso de este tipo de bug que se te venga a la mente de inmediato?

  • Es genial ver que serde avance tan rápido
    Justo estaba mirando simdutf8 y me di cuenta de que el PR de parsing de UTF-8 con soporte SIMD lleva casi 5 años
    https://github.com/rust-lang/rust/issues/68455

  • Leí con gusto el blog de esta persona porque me dio una fuerte vibra de jart
    No sé si la parte de “tendremos que reinventar la rueda, pero si lo piensas, es bastante genial” va en serio o es irónica
    Al leerlo empecé a reírme burlándome del autor, pero el resto de la página parece tener bastante autocrítica

    • Creo que eso no se refiere a que tener que reinventar la rueda sea genial, sino a que el enfoque es bastante genial
    • ¿Qué significa jart?

  • “Enseñar a pensar es tan importante como enseñar a programar, pero casi nunca se hace”
    Me suena a la arrogancia de creer que la otra persona no piensa

    • No veo arrogancia en esa frase
      No asume que los demás no piensen; más bien es una observación de que la mayoría de los posts de blog y guías de uso solo muestran el resultado final y no necesariamente los pasos para llegar ahí
    • El autor no está afirmando eso
      Enseñar a pensar significa que hay que investigar y que no puedes saltarte ese paso; y haber investigado tampoco elimina tu responsabilidad de llegar a tus propias conclusiones
      Es fácil saltarse una de las dos cosas, pero es la forma equivocada de hacerlo

  • serde_json, si haces una build de debug y una de release, termina con 3 GB de dependencias
    Si usas serde en unos cuantos proyectos activos, te quedas sin espacio en disco
    No sé por qué parsear JSON necesita 3 GB de dependencias; estoy a favor de reutilizar código, pero las dependencias del lado JSON de serde parecen bastante desordenadas
    Si aparece un exploit en una de esas dependencias, la mitad del ecosistema Rust queda vulnerable
    Rust debería traer JSON incorporado

    • Solo tiene 5 dependencias, una de ellas opcional y otra es el propio serde: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      Es muy probable que eso no sea lo que realmente midió al hablar de 3 GB de dependencias
      No puedo asegurarlo porque lo está presentando como un hecho sin pruebas, pero si tuviera que adivinar, diría que usó mucho #[derive(Serialize, Deserialize)], se generó una gran cantidad de código y luego está midiendo el tamaño de todo el directorio target
      Una build simple, como muestran otros comentarios, queda en el orden de decenas de MB
    • No creo que incorporar JSON en Rust sea un enfoque razonable
      Eso solo atrae bloat, y la biblioteca estándar no es distinta de otros crates salvo por sus garantías de estabilidad, así que no aporta ventajas
      Al final solo tiene el efecto de atar el ciclo de releases de la biblioteca al ciclo de releases del compilador
      De hecho, antes rustc-serialize era algo cercano a estar incorporado, y Rust ya intentó ese camino
      Además, serde_json en su estado predeterminado no es grande
      Ni serde_json ni serde son grandes, y ambos mantienen un MSRV muy bajo que otros crates no suelen soportar bien, así que en la práctica tampoco pueden tener muchas dependencias
    • El bloat de dependencias es un problema general de Rust
      El árbol de dependencias de cualquier proyecto Rust de cierto tamaño se vuelve bastante horrible muy rápido; auditar todas esas dependencias es inviable en la práctica y la confianza en muchas de ellas también es baja
      Después de haber trabajado con Rust durante algunos años, creo que no volvería a tocarlo hasta que el ecosistema madure mucho más
      Esa madurez llegará con una adopción empresarial a gran escala; si no, lo usaría solo en proyectos no-std, sin dependencias, o como reemplazo puro de C
      Aunque si Zig se estabiliza, podría desplazar a Rust incluso para ese uso
    • Rust emite una cantidad anormalmente grande de información de depuración
      Es tan absurdamente grande que supongo que simplemente debe ser un bug
      Compiles lo que compiles, se acumulan gigabytes en la carpeta target, pero eso no representa el artefacto final después de quitar la información de depuración o al menos usar una configuración menos detallada
    • En un proyecto de cierto tamaño, parece que la carpeta target literalmente siempre ocupa como mínimo algunos GB