Puedes superar la búsqueda binaria

 (lemire.me)
1 puntos por GN⁺ 3 시간 전 | 1 comentarios | Compartir por WhatsApp
  • La verificación de pertenencia en arreglos ordenados puede hacerse más rápido que la búsqueda binaria de libro de texto, y SIMD Quad fue más rápido que std::binary_search en todas las condiciones medidas
  • SIMD Quad divide un arreglo ordenado de enteros sin signo de 16 bits en bloques de 16 elementos, realiza una búsqueda por interpolación cuaternaria en los límites de bloque y comparaciones paralelas SIMD dentro del bloque
  • ARM moderno de 64 bits y x64 (Intel/AMD) pueden comparar 8 enteros de 16 bits con una sola instrucción, por lo que ya no es tan necesario seguir la estructura de búsqueda binaria que inspecciona un solo valor a la vez
  • El benchmark se ejecutó con 100,000 arreglos ordenados de tamaños entre 2 y 4096 y 10 millones de consultas de pertenencia; el modo cold simula fallos de caché y el modo warm simula aciertos de caché
  • En Intel, SIMD Quad fue más de 2 veces más rápido que la búsqueda binaria con caché warm; en Apple, fue más de 2 veces más rápido con caché cold; y en Intel, con arreglos grandes y caché cold, el enfoque cuaternario aprovechó mejor el paralelismo a nivel de memoria

Cuello de botella en la verificación de pertenencia en arreglos ordenados

  • La forma más simple de verificar si un valor existe en un arreglo ordenado es la búsqueda lineal, que recorre los valores uno por uno; en C++ se puede lograr el mismo efecto con std::find
  • En arreglos grandes, la búsqueda binaria es más rápida, ya que descarta la mitad superior o inferior según el valor central del rango de búsqueda, repitiendo el proceso hasta encontrar el valor o llegar a un rango vacío
  • std::binary_search de C++ devuelve un booleano indicando si el valor existe
  • El formato Roaring Bitmap usa arreglos de enteros de 16 bits con tamaños entre 1 y 4096, y utiliza búsqueda binaria para comprobar pertenencia

Punto de partida de SIMD Quad

  • La mayoría de los procesadores modernos cuentan con instrucciones de paralelismo de datos SIMD, y ARM de 64 bits y x64 (Intel/AMD) pueden comparar 8 enteros de 16 bits contra un valor objetivo con una sola instrucción
  • Debido a esta característica, no es necesario seguir bajando con búsqueda binaria hasta bloques menores de 8, y también es barato comparar 16 o más elementos
  • La búsqueda binaria inspecciona un valor a la vez, pero los procesadores recientes pueden cargar y revisar varios valores a la vez y además tienen buen paralelismo a nivel de memoria
  • En vez de dividir el arreglo por la mitad, se puede intentar una búsqueda cuaternaria que lo divide en cuatro partes; aunque aumenta un poco el número de instrucciones, es posible que el cuello de botella no sea la cantidad de instrucciones

Estructura del algoritmo SIMD Quad

  • SIMD Quad es un algoritmo de búsqueda para arreglos ordenados de enteros sin signo de 16 bits que combina búsqueda por interpolación cuaternaria y SIMD
  • Divide el arreglo en bloques de tamaño fijo de 16 elementos, aunque el último bloque puede ser una excepción
  • Usa el último elemento de cada bloque como clave de interpolación para acotar el rango a un único bloque donde probablemente esté el valor objetivo, y luego examina simultáneamente los 16 elementos de ese bloque con SIMD
  • El flujo central es una búsqueda jerárquica que reduce comparaciones con búsqueda por interpolación en los límites de bloque y realiza comparación paralela con SIMD dentro del bloque
  • Los pasos de funcionamiento son los siguientes
    • Si hay menos de 16 elementos, se hace una búsqueda lineal simple sobre todo el arreglo
    • El arreglo de tamaño cardinality se divide en bloques de 16 elementos consecutivos, y el número total de bloques es num_blocks = cardinality / 16
    • Se usan como claves los últimos elementos de bloque en posiciones como 16-1, 32-1, etc., comparando contra el objetivo pos los puntos de 1/4 del rango actual de búsqueda y ajustando base
    • Según el resultado de la interpolación, se selecciona el índice de bloque adecuado lo
    • Si el bloque es válido, en ARM se cargan 16 elementos con NEON y en x64 con SSE2 para hacer comparaciones de igualdad paralelas contra el valor objetivo; si hay coincidencia, devuelve true
    • Los elementos restantes que no entran en bloques completos de 16 se revisan con búsqueda lineal

Metodología del benchmark

  • El benchmark generó 100,000 arreglos ordenados de enteros sin signo de 16 bits para cada tamaño entre 2 y 4096
  • Para cada tamaño se ejecutaron 10 millones de consultas de pertenencia en dos modos
    • Modo cold: cada consulta busca en un arreglo distinto para simular fallos de caché
    • Modo warm: las consultas se agrupan por arreglo y se busca 100 veces seguidas en el mismo arreglo para simular aciertos de caché
  • Lo que se midió fue el tiempo promedio por consulta, y los algoritmos comparados fueron búsqueda lineal (std::find), búsqueda binaria (std::binary_search) y SIMD Quad
  • Los sistemas de medición fueron Apple M4 con Apple LLVM, e Intel Emerald Rapids con GCC

Resultados de las mediciones

  • En la comparación entre búsqueda lineal y búsqueda binaria, a medida que el arreglo crece, la búsqueda binaria supera a la lineal
  • Con caché cold, la búsqueda lineal queda relativamente más en desventaja porque hay más accesos a datos y más fallos de caché
  • Después de confirmar la superioridad general de la búsqueda binaria sobre la lineal, se la comparó con SIMD Quad
  • Los resultados en las plataformas Intel y Apple fueron claramente distintos
    • En la plataforma Intel, con caché warm, SIMD Quad fue más de 2 veces más rápido que la búsqueda binaria
    • En la plataforma Intel, con caché cold, la ganancia fue menor
    • En la plataforma Apple, al contrario, SIMD Quad fue más de 2 veces más rápido con caché cold, y la ganancia fue más limitada con caché warm
  • En todos los casos, SIMD Quad fue más rápido que la búsqueda binaria
  • La parte SIMD reduce trabajo con instrucciones especiales y tiene menos instrucciones y bifurcaciones, por lo que la mejora de velocidad es fácil de entender

Efecto de la búsqueda cuaternaria

  • También se comparó una versión SIMD binary que mantiene la optimización SIMD pero reemplaza la búsqueda por interpolación cuaternaria por una búsqueda binaria estándar
  • En la plataforma Apple, el efecto del enfoque cuaternario fue pequeño
  • En la plataforma Intel, el enfoque cuaternario fue una optimización significativa en arreglos grandes con caché cold
  • En servidores Intel, la búsqueda cuaternaria aprovechó mejor el paralelismo a nivel de memoria

Claves de implementación

  • La función simd_quad recibe un arreglo uint16_t, el número de elementos cardinality y el valor buscado pos, y devuelve un booleano
  • gap está fijo en 16, y si cardinality < gap, busca el valor con un bucle simple
  • El bucle de búsqueda por bloques, mientras n > 3, lee los últimos valores de bloque en los puntos 1/4, 2/4 y 3/4, los compara con pos y mueve base con la suma de los tres resultados de comparación
  • Luego, mientras n > 1, realiza comparaciones usando la mitad como referencia para reducir el rango restante, y finalmente selecciona el bloque lo
  • El bloque seleccionado compara 16 elementos en dos grupos usando vceqq_u16 de ARM NEON o _mm_cmpeq_epi16 de x64 SSE2
  • El rango restante de elementos devuelve si v == pos en el punto donde v >= pos; si no aparece hasta el final, devuelve false

Conclusión y recursos

  • La búsqueda binaria de libro de texto es un algoritmo razonable, pero se puede acelerar de forma significativa en rendimiento real
  • Los algoritmos estándar muchas veces no están diseñados suponiendo el alto paralelismo de las computadoras actuales
  • SIMD Quad es un enfoque que busca aprovechar tanto el paralelismo a nivel de memoria como el paralelismo de datos
  • Es posible que existan algoritmos aún mejores, y hace falta un enfoque más creativo
  • Código fuente
  • Intersecciones más rápidas entre arreglos ordenados con shotgun

Lecturas relacionadas

1 comentarios

 
GN⁺ 3 시간 전
Comentarios de Hacker News
  • Dejando de lado el punto de Daniel Lemire sobre optimización de hardware de bajo nivel, binary search o sus variantes de implementación solo son lo mejor cuando no sabes nada salvo que los datos están ordenados o son monótonos
    Si tienes conocimiento previo sobre la distribución de los datos, puedes usar esa información para diseñar algoritmos mucho más rápidos. Por ejemplo, en un diccionario en papel una persona puede saltar a un grupo de páginas adecuado más rápido que con una binary search pura e idealizada
    Matemáticamente, buscar en una lista ordenada se parece a invertir una función monótona mediante un algoritmo de control en lazo cerrado, y podrías definir una función de costo apropiada y usar gradient descent o alguna variante acelerada
    Más en general, para resolver un problema de forma más eficiente, lo mejor suele ser usar más información sobre el problema específico que quieres resolver, en vez de traer una solución demasiado abstracta. Eso puede dar mejoras escalables de órdenes de magnitud, más allá de las mejoras por factor constante que obtienes de usar mejor el hardware
    • He pensado bastante sobre binary search, pero no he logrado superar esta implementación: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
      1. verifica en O(1) si es una lista densa, 2) revisa el límite superior, 3) usa binary search de número fijo de iteraciones
        Tener un número fijo de iteraciones le viene bien al branch predictor, y el loop central también está bastante ajustado y optimizado para el hardware objetivo, evitando multiplicaciones. Todos los intentos de hacerlo más inteligente empeoraron el loop y no recuperaron el costo. Además es una estructura array-of-structs de tamaño 12 y N normalmente también es pequeño, lo que lo hace más difícil
    • La frase “es mejor usar más información sobre el problema específico que quieres resolver” es obvia y a la vez profunda. Cuanta más información ya tienes, más significa que ya tienes más información
    • Recuerdo haber leído sobre treap; en vez de balancear el árbol, la idea era Huffman encode la profundidad de búsqueda con pesos para reducir el tiempo promedio de acceso cuando las frecuencias de acceso son desiguales
      No lo guardé en marcadores, así que termino volviéndolo a buscar unas dos veces al año
    • Sí, pero la clave es que muchas veces no sabes más sobre los datos
      Por eso B-tree es el estándar en bases de datos. Los datos pueden ser cualquier cosa, y si traes muchas filas nuevas de golpe, sus propiedades pueden cambiar muchísimo en cualquier momento
      Podrías diseñar algo que intente acelerar los lookup con algoritmos como gradient descent, pero B-tree ya es muy rápido, tiene rendimiento de peor caso y requerimientos de I/O predecibles, y además ofrece ventajas como range scan, ordered traversal y condiciones por prefijo
      Puedes construir algoritmos de lookup más eficientes para ciertas distribuciones de datos, pero muchas veces pierdes propiedades importantes. Aunque otro algoritmo produzca una estimación inicial más cercana, puede terminar siendo más lento para encontrar el elemento final, y aunque su promedio sea mejor, su peor caso puede ser horrible y volverlo poco práctico
      Incluso en un diccionario en papel, después de la primera estimación casi siempre usabas algo cercano a binary search, y eso solo te ahorra unos cuantos movimientos. Una vez que llegas a unas pocas páginas del lugar correcto, terminas haciendo más búsqueda lineal de la necesaria; una binary search estricta podría ser más rápida, pero hay que equilibrarlo con el tiempo de pasar páginas
    • Fritz Henglein hizo trabajo interesante sobre ordenamiento y agrupación rápidos. El paper principal parece ser Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
      Ed Kmett refinó la idea en la librería discrimination[2] para Haskell, y una charla técnica relacionada[3] también fue muy interesante
      [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
      [2]: https://hackage.haskell.org/package/discrimination
      [3]: https://www.youtube.com/watch?v=cB8DapKQz-I
  • Me parece que “quaternary” se parece más a hacer unrolling de una iteración del loop de binary search. Al final igual necesitas aproximadamente el mismo número de comparaciones para encontrar la partición que contiene el elemento, solo que procesas 4 a la vez en lugar de 2, así que parecería que con loop unrolling se lograría algo parecido
    • Es más complicado que eso. Los procesadores modernos hacen speculative execution, así que adivinan el resultado de una comparación y siguen avanzando por una rama hasta que descubren que se equivocaron o alcanzan algún límite interno
      Si se equivocan, descartan ese trabajo especulativo, pagan una penalización de algunos ciclos y reinician desde otro punto
      Eso significa que, desde el punto de vista del procesador, todos los loops ya están en cierto grado desenrollados, y el costo principal de binary search es traer datos desde memoria o caché. Así que el verdadero juego es emitir cuanto antes las solicitudes de datos que vas a necesitar después, para reducir la latencia
      Quad search o búsquedas de orden aún mayor hacen prefetch superficial de todos los casos posibles, en vez de hacer prefetch profundo solo de un lado de cada branch. Así te aseguras de emitir el prefetch que realmente vas a necesitar, y además reduces un poco el bandwidth desperdiciado en datos que no usarás en la ruta real de ejecución
      El “número de comparaciones” casi no sirve como métrica para comparar algoritmos de búsqueda si quieres predecir rendimiento real. El cuello de botella no es la cantidad de comparaciones, sino aprovechar al máximo el bandwidth de memoria y caché. Si además consideras cómo manejan los branches los procesadores modernos, sí puede verse como una forma de loop unrolling
    • Puede verse como un poco de loop unrolling. La mejora no viene tanto de reducir drásticamente el número de instrucciones o lecturas de memoria, sino de aliviar las dependency entre operaciones para que no sea una ejecución puramente serial. También se parece a ejecutar especulativamente ambos lados de un branch
    • Quaternary search básicamente hace al mismo tiempo las comparaciones de la iteración actual y las dos comparaciones posibles de la siguiente iteración. Es un poco más complejo que un simple loop unrolling
      En cualquier caso, ambas búsquedas son O(log N) y solo cambian las constantes. En clases de algoritmos las constantes importan menos, pero en la práctica pueden importar bastante
    • Hasta cierto punto sí, pero también elimina la data dependency entre pasos desenrollados
    • Porque los procesadores no funcionan de la forma ingenua en que la gente suele imaginar
  • Hace poco también escribí una nota[1] sobre Exponential Search[2]. Es otro algoritmo útil cuando tienes que repetir binary search sobre un arreglo donde los elementos que vas buscando también están ordenados
    En nuestro workload dio una mejora de velocidad de 8x
    [1] https://lalitm.com/post/exponential-search/
    [2] https://en.wikipedia.org/wiki/Exponential_search
    • Exponential search es útil en APIs REST que direccionan recursos con IDs secuenciales, cuando necesitas el último ID pero no existe un endpoint dedicado
      HEAD /users/1 -> 200 OK
      HEAD /users/2 -> 200 OK
      HEAD /users/4 -> 200 OK
      ...
      HEAD /users/2048 -> 200 OK
      HEAD /users/4096 -> 404 Not Found
      Luego haces binary search entre 2048 y 4096 y encuentras el user más reciente y, de paso, la cantidad de users. Es información bastante útil cuando investigas empresas SaaS competidoras
  • La CPU siempre accede de una vez a toda una cache line de 64 bytes, así que también puedes buscar dentro de toda la cache line. Una vez que los datos ya entraron al CPU, es casi gratis
    Por eso quisiera probar una búsqueda “binaria” donde revises todos los valores de la “cache line del medio” y, si no está, vayas a la izquierda o a la derecha. Buscar dentro de la cache line puede hacerse con una sola instrucción 512bit SIMD
    Una cache line son 64 bytes, es decir 32 enteros de 16 bits, así que este tipo de búsqueda podría ser casi 32 veces más rápida que una binary search simple. Al menos reduce los accesos a memoria en 32x, y en la mayoría de programas reales eso es lo dominante
    • Si comparas el target con toda la cache line superior de un binary search tree implementado como sorted vector, la probabilidad de acierto sigue siendo baja. En cambio, tendrías que usar la información extra de la línea para reducir la búsqueda, y eso te lleva a B-Tree/B+tree
      Si usas key de 4 bytes y child pointer o índice de arreglo de 4 bytes, un nodo interno llena exactamente una cache line de 64 bytes con 7 keys, 8 child pointers y 1 next pointer. La profundidad de un árbol con 1 millón de entradas baja de alrededor de 20 a alrededor de 7, y es probable que los niveles superiores se queden en caché
      También podrías aplicar SIMD dentro de un nodo B-tree para acelerar la búsqueda interna, pero sigue habiendo mucha dependencia de datos
  • Para arreglos pequeños, linear search con sentinel value al final ya es difícil de superar. Lo malo de esa afirmación es que “pequeño” es un calificativo demasiado ambiguo, así que cuesta sentirla concreta
    • Viendo el excelente benchmark de este artículo, linear search empieza a quedarse atrás más o menos alrededor de 200 a 400 elementos, así que no es solo una verdad trivial
      En general me gustó porque explora a fondo algo que me preguntaba seguido, con un estudio de ablación realmente útil
  • Hice algunos experimentos de búsqueda con arreglos pequeños, de entre 16 y 32 elementos, y binary search resultó ser de las peores opciones por la cantidad de branches
    En arreglos pequeños, lo más rápido fue linear branchless search. Es decir, recorrer todos los elementos sin salirte antes del loop. Por ejemplo, si solo quieres saber si cierto número está en el arreglo, haces OR lógico de los resultados de verificar cada elemento
    No usé SIMD, pero en arreglos pequeños el costo de los branches es tan alto que es más rápido revisar todos los elementos de forma simple y sin branches
    • Me pregunto si parte de que sea más rápido es que sigue un patrón que le gusta al prefetcher
  • La explicación del algoritmo me confundió un poco
    La parte de SIMD solo aparece en la etapa final, para buscar entre los últimos 16 elementos
    La parte Quad revisa 3 puntos para crear 4 caminos, pero no está buscando simplemente la key exacta, sino el bloque correcto
    El detalle me parece interesante: el autor usa el último elemento de cada bloque para la quad search. Me pregunto cómo cambiaría el algoritmo si usara el primer elemento de cada bloque, o uno arbitrario
  • La intuición central aquí, comparar varios elementos con SIMD, parece que también podría usarse a mayor escala y no solo en la etapa final
    La idea general sería 1) traer varios elementos con gather desde 16 posiciones espaciadas uniformemente, 2) compararlos en paralelo con una instrucción SIMD, 3) enfocarse en el bloque correcto y 4) cuando el bloque sea pequeño, cambiar a linear search; si no, repetir el ciclo gather/compare
    Las instrucciones gather leen memoria no contigua y leen más que una binary search normal, pero permiten comparación multiway y se saltan cuatro niveles de binary search, así que en tablas grandes podrían convenir
    Claro, no todos los tipos de datos permiten una comparación completa de 16 vías. En búsquedas float64, incluso con AVX-512, estás limitado a 8 vías, mientras que int32 y float32 sí permiten 16 vías
    • gather es extremadamente lento. Quien de verdad esté persiguiendo eficiencia lo va a evitar
      Apostaría a que binary search termina siendo más rápido en la práctica que un enfoque basado en gather
  • Los algoritmos clásicos de ciencias de la computación básicamente están “diseñados” para CPU sin paralelismo: sin varios cores, sin Hyper-threading, sin instrucciones tipo SIMD, y con el supuesto de que todos los accesos a memoria cuestan lo mismo, sin diferencias de latencia como L1/L2/L3 cache. También se asume que los datos son genéricos y aleatorios
    En cuanto te sales de cualquiera de esos supuestos, aparecen muchos ajustes para obtener mejor rendimiento
    Lo bueno de los algoritmos clásicos es que dan un excelente punto de partida para desarrollar soluciones más óptimas y eficientes cuando conoces mejor la forma de los datos o las características y rarezas del CPU específico
    En la frontera de la optimización, casi siempre terminas mirando cómo se guardan y acceden los datos en memoria, y si los cambios que haces para mejorarlo no perjudican etapas posteriores. En un trabajo de hace años, alguien optimizó mucho una parte específica del código, pero esa optimización expulsó más información de caché para pasos posteriores, y toda la aplicación terminó siendo más lenta
    Probablemente esto no sea más que una reformulación de la quinta regla de programación de Rob Pike o, yéndonos más atrás, de algo que decía Fred Brooks en The Mythical Man Month. Referencia: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
  • Cuando era adolescente, pasé un fin de semana entero pensando que si binary search era buena porque reduce el espacio de búsqueda a la mitad en cada paso, entonces quizá ternary search sería mejor porque lo divide en tercios en cada paso
    En vez de comparar solo con el valor del medio, comparas con el valor en 1/3 y, si eso es demasiado bajo, comparas con el valor en 2/3
    Pero concluí que al final era equivalente, porque en cada paso el espacio de búsqueda se reduce a 1/3 en vez de 1/2, pero haces en promedio 3/2 veces más comparaciones que en binary search
    Corrección: como respondió zamadatix, en realidad son 5/3 comparaciones, porque en el caso de 2/3 tienes que hacer dos comparaciones
    • Ese enfoque ternario no da un promedio de 3/2 comparaciones por nivel
      El primer tercio requiere 1 comparación, el segundo tercio 2 y el tercero también 2, así que el promedio es (1+2+2)/3 = 5/3. Es fácil equivocarse porque se siente como “a veces 1, a veces 2, así que 50/50”, pero en realidad la probabilidad de acertar en la primera comparación es 1/3 y la de necesitar 2 comparaciones es 2/3
      Así que ternary resulta apenas un poco peor en número total promedio de comparaciones. 5/3 * Log_3[n] = 1.052... * Log_2[n]
      O sea, reduces niveles, pero en promedio haces más comparaciones para llegar al final. Esto aplica de forma bastante general a búsquedas con más de 2 particiones bajo varios supuestos estándar, como distribución uniforme del valor buscado y costos idealizados de operación. Las diferencias del hardware real que trata el artículo aparecen justo ahí
    • A esa idea adolescente sí le estabas viendo algo
      Solo que no como una versión ternaria del algoritmo de binary search. Eso en realidad no sería ternary search, sino algo más cercano a una binary search sesgada. Las comparaciones son esencialmente binarias, así que un algoritmo de búsqueda basado en comparaciones es, en cierto sentido, una especie de binary search, y elegir algo distinto del elemento central es menos eficiente desde el punto de vista de complejidad algorítmica. Claro, en hardware real podría funcionar mejor bajo ciertas condiciones. Para tener una ternary search de verdad necesitarías una operación básica de 3-way comparison
      Lo interesante aparece al pensar en radix efficiency[1], donde la mejor opción es 3, el número natural más cercano a e. También tiene relación con tree search, así que un árbol ternario puede ser mejor que uno binario
      [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
    • En medios donde no puedes hacer seek rápido, como disco, por ejemplo puedes usar un 128-way B-tree. El costo de traer 128 keys no es mucho mayor que el de traer 1 key, pero te ahorras 7 fetches adicionales
    • Me pregunto si después imaginaste un CPU con comparador ternario
    • Desde tu adolescencia, los CPU se han ensanchado muchísimo tanto en ancho de ejecución como en capacidad vectorial. Ese mayor throughput desplaza el equilibrio hacia gastar más operaciones para reducir la dependency chain
      Esa idea quizá era irrealista en los CPU de entonces, pero podría ser bastante más realista en los de ahora