Un algoritmo de búsqueda de subcadenas adecuado para SIMD (2018)

• APIs como strstr y std::string::find asumen una búsqueda única de subcadenas, pero en CPUs modernas el costo de comparar cadenas cortas y vectores es bajo, así que un enfoque SIMD puede ser ventajoso
• La idea central es convertir la condición de hash débil de Karp-Rabin en un predicado vectorial y realizar una comparación exacta de la subcadena solo en las posiciones candidatas
• El algoritmo SIMD genérico reduce candidatos comparando en paralelo el primer y el último carácter de la needle, y valida con memcmp solo las posiciones con posibilidad de coincidencia
• También se comparan los enfoques SSE4.1 MPSADBW y SSE4.2 PCMPESTRM, pero las mediciones muestran que el SIMD genérico es más rápido de forma más estable, y PCMPESTRM suele ser incluso más lento que MPSADBW
• El SIMD genérico fue más rápido que strstr de C en todas las plataformas, pero no es seguro porque puede leer fuera de la cadena de entrada, y además la comparación no es totalmente equivalente porque recibe la longitud por adelantado

---

Suposiciones de costo que cambiaron en la búsqueda de cadenas

• APIs como strstr en C, std::string::find en C++ y pos, index de cadenas en Python están pensadas para una búsqueda única de una subcadena dentro de una cadena dada
• Los algoritmos clásicos se dividen en dos grandes grupos
  • métodos basados en autómatas finitos deterministas como Knuth-Morris-Pratt y Boyer Moore
  • métodos basados en comparaciones simples como Karp-Rabin
• Los algoritmos estándar asumen que comparar 1 par de caracteres, consultar una tabla auxiliar y hacer una rama condicional es barato, mientras que comparar dos subcadenas es costoso
• En CPUs modernas de escritorio, esta suposición puede dejar de cumplirse
  • en CPUs de 64 bits no hay diferencia de costo entre comparar 1, 2, 4 u 8 bytes
  • si hay soporte para instrucciones SIMD, comparar vectores de 16, 32 o 64 bytes puede ser tan barato como comparar un solo byte
  • consultar tablas implica un costo de acceso a memoria comparable a una ida y vuelta al caché L1, y leer caracteres individualmente tiene un costo similar
  • una mala predicción de rama puede introducir una penalización de aproximadamente 10~20 ciclos
  • una cadena corta de dependencias entre lectura de caracteres, comparación y rama condicional dificulta aprovechar la ejecución out-of-order del CPU

Enfoque: usar un predicado vectorial en lugar de un hash débil

• Karp-Rabin realiza una comparación exacta solo cuando el hash débil de la subcadena buscada coincide con el hash del segmento actual de la cadena
• El enfoque SIMD reemplaza esa condición de hash por un predicado vectorial
  • el predicado se calcula en paralelo
  • solo se realiza una comparación exacta de subcadena en cada posición marcada como verdadera en el vector de predicados
• La especialización por longitud también se usa para mejorar el rendimiento
  • una implementación general llama a funciones como memcmp para comparar subcadenas
  • si se conoce la longitud de la subcadena a buscar, esa llamada puede reemplazarse por unas pocas instrucciones de CPU, y en algunos casos por una sola instrucción
  • esto reduce el costo de la llamada a función y el costo interno de memcmp

Algoritmo 1: SIMD genérico

• El algoritmo SIMD genérico puede aplicarse a varios conjuntos de instrucciones SIMD y también al enfoque SWAR
• El predicado básico verifica si coinciden tanto el primer carácter como el último carácter de la needle
  • se llena el registro F con el primer carácter
  • se llena el registro L con el último carácter
  • en cada iteración se lee el bloque A del haystack en el offset actual i, y el bloque B en i + k - 1
  • luego se calcula F == A y B == L, y se combinan ambos resultados para crear una máscara de posiciones candidatas
  • solo en las posiciones donde la máscara es verdadera se realiza la comparación exacta de la subcadena
• En el ejemplo de buscar "cat" dentro de "a_cat_tries", la única posición donde coinciden tanto la c inicial como la t final es el índice 2, así que solo se hace una comparación exacta
• Elegir siempre el primer y último carácter no siempre es buena idea
  • si la cadena de entrada está compuesta mayormente por 'A' y la needle es "AjohndoeA", puede haber muchos candidatos
  • la implementación puede elegir, en lugar del último carácter, el carácter más lejano que sea distinto del primero
  • si todos los caracteres de la needle son iguales, puede usarse un procedimiento especial para patrones como "AAAAA"

Diferencias entre implementaciones

• Las implementaciones con SSE y AVX2 tienen casi la misma estructura y usan el número mínimo de instrucciones
  • como ya se sabe que el primer y el último carácter coinciden, memcmp no necesita volver a compararlos
• El enfoque SWAR aprovecha que si el resultado de XOR es 0, entonces los bytes son iguales
  • en vez de hacer AND de resultados parciales como en SSE/AVX2, usa OR
  • encontrar las posiciones de bytes en 0 requiere más trabajo
  • la implementación en C++ para vectores de 64 bits calcula la máscara exacta de bytes
• AVX512F no tiene operaciones a nivel byte y su elemento vectorial más pequeño es una palabra de 32 bits, por lo que requiere la técnica SWAR
  • calcula dos XOR y un OR con instrucciones AVX512F
  • encuentra los elementos que contienen un byte 0 dentro de cada elemento de 32 bits
  • para cada uno de esos elementos de 32 bits verifica 4 posibles subcadenas candidatas
• La implementación de ARM Neon de 32 bits usa registros SIMD de 128 bits
  • el largo viaje de ida y vuelta entre la unidad Neon y el CPU se convierte en un cuello de botella
  • por eso guarda los resultados de comparación como palabras de 64 bits en memoria para procesarlos
  • al desenrollar 2 veces el bucle interno, el rendimiento mejora cerca de 1.2x
• La implementación AArch64 es casi igual al procedimiento con ARM Neon, pero leer directamente los lanes del registro SIMD es rápido

Algoritmo 2: SSE4.1 MPSADBW

• MPSADBW en SSE4.1 y AVX2 calcula la distancia Manhattan entre un subvectores de 4 bytes de un registro y 8 subvectores consecutivos de 4 bytes de otro registro
• Si dos subvectores son iguales, la distancia L1 es 0, por lo que puede usarse para buscar posiciones candidatas
  • este enfoque usa como predicado la igualdad de los primeros 4 caracteres
• Comparar los primeros 4 caracteres parece más fuerte que comparar el primero y el último, pero en el peor caso no evita la complejidad cuadrática
  • si el haystack está lleno de "a" y la needle es "aaaabcde", el predicado es verdadero en todos los caracteres de entrada
• El enfoque MPSADBW tiene varias restricciones
  • en principio no se adapta bien a subcadenas de longitud menor que 4
  • sí puede manejar longitud 3, pero requiere código adicional
  • en SSE, MPSADBW procesa solo 8 bytes por vez
  • en AVX2, MPSADBW no opera sobre todo el registro de 256 bits sino por lanes de 128 bits, así que hace falta código extra de carga
  • la latencia de la instrucción es alta, de 5~7 ciclos según el CPU, aunque su throughput es de 1~2 ciclos, por lo que el desenrollado del bucle puede ocultar esa latencia
• AVX512F no incluye MPSADBW, pero como soporta elementos de 32 bits de forma nativa, puede imitarse el predicado de igualdad del prefijo de 4 bytes
  • en cada iteración se construyen 4 vectores AVX512 con los posibles prefijos de 4 bytes
  • cada construcción de vector requiere 2 desplazamientos y 1 OR
  • el bucle de comparación se vuelve más complejo, y para llenar el último elemento hacen falta 4 bytes más allá del vector

Algoritmo 3: SSE4.2 PCMPESTRM

• SSE4.2 introdujo el conjunto de instrucciones STNI con la idea de servir como bloques de construcción para operaciones con cadenas
• Intel prácticamente abandonó STNI en procesadores posteriores y no introdujo una versión AVX2; además, estas instrucciones son muy lentas
  • una latencia de 11 ciclos se considera difícil de aceptar
• Las instrucciones PCMPxSTRx tienen cuatro variantes según cómo se determine la longitud de la cadena y cómo se almacene el resultado
  • la longitud puede darse explícitamente o puede considerarse que la cadena termina en el primer byte 0, como en las cadenas C tradicionales
  • el resultado puede guardarse como máscara de bits o bytes, o como el número del primer o último bit activado de la máscara
• Aquí se usa el modo de comparación range ordered
  • pese al nombre, cuando se supera el ancho del registro o se trata de una subcadena, encuentra el prefijo correspondiente
  • en el ejemplo de buscar "ABCD" dentro de "ABCD_ABC_ABCD_AB", el sufijo "AB" también puede tratarse como coincidencia
  • por eso, lo único que puede asumirse con seguridad es la coincidencia del primer carácter, y el resto debe verificarse con memcmp

Entorno de medición de rendimiento

• Se midió el rendimiento de varias implementaciones SIMD, incluyendo especialización en tiempo de ejecución para subcadenas cortas
• Se incluyó strstr de C como referencia, pero se excluyó std::string::find de GNU libc en las tablas x64 debido a un bug de rendimiento
• Cada programa de prueba se ejecutó tres veces
• Entorno de pruebas x64
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• Entorno de pruebas ARM
  • ARMv7 Raspberry Pi 3, código de 32 bits, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, código de 64 bits, Clang 3.8.0

Resultados en x64

• La implementación SIMD genérica mostró las mayores mejoras frente a strstr en x64
  • en Westmere, SSE2 generic marcó 0.74589 segundos, frente a 0.82246 de strstr
  • en Haswell, AVX2 generic marcó 0.38653 segundos, frente a 0.52786 de strstr
  • en Skylake, AVX2 generic marcó 0.36309 segundos, frente a 0.66148 de strstr
  • en KNL, AVX512F generic marcó 1.14057 segundos, frente a 4.94606 de strstr
• La mejora máxima fue de 1.10x en Westmere, 1.37x en Haswell, 1.82x en Skylake y 4.33x en KNL
• El rendimiento de strstr en Bulldozer fue 9.37792 segundos, tan malo que cuesta usarlo como referencia
• El enfoque MPSADBW tuvo un desempeño flojo en general salvo en Skylake, y fue especialmente malo en KNL
• El enfoque PCMPESTRM resultó aún más lento que MPSADBW

Resultados en ARM

• En ARMv7, std::strstr tardó 7.30405 segundos y std::string::find 4.17131 segundos
• En ARMv7, ARM Neon 32-bit generic logró 1.29861 segundos, hasta 3.1x más rápido que std::string::find
• En ARMv8, std::strstr tardó 3.37546 segundos y std::string::find 1.81368 segundos
• En ARMv8, AArch64 64-bit generic logró 0.27897 segundos, hasta 6.5x más rápido que std::string::find
• En ARMv8, SWAR 64-bit generic logró 0.46269 segundos, con un rendimiento cercano al procedimiento SIMD de 32 bits

Conclusiones y límites

• El algoritmo SIMD genérico fue más rápido que strstr de C en todas las plataformas
• Conviene que la implementación elija la versión SIMD más alta disponible en cada CPU específico
• MPSADBW no muestra buen rendimiento salvo en el caso de Skylake, y en Knights Landing es muy malo
• PCMPESTRM rinde peor que MPSADBW
• El rendimiento de ARM Neon fue bueno, incluso incluyendo la implementación SWAR
  • la versión SWAR es 1.7x más rápida que string::find
  • la versión SIMD es 3.1x más rápida que string::find
• La comparación con strstr puede no ser totalmente justa
  • strstr procesa cadenas cuya longitud no conoce
  • estas implementaciones reciben la longitud como argumento y la aprovechan
• La implementación no es segura
  • puede leer datos fuera de la cadena de entrada
  • si la cadena está justo antes de memoria no mapeada, puede producirse una violación de acceso
  • AddressSanitizer también puede reportar el problema
  • hacerla segura sería posible, pero no era el objetivo
• Todas las implementaciones y programas de prueba están en GitHub