La función `tolower()` implementada con AVX-512

 (dotat.at)
1 puntos por GN⁺ 2024-07-30 | 1 comentarios | Compartir por WhatsApp
  • Es un experimento para extraer rendimiento SIMD incluso en cadenas pequeñas, procesando 64 bytes por vez con AVX-512-BW mientras copia la cadena y convierte mayúsculas ASCII a minúsculas
  • La clave de la implementación es comparar cada byte para verificar si está entre 'A' y 'Z', y luego aplicar una operación enmascarada que suma 'a' - 'A' solo en esas posiciones
  • Los fragmentos restantes de cadenas cortas y el final de las cadenas largas se procesan con load/store enmascarados, reduciendo el costo habitual de manejar trozos pequeños en código SIMD
  • En mediciones de una copia de aproximadamente 1MiB en fragmentos de 1 byte a 1KiB con Clang 16, Debian 11 y AMD Ryzen 9 7950X, tolower64 se mantuvo de forma consistente entre las implementaciones más rápidas comparadas
  • En Zen 4, AVX-512-BW mostró encajar bien para el procesamiento de cadenas, aunque no se pudo verificar en detalle directamente ARM SVE ni la extensión Vector de RISC-V

Crear un tolower() de 64 bytes con AVX-512-BW

  • El objetivo es implementar con SIMD un kernel tolower() que copie una cadena mientras convierte a minúsculas los caracteres ASCII en mayúscula
  • AVX-512-BW es una extensión que soporta operaciones a nivel de byte y palabra, y hoy puede usarse en procesadores AMD Zen recientes
    • AVX-512 está dividido en varias extensiones, por lo que la compatibilidad es compleja
    • Se considera que el soporte del lado de Intel es especialmente inconsistente
  • ARM SVE también ofrece load/store enmascarados a nivel de byte adecuados para procesamiento de cadenas
    • Está disponible en núcleos big-ARM Neoverse recientes, por ejemplo en Amazon Graviton
    • No puede usarse en Apple Silicon
  • La extensión Vector de RISC-V también sigue un estilo similar al de ARM SVE, y puede encontrarse en varias computadoras single-board pequeñas

Cómo funciona tolower64()

  • tolower64() es un kernel basado en AVX-512 que procesa 64 bytes a la vez
  • Primero se cargan valores de referencia en registros vectoriales para 64 bytes
    • 'A'
    • 'Z'
    • 'a' - 'A'
  • Luego se compara el vector de caracteres de entrada c con 'A' y 'Z' para generar dos máscaras de 64 bits
    • posiciones donde c >= 'A'
    • posiciones donde c <= 'Z'
  • Ambas máscaras se combinan con _kand_mask64() para crear la máscara is_upper, que marca solo las posiciones de mayúsculas
  • Por último se aplica _mm512_mask_add_epi8()
    • los bytes donde is_upper es false conservan el valor original c
    • los bytes donde is_upper es true pasan a ser c + ('a' - 'A')

Manejo de cadenas largas y cortas

  • La mayor parte de las cadenas largas se procesa con load/store vectoriales desalineados normales
    • _mm512_loadu_epi8()
    • tolower64()
    • _mm512_storeu_epi8()
  • Para las cadenas cortas y el fragmento final restante de las cadenas largas se usan load/store desalineados enmascarados
  • La máscara se construye activando solo los len bits bajos
    • uint64_t len_bits = (~0ULL) >> (64 - len)
    • se carga en un registro de máscara SIMD con _cvtu64_mask64(len_bits)
  • _mm512_maskz_loadu_epi8() rellena con 0 las posiciones del registro destino donde la máscara está desactivada
  • _mm512_mask_storeu_epi8() solo almacena las posiciones donde la máscara está activada
  • Este enfoque es clave para procesar rápido los fragmentos pequeños de cadenas

Condiciones del benchmark y comparativas

  • El benchmark se ejecutó con Clang 16, Debian 11 y AMD Ryzen 9 7950X
  • Lo medido fue una copia de aproximadamente 1MiB, variando la longitud de los fragmentos desde 1 byte hasta 1KiB
  • Para reflejar diferencias de alineación entre la cadena fuente y la destino, se dejaron algunos bytes entre ambas cadenas, y esos bytes no se incluyeron en la cantidad medida de 1MiB
  • Como la caché L2 del Ryzen 9 7950X es de 1MiB por núcleo, se espera que cada ejecución de prueba llegue hasta la caché L3
  • Cada función se compiló por separado para evitar interferencias por inlining y movimiento de código
    • en código real, es más probable que se prefiera fomentar el inlining en lugar de impedirlo

Resultados: el rendimiento fluido de tolower64

  • El tolower64 rosa se mantiene en general muy cerca del grupo más rápido entre las funciones probadas
    • cae un poco al pasar al segundo vector cuando la longitud llega a 65 bytes
    • sube rápido y no presenta valles profundos de rendimiento, mostrando que los load/store enmascarados son efectivos para manejar fragmentos cortos de cadenas
  • El copybytes64 verde es una versión de memcpy que usa AVX-512 de forma similar
    • no es mucho más rápido que tolower64
    • como las versiones recientes de Clang reconocen el significado de esta función y la reescriben por completo, se compiló con Clang 11
  • El copybytes1 naranja es una versión de memcpy por bytes
    • se compiló con Clang 11
    • muestra que las heurísticas de autovectorización de Clang 11 son relativamente pobres para fragmentos de cadena menores de 256 bytes
  • El tolower rojo es la línea base que llama al tolower() estándar de <ctype.h>, y es muy lento
  • El tolower1 morado es un tolower() por bytes compilado con Clang 16
    • la autovectorización de Clang 16 mejoró mucho frente a Clang 11
    • sigue siendo más lento que la versión escrita a mano y genera código mucho más complejo
    • el manejo de fragmentos cortos de cadena no es tan bueno como en tolower64, por lo que la gráfica de rendimiento oscila con picos marcados
  • El tolower8 café es el tolower() SWAR de una entrada anterior
    • Clang intenta autovectorizarlo, pero como la función es compleja, el resultado no es bueno
    • aunque se compiló con Clang 16, aparece el mismo precipicio de rendimiento alrededor de 256 bytes típico del estilo de Clang 11
  • El memcpy azul llama al memcpy de glibc
    • al principio es rápido, pero hay una zona donde cae a aproximadamente la mitad de la velocidad de copybytes64
    • no se pudo determinar la causa

Conclusiones y código

  • AVX-512-BW es muy adecuado para manejar cadenas, en especial cadenas cortas
  • En Zen 4 es muy rápido, y las funciones intrínsecas son relativamente fáciles de usar
  • La característica más llamativa es su rendimiento fluido
    • casi no aparecen los valles de rendimiento que suelen surgir cuando la autovectorización cambia a código escalar en fragmentos pequeños de cadenas
  • No fue posible acceder fácilmente a equipos con soporte de ARM SVE o de la extensión Vector de RISC-V, por lo que no se investigaron esas dos extensiones en detalle
  • El código puede verse en el repositorio git del sitio web

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-07-30
Opiniones de Hacker News

  • El truco de “unsafe read beyond of death” se considera comportamiento indefinido en los modelos de memoria de Rust y LLVM, aunque el hardware lo permita.
    Como con otros comportamientos indefinidos, durante la optimización el compilador puede asumir que “eso no ocurre”, lo que puede producir resultados inesperados; para evitarlo habría que usar ensamblador en línea.
    https://github.com/ogxd/gxhash/issues/82

    • Sería bueno tener una opción que no fuera ensamblador para estos casos.
      No parece tan difícil admitir una carga del estilo “los valores fuera del rango asignado se leen como elementos no especificados, y solo es comportamiento indefinido cuando al hardware no le gusta”; incluso bastaría con que internamente fuera un alias de esa llamada en ensamblador.
      Yendo más allá, sería ideal que después de toda asignación —malloc, pila, constantes, etc.— se garantizara al menos algo así como 64 bytes de direcciones sin fault, pero eso es mucho más complejo porque requiere la cooperación de varios componentes.
      Con un asignador personalizado es trivial, pero en ese caso es difícil usar código SIMD con datos fuera del heap personalizado y uno queda atado a una probabilidad diminuta de segfault.
      Los sanitizers o Valgrind seguirían siendo útiles, porque podrían rastrear los valores fuera de rango como valores indeterminados y emitir errores cuando se usen realmente.
    • Incluso a nivel de hardware, dudo que eso sea realmente cierto.
      Me pregunto qué pasa si se lee desde una página no mapeada o memoria protegida, y como no vi el código no sé si las garantías de alineación evitan eso.
    • La explicación de que “si es comportamiento indefinido, el compilador puede asumir que eso no ocurre” es incorrecta.
      Comportamiento indefinido es un término técnico del estándar C, así que generalizarlo de por sí es raro; ANSI C no permite explícitamente esa suposición, e ISO C, aunque es más abierto, tampoco justifica concretamente esa suposición.
      Considero que explicarlo como “UB = asumir que no puede ocurrir” se acerca bastante a una táctica de miedo deshonesta.

  • Al ver el código prolijo y de buen rendimiento del artículo, me da curiosidad cómo competirán la implementación de AVX512 de AMD y el próximo AVX10 de Intel.
    El punto central de AVX10 parece estar en resolver la situación de los núcleos P/E de Intel, mientras que AMD parece haber elegido un mejor enfoque: usar, según el caso, la implementación de ancho completo de Zen5 o el procesamiento en dos pasadas de 256 bits de Zen4 y Zen5 móvil, manteniendo la API fluida.
    Todas las grandes mejoras de rendimiento del artículo también provienen de núcleos Zen4, y como AVX512 tiene muchas ventajas, es frustrante que Intel lo haya limitado tanto por segmentación de mercado que en la práctica impidió su adopción en código de cliente de propósito general.

    • Si Intel realmente incluye AVX10/256 en todos los CPU que lance de aquí en adelante, terminará ganando por disponibilidad.
      El mercado ha rechazado una y otra vez ramificar rutas de código por CPU, y en la práctica las implementaciones SIMD importantes apuntan al mínimo común denominador.
      AVX10.1/256 y AVX512VL tienen un subconjunto común, así que cuando pase suficiente tiempo y la mayoría de los CPU lo soporten, la gente apuntará a esa parte.
      AMD seguirá consiguiendo victorias fáciles en algunas apps de benchmark actualizadas para soportar AVX512, pero si Intel mantiene su plan de AVX10, es probable que AMD también termine usando de forma generalizada pipelines SIMD de dos pasadas para soportar AVX10/256 eficientemente mientras conserva la compatibilidad con AVX512.
      Intel tomó muchas malas decisiones en la última década, pero fragmentar el mercado con el conjunto de instrucciones fue una de las peores. Mató por su propia cuenta el impulso y el interés por sus innovaciones más recientes, y como funciones como las operaciones con máscaras son mucho más importantes que el ancho en sí, espero que ponga AVX10/256 en toda su línea.
    • La implementación de AVX512 de Zen 4 no es double-pumped, y los periodistas de tecnología deberían dejar de llamarla así.
      Esa expresión tiene un significado específico y no coincide con el funcionamiento real.
      Zen 4 simplemente decodifica las operaciones sobre registros ZMM en varias microoperaciones y las agenda en unidades de 256 bits libres; los shuffles de ancho completo de 512 bits se manejan de forma especial con hardware dedicado para evitar una emulación costosa.
      Por eso, aunque Zen 4 tiene cuatro unidades SIMD de 256 bits, se comporta como un potente núcleo de 2×512 bits; esta implementación no es en absoluto una forma barata y probablemente sea la mejor que se haya visto hasta ahora en hardware de consumo.
    • No entiendo por qué Intel no resuelve esto poniendo AVX512 de dos pasadas en los núcleos E. O, si no, que fabrique CPU de escritorio solo con núcleos P, como debería haber sido desde el principio.
      Ya tuvo varios años para arreglarlo, y molesta que aunque AMD lo soporte, la adopción no avance por la cuota de mercado; lamentablemente, AVX10 parece que permitirá que Intel mantenga al mundo frenado por más tiempo.
      En escritorio quiero ver mejores núcleos, más núcleos y un conjunto de instrucciones bien estandarizado que habilite funciones útiles como SIMD ancho, float16 y gather/scatter; AMD lo está haciendo bastante bien.
      En cambio, Intel pone núcleos débiles junto a núcleos decentes, limita los núcleos decentes para ajustarlos a los débiles, lanza CPU con la misma cantidad de núcleos durante varias generaciones, usa núcleos débiles para aparentar tener muchos núcleos, saca demasiadas variantes de instrucciones como para que sea difícil que surja un conjunto común útil, y abandona incluso el soporte de instrucciones que parecía haber prometido.
      Mi preferencia de fabricantes de escritorio fue Intel en los 90, AMD a comienzos de los 2000, Intel a fines de los 2000 y en los 2010, y ahora nuevamente AMD. Me pregunto qué hará Intel, además de obstaculizar a su rival, para recuperar base; y la competencia debe continuar para que ninguna de las partes se acomode demasiado.

  • Material interesante para ver por diversión: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

    • También existe esto: si se convierte la ß alemana a mayúsculas, cambia la longitud de la cadena
      Por ejemplo, "straße".upper() se convierte en 'STRASSE'
      Además, si no se especifica la configuración regional, al convertir ida y vuelta a mayúsculas/minúsculas la i sin punto de las lenguas túrquicas, 'ı'.upper().lower() se convierte en 'i' y se rompe
    • Por suerte, como este código surgió de trabajo con DNS, es solo ASCII, así que no hace falta lidiar con esa complejidad
      Hay varios protocolos ASCII que no distinguen mayúsculas y minúsculas, y aparecen a menudo en las rutas calientes de muchos servidores
    • Las cadenas que se usan internamente como IDs son distintas del texto ingresado por personas
      Para las primeras, normalmente basta con ASCII puro en una codificación de 8 bits, pero lo segundo se vuelve complejo
      Una dirección DNS es un ejemplo sencillo: técnicamente puede contener casi cualquier Unicode, pero para la resolución DNS real se transforma en un subconjunto muy limitado de ASCII, y ese proceso de resolución no distingue mayúsculas y minúsculas
      Por supuesto, también hay cosas como lenguajes de programación que admiten todos los sistemas de escritura de Unicode y cuyos identificadores no distinguen mayúsculas y minúsculas. Si estás lidiando con algo así, mis condolencias
    • En relación con el ejemplo en que el alemán maße se convierte en MASSE, en alemán también existe la Eszett mayúscula, ẞ
      Todavía no está ampliamente distribuida y hay pocas fuentes que la soporten, pero en teoría ya existe

  • Me da la impresión de que la explicación de “suma con máscara” del artículo está equivocada
    Me pregunto si no debería sumar cuando is_upper es false y copiar tal cual cuando es true

    • Ah, me di cuenta tarde de que el nombre de la variable to_upper está al revés y debería llamarse to_lower
      Gracias por señalar la parte confusa; corregí el artículo y el código
    • Esta operación es tolower
      La A mayúscula es 0x40 y la minúscula es 0x60, así que sumar 0x20 debe ocurrir cuando is_upper es true

  • Estas optimizaciones SWAR muchas veces solo son útiles cuando la cadena está alineada a una dirección de 8 bytes
    Si se aplica un algoritmo SWAR a una cadena no alineada, es común que termine siendo más lento que el algoritmo original
    Si se divide en tres etapas —procesar el inicio hasta una dirección alineada, procesar el cuerpo alineado y procesar la cola de menos de 8 bytes— aumentan las instrucciones
    Aquí hay un caso parecido a la afirmación incorrecta de que utf8.IsValid es más rápido en Go, junto con benchmarks: https://github.com/sugawarayuuta/charcoal/pull/1

    • Las operaciones SIMD con máscara de AVX-512 y ARM SVE surgieron para resolver ese problema
      Las operaciones de memoria siempre están alineadas y usan el tamaño completo del vector, pero se puede aplicar una máscara solo a los elementos válidos
      Incluso si una operación de memoria vectorial con máscara no está alineada y cruza una página no mapeada o protegida, si ese lane está desactivado por la máscara, no se produce un fault
      Para operaciones como strlen(), donde no se conoce la longitud de antemano, también hay instrucciones especiales de carga que reducen la longitud del vector justo antes del primer elemento que provocaría un fault

  • La suma con máscara se ve genial. Sería bueno poder manipular directamente los registros de máscara de AVX512 desde los intrinsics de .NET, pero por ahora hay que depender de “modismos reconocidos”.
    Si se analiza el bucle central del autor generado por GCC con uiCA (CQA/MAQAO) tomando Ice Lake como referencia, da alrededor de 32 B/ciclo; convertido a 3 GHz, serían casi 96 GiB/s suponiendo que no haya cuello de botella de memoria. Claro que, en algoritmos como este, el acceso a memoria siempre es el cuello de botella.
    Aun así, no parece estar tan cerca del uso óptimo, y con Clang se llega hasta 42.67 B/ciclo gracias a un desenrollado mejor resuelto y una mejor selección de instrucciones. Tampoco creo que la caché L2 pueda sostener ese throughput, pero es interesante que la conversión de mayúsculas/minúsculas de cadenas de longitud media termine más o menos en el tiempo que tarda la luz de la pantalla en llegar a la córnea.
    Hace unos meses implementé en C# una conversión similar de mayúsculas/minúsculas ASCII dentro de UTF-8: https://github.com/U8String/U8String/blob/main/Sources/U8Str...
    Como las cadenas cortas dominan la mayoría de los codebases, la conversión desenrollada para longitudes menores que el tamaño de vector es importante, y el switch se compila como una tabla de saltos con fall-through sin ramas.
    Por ahora solo uso hasta 256 bits, porque en casos como Zen 3 o 4, que solo tienen unidades SIMD 256×4, eso ya las satura. Aquí hay un ejemplo comparado lado a lado con una versión en C: https://godbolt.org/z/eTGYhTPan
    En AVX512 parece que también sería posible hacer la conversión de 3 instrucciones con vpternlogd, y cuando podía usar hardware AVX512, .NET lo optimizaba así con ancho de 256 bits + AVX512VL, pero ahora, curiosamente, no logro reproducirlo con ancho de 512 bits.
    También se verá un intento fallido de SWAR en el dispatch del switch; me interesa saber la licencia del artículo. Si pasa el test suite, me gustaría usarlo.

    • Clang y GCC tienen formas distintas de manejar los intrinsics, y en particular con instrucciones AVX-512 Clang es más propenso que GCC a desviarse del opcode y el algoritmo especificados en la guía de Intel.
      Viendo la estructura de ambos compiladores se entiende, pero a veces el resultado mejora y otras veces perjudica.
      Hace unos años trabajé en un proyecto muy vectorizado que tenía que compilarse con ambos, y terminé manteniendo en el repositorio ensamblador inline específico para ciertos targets y archivos .S, junto con una versión de referencia en C.
      El Makefile se volvió un desastre y hubo que meter benchmarks en el test suite, así que la carga de mantenimiento fue alta; por eso llegué a la conclusión de que hay que ser muy cuidadoso al usar intrinsics como una herramienta de bajo nivel mejor que la autovectorización.
      Ejemplo: en https://godbolt.org/z/T4Pjhrz5d, la salida de GCC fue la esperada, pero la de Clang fue sorprendente y en la práctica más lenta. Si se ejecuta en bucle, según uiCA son 7 ciclos frente a 4 de GCC, y también se notó en un benchmark de una app real donde esta función se ejecutaba miles de millones de veces dentro de un algoritmo de fuerza bruta.
      Recuerdo que, al mirar el codebase de LLVM, también vi un problema por el que Clang 16 quizá ni siquiera emitía algunas instrucciones AVX-512 con máscara debido a una refactorización interna.
    • El análisis es muy útil.
      No apuntaba al máximo rendimiento posible; al principio solo quería ver si funcionaba, y fue un bonus que el primer intento saliera bastante bien.
      Mi interés principal son las cadenas más cortas que un registro vectorial y eliminar los valles en la gráfica de throughput.
      Si sigues el enlace al código al final del post del blog, ahí está la información de licencia; salvo la parte MPL-2.0 escrita originalmente para BIND, es 0BSD o MIT-0.
    • Aunque no se ve tan claro mirando un gran bloque de ensamblador, Clang reescribe (x >= 'a' && x <= 'z') en la forma (x - 'a') < ... y se ahorra una instrucción.
      Por alguna codificación rara de opcode, a veces incluso se reduce una carga de registro.

  • No sé qué es swar.

    • Es la sigla de “SIMD Within A Register”.
      Normalmente se refiere a una técnica en la que se empaquetan varios elementos dentro de un solo registro y se usa, en la práctica, como SIMD aun sin instrucciones SIMD explícitas.
      Por ejemplo, si metes un número de 31 bits y uno de 32 bits en un registro de 64 bits y dejas 1 bit para el carry, puedes hacer dos sumas con una sola suma de 64 bits.
      En juegos se han usado trucos así para gráficos, empaquetando valores RGB(A) en enteros de 32 bits, y ScummVM también tiene código que interpola 2 píxeles RGB de 16 bits dentro de un valor de 32 bits, 6 componentes en total: https://github.com/scummvm/scummvm/blob/master/graphics/scal...
    • Significa SIMD dentro de un registro.

  • Desde que apareció Unicode, el concepto de mayúsculas y minúsculas se volvió un pantano.
    Para hacerlo bien se necesitan muchos datos.
    Si estás trabajando en algo cuyo éxito depende de que ASCII tolower se ejecute a tiempo, probablemente conviene cambiar el tablero de juego y modificar las precondiciones.

  • Una vez evité por completo el problema de las lecturas más allá del buffer en SIMD poniendo un borde negro alrededor de la imagen.
    Funcionó muy bien y, en velocidad, pude superar algunas implementaciones de OpenCV, pero no siempre se tiene un control tan completo de la entrada.

  • Me pregunto si lo han probado de esta forma. El resultado de la autovectorización se ve bastante limpio.
    https://godbolt.org/z/1c5joKK5n

    • Eso es básicamente lo mismo que tolower1. Mira los bullets debajo de la gráfica.