La función `tolower()` usando AVX-512

• Hace algunos años escribí sobre cómo acelerar tolower() usando trucos de SWAR. Hace unos días, un artículo de Olivier Giniaux me llamó la atención por una optimización para procesar cadenas pequeñas usando instrucciones SIMD. Este método se usa en una función hash rápida escrita en Rust.

• Las instrucciones SIMD permiten procesar cadenas cortas con facilidad, pero siempre me resultó incómodo que la transferencia entre memoria y registros vectoriales fuera complicada. El artículo de Olivier presentó una forma interesante de resolver este problema.

Señales de esperanza

• Algunos conjuntos de instrucciones SIMD ofrecen útiles funciones de carga y almacenamiento con máscara para procesar cadenas. Funcionan a nivel de byte.

  • ARM SVE: disponible en núcleos ARM Neoverse recientes, por ejemplo Amazon Graviton. Sin embargo, no está disponible en Apple Silicon.
  • AVX-512-BW: disponible en procesadores AMD Zen recientes. AVX-512 es un conjunto de extensiones complejo, y en Intel su soporte es bastante irregular.

• Como tengo una máquina con AMD Zen 4, decidí probar AVX-512-BW.

tolower64()

• Usando la guía de intrinsics de Intel, escribí una función básica tolower() capaz de procesar 64 bytes a la vez.
  • Usé * como comodín para buscar mm512*epi8 y encontrar funciones AVX-512 orientadas a bytes.
  • Llené algunos registros con 64 bytes útiles.
  • Configuré los valores necesarios para convertir mayúsculas en minúsculas.
  • Comparé los caracteres de entrada con A y Z para verificar si eran mayúsculas.
  • Usé una máscara para convertirlos a minúsculas cuando correspondía.

Cargas y almacenamientos masivos

• Había que envolver el kernel tolower64() en una función más práctica. Por ejemplo, una función que copie una cadena mientras la convierte a minúsculas.
  • Para cadenas largas, se usan instrucciones de carga y almacenamiento vectorial no alineadas.

Carga y almacenamiento con máscara

• Para cadenas pequeñas y el tramo final de cadenas largas, se usan cargas y almacenamientos no alineados con máscara.
  • La máscara tiene activados los primeros len bits.
  • Las cargas y almacenamientos son similares a las versiones de ancho completo, pero con la máscara añadida.

Benchmarks

• Se midió el rendimiento de varias funciones similares.

  • Compiladas con Clang 16 y ejecutadas en un AMD Ryzen 9 7950X.
  • Cada función se compiló por separado para evitar interferencias por inlining y movimiento de código.

• Resultados:

  • tolower64 es la más rápida de todas las funciones probadas.
  • copybytes64 usa AVX-512 de forma similar a tolower64, pero no resulta mucho más rápida.
  • copybytes1 hace memcpy byte por byte, mostrando que la autovectorización de Clang 11 es relativamente pobre.
  • La tolower() estándar es la más lenta.
  • tolower1 es una tolower() byte por byte compilada con Clang 16; la autovectorización mejoró, pero sigue siendo lenta.
  • tolower8 es la tolower() SWAR presentada en una entrada anterior del blog; Clang intenta autovectorizarla, pero el resultado no es bueno.
  • memcpy al principio es rápida, pero cae hasta la mitad de la velocidad de copybytes64.

Conclusión

• AVX-512-BW es muy útil, especialmente al procesar cadenas cortas.

• Es muy rápido en Zen 4, y las funciones intrínsecas son fáciles de usar.

• El rendimiento de AVX-512-BW es muy uniforme.

• No pude investigarlo en detalle porque no tengo una máquina con soporte para ARM SVE, pero me da curiosidad qué tan bien funciona SVE con cadenas cortas.

• Ojalá estas extensiones de conjuntos de instrucciones se adopten más ampliamente. Podrían mejorar mucho el rendimiento del procesamiento de cadenas.

• El código de esta entrada del blog está disponible en mi sitio web.

Resumen de GN⁺

• Este artículo explica cómo procesar cadenas cortas de forma eficiente usando instrucciones SIMD.
• Muestra que los conjuntos de instrucciones AVX-512-BW y ARM SVE son útiles para el procesamiento de cadenas.
• Según los benchmarks, AVX-512-BW ofrece un rendimiento sobresaliente, especialmente con cadenas cortas.
• El artículo será útil para desarrolladores interesados en la optimización de rendimiento.

[GN⁺]

Comentarios de Hacker News

• En el modelo de memoria de Rust y LLVM, el truco de "unsafe read beyond of death" se considera comportamiento indefinido

  • El compilador puede asumir, para fines de optimización, que ese comportamiento no ocurre
  • Para evitarlo, hay que usar ensamblador en línea

• Surge curiosidad sobre la implementación de AVX512 de AMD y la competencia con AVX10 de Intel

  • AVX10 existe para resolver el problema de los núcleos P vs E de Intel
  • AMD usa, según el caso, el ancho completo de Zen5 o el doble bombeo de 256 bits en Zen4 y Zen5 Mobile
  • Las grandes mejoras de rendimiento se dan en los núcleos Zen4

• La optimización SWAR solo es útil para cadenas alineadas a direcciones de 8 bytes

  • Si se aplica a cadenas no alineadas, es más lenta que el algoritmo original
  • Si se divide el algoritmo en tres partes, se necesitan más instrucciones

• La adición de máscaras se ve elegante

  • Ojalá hubiera una forma, en las funciones integradas de .NET, de manipular directamente los registros de máscara de AVX512

• Con Clang se pueden obtener mejores resultados

  • Ofrece una mejor selección de instrucciones y un resultado mejor resuelto

• El bucle principal para cadenas cortas tiene una instrucción menos

  • Es importante procesar rápido las cadenas cortas

• Se escribió en C# una implementación similar para convertir mayúsculas/minúsculas de ASCII a UTF-8

  • Como las cadenas cortas dominan la mayoría de los codebases, es importante procesarlas rápido

• Hay un ejemplo de uso de SIMD para convertir texto a uwu usando AVX512

• Sería más impresionante si se considerara la conversión de caracteres Unicode

  • A la mayoría de los programadores solo les importa ASCII, pero existe todo un mundo más allá del conjunto de caracteres estándar

• En el pasado hubo experiencia agregando bordes negros alrededor de imágenes para evitar problemas de búfer con SIMD

  • No siempre se puede controlar por completo la entrada