Algoritmo de búsqueda de subcadenas apto para SIMD (2018)

• Trata sobre un algoritmo de búsqueda de subcadenas compatible con SIMD
• Presenta un enfoque técnico para una búsqueda de cadenas rápida
• Apunta a mejorar la eficiencia frente a los métodos existentes aprovechando el procesamiento en paralelo
• Destaca como un consejo de rendimiento útil para desarrolladores y profesionales de TI
• Este algoritmo está relacionado con la optimización para hardware moderno

---

Resumen

• Este documento presenta un algoritmo de búsqueda de subcadenas optimizado para el conjunto de instrucciones SIMD (Single Instruction, Multiple Data)
• En el entorno actual de TI, donde la velocidad de procesamiento de cadenas se ha vuelto importante, aborda una solución de procesamiento en paralelo que complementa las limitaciones de los métodos tradicionales de búsqueda secuencial
• Al usar SIMD, es posible comparar varios datos al mismo tiempo de una sola vez, por lo que se pueden esperar mejoras importantes de rendimiento en la búsqueda de cadenas de gran volumen

Contenido principal

• El algoritmo SIMD divide la cadena de entrada en varias partes y compara varios bytes a la vez con la misma instrucción
• Con este enfoque, es posible una búsqueda más rápida y eficiente que la comparación tradicional basada en bucles repetitivos
• Se utiliza de forma efectiva sobre todo en áreas que requieren procesamiento de grandes volúmenes de datos a alta velocidad, como búsqueda de texto, análisis de logs y secuenciación de ADN

Ventajas para desarrolladores e ingenieros

• Al aplicar un algoritmo compatible con SIMD, es posible maximizar el potencial de las CPU modernas con cambios mínimos en el código
• Ofrece ventajas en velocidad y eficiencia frente a la lógica de búsqueda existente
• También destaca por su excelente escalabilidad de rendimiento en entornos multinúcleo

Conclusión

• En servicios de TI, análisis de datos y motores de búsqueda en tiempo real donde el rendimiento de búsqueda de subcadenas es importante, adoptar un algoritmo basado en SIMD puede traducirse en mejoras reales de rendimiento
• Es una estrategia de optimización esencial para aprovechar los entornos de hardware más recientes

[GN⁺]

Comentarios en Hacker News

• Se explica que la aceleración de ripgrep usa un enfoque AVX2 (genérico) mediante el crate regex de Rust. Por ejemplo, incluso en una expresión regular como \w+\s+Sherlock\s+\w+, se enfatiza que es posible extraer solo Sherlock y buscarlo rápidamente. La implementación real puede verse aquí. También se menciona que la principal diferencia con el algoritmo de este artículo es que, en lugar de usar el primer/último byte del needle, emplea una heurística que optimiza la búsqueda con 2 bytes menos frecuentes usando la distribución de fondo. Los benchmarks muestran un rendimiento muy superior al método Two-Way simple o al memmem de GNU libc. En el benchmark prebuilt también se subraya una limitación del API: las rutinas tipo memmem pierden eficiencia porque deben reconstruir repetidamente el estado cada vez que el needle queda fijo

  • Señalan la duda de cómo se conoce la distribución de fondo de bytes, y si escanear esa distribución una por una en el haystack no terminaría perjudicando el rendimiento

• Se comparte la experiencia de haber implementado este tipo de algoritmo de búsqueda de cadenas al intentar optimizaciones SIMD en Wasm/WASI libc. Se opina que, cuando la longitud del haystack está definida y el needle es lo bastante grande, es útil combinarlo con Quick Search, y se dejan código relacionado y un enlace con la explicación del algoritmo

• Comparten que en C# también se aplica SIMD a IndexOf, y que se pueden ver más detalles aquí

• También se presenta la experiencia de haber implementado personalmente varios algoritmos usando un enfoque SIMD para búsqueda de cadenas y split. Se comparte el source de conversion.cxx de tamgu. Se aclara que se usó otro algoritmo distinto al mencionado en el texto principal

  • Piden un resumen breve de ese algoritmo propio. Como ejemplo, se añade que el algoritmo 1 del texto original compara el primer/último carácter, mientras que el algoritmo 2 compara simultáneamente las primeras 4 letras para revisar múltiples posiciones candidatas

  • Se comparte además la experiencia de haber intentado implementar hace unos años una versión modificada para búsqueda de ventanas LZ77 usando SIMD genérico de Zig. Puede verse más al respecto aquí

• Hay una opinión de que esto hace recordar al proyecto hparse, que usa algoritmos SIMD para parsing HTTP rápido

• Se menciona que el algoritmo swar incurre en UB (comportamiento indefinido) al hacer cast de datos alineados a 1 byte en unidades de 8 bytes. También se señala que podrían existir problemas de rendimiento por unaligned load

  • Otra opinión dice que este tipo de código a menudo se ha entendido como algoritmo idealizado o pseudocódigo pensado para legibilidad. Se critica que no usa mempcy y que la verificación de límites también es imprecisa. Existen hasta 3 casos de UB: asumir que la longitud del haystack es múltiplo de 8, o que si el needle está vacío puede haber unsigned integer overflow y un acceso out-of-bounds, entre otros. También se comparte la experiencia de que en código demo de SIMD a menudo solo se muestra el uso interesante de vectores y se omiten las condiciones de borde

• Se recalca que ya es sabido que strstr de libc es lento, pero que musl es rápido y usa un algoritmo moderno. Ahora solo faltaría ponerle nombre para sumarlo a smart shootout. Surge curiosidad por cómo se compararía con los mejores algoritmos SIMD

  • Como benchmark de referencia, se presenta una comparación entre Two-Way de musl y el algoritmo libc con optimización SIMD compartido por esa persona. El método de benchmark se basa en este código relacionado. Las mejoras por uso de SIMD pueden verse en esta tabla. Se evalúa con honestidad que no es algo sobresaliente, sino una mejora bastante decente. Se menciona que musl está especializado en cadenas de longitud fija (memmem), mientras que en el entorno Wasm esa persona pudo probar varias optimizaciones libremente para cadenas de longitud desconocida (strstr). Las cadenas terminadas en NUL dificultan varios algoritmos buenos

  • Se comparte el deseo personal de que smart incluya más algoritmos SIMD, y de hacer pruebas directas si hay tiempo

• Preguntan si en la comparación SIMD de búsqueda de cadenas no falta la versión de 2018

• Preguntan cuál es el umbral real a partir del cual SIMD resulta eficiente según el tamaño de la cadena. Se enfatiza que, en general, en cadenas pequeñas el overhead de configurar SIMD (alineación, cálculo de longitud, etc.) puede hacer que sea más lento que una búsqueda simple basada en bytes. Se aclara que esto puede variar mucho según la arquitectura de hardware

  • Según la experiencia de esa persona, en realidad ocurre lo contrario. Estos algoritmos son casi de fuerza bruta, sin configuración innecesaria, por lo que su complejidad temporal empeora con needles largos y repetitivos. En cambio, los algoritmos avanzados de búsqueda de cadenas que evitan problemas cuadráticos o logran ejecución sublineal requieren una configuración costosa porque analizan con más profundidad la estructura del needle

• Expresan el deseo de poder usar SIMD directamente desde Python sin llamar a otros lenguajes

  • Se menciona el blog de Austin y una recopilación (story on vowels detection enlace), y se pregunta de forma concreta qué significa “usar SIMD directamente sin llamar a otro lenguaje”. Después de todo, Assembly también es “otro lenguaje”, dicen en tono de broma. Se explica que el ecosistema de Python y SIMD abarca un espectro muy amplio, como PeachPy (escritura de ensamblador x86 desde Python), Mojo (un nuevo lenguaje con estilo Python) y bibliotecas SIMD con bindings delgados para CPython. Preguntan qué enfoque se desea exactamente y, si el objetivo es ASCII, recomiendan también la función find_first_of de StringZilla (código)

  • Se cuestiona por qué querer hacerlo directamente en Python. Si el problema es el límite de rendimiento, se aconseja que solo con cambiar de lenguaje puede lograrse una mejora de 20 a 50 veces o más