El SWAR mágico de merykitty en 1brc: 8 líneas de código explicadas en 3 mil palabras

 (questdb.io)
2 puntos por GN⁺ 2024-03-11 | 1 comentarios | Compartir por WhatsApp
  • El cuello de botella de 1BRC era parsear a velocidad extrema 1.000 millones de valores de temperatura en CSV, y el código SWAR de merykitty de Quân Anh Mai llamó la atención por convertir temperaturas a enteros con operaciones ALU fijas, sin if
  • Este código usa SWAR (SIMD Within A Register), una técnica que maneja de una vez los 8 bytes contenidos en un solo long, procesando varios caracteres casi en paralelo dentro de un registro común de CPU
  • El flujo de procesamiento pasa por detectar el signo menos, eliminar el signo, encontrar la posición del punto decimal, alinear a XY.Z, convertir dígitos ASCII, hacer una multiplicación mágica y aplicar el signo
  • Los formatos de entrada son cuatro: -XX.X, -X.X, X.X, XX.X; según la posición del punto decimal, se desplazan bytes para ajustar longitudes distintas a la misma disposición de bits
  • En lugar de reducir bifurcaciones y bucles, implementa un parser de alto rendimiento aprovechando al máximo las propiedades de los códigos ASCII, el complemento a dos, las máscaras de bits y la naturaleza de desplazamientos y sumas de la multiplicación

El parsing de temperaturas que fue el cuello de botella en 1BRC

  • En One Billion Row Challenge (1BRC), parsear muy rápido los valores de temperatura de un archivo CSV se convirtió en el cuello de botella principal
  • Solo con optimizaciones previas, el código Java paralelo idiomático ya había acelerado de 71 segundos a 1,7 segundos
  • El formato de temperatura es simple, pero al parsear 1.000 millones de valores en menos de un segundo, incluso costos pequeños se acumulan mucho
    • Los formatos posibles son -XX.X, -X.X, X.X, XX.X
  • Los primeros participantes usaron Double.parseDouble(), pero luego aparecieron parsers personalizados sin bucles
  • Parte de la solución de Quân Anh Mai, @merykitty, procesaba con una sola lectura de archivo y sin if, y se difundió como un componente casi estándar entre las mejores soluciones de 1BRC
  • El ganador, Thomas Wuerthinger, mencionó explícitamente a Quân Anh como parte del equipo que contribuyó a su solución

Qué hace el código de merykitty

  • El código recibe un long que contiene 8 bytes de entrada CSV y devuelve el valor entero de la temperatura, equivalente a 10 veces la temperatura real
  • La entrada llega desde un archivo CSV con mmap mediante lectura directa de memoria nativa, y esa parte se separa como un tema aparte
  • Las operaciones consisten en 18 instrucciones ALU en un orden fijo
    • Desplazamientos de bits, AND, NOT, XOR
    • Sumas, restas y multiplicaciones
    • Long.numberOfTrailingZeros()
  • numberOfTrailingZeros() usa una instrucción especial de CPU mediante un intrinsic del compilador del JDK
  • Como no usa instrucciones SIMD dedicadas, sino registros e instrucciones comunes de CPU para manejar varios bytes, corresponde a la técnica SWAR
  • El código de ejemplo es una versión levemente modificada del original para facilitar la lectura; el original está en CalculateAverage_merykitty.java

Etapas completas del procesamiento

  • El código parsea la temperatura en el siguiente orden
    • Revisa si el primer carácter es - para detectar si es negativa
    • Si existe el carácter de signo, convierte ese byte en 0
    • Encuentra la posición del punto decimal .
    • Desplaza los bits dentro del long para que los números encajen en la plantilla XY.Z
    • Convierte los caracteres ASCII a valores numéricos reales
    • Multiplica cada dígito por sus pesos 1x, 10x, 100x y los suma
    • Aplica el signo al final
  • Aunque por fuera parece un problema de parsing de alto nivel, cada etapa se implementa solo con operaciones ALU

Paso 1: detectar el signo menos

  • La detección del signo empieza con este código
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
  • Si se cambia el orden para explicarlo, puede verse como ( ~(inputData << 59) ) >> 63
  • Aprovecha la propiedad de ASCII de que el signo menos - tiene el bit 4 en 0, mientras que los caracteres numéricos tienen ese bit en 1
  • Al desplazar la entrada 59 bits a la izquierda, el bit distintivo del primer carácter pasa al bit más significativo
  • Después de invertir los bits con NOT y hacer un desplazamiento aritmético a la derecha de 63 bits, el bit más significativo se propaga por todo el long
  • El resultado, broadcastSign, queda con todos los bits en 1 si hay un signo menos, o con todos los bits en 0 si no lo hay

Paso 2: eliminar el carácter de signo

  • Como la información de si es negativo ya quedó guardada en broadcastSign, se elimina el carácter de signo de los datos de entrada
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
  • Si broadcastSign está lleno de 1, broadcastSign & 0xFF deja solo los 8 bits menos significativos en 1
  • Al aplicar NOT, se crea una máscara donde solo los 8 bits menos significativos son 0
  • Al hacer AND con inputData, se elimina el - del byte menos significativo
  • Si no hay signo menos, broadcastSign es 0, por lo que la máscara queda con todos los bits en 1 y se conservan los bytes numéricos

Paso 3: encontrar la posición del punto decimal

  • La posición del punto decimal se calcula con este código
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
  • El carácter . comparte con el signo menos la propiedad de tener el bit 4 en 0
  • Para revisar solo el bit 4 de las posibles posiciones del punto decimal, se usa la máscara DOT_DETECTOR = 0x10101000
  • En negatedInput, que es la entrada original invertida, el bit correspondiente a la posición del punto decimal queda en 1
  • Long.numberOfTrailingZeros() devuelve la posición de ese bit en 1
  • En el ejemplo -10.8, el punto decimal está en la posición de bit 28, así que dotPos = 28

Paso 4: alinear a una plantilla fija

  • Se desplaza la entrada a la izquierda según la posición del punto decimal para que siempre encaje en la misma plantilla
long alignedToTemplate = withSignRemoved << (28 - dotPos);
  • La plantilla objetivo es la siguiente
0 0 0 Z . Y X 0
  • Aquí, X es la decena, Y es la unidad y Z es el primer decimal
  • 0 no significa el ASCII "0", sino un byte con valor 0
  • Después de eliminar el signo, la entrada puede estar en una de cuatro disposiciones
    • 0 0 0 Z . Y X 0
    • 0 0 0 0 Z . Y 0
    • 0 0 0 0 Z . Y X
    • 0 0 0 0 0 Z . Y
  • -10.8 ya tiene dotPos = 28, por lo que el desplazamiento es 0
  • En -7.7, el punto decimal está en la posición de bit 20, así que se desplaza 8 bits, es decir, un byte a la izquierda, y queda un 0 en el lugar de X

Paso 5: convertir los dígitos ASCII en valores

  • Después de alinear, se dejan solo los valores numéricos de los caracteres ASCII
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
  • Los dígitos ASCII del 0 al 9 van de 0x30 a 0x39 en hexadecimal
  • Si se dejan solo los 4 bits inferiores, el código de carácter se convierte en el valor numérico real
  • Se aplica una máscara que tiene F solo en las posiciones numéricas de la plantilla
0 0 0 Z . Y X 0
000000F000F0F00
  • En el ejemplo -10.8, después de aplicar la máscara solo quedan los valores que representan Z=8, Y=0, X=1

Paso 6: sumar los valores posicionales con una multiplicación mágica

  • El valor absoluto final debe calcularse como 100 * X + 10 * Y + Z
  • Aprovechando que la multiplicación es una combinación de desplazamientos y sumas, el cálculo ponderado de varios dígitos se procesa con una sola multiplicación
  • Si primero pensamos en X + Y + Z, se pueden sumar los valores de digits desplazados a las posiciones de 0, 16 y 24 bits para reunir la suma en cierto tramo de bits
  • Esa combinación de desplazamientos y sumas puede expresarse como la siguiente multiplicación
0x1 + 0x10000 + 0x1000000
  • En la práctica, como cada dígito tiene un peso distinto, MAGIC_MULTIPLIER se construye así
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
  • La fórmula es la siguiente
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
  • 0x3FF es una máscara que separa solo un resultado de 10 bits de ancho
  • 100 * X puede crecer hasta 10 bits y solaparse con bits vecinos, pero gracias a que los dos bits de la derecha de Y * 100 quedan en 0, se asegura el espacio de bits necesario
  • merykitty dejó en esta parte el comentario // That was close :)

Paso 7: aplicar el signo sin bifurcaciones

  • En este punto están el valor absoluto absValue y la información de signo broadcastSign
  • broadcastSign funciona como 0 si es positivo y como -1 si es negativo
  • En complemento a dos, un número negativo se expresa con la siguiente fórmula
-n = NOT(n) + 1
  • XOR puede usarse como un NOT condicional
    • n XOR -1 es NOT(n)
    • n XOR 0 es n
  • El +1 opcional se maneja con -broadcastSign
temperature = (absValue ^ broadcastSign) - broadcastSign;
  • Como resultado, sin usar if, los positivos quedan igual y los negativos se convierten a su valor negativo en complemento a dos

Bonus: calcular la posición inicial de la siguiente fila CSV

  • En la solución completa de 1BRC, también hay que calcular de forma barata el inicio de la siguiente línea CSV
  • Después del punto decimal siempre vienen un dígito decimal y un salto de línea, así que se obtiene el inicio de la siguiente fila a partir de la posición del punto decimal
  • Como dotPos es una posición en bits, se usa un desplazamiento de 3 bits a la derecha para dividir por 8
nextLineStart = (dotPos >>> 3) + 3;
  • El +3 es el valor necesario para apuntar al primer byte después del punto decimal, el dígito decimal y el salto de línea

Conclusión

  • El código SWAR de merykitty parsea de forma unificada cuatro formatos de cadenas de temperatura usando solo operaciones de bits fijas
  • Las claves son las propiedades de bits de los códigos ASCII, la alineación basada en la posición del punto decimal, la extracción de dígitos con máscaras, la suma de valores posicionales mediante multiplicación y la aplicación del signo con complemento a dos
  • Separado por etapas, su funcionamiento se puede seguir, pero sigue siendo impresionante que se haya combinado todo esto en unos pocos días durante un desafío online

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-03-11
Opiniones en Hacker News
  • La explicación paso a paso es realmente excelente
    Hace más de 2 años descubrí que byte array view var handle es bastante adecuado para crear rutinas SWAR eficientes en Java/Scala
    También hay muchos ejemplos de uso de SWAR aquí, como parseo de cadenas Base16/64, java.time.*, parseo de valores numéricos directamente desde arreglos de bytes: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...
  • El artículo es bueno y, en el contexto del código, la solución es excelente, pero este enfoque asume que los datos tienen el formato correcto
    Gran parte del valor de un parser curtido en producción está en la verificación y recuperación de errores eficientes
    • Sería interesante desglosar cómo una entrada inválida podría afectar la salida
      Y también me da curiosidad cuánto trabajo haría falta para detectarla y devolver algún valor centinela de error, al estilo del código actual
      Aunque no lo suficiente como para intentarlo yo mismo ;-)
  • La técnica de multiplicar cada dígito de un bitfield numérico por la potencia de 10 correspondiente y usar MUL para hacer desplazamientos/sumas es bastante conocida
    Ver el artículo de Lemire: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
  • Según el artículo, SWAR significa SIMD Within A Register
  • Si te gusta este tipo de contenido, el paper de simdjson usa técnicas parecidas, está muy bien escrito y tiene buenos ejemplos
    Paper: https://arxiv.org/abs/1902.08318
    Github: https://github.com/simdjson/simdjson
    • Esto no es SWAR, pero entiendo por qué resultaría interesante
  • ¿Alguien puede explicar por qué BRC no queda limitado por el cuello de botella de entrada/salida? No entiendo por qué el CPU sería el cuello de botella
    • En sistemas modernos, la E/S de disco local ya no es el cuello de botella: https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/
      Además, el 1BRC oficial especifica que evalúa los resultados desde un disco RAM para excluir por completo la velocidad de E/S: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
      “Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
    • Como contexto, hay una entrevista con Daniel Lemire. Es alguien que construyó toda su carrera sobre la observación de que la E/S no siempre es el cuello de botella: https://corecursive.com/frontiers-of-performance-with-daniel...
    • No he mirado este problema en detalle, pero se puede empezar por el lado contrario. ¿Por qué piensas que la E/S de memoria es el cuello de botella?
      Según mi comprensión limitada, se trae un archivo de texto grande de forma secuencial a L1 y se lee una vez por cada valor. En la mayoría de los procesadores se pueden hacer dos de esas lecturas por ciclo. La parte lenta sería traerlo de la RAM a L1, pero la lectura secuencial es bastante rápida
      Luego se procesa cada lectura. A primera vista, en una versión optimizada eso parecería tomar alrededor de 4 ciclos. Después hay que escribir el resultado en algún lado, y probablemente antes de eso haga falta una o dos lecturas aleatorias. ¿Esa es la parte que ves como cuello de botella de E/S?
      No digo que sea obvio que esté limitado por CPU, pero tampoco parece obvio que no lo esté
      Edición: no consideré que tal vez te referías a “E/S de disco”. Como dijeron otros, aquí prácticamente no es un factor
    • Las pruebas se ejecutan con memfs. El archivo y todo lo demás están en RAM desde el inicio
    • El dataset es lo bastante pequeño como para caber en la page cache del kernel de Linux, y el benchmark se repite 5 veces seguidas, así que la primera iteración podría estar limitada por E/S de disco, pero las otras 4 no
      Es decir, todos los datos quedan en RAM; más precisamente, en la page cache
  • En el 68000 solíamos usar SWAR con bastante eficacia. Con una sola instrucción se procesaban 4 bytes en paralelo
    Si no recuerdo mal, manejar el overflow era complicado. Este artículo me gustó mucho
  • Se dijo: “El verdadero misterio es que una sola persona trabajando sola haya creado todo esto mientras hacía por unos días, de manera casual, un reto online cuya recompensa era una camiseta y una taza de café”. ¿Por qué sería un misterio?
    Todavía hay gente que sabe programar realmente el CPU y entiende lo que está haciendo
    El verdadero misterio es que la gran mayoría de quienes se llaman programadores carecen de una comprensión profunda, e incluso parecen no saber que tienen una carencia grave
  • En C# no hace falta usar estos trucos SWAR. En su lugar, ofrece una API SIMD multiplataforma de primera clase
    Que de hecho funciona bien se puede comprobar en la solución en C# que, hasta donde se ha publicado, parece ser la más rápida de 1BRC: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
  • ¿Esto se puede vectorizar con SSE? Parece que la mayor parte del procesamiento central podría hacerse con vectores de 4 enteros de 32 bits
    El problema es si el costo de construir el vector inicial y extraer los resultados no sería excesivo
    • Sí se puede, y varias otras implementaciones de 1BRC lo hicieron así
      Aunque dudo que HotSpot lo logre por sí solo, y aparte está el hecho de que la mayoría de los envíos de 1BRC se ejecutaron con Graal para reducir el overhead de arranque
      SSE2 básico no tiene multiplicación de 32 ni de 64 bits, así que la multiplicación 32×32→64 bits es un problema, pero SSE4.1 agrega exactamente el pmuldq que se necesita. Eso sí, como el resultado es de 64 bits, para procesar un vector completo de enteros de 32 bits harían falta dos operaciones de este tipo
    • Como el campo de temperatura está mezclado con el campo de nombre, parece difícil obtener beneficios adicionales con SSE
      Además, el campo de temperatura tiene longitud variable, así que incluso si estuviera almacenado por columnas, es posible que no hubiera ganancia
      Sin embargo, SSE sí se aplicó con éxito para encontrar el separador entre el nombre y la temperatura
    • Este tipo de código probablemente se autovectorice, ya sea desde el principio o después de que HotSpot detecte el hotspot