Puede hacerse más rápido que la búsqueda binaria

 (lemire.me)
3 puntos por GN⁺ 2026-05-01 | 1 comentarios | Compartir por WhatsApp
  • La búsqueda binaria, usada comúnmente para encontrar un valor en un arreglo ordenado, solo compara un valor a la vez, pero los CPU modernos pueden comparar varios valores simultáneamente con una sola instrucción, y aprovechar esa capacidad puede aumentar mucho la velocidad de búsqueda
  • SIMD Quad es un algoritmo de búsqueda jerárquica que divide el arreglo en bloques de 16 elementos, reduce rápidamente la ubicación del bloque con una búsqueda por interpolación cuaternaria y luego compara de una vez los 16 elementos del bloque con instrucciones SIMD
  • En los benchmarks mostró un rendimiento más de 2 veces superior a la búsqueda binaria con caché warm en Intel, y también más de 2 veces superior con caché cold en Apple; además, fue mejor que std::binary_search en todas las condiciones medidas
  • En vez de dividir la búsqueda por la mitad, usar una división en cuatro partes aumenta un poco la cantidad de instrucciones, pero en arreglos grandes sobre Intel aprovecha mejor el paralelismo a nivel de memoria, lo que mejora el rendimiento con caché cold
  • Como los algoritmos de libro de texto no fueron diseñados asumiendo el paralelismo de datos y de memoria de los CPU actuales, es posible lograr mejoras reales de rendimiento rediseñándolos según las características del hardware

Idea principal

  • La búsqueda binaria compara un valor por vez, pero los procesadores ARM de 64 bits y x64 modernos pueden comparar simultáneamente 8 enteros de 16 bits con una sola instrucción
  • Si se aprovecha esa capacidad del hardware, la unidad de búsqueda puede pasar de elementos individuales a bloques, reduciendo drásticamente la cantidad de comparaciones
  • En lugar de dividir el arreglo a la mitad, una búsqueda en 4 partes puede aumentar un poco la cantidad de instrucciones, pero es probable que el cuello de botella no esté ahí, y además permite aprovechar mejor el paralelismo a nivel de memoria

Forma básica de verificar pertenencia en arreglos ordenados

  • La forma más simple de comprobar si un valor existe en un arreglo ordenado es la búsqueda lineal, recorriendo un valor a la vez; en C++ se puede lograr el mismo efecto con std::find
  • En arreglos grandes, la búsqueda binaria es más rápida, repitiendo el proceso de descartar la mitad superior o inferior según el valor del punto medio
  • std::binary_search en C++ devuelve un booleano indicando si el valor existe
  • El formato Roaring Bitmap usa arreglos de enteros de 16 bits de tamaño entre 1 y 4096, y usa búsqueda binaria para verificar la existencia de valores

Estructura del algoritmo SIMD Quad

  • Divide un arreglo ordenado de enteros sin signo de 16 bits en bloques de tamaño fijo de 16 elementos
  • Usa el último elemento de cada bloque como clave de interpolación para reducir la búsqueda a un solo bloque con alta probabilidad de contener el valor objetivo, y luego revisa en paralelo con SIMD los 16 elementos de ese bloque
  • Pasos de funcionamiento:
    • Si hay menos de 16 elementos, hace una búsqueda lineal simple sobre todo el arreglo
    • Divide el arreglo en bloques de 16 elementos consecutivos, y el número total de bloques es num_blocks = cardinality / 16
    • Usa el último elemento de cada bloque como clave para comparar el valor objetivo con los puntos de 1/4 del rango actual y ajustar base
    • Si el bloque es válido, carga 16 elementos y realiza comparación de igualdad en paralelo usando NEON en ARM o SSE2 en x64
    • Los elementos restantes que no entran en un bloque completo se revisan con búsqueda lineal

Metodología de benchmark

  • Para cada tamaño de arreglo entre 2 y 4096 se generaron 100,000 arreglos ordenados de enteros sin signo de 16 bits
  • Para cada tamaño se hicieron 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: se busca 100 veces seguidas en el mismo arreglo para simular aciertos de caché
  • Lo medido fue el tiempo promedio por consulta, y se compararon búsqueda lineal (std::find), búsqueda binaria (std::binary_search) y SIMD Quad
  • Los sistemas de medición fueron Apple M4 (Apple LLVM) e Intel Emerald Rapids (GCC)

Resultados de medición

  • A medida que el arreglo crece, la búsqueda binaria supera claramente a la lineal, y con caché cold la búsqueda lineal sale más perjudicada por la mayor cantidad de accesos a datos
  • Plataforma Intel: con caché warm, SIMD Quad fue más de 2 veces más rápido que la búsqueda binaria; con caché cold la ventaja fue menor
  • Plataforma Apple: con caché cold, SIMD Quad fue más de 2 veces más rápido; con caché warm la ventaja fue más limitada
  • En todos los casos, SIMD Quad fue más rápido que std::binary_search
  • La parte SIMD reduce trabajo con instrucciones especializadas, y al requerir menos instrucciones y ramas, la causa de la mejora de velocidad es clara

Efecto de la búsqueda cuaternaria

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

Puntos clave de la implementación

  • La función simd_quad recibe un arreglo uint16_t, la cantidad de elementos cardinality y el valor buscado pos, y devuelve un booleano
  • gap se fija en 16; si cardinality < gap, busca con un bucle simple
  • El bucle de búsqueda por bloques, mientras n > 3, lee y compara los últimos valores de bloque en las posiciones 1/4, 2/4 y 3/4, y mueve base según la suma de los tres resultados de comparación
  • El bloque seleccionado compara 16 elementos en paralelo en dos grupos usando vceqq_u16 de ARM NEON o _mm_cmpeq_epi16 de x64 SSE2
  • En la sección de elementos restantes, devuelve si v == pos en el punto donde v >= pos

Conclusión

  • La búsqueda binaria de manual es un algoritmo razonable, pero puede hacerse significativamente más rápida en términos de rendimiento real
  • Muchos algoritmos estándar no fueron diseñados asumiendo 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
  • Podrían existir algoritmos aún mejores, y hacen falta enfoques más creativos
  • Código fuente
  • Intersecciones más rápidas entre arreglos ordenados con shotgun

Lecturas relacionadas

1 comentarios

 
GN⁺ 2026-05-01
Comentarios de Hacker News

  • Independientemente de la optimización de hardware de bajo nivel de la que habla Daniel Lemire, la búsqueda binaria o sus variantes de implementación solo son óptimas cuando no sabes nada más que el hecho de que los datos están ordenados o son monótonos
    Si tienes información previa sobre la distribución de los datos, puedes usarla para construir algoritmos mucho más rápidos. Un ejemplo es cómo una persona en un diccionario de papel puede saltar al grupo de páginas adecuado más rápido que con una búsqueda binaria pura
    Matemáticamente, buscar en una lista ordenada se parece más a encontrar la función inversa de una función monótona con un algoritmo de control de lazo cerrado, y también podrías definir una función de costo para usar descenso por gradiente o variantes aceleradas. Más en general, en vez de tomar la solución de una formulación demasiado abstracta, casi siempre es más eficiente aprovechar más información del problema específico que quieres resolver, y eso puede dar mejoras de velocidad escalables mucho mayores que las mejoras por constante que obtienes al aprovechar mejor el hardware

    • He pensado bastante sobre la búsqueda binaria, pero no he encontrado nada mejor que esta implementación: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
      1. Verificar en O(1) si es una lista densa
      2. Verificar el límite superior
      3. Búsqueda binaria con número fijo de iteraciones
        El número fijo de iteraciones le viene bien al predictor de saltos, y el bucle central también está bastante ajustado y optimizado para el hardware objetivo, evitando multiplicaciones. Los intentos de hacerlo más inteligente empeoraron el bucle y no dieron beneficios. También es difícil porque el formato de arreglo de structs tiene tamaño 12 y normalmente N es pequeño
    • Recuerdo haber leído un artículo sobre treaps donde, en vez de balancear el árbol, se usaban pesos para ajustar la profundidad de búsqueda como en la codificación Huffman, reduciendo el tiempo promedio de acceso cuando las frecuencias de acceso son distintas
      No lo guardé en marcadores, así que lo vuelvo a buscar como dos veces al año. La leyenda dice que sigo buscándolo hasta hoy
    • Sí, pero el punto clave es que muchas veces no puedes saber más sobre los datos
      Por eso en bases de datos el estándar son los árboles B. Los datos pueden ser cualquier cosa, y si cargas un gran lote de filas nuevas sus características pueden cambiar mucho en cualquier momento
      Puedes crear algoritmos que aceleren búsquedas con algo como descenso por gradiente, pero los árboles B ya son muy rápidos y además tienen muchas ventajas: rendimiento predecible en el peor caso y en requisitos de I/O, escaneos por rango, recorrido ordenado y soporte para condiciones por prefijo
      Sí puedes crear algoritmos de búsqueda más eficientes para distribuciones específicas de datos, pero muchas veces pierdes propiedades importantes. Aunque otro algoritmo pueda dar una estimación inicial más cercana, quizá sea más lento al encontrar el elemento final, o quizá su promedio sea mejor pero su peor caso sea tan malo que no sirva
      Incluso en un diccionario de papel, después de la primera estimación casi siempre usabas algo muy parecido a búsqueda binaria, y esa estimación inicial solo te ahorraba unas pocas etapas. Una vez que llegabas al bloque de páginas adecuado, lo normal era hojear linealmente más de lo necesario; una búsqueda binaria estricta quizá sería más rápida, pero también hay que equilibrarla con el tiempo de pasar páginas
    • La idea de que “usar más información sobre el problema específico que quieres resolver es más eficiente” es obvia y profunda a la vez. Cuanta más información ya tienes, más información ya tienes
    • Fritz Henglein hizo trabajo interesante sobre ordenamiento/agrupación rápida. El paper clave parece ser Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
      Ed Kmett refinó esa idea en la biblioteca discrimination[2] para Haskell, y la charla técnica relacionada[3] también es 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

  • ¿La “búsqueda cuaternaria” no es al final solo una búsqueda binaria con una iteración desenrollada? Para encontrar el intervalo donde está el elemento, el número de comparaciones parece más o menos parecido, solo que procesa 4 a la vez en vez de 2. Da la impresión de que desenrollar el bucle lograría lo mismo

    • Es más complicado que eso. Los procesadores modernos hacen ejecución especulativa, predicen el resultado de una comparación y siguen avanzando por una rama hasta que descubren que se equivocaron o llegan a un límite interno. Si fallan, descartan ese trabajo especulativo, pagan una penalización de algunos ciclos y recomienzan desde otro punto
      En la práctica, desde la perspectiva del procesador, todos los bucles ya están algo desenrollados, y solo queda el pequeño overhead del bucle mismo. En búsqueda binaria, el costo principal es traer datos desde memoria o caché, así que la verdadera pelea es lograr pedir lo antes posible los datos que vas a necesitar después para esperar menos a que lleguen
      La diferencia de algoritmos como la búsqueda cuaternaria es que, en vez de traer por adelantado en profundidad solo un lado de cada rama, hacen prefetch superficial de todos los casos posibles. Así, los prefetches que al final serán necesarios se emiten de todos modos, y se usa un poco menos de ancho de banda en datos que no se usarán en la ruta real de ejecución
      Para predecir el rendimiento real de un algoritmo de búsqueda, el “número de comparaciones” casi no sirve como métrica. El cuello de botella no es cuántas comparaciones puedes hacer, sino qué tan bien aprovechas el ancho de banda de memoria y caché. Si consideras a fondo el comportamiento de ramas en procesadores modernos, podrías verlo como una forma de desenrollado de bucle
    • En cierto sentido sí puede verse como un poco de desenrollado de bucle. La mejora de rendimiento no viene de reducir mucho el número de instrucciones o de lecturas de memoria, sino de aliviar las dependencias entre operaciones para evitar una ejecución puramente serial. También podría verse como algo parecido a ejecutar especulativamente ambos lados de una rama
    • La búsqueda cuaternaria básicamente hace, al mismo tiempo que la comparación de la iteración actual, las dos comparaciones posibles de la siguiente iteración. Es un poco más compleja que un simple desenrollado de bucle
      De todos modos, ambas búsquedas son O(log N) con distintas constantes. En clases de algoritmos las constantes no importan mucho, pero en la realidad sí pueden importar bastante
    • Hasta cierto punto sí, pero también elimina la dependencia de datos entre los pasos desenrollados
    • Porque los procesadores no funcionan como solemos imaginar ingenuamente

  • Hace poco también escribí un artículo[1] sobre búsqueda exponencial[2]. Es un algoritmo útil cuando tienes que hacer búsqueda binaria repetidamente en un arreglo y los elementos buscados también vienen ordenados; en nuestra carga de trabajo dio una mejora de 8x
    [1] https://lalitm.com/post/exponential-search/
    [2] https://en.wikipedia.org/wiki/Exponential_search

    • La búsqueda exponencial 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 búsqueda binaria entre 2048 y 4096 y puedes encontrar al usuario más reciente y, de paso, el número de usuarios. Es útil saberlo cuando investigas a una empresa SaaS competidora

  • Como la CPU siempre accede a toda una línea de caché, normalmente 64 bytes, parece mejor buscar toda la línea de caché. Una vez que los datos ya están dentro de la CPU, son casi gratis
    Así que me gustaría probar una variante de búsqueda “binaria” donde inspeccionas todos los valores de la línea de caché del medio y, si no hay coincidencia, te vas a la izquierda o derecha. Buscar dentro de una línea de caché se puede hacer con una sola instrucción SIMD de 512 bits. Una línea de caché de 64 bytes equivale a 32 enteros de 16 bits, así que podría ser casi 32 veces más rápido que una búsqueda binaria simple o, al menos, reducir 32 veces los accesos a memoria, que en la mayoría de programas reales sería lo dominante

    • La probabilidad de encontrar el valor objetivo en las líneas de caché superiores del árbol de búsqueda binaria, es decir, del vector ordenado, es baja. En cambio, conviene usar los datos extra dentro de la línea para reducir el rango de búsqueda, y eso lleva a árboles B o árboles B+
      Si usas claves de 4 bytes y punteros a hijos de 4 bytes, o índices de arreglo, un nodo interno puede llenar exactamente una línea de caché de 64 bytes con 7 claves, 8 punteros a hijos y 1 puntero siguiente. En 1 millón de elementos, la profundidad del árbol baja de cerca de 20 a cerca de 7, y es probable que los primeros niveles se queden en caché
      Con algo de trabajo puedes acelerar la búsqueda dentro de un nodo de árbol B usando SIMD, pero la dependencia de datos es muy alta

  • En arreglos más pequeños, una búsqueda lineal con valor centinela al final ya es difícil de vencer. Pero parte de por qué esta afirmación se siente ambigua es que “pequeño” es una condición demasiado difusa para percibirse bien

    • Eso no es cierto. Si ves el excelente benchmark de este artículo, la búsqueda lineal empieza a quedarse atrás alrededor de 200~400 elementos
      En general me gustó el artículo. Explora a fondo algo que siempre me había dado curiosidad, incluso con experimentos de eliminación muy útiles
    • No es de eso de lo que trata este artículo

  • Hice algunas pruebas de búsqueda en arreglos pequeños, de 16 a 32 elementos, y la búsqueda binaria resultó ser de las peores por la cantidad de ramas. En arreglos pequeños, el método más rápido fue una búsqueda lineal sin ramas
    Recorres todos los elementos sin cortar el bucle a la mitad. Por ejemplo, si quieres saber si cierto número está en el arreglo, combinas con OR lógico el resultado de revisar todos los elementos. No usé SIMD, pero en arreglos pequeños las ramas son tan caras que es más rápido revisar todo sin ramas

    • Me pregunto si es más rápido porque al prefetcher le gusta ese patrón de acceso

  • La explicación del algoritmo me pareció un poco confusa
    La parte de SIMD solo se usa en la etapa final, es decir, al buscar entre los últimos 16 elementos
    La parte de búsqueda cuaternaria consiste en revisar 3 puntos para crear 4 caminos, pero no está buscando simplemente la clave correcta sino el bloque correcto
    Los detalles son interesantes: el autor usa el último elemento de cada bloque para la búsqueda cuaternaria. Me pregunto cómo cambiaría el algoritmo si usara el primer elemento o un elemento arbitrario

  • La intuición clave aquí de comparación múltiple con SIMD parece aplicable también a una escala mayor que la etapa final
    La idea general sería: a) traer varios elementos en 16 posiciones uniformemente espaciadas con gather b) compararlos en paralelo con instrucciones SIMD c) concentrarse en el bloque correcto d) cuando el bloque sea pequeño, cambiar a búsqueda lineal; si no, repetir el ciclo de gather/comparación
    Las instrucciones gather leen de memoria no contigua y, para una búsqueda binaria, leerían más de lo necesario. Aun así, si permiten comparaciones en múltiples direcciones y condensan 4 etapas de búsqueda binaria, parecería que podrían ganar en tablas grandes
    No todos los tipos de datos permiten una comparación completa de 16 vías. La búsqueda sobre float64 está limitada a comparaciones de 8 vías incluso con AVX-512, pero int32 y float32 sí permiten 16 vías

    • gather es extremadamente lento. Si te importa la eficiencia, lo evitarías
      Creo que es muy probable que la búsqueda binaria real siga siendo más rápida que un enfoque basado en gather

  • Los algoritmos clásicos de ciencias de la computación, en la práctica, fueron “diseñados” para CPUs sin paralelismo. Sin múltiples núcleos, sin Hyper-threading, sin instrucciones SIMD, con todos los accesos a memoria costando lo mismo, sin conceptos como latencia de caché L1/L2/L3, y asumiendo datos generales/aleatorios
    En cuanto sales de cualquiera de esas suposiciones, aparecen muchos ajustes posibles para mejorar el rendimiento
    Los algoritmos clásicos son un excelente punto de partida para desarrollar soluciones más optimizadas una vez que conoces mejor la forma específica de los datos o las características/capacidades de cierta CPU
    Cuando llegas a la punta más afilada de la optimización, normalmente terminas mirando cómo se almacenan y acceden los datos en memoria, y si un cambio para mejorarlo no perjudica etapas posteriores. Hace mucho, en un trabajo, alguien optimizó demasiado cierta parte del código, pero esa optimización terminó expulsando de caché mucha información necesaria después, y la aplicación completa se volvió más lenta
    Esto probablemente se acerca a la quinta regla de programación de Rob Pike, o más bien a una reformulación de algo que dijo Fred Brooks en The Mythical Man Month. Referencia: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...

  • Cuando era adolescente, me pasé un fin de semana entero pensando que, si la búsqueda binaria era buena porque reduce el espacio de búsqueda a la mitad en cada paso, entonces la búsqueda ternaria debería ser mejor porque lo reduce a un tercio
    En vez de comparar solo el valor del medio, comparas el valor en 1/3 y, si es demasiado bajo, comparas el valor en 2/3
    Pero pensé que, aunque en cada paso reducías por 1/3 en vez de por 1/2 como en búsqueda binaria, hacías en promedio 3/2 veces más comparaciones, así que al final quedaba igual
    Corrección: viendo la respuesta de zamadatix, en realidad como en 2/3 de los casos hay que hacer 2 comparaciones, el promedio es 5/3

    • Ese enfoque ternario en realidad no hace 3/2 comparaciones por paso en promedio
      Primer tercio: 1 comparación
      Segundo tercio: 2 comparaciones
      Tercer tercio: 2 comparaciones
      (1+2+2)/3 = 5/3 comparaciones en promedio. Es fácil confundirlo con 50% porque “a veces comparas 1 vez y a veces 2”, 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í se puede mostrar que, en número total promedio de comparaciones, la búsqueda ternaria es un poco peor: 5/3*Log_3[n] = 1.052... * Log_2[n]
      O sea, disminuye el número de pasos, pero en promedio exige más comparaciones para llegar al final. Esto en general aplica a todos los esquemas de este tipo, es decir, cuando el factor de partición es mayor que 2. Claro, hay varias suposiciones detrás, como distribución uniforme del valor buscado y costo idealizado de las operaciones, y justo ahí entra la discusión del artículo principal
    • Resulta que esa idea adolescente sí tenía algo de valor
      No como versión ternaria del algoritmo de búsqueda binaria. Eso en realidad no sería una búsqueda ternaria de verdad, sino más bien una búsqueda binaria sesgada. Como la comparación es esencialmente binaria, todos los algoritmos de búsqueda basados en comparaciones son una forma de búsqueda binaria, y elegir algo distinto al elemento central es menos eficiente en términos de complejidad algorítmica. Aun así, en hardware real podría ser mejor bajo ciertas condiciones. Para tener una búsqueda ternaria auténtica necesitarías una comparación de 3 vías como operación básica
      La cosa se pone interesante al considerar la “eficiencia de radix”[1]. La mejor elección es 3, el número natural más cercano a e. También se relaciona con búsqueda en árboles, donde un árbol ternario puede ser mejor que uno binario
      [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
    • En lugares como disco, donde la búsqueda rápida no es posible, podrías usar por ejemplo un árbol B de 128 vías. Traer 128 claves no cuesta mucho más que traer 1, pero te ahorra 7 lecturas adicionales
    • ¿Y luego imaginaste una CPU con comparadores ternarios?
    • Desde tu adolescencia, las CPUs se han ensanchado dramáticamente tanto en ancho de ejecución como en capacidades vectoriales. A medida que sube el throughput, el equilibrio se desplaza hacia gastar más operaciones para reducir cadenas de dependencia
      Así que, aunque en las CPUs de esa época esa idea no era viable, quizá en las actuales sí tenga más posibilidades