Algoritmos SIMD diseñados desde cero

 (mcyoung.xyz)
2 puntos por GN⁺ 2023-11-29 | 1 comentarios | Compartir por WhatsApp
  • El códec base64 vb64 hecho con std::simd de Rust logra código SIMD rápido y portable no tanto vectorizando tal cual un bucle procedural, sino rediseñando la disposición de los datos y el flujo de operaciones como si fuera un circuito
  • La optimización clave consiste en reducir los stalls causados por ramas y accesos a memoria, creando una estructura branchless que ejecuta las mismas operaciones sin importar la entrada mediante comparación, máscara, select y shuffle
  • En la decodificación base64, para convertir caracteres ASCII en sextetos se construye un perfect hash usando byte >> 4 y una corrección para /, y se buscan offsets con una lookup table dentro del vector SIMD y shuffle
  • Al empaquetar cuatro sextetos de 6 bits en tres bytes, se amplían los lane a u16, se hace shift, luego se separan los bytes low/high y se combinan fragmentos de bytes de lanes adyacentes con rotate_lanes_left y OR
  • En los benchmarks, con la combinación -Zbuild-std, -Ctarget-cpu=native y N = 32, más una optimización de carga del remainder, mostró casi el doble de rendimiento frente a la implementación base64 baseline de crates.io en casi todo el rango

Contexto físico que hace necesario SIMD

  • La mejora del rendimiento de las computadoras no está conectada solo con la CS teórica, sino directamente con limitaciones físicas
  • La ley de Moore parece seguir vigente todavía en 2023, pero en los últimos 15 años se derrumbó el efecto de Dennard scaling, por lo que transistores más densos terminan aumentando la densidad de consumo eléctrico
  • Después de que se volvió difícil seguir subiendo la frecuencia de reloj, desde comienzos de los 2000 la dirección principal de mejora del rendimiento pasó a usar más núcleos
  • El multithreading requiere cooperación entre núcleos, lo que introduce costos de sincronización, y los flujos de control como saltos, llamadas virtuales y sincronización provocan stalls
  • Hay dos causas principales de stall
    • Ramas: flujos de control como if, bucles, llamadas a funciones, retornos de función y switch de C
    • Operaciones de memoria: load/store, en especial accesos poco amigables con la caché

Código procedural y paralelismo a nivel de instrucciones

  • Los núcleos modernos de CPU no ejecutan el código línea por línea, sino que emiten al mismo tiempo operaciones que no dependen unas de otras
  • Operaciones independientes entre sí, como a = x + y y b = x ^ y, pueden usar al mismo tiempo los circuitos de add y xor
  • A esto se le llama paralelismo a nivel de instrucciones, y las dependencias que lo obstaculizan se conocen como data hazards
  • Cuanto mejor logra la CPU saturar sus functional units, más operaciones procesa por unidad de tiempo
  • Las ramas generan stalls porque hay que esperar el cálculo de la condición antes de traer la siguiente instrucción, y las operaciones de memoria también porque los datos deben llegar físicamente hasta la CPU
  • Como la GPU trata imágenes como vectores de píxeles y realiza muchas operaciones con alta localidad, se parece más a una máquina SIMD diseñada para procesamiento por lotes y flujo de control limitado
  • SIMD significa single instruction, multiple data: una sola instrucción ejecuta operaciones en paralelo sobre múltiples lanes de datos

Forma de pensar por lanes

  • SIMD y vector suelen usarse casi con el mismo significado, y la unidad básica de una instrucción SIMD es el vector, un arreglo de números de tamaño fijo
  • Cada componente de un vector se llama lane
  • Como los vectores SIMD deben caber en registros, por lo general son pequeños
    • En el entorno de ejemplo, el ancho máximo del vector es de 256 bits
    • Eso corresponde a 32 bytes de u8x32 o a 4 doubles de f64x8
  • Incluso un vector pequeño puede traducirse en una mejora de latencia si reduce 4 veces la carga necesaria para saturar el pipeline

Divide y vencerás visto con popcnt

  • La operación vectorial más simple es bitwise and/or/xor
  • Incluso un entero normal puede verse, desde la perspectiva de operaciones bitwise, como un vector de lanes de 1 bit
    • i32 es, desde esta perspectiva, lo mismo que i1x32
  • popcnt es la operación de contar cuántos bits en 1 hay dentro de un entero, y si vemos i32 como i1x32, es una operación de reduce
  • Una implementación ingenua que saca los 32 bits como arreglo y los suma puede generar mal código
  • Una mejor forma es sumar pares de bits adyacentes, luego pares de pares, e ir ampliando el ancho de lane durante la suma
    • Separar bits pares/impares con las máscaras 0x55555555 y 0xaaaaaaaa
    • Alinear los lanes con shift y luego sumar
    • Repetir después en unidades de 2, 4, 8 y 16 bits
  • Esta implementación no se optimiza a la instrucción popcnt, pero en sistemas sin esa instrucción produce código pequeño y rápido
  • También puede aplicarse a u64 agregando solo una etapa más de reducción, sin necesidad de una suma completa de u64
  • Este enfoque de divide y vencerás es un patrón central de la programación SIMD

Herramientas principales del conjunto de instrucciones SIMD

  • Los vectores SIMD reales ofrecen una semántica más compleja que los escalares, y las funciones para reemplazar flujo de control lento son especialmente importantes
  • Las instrucciones disponibles dependen mucho de la arquitectura
    • Muchos núcleos x86 de alto rendimiento implementan AVX2
    • AVX2 ofrece vectores ymm de 256 bits
    • El propio registro no tiene una cantidad de lanes; la instrucción define cómo se interpretan
    • Por ejemplo, vpaddb interpreta ymm como i8x32
  • En general, pueden usarse las siguientes operaciones
    • Operaciones bitwise: el ancho de lane siempre está implícitamente fijado en 1 bit
    • Aritmética por lane: suma, resta, multiplicación, división, shift entero, min/max, etc.
    • Comparación por lane: genera un vector máscara como m[i] = a[i] < b[i]
    • select: usa una máscara para elegir, por lane, valores de uno de dos vectores
    • shuffle/swizzle: trata un vector como una lookup table y reordena lanes con un vector de índices
  • Los valores true/false de un vector máscara suelen usar patrones de bits all-ones o all-zeros
  • Comparación y select son herramientas clave para que el código SIMD se mantenga branchless
  • El código branchless ejecuta las mismas operaciones independientemente de la entrada y descarta resultados innecesarios con propiedades como x * 0 = 0 y a ^ b ^ a = b

Alinear la posición de los datos con shuffle

  • shuffle es la herramienta clave en SIMD para llevar los datos a la “posición correcta”
  • broadcast o splat crea un vector donde todos los lanes tienen el mismo escalar, y puede expresarse como un shuffle de índices [0, 0, ...]
  • interleave o zip/pack alterna los lanes de dos vectores a y b
    • c = [a[0], b[0], a[1], b[1], ...]
    • Puede implementarse con shuffle2
  • deinterleave o unzip/unpack es lo contrario de interleave
  • rotate rota los lanes con la forma b[i] = a[(i + j) % n], y eso también es shuffle
  • En programación SIMD es común reinterpretar y reordenar bloques de datos más grandes que un entero en bloques pequeños de distintos tamaños

intrinsics, target feature, portable SIMD

  • Las operaciones disponibles en SIMD varían según la arquitectura y la extensión del conjunto de instrucciones
  • En x86 puede haber operaciones que no existen en ARM, y hasta dentro del mismo fabricante hay extensiones, como Intel AVX-512, que solo están disponibles en chips de servidor más avanzados
  • La toolchain generaliza estas extensiones como target feature
    • lscpu en Linux muestra las features que reconoce la CPU
    • LLVM selecciona instrucciones distintas según la configuración de features
    • LLVM necesita +avx2 para generar código que use ymm
  • -march=native o -Ctarget-cpu=native pueden generar buen código para la máquina donde se compila, pero pueden reducir la portabilidad a otros procesadores
  • La detección de features en tiempo de ejecución consiste en verificar qué capacidades soporta la CPU y decidir qué versión de una función llamar; se usa en código distribuido a muchos dispositivos, como las bibliotecas de cifrado
  • El código SIMD en C++ normalmente usa intrinsics como _mm256_cvtps_epu32
    • Representan operaciones de bajo nivel de un conjunto de instrucciones específico
    • No necesariamente se mapean a una sola instrucción
    • El compilador puede hacer fusión, eliminación de redundancias y optimización en la selección de instrucciones
  • Si se termina escribiendo código parecido una y otra vez para varios conjuntos de instrucciones, la ventaja de mantenimiento frente a assembly puede no ser tan grande
  • Las bibliotecas de portable SIMD manejan parte de la selección de instrucciones a nivel de biblioteca y dejan el resto al compilador
  • La implementación de vb64 es un experimento para comprobar si el portable SIMD de Rust genera código competitivo

convertir la decodificación base64 a SIMD

  • base64 es una forma de codificar datos binarios arbitrarios como ASCII
  • La secuencia de bytes de entrada se trata como un vector de bits y se divide en chunks de 6 bits llamados sextet
  • Los valores de sextet se mapean a los siguientes caracteres
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • Hay varias variantes de base64, pero la mayor parte de la complejidad es compartida
  • Hay dos puntos importantes a tener en cuenta
    • base64 es un formato donde los bits dentro del byte son big endian
    • La longitud de entrada puede no ser divisible entre 4; en principio se ajusta a un múltiplo de 4 con padding =, pero también se pueden procesar mensajes con padding incorrecto
  • La longitud decodificada se calcula como input / 4 * 3, sumando la longitud restante según input % 4

refactorización básica hacia branchless

  • Un decodificador base64 simple tiene varias ramas
    • Un loop que recorre la entrada por chunks
    • Un loop de bytes dentro del chunk
    • Un match por cada carácter ASCII
    • return Err en caso de error
    • Un match dentro de decoded_len
    • La posible llamada a Vec::extend_from_slice y al allocator
  • La guía de optimización es eliminar todas las ramas
  • El match de decoded_len mapea los valores 0, 1, 2, 3 de input % 4 a 0, 1, 1, 2
  • Si se reemplaza por mod4 - mod4 / 2, se obtiene una versión branchless
  • LLVM puede convertir el match original en una switch table, pero en esta parte los accesos innecesarios a memoria perjudican el rendimiento

aislar el loop más caliente

  • La fortaleza de SIMD está en procesar muchos datos a la vez para hacer un fuerte unroll del loop y acercarse a un diseño branchless
  • El objetivo del hot loop es leer hasta 4 bytes, producir hasta 3 bytes decodificados e indicar también si hay error de sintaxis
  • Hay tres hechos que se pueden aprovechar
    • La longitud de salida puede calcularse con decoded_len() branchless
    • Un base64 inválido puede tratarse como una ruta muy poco frecuente, y si hace falta la posición del error se puede volver a escanear después
    • Como A vale 0 en base64, hacer padding del chunk truncado con A no cambia el valor
  • decode_hot() se separa como una función que procesa cuatro bytes de entrada y devuelve el resultado decodificado junto con un bool de éxito
  • Devolver el bool por separado en lugar de Option<[u8; 3]> facilita eliminar después la rama if !ok
  • En la versión SIMD, la entrada se recibe como Simd<u8, 4> y la salida también se deja como Simd<u8, 4> para ajustarse a una cantidad de lanes potencia de dos
    • En realidad solo se necesitan 3 bytes de salida
    • El último lane no se usa

cómo convertir ASCII a sextet

  • La mayor parte del match que convierte caracteres ASCII a sextet puede expresarse como byte - C
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • Basta con crear un vector de offsets por lane y hacer ascii - offsets
  • El primer enfoque es compare-and-select
    • Se crean máscaras para A-Z, a-z, 0-9, +, /
    • Los lanes donde no se seleccione ninguna máscara se consideran inválidos
    • Se hace splat del offset correspondiente a cada máscara y se combinan con OR
  • Este método es elegante y puede generar código competitivo, pero requiere 8 comparaciones en total y puede generar presión de registros por la cantidad de valores vivos

tabla hash SIMD y perfect hash

  • Los rangos de bytes de A-Z, a-z, 0-9 son 0x41..0x5b, 0x61..0x7b y 0x30..0x3a, y cada uno tiene un high nibble distinto
  • Como + y / son 0x2b y 0x2f, en la mayoría de los casos byte >> 4 basta para distinguirlos
  • En el caso de /, restar uno lo convierte en un perfect hash sobre el rango
  • El mapeo de (byte >> 4) - (byte == '/') es el siguiente
    • A-Z → 4 o 5
    • a-z → 6 o 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • Como este valor es pequeño, la tabla de lookup de offsets se puede meter dentro de un vector SIMD y hacer el lookup con shuffle
  • La idea de este perfect hash fue propuesta por un usuario anónimo en este GitHub issue
  • Simd::swizzle_dyn() tiene la restricción de que el arreglo de índices y la longitud de la tabla de lookup deben ser iguales
  • En el enfoque de perfect hash no se obtiene la validación como efecto secundario durante el cálculo del sextet, así que se valida cada byte con el exact bloom filter del mismo GitHub issue
  • Hay un ejemplo de implementación en simd.rs de vb64

empaquetar cuatro sextets en tres bytes

  • La etapa de combinar cuatro sextets de 6 bits en tres bytes es más complicada
  • Si se deja un sextet de entrada específico en all-ones y se observa a dónde se mueven los bits en la salida, se puede seguir la relación de distribución
  • Un shuffle a nivel de byte no basta
    • Lo que hay que mover son fragmentos de byte
    • Solo con shift tampoco alcanza
    • Los bits desplazados de más tienen que pasar al lane adyacente
  • La solución es hacer más grandes los lanes
  • Se hace cast de sextets a un vector u16 y luego se aplica shift por lane
    • input[0] se ajusta con un shift de 2 bits
    • input[1] se ajusta con un shift de 4 bits
    • input[2] se ajusta con un shift de 6 bits
    • input[3] se ajusta con un shift de 8 bits
  • Del resultado del shift se separan los vectores de low byte y high byte
  • Luego, con hi.rotate_lanes_left::<1>() se alinean los fragmentos del high byte con el lane adyacente y se combinan con lo | hi_rotated
  • Como este método aprovecha mucho las primitivas de hardware, el código es compacto y eficiente

Ampliación del número de lanes y eliminación de garbage lanes

  • Simd<u8, 4> es incluso más pequeño que el registro vectorial mínimo de 128 bits en x86, así que decode_hot() se hizo genérico sobre el número de lanes N
  • La restricción LaneCount<N>: SupportedLaneCount garantiza cantidades pequeñas de lanes que sean potencia de dos
  • La lookup table y la shift table crean vectores de patrones repetidos con el helper tiled()
  • Con N = 4 bastaba con ignorar el valor basura del último lane, pero cuando N crece, se mezcla basura en cada cuarto lane
  • Para eliminarla se usa shuffle
    • La relación deseada es shuffled[i] = output[i + i / 3]
    • Se salta cada cuarto índice para borrar los garbage lanes
    • La parte que desborda corresponde al cuarto superior del vector de salida final, así que se ignora
  • Así, decode_hot::<32>() puede decodificar en paralelo 32 bytes base64

Optimización del outer loop

  • decode() también se hizo genérico respecto al número interno de lanes N
  • Los costos restantes son los siguientes
    • La rama de comparación de longitud en for chunks in ...
    • El memcpy de longitud variable de [T]::copy_from_slice
    • La rama ok en cada iteración del loop
    • La posible llamada al allocator de Vec::extend_from_slice y otro memcpy
  • Como se conoce la longitud de salida, se reserva espacio por adelantado con out.reserve(final_len + N / 4)
  • Además, se deja espacio de slop para hacer un store SIMD completo en lugar de un memcpy de longitud variable
  • Cada iteración escribe el vector SIMD completo, y la siguiente escritura avanza 3/4 * N para sobrescribir los bytes basura anteriores
  • Los últimos bytes basura no se incluyen en el Vec::set_len() final, así que se tratan como si hubieran sido eliminados
  • Aunque haya un early return por if !ok, como no se hizo commit con set_len(), out permanece sin modificar

Posponer el manejo de errores fuera del hot loop

  • En vez de hacer return con if !ok en cada iteración, se acumula con error |= !ok
  • Solo se verifica si hubo error una vez, justo antes del set_len() final
  • Bajo la suposición de que la mayoría de los blobs base64 son válidos, la ruta de error se empuja fuera del hot loop
  • Aunque haya un error de sintaxis, las operaciones SIMD posteriores no se comportan de forma arbitraria, así que las escrituras basura no se confirman y desaparecen
  • Después, llamadas como Vec::push() pueden sobrescribir esa misma región del buffer

Unroll and jam y manejo del remainder

  • Para reducir el memcpy de longitud variable de copy_from_slice, se aplica unroll and jam
  • El loop se divide en dos partes
    • hot vectorized loop: siempre procesa entradas de longitud N
    • cold remainder part: procesa como mucho una vez una entrada con i < N
  • Se usa Iterator::chunks_exact() de Rust para implementar un unroll-and-jam manual
  • En el hot loop se llama a Simd::from_slice() para hacer una sola carga del tamaño del vector
  • El bounds check queda en una forma que el compilador puede eliminar con facilidad

Benchmarks y optimización de carga manual

  • Los benchmarks decodifican mensajes desde longitud 0 hasta alrededor de 200 o 500 bytes, y comparan con la implementación base64 de referencia de crates.io
  • Las opciones de compilación usan -Zbuild-std y -Ctarget-cpu=native
  • Tras el ajuste, N = 32 dio el mejor resultado, usando un registro YMM por iteración del hot loop
  • Al principio superó a la baseline, pero apareció una variación de rendimiento con forma de heartbeat fuertemente correlacionada con data.len() % 32
  • Tras revisar el assembly, se concluyó que copy_from_slice probablemente se inlineó/unrolleó como un loop de cargas byte a byte
  • También se probó Simd::gather_or(), pero producía un assembly peor, así que no se usó
  • En su lugar, se escribió una función de carga manual para datos de longitud variable
    • La parte hot hace en el loop cargas escalares lo más grandes posible, de tipo u128
    • LLVM baja eso a cargas XMM en chunks de 16 bytes
    • El remainder usa cargas superpuestas de u64, u32 y u8
  • Para leer 15 bytes, se lee un u64 desde p y otro u64 desde p + 7, superponiendo 1 byte, y se combinan con OR
  • Para 4~7 bytes se usan cargas superpuestas de u32
  • Para 1~3 bytes se lee desde p, p + len/2 y p + len - 1; algunos bytes pueden cargarse de forma duplicada, pero se reduce el número de ramas
  • Después de aplicar el nuevo código de carga, la varianza se volvió muy pequeña y mostró el doble de rendimiento frente a la baseline en casi todo el rango

Encoding y base64 web-safe

  • La función de encoding se puede implementar con encode_hot(), que realiza a la inversa las operaciones de decode_hot()
  • El perfect hash usado en decodificación no encaja para encoding, por lo que se necesita un hash nuevo
  • El código de carga/almacenamiento alrededor del encoder también difiere un poco del decoder
  • vb64 también implementa una rutina eficiente de encoding
  • El base64 web-safe es una variante que reemplaza + y / por - y _
  • La construcción del perfect hash para base64 web-safe es más complicada; por ejemplo, podría requerir algo como (byte >> 4) - (byte == '_' ? '_' : 0)
  • vb64 todavía no soporta base64 web-safe

Conclusión

  • Se aclara que vb64 no es una librería pensada para resolver un cuello de botella importante, y que no se sabe en qué casos reales la decodificación base64 es de verdad el cuello de botella
  • El código branchless suele ser excesivo, pero ayuda a entender qué puede y qué no puede hacer el compilador
  • std::simd de Rust es, en general, bueno y genera código excelente
  • Aunque hay algunos rough edges que sería bueno corregir para simplificar más el código SIMD, la evaluación es satisfactoria con el resultado actual
  • SIMD y la optimización de rendimiento son temas complejos que requieren muchos trucos y conocimiento del hardware, y buena parte de eso ni siquiera está documentada

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-11-29
Opiniones en Hacker News

  • Me pareció interesante ver portable SIMD en uso real, y al reproducir el benchmark en un sistema Zen 3 obtuve la misma mejora de velocidad.
    En una MacBook Pro M1, con una longitud de entrada de 110 bytes, la mejora de rendimiento empezó en 1.4x y fue subiendo gradualmente hasta 2x; es menor que en x86_64, pero parece que cumple el objetivo.
    Sin embargo, al ver el código, confirma mi experiencia de que Rust tiene una ergonomía bastante mala para SIMD y trabajo con punteros, y más ampliamente para ingeniería de rendimiento.

    • Como ingeniero de Rust, estoy de acuerdo hasta cierto punto, pero el trabajo con punteros y memoria cruda tiene muchas restricciones intencionalmente por seguridad, y en parte busca obligarte a pensar realmente en lo que está haciendo el lenguaje.
      Aun así, portable SIMD en Rust todavía no es una buena historia comparado con C++, y si quieres bajar a regiones de bytes crudos, punteros y manipulación de buffers, tienes que familiarizarte con Pin, MaybeUninit, etc.
      portable_simd y allocator_api llevan años en estado inestable, tienen una barrera de entrada alta y son más torpes, pero en su mayoría es un diseño intencional.
      Dicho eso, nada te impide crear tus propias abstracciones para que sean más cómodas dentro de tu programa, o usar crates de terceros.
    • No estoy de acuerdo con que la ergonomía sea mala.
      Los intrinsics SSE de C++ son mucho peores: los guiones bajos se ven horribles y los nombres son difíciles de memorizar.

  • A veces de verdad me sorprende cuando implemento algo lo mejor posible en C++ clásico y luego alguien llega con una versión SIMD que lo hace más de 10 veces más rápido.
    A cambio, ese código es menos portable.
    Ojalá la autovectorización de los compiladores mejorara, y también hubiera soporte como anotaciones a nivel de lenguaje para permitir localmente cierto reordenamiento de operaciones.

    • Un buen código SIMD tiene que considerar cuidadosamente cómo están dispuestos los datos en memoria.
      Como el compilador no puede reacomodar los datos por ti fuera de contextos muy locales, la autovectorización se vuelve realmente difícil.
    • Incluso si el compilador pudiera optimizar perfectamente, hay muchas garantías seriales inevitables.
      Por ejemplo, en for(double v: vec) sum+=v, la suma de punto flotante no es asociativa, así que sumar los valores en orden no es lo mismo que el enfoque SIMD de sumar cada 8 elementos y luego combinar los resultados.
      Desde el punto de vista del compilador puede parecer una optimización obvia, pero a menos que le indiques que relaje ciertas garantías, prioriza la garantía de semántica serial sobre la optimización.
      Por eso se vuelve un desastre, y como dice janwas, creo que para rutas calientes conviene usar bibliotecas, en especial algo como Google Highway o Intel ISPC.
    • Ese es uno de los puntos de un lenguaje de programación de sistemas como C++.
      Intenta ser eficiente de la forma más portable posible, pero también facilita la programación específica para un objetivo cuando hace falta.
      Los compiladores de FORTRAN definitivamente hacen mejor la autovectorización, porque no se permite el aliasing.
      C++ está limitado por seguir el modelo de memoria de C.
    • También podrías simplemente usar CUDA.
      CUDA es C++ diseñado para la máquina SIMD definitiva de hoy, la GPU, y ROCm en la práctica se parece mucho a CUDA para AMD.
      Personalmente me gustaba C++AMP de Microsoft; creo que era lo más fácil para empezar.
      Es una pena que al final no se consolidara.
    • En mi experiencia, esto pasa con frecuencia.
      Además, si usas una biblioteca wrapper de SIMD, en realidad puedes hacerlo bastante portable.

  • Como pequeña nota, el compilador no pudo optimizar esa implementación de popcount a una sola instrucción, pero sí puede con otras implementaciones.
    Claro que es bastante delicado: https://godbolt.org/z/T69KxWWW8

  • Se dijo que _mm256_cvtps_epu32 representa una operación de bajo nivel de un conjunto de instrucciones específico y se explicó como un cast de float a int de AVX2, pero esa instrucción pertenece a AVX-512.
    AVX2 no tiene cast de float a int, y en AVX1 el resultado entero es signed y la instrucción es _mm256_cvtps_epi32.

  • Me pregunto cómo se compararía con fastbase64[0].
    El artículo es excelente y da gusto ver contenido así en línea, pero me cuesta compartir el optimismo del autor sobre las bibliotecas SIMD portables.
    [0]: https://github.com/lemire/fastbase64

  • Creo que ISPC simplemente es mejor que añadir SIMD a C++ o Rust.
    También soporta despacho dinámico, una característica dolorosa de implementar por cuenta propia.

    • Cualquier herramienta que haga que más gente use SIMD suele ser algo bueno, pero personalmente prefiero que SIMD esté integrado en la misma toolchain.
      Así puedes volver a hacer llamadas inline a C++, usar templates y clases en el código SIMD, y también inlinear varias regiones de código SIMD juntas.
      Estoy de acuerdo en que implementar despacho dinámico es difícil, pero Highway se encarga de esa parte.
    • Me pregunto si es fácil que C++ o Rust llamen a ISPC para una subrutina pequeña como la del texto.

  • Excelente artículo, y me deja una fuerte sensación de “yo jamás podría llegar a ser tan inteligente”.

    • Es solo que no es tu área de trabajo.
      Es parecido a que una persona común no sea ingeniera de software ni física.
      Si estudias con concentración durante unos meses, probablemente podrías hacerlo a un nivel similar.
    • Si tienes la oportunidad de encontrarte con un empleador o proyecto que necesite este tipo de cosas, probablemente puedas “llegar a ser así de inteligente”.
      Al final es cuestión de interés y necesidad.
      Yo también voy y vengo entre optimización de rendimiento e ingeniería bare-metal más cercana al sistema en proyectos personales, pero me gustaría que en mi trabajo hiciera falta más de eso.
      Solo que la mayor parte del trabajo en la industria no exige eso.
    • Sería bueno hacer AoC '23 con APL/j/k, BQN, Python/numpy, CUDA, etc.
      No Python idiomático, sino resolver todo con numpy.
      Es divertido y puedes aprender este tipo de ingenio; además, muchas partes del artículo se sienten muy naturales desde la forma de pensar con la que se resuelven problemas en esos lenguajes.
      Con el tiempo empiezas a ver los problemas de esa forma.
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • Es un artículo interesante.
    En el primer ejemplo del inicio dice que una implementación no vectorizada de popcnt produce “código francamente ridículamente malo”, pero si se usa el modo release con la CPU objetivo nativa, esa función parece vectorizarse bastante bien.
    https://godbolt.org/z/WE1Eq65jY

    • El código de abajo debería producir una salida equivalente.
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      Esto se compila como popcnt eax, edi; ret.
      En vectores de bits grandes, una implementación con AVX2 puede ser más rápida que POPCNT.
      Ver “Faster Population Counts Using AVX2 Instructions”: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32 bits no es lo suficientemente grande, y el código que genera Rust en realidad es ridículamente malo.
    • Idealmente, parecería que esto debería bajar a la instrucción popcnt.
    • La autovectorización a veces ocurre y a veces no.
      Hace poco escribí código que tenía que contar la cantidad de bits en la máscara resultante de una operación vectorial, y eso sí se convirtió bien en popcnt.
      https://godbolt.org/z/zT9Whcnco

  • Por partes como “esto parece una pregunta con trampa… ¿no es simplemente add?”, normalmente uno termina queriendo apuntar a una representación vectorial intermedia y dejar que el compilador decida los detalles.
    Por ejemplo, los chips Haswell tenían varias unidades de ejecución de punto flotante por núcleo, y la CPU podía ejecutar más de una operación de punto flotante en pipeline al mismo tiempo, pero solo una de ellas podía ser una instrucción add.
    Si había muchas sumas que no dependían de resultados anteriores y se podía evitar la latencia, también era posible enviar una instrucción de fused multiply-add con término multiplicador 1 para duplicar el throughput de sumas.
    Esa instrucción podía ejecutarse al mismo tiempo que una suma vectorial normal de punto flotante.