La búsqueda binaria branchless más rápida

 (mhdm.dev)
1 puntos por GN⁺ 2023-08-13 | 1 comentarios | Compartir por WhatsApp
  • sb_lower_bound mantiene la misma interfaz que std::lower_bound y, cuando la rama de comparación se compila como movimiento condicional (cmov), muestra resultados hasta 2 veces más rápidos que la búsqueda binaria común
  • El resultado de la comparación en una búsqueda binaria no permite saber de antemano la posición buscada, por lo que son frecuentes las fallas de predicción de ramas; en x86, la opción clang -mllvm -x86-cmov-converter=false ayuda a reducirlas
  • Esta implementación reduce length a la mitad en cada iteración y actualiza solo first según el resultado de la comparación, reduciendo la cantidad de instrucciones; en el rango 2^k <= n < 2^(k+1) siempre realiza k+1 comparaciones
  • En benchmarks con clang -cmov, los tiempos promedio de ejecución fueron std::lower_bound 61.30 ns, sb_lower_bound 33.24 ns y bb_lower_bound 32.73 ns; las medias geométricas también mostraron una gran diferencia: 39.17 ns, 19.81 ns y 21.33 ns, respectivamente
  • En búsquedas de strings de 8 bytes, donde la función de comparación es lenta, hubo casos en los que std::lower_bound quedó ligeramente por delante; en arreglos grandes, una variante con prefetching fue en promedio unas 2.3 veces más rápida que std::lower_bound

Estructura básica de sb_lower_bound

  • sb_lower_bound es una función de C++ con la misma forma que std::lower_bound
    • Las entradas son first, last, value, comp
    • El valor de retorno es un iterador a la primera posición donde la comparación falla; si todos los elementos cumplen la condición, devuelve last
  • El bucle principal reduce length a la mitad y mueve first hacia adelante solo cuando comp(first[length], value) es verdadero
  • Aquí, “branchless” no significa que desaparezca el if, sino que ese if se compila como una instrucción de movimiento condicional, como cmov, en lugar de un salto condicional
  • En clang, al usar la opción -mllvm -x86-cmov-converter=false, esta forma puede compilarse como movimiento condicional

Dónde se vuelve lento std::lower_bound

  • Una búsqueda binaria típica compara el elemento del medio con value y luego elige el intervalo izquierdo o derecho
  • Cuando no se conoce la posición del objetivo de búsqueda, if (comp(first[half], value)) suele convertirse en una rama difícil de predecir
  • La CPU ejecuta instrucciones por adelantado mediante predicción de ramas, pero si la predicción falla, debe descartar el trabajo realizado
  • Con movimientos condicionales, se puede elegir el valor según el resultado de la comparación reduciendo los saltos condicionales
  • clang -cmov también puede convertir algunos if/else de std::lower_bound en movimientos condicionales, lo que lo hizo alrededor de un 25% más rápido
  • gcc no tiene una buena opción para forzar movimientos condicionales en la misma situación, y actualmente tampoco emite código branchless para sb_lower_bound, independientemente del nivel de optimización

Búsqueda “óptima” desde la perspectiva de la cantidad de comparaciones

  • Aquí, “óptima” se refiere a una búsqueda binaria con el mínimo número de comparaciones
  • En una lista de tamaño n, los posibles resultados de std::lower_bound son n+1: las n posiciones de elementos más una posición final
  • Si el tamaño de la lista es 2^k - 1, hay 2^k resultados posibles, y como cada comparación aporta 1 bit de información verdadero/falso, el número óptimo de comparaciones es k
  • En casos “nice” con longitud 2^k - 1, es posible una búsqueda óptima con un bucle muy corto
  • Si la longitud no coincide, puede producirse un acceso fuera de rango, como cuando value es 4 en [0, 1, 2, 3, 4, 5]

Características de rendimiento y restricciones de sb_lower_bound

  • Al dividir un intervalo de longitud par, sb_lower_bound en algunos casos no salta suficientes elementos aunque el resultado de la comparación sea verdadero
  • En el rango 2^k <= n < 2^(k+1), siempre realiza k+1 comparaciones
  • En el mismo rango, std::lower_bound realiza k o k+1 comparaciones, con un promedio de aproximadamente log2(n+1) comparaciones
  • Aunque puede realizar más comparaciones, la cantidad de instrucciones dentro del bucle es mucho menor, por lo que el tiempo total de ejecución resulta más rápido
  • Si la función de comparación es muy lenta, la diferencia entre k+1 y log2(n+1) comparaciones puede afectar el rendimiento
  • Para forzar movimientos condicionales en gcc, se puede usar cmov con ensamblador inline específico de x86, pero el método simple aumenta la cantidad de instrucciones y las alternativas requieren escribir ensamblador por separado para cada tipo

La variante más rápida bb_lower_bound

  • bb_lower_bound divide el intervalo de otra manera hasta que la longitud queda en la forma 2^k - 1, y luego busca con un segundo bucle rápido
  • length & (length + 1) se usa para determinar si la longitud tiene la forma 11..1, es decir, 2^k - 1
  • Para longitudes no estándar, usa un valor MAGIC auto step = length / 8 * 6 + 1 para acercarse rápidamente a un intervalo “nice”
  • En general, step debe ser al menos length / 2 para poder pasar con frecuencia al bucle rápido, pero si queda demasiado cerca de length, se pierde la ventaja de la búsqueda binaria
  • Debido al break, bb_lower_bound tiene ramas
  • Usar una tabla con el step más rápido precalculado para todas las longitudes sigue siendo un camino aún no explorado

La implementación completamente branchless no fue más rápida

  • En una máquina de 64 bits, el bucle de sb_lower_bound itera como máximo 64 veces, por lo que es posible crear una versión “completamente branchless” que elimine incluso la comprobación de length usando switch y fall-through intencional
  • Esta estructura salta a la posición de código correspondiente al número de comparaciones necesarias mediante std::bit_width(length)
  • En rendimiento real, no fue más rápida
  • Las CPU x86 modernas manejan bien ramas predecibles como las condiciones de bucle, por lo que eliminar la comprobación de length no aportó beneficios
  • También se concluyó que el bucle común es mejor porque evita plantillas, macros y copiar-modificar 64 casos

Resultados de benchmark

  • Los resultados en tiempo promedio de ejecución (ns) con clang -cmov fueron los siguientes
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • En la media geométrica del tiempo de ejecución (ns), sb_lower_ también fue el más bajo
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound es una variante que usa first += comp(first[length], value) * (length + rem) en lugar de if, para inducir a gcc a generar movimientos condicionales
  • Como esta optimización podría desaparecer en una próxima versión de gcc, requiere comentarios y precaución
  • Los comandos de benchmark usaron g++-10, clang++-10 y clang++-10 -mllvm -x86-cmov-converter=false, con -march=haswell
  • -march=native o no especificar -march no afectó mucho el ranking, y las pruebas se realizaron en un Intel i7 Kaby Lake

Medición de fallas de predicción de ramas

  • Una ejecución común de clang medida con perf registró alrededor de 6,940 millones de branches y unos 1,200 millones de branch-misses, con una tasa de branch-misses de 17.34%
  • La ejecución con clang -cmov registró alrededor de 4,070 millones de branches y unos 35.95 millones de branch-misses, reduciendo la tasa de branch-misses a 0.88%
  • -cmov elimina alrededor de 2,900 millones de ramas y unos 1,200 millones de fallos de rama
  • Las ramas eliminadas eran ramas que fallaban la predicción con una probabilidad aproximada del 41%
  • Esto se acerca al 50% esperable en una rama totalmente impredecible

Con funciones de comparación lentas, los resultados cambian

  • Para evaluar una situación con una función de comparación más lenta, se probaron búsquedas de strings de 8 bytes
  • En tiempo promedio de ejecución (ns), std::lower_bound fue ligeramente más rápido o similar a sb_lower_bound
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • En este caso, std::lower_bound es apenas, pero de forma consistente, más rápido que sb_lower_bound
  • Una biblioteca puede apuntar al mejor rendimiento usando sb_lower_bound cuando opera directamente sobre tipos primitivos, y std::lower_bound en los demás casos

Diferencias visibles en el ensamblador

  • El hot loop de std::lower_bound con clang -cmov incluye movimientos condicionales como cmova y cmovbe, pero usa varias instrucciones para actualizar la longitud y la posición
  • El hot loop de sb_lower_bound calcula la mitad de la longitud, el resto y el puntero a mover, y luego actualiza first con cmova
  • El ensamblador de branchless_lower_bound es muy corto y limpio, pero en las pruebas de rendimiento sb_lower_bound obtuvo mejores resultados con menor overhead

Actualización: sb_lower_bound más corto

  • Tras un comentario del autor de orlp.net, sb_lower_bound puede refactorizarse para reducir las instrucciones del ensamblador del hot loop de 9 a 8
  • La clave es que length - half equivale a half + length % 2
  • La forma refactorizada calcula half = length / 2, y si la comparación es verdadera ejecuta first += length - half, luego actualiza length = half
  • Con clang -cmov, el tiempo promedio de ejecución mejoró levemente de unos 33 ns a unos 32 ns

En arreglos grandes, el prefetching es efectivo

  • El prefetching sugerido en los comentarios consiste en traer a la caché L1/L2 la memoria necesaria antes de tiempo, para reducir la latencia cuando se accede realmente
  • Las latencias de ejemplo son aproximadamente 4 ciclos para L1, 12 ciclos para L2, 40 ciclos para L3 y 200 ciclos para memoria
  • Tanto gcc como clang soportan __builtin_prefetch()
  • Al hacer prefetch de la posición length / 4, 1 de cada 2 se desperdicia; si también se agrega hasta length / 8, 5 de cada 6 se desperdician
  • El propio cálculo de las posiciones de prefetch y las llamadas también tienen overhead, y en un hot loop acortado ese costo es importante
  • Varias estrategias de prefetch no ayudaron en arreglos de menos de 256 KB
  • A partir de 256 KB, sbp_lower_bound con prefetching mejoró el tiempo promedio de ejecución de unos 32 ns a unos 26 ns en pruebas de hasta aproximadamente 4 millones de entradas, es decir, 16 MB
  • En pruebas ampliadas luego hasta unos 128 millones de entradas, es decir, 512 MB, la versión con prefetching fue unas 2.3 veces más rápida que std::lower_bound en tiempo promedio
    • La comparación fue std::lower_bound alrededor de 161 ns y la versión con prefetching alrededor de 71 ns

Observaciones y alternativas en datasets grandes

  • En tamaños muy grandes, el std::lower_bound branchless generado por clang -cmov fue más lento que la versión con ramas
  • Las CPU modernas pueden seguir ramas predichas y avanzar con cargas de memoria y ejecución especulativa, lo que en la práctica puede actuar como prefetching
  • sbpm_lower_bound es una versión de sbm_lower_bound con prefetching, e induce a gcc a generar código branchless mediante multiplicación booleana
  • Entre 1 millón y 10 millones de elementos hubo saltos en la gráfica de rendimiento, lo que sugiere que teóricamente podría haber margen para una implementación más rápida
  • Sin embargo, el código de prefetching se vuelve cada vez más complejo y acumula constantes mágicas; se considera que cuanto mayor sea la complejidad, menor será la probabilidad de contribuirlo a gcc/libstdc++ o llvm/libc++
  • Una alternativa que rompe las restricciones de std::lower_bound es Eytzinger Binary Search, que reorganiza el arreglo de entrada en forma de heap de medianas binarias para hacer las consultas más cache-friendly
  • En una prueba de árbol 16-ario de enteros de Sergey Slotin en CppCon 2022, los resultados fueron de 7 a 15 veces más rápidos que std::lower_bound

Código y condiciones de uso

  • Si la búsqueda o la comparación es la parte más lenta del programa y al procesador le resulta difícil predecir los resultados de las comparaciones, en x86 se puede probar la opción de clang -mllvm -x86-cmov-converter=false
  • Si se necesita una búsqueda binaria más rápida, se puede probar sb_lower_bound; en gcc, sbm_lower_bound también es una opción
  • El código está publicado bajo licencia MIT
  • El código y los benchmarks pueden consultarse en github.com/mh-dm/sb_lower_bound/

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-08-13
Opiniones de Hacker News

  • Cada vez que veo que la gente intenta eliminar ramas, me pregunto si sabe que los fallos de predicción de ramas que detienen pipelines largos no son un elemento indispensable de la arquitectura de CPU.
    Los pipelines son largos porque se hacen muchos análisis y transformaciones justo antes de la ejecución, pero como no son algoritmos con mucha dependencia de estado, la mayor parte podría hacerse por adelantado.
    La CPU Transmeta Crusoe funcionaba de esa manera, y se puede imaginar un mundo en el que no haya que preocuparse por las ramas.
    Si se mira más a fondo, toda operación es una rama que observa el estado de los bits y cambia el resultado, pero esas ramas locales dentro de la ALU no son ramas sobre el pipeline principal, así que no perjudican mucho el rendimiento.

    • ¿Eres Dave? :-) Hace tiempo había un paper que comparaba CISC superescalar y RISC uniescalar desde el punto de vista del rendimiento por unidad de tiempo y de las instrucciones por ciclo.
      Recuerdo haberle dicho también a srk en esa época que elegir entre IPC y rendimiento como métrica influye en qué se considera bueno o malo.
      El lado de IPC asumía que, si se lograba un IPC más alto, el proceso de fabricación subiría la frecuencia y todos ganarían; el lado del rendimiento tomaba un enfoque más realista: la ley de Moore murió, y si haces correr el silicio más rápido se derrite, así que gana quien diseñe la ISA de forma inteligente.
      En los últimos 20 años ambos lados tuvieron éxitos y frustraciones, y es interesante que hoy RISC-V esté volviendo a este tipo de preguntas en arquitectura de CPU.
      También es un buen lugar para seguir cómo se agregan ideas superescalares modernas sobre la base de la flexibilidad del conjunto de instrucciones, y a largo plazo creo que ese lado va a ganar.
    • Esto está completamente equivocado.
      La traducción de Transmeta no eliminaba el costo de las ramas.
      Recuerdo que Linus, que trabajaba en Transmeta, dijo en un hilo de comp.arch algo parecido a que “el trabajo de la CPU es generar fallos de caché lo más rápido posible”.
      Los fallos de caché obligatorios existen, y ningún JIT puede eliminarlos.
      En el mundo real, incluso con cachés enormes como las actuales, tampoco se pueden evitar los fallos por capacidad.
      Itanium también creía que podía eliminar el costo de las ramas mediante análisis estático, y basta recordar cómo terminó eso.
      Ojalá los programadores leyeran algunos libros de arquitectura de computadoras antes de concluir con tanta confianza que pueden crear fácilmente algo mejor que los procesadores modernos.
      Creo que están subestimando por al menos 7 dígitos la escala del esfuerzo intelectual que hay dentro de los procesadores actuales.
    • Puede no haber estado, pero depende mucho de factores que no se conocen en tiempo de compilación.
      Uno de ellos son los datos de entrada que se procesan.
      La búsqueda binaria es justamente un caso así: el compilador no sabe en qué posición se encontrará el resultado.
      Otro es la microarquitectura, en especial la jerarquía de caché y la configuración de las unidades de ejecución.
      Si se cambia a una ISA con instrucciones parecidas a las microoperaciones de las CPU actuales, habría que recompilar para cada microarquitectura.
      Dicho eso, técnicamente esto se puede resolver con un JIT del sistema operativo, al estilo de las GPU actuales: distribuir los programas en formato de bytecode (DXBC, SPIR-V, NVPTX) y que el driver de GPU en modo usuario los recompile a instrucciones reales del hardware.
      La variable más grande es que otros hilos de CPU ejecutan código desconocido.
      Incluso si se elimina el hyperthreading para hacer independientes los núcleos, seguirán existiendo recursos compartidos a nivel de todo el chip, como la caché L3, la memoria externa, el ancho de banda de I/O, la energía y el calor.
    • Creo que el punto clave está en la definición de rama.
      Si redefinimos todo como Branch™, entonces algunas Branch™ se pueden calcular por adelantado, incluyendo cosas que en realidad no son ramas.
      Pero la eliminación de ramas de la que se suele hablar no trata de casos como if/else, donde el camino de cálculo se divide de verdad.
      Incluso en ese mundo podrían hacerse optimizaciones útiles, pero estarían limitadas a las Branch™ que intentan calcular simultáneamente varios resultados futuros.
    • También se podría reformular la razón por la que los pipelines son largos diciendo que dentro del procesador hay mucho trabajo independiente que se puede hacer al mismo tiempo.
      Cada vez que hay una operación que puede realizarse de forma independiente, aparece la posibilidad de ejecutarla en paralelo.
      No hablo solo de decodificar, traer instrucciones y ejecutar.
      Si tienes una ALU y un shifter independientes, puedes desplazar mientras sumas; y si tienes un sumador y un multiplicador dedicados, no hay razón para no intentar ambas cosas al mismo tiempo.
      Eso, a su vez, hace que quieras tener varias instrucciones en curso a la vez, lo que significa que debes poder traer y decodificar instrucciones más rápido de lo que las procesas.
      Además, naturalmente lleva a situaciones en las que quieres reordenar para que N instrucciones Add no impidan ver un Shift independiente.
      Puedes pensar que la arquitectura actual es más compleja de lo necesario, y puede que no estés equivocado.
      Aun así, hay una cantidad enorme de ingeniería invertida en crear la estructura actual, así que si crees que con otro enfoque se podría hacer algo mucho más rápido, conviene investigar a fondo qué tan precisa es esa afirmación.

  • En la parte que dice “Ojalá existiera un lenguaje bare metal limpio y rápido para escribir todo esto…”, el autor agregó notas al pie de “BUT RUST..” y “BUT ZIG..”, pero me pregunto qué tal sería Nim
    Parece que tiene una implementación de biblioteca nativa de lowerBound: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    Estrictamente hablando no es un lenguaje “bare metal”, pero compila a C o C++, así que sería interesante ver a qué código compila aquí
    Y también me pregunto cuál es el problema con C

  • No estoy muy seguro de que esto siga siendo lower_bound
    Puede que haya leído mal el código, pero cuando hay duplicados parece devolver cualquier coincidencia, no la primera coincidencia
    Si la función de comparación busca un prefijo de cadena específico para autocompletado, incluso en una lista única puede haber varios elementos que coincidan, y en ese caso quieres el primer elemento de la lista

    • Como cada vez que coincide reduce la longitud restante a la mitad, y solo sale del bucle cuando la longitud es 0, debería devolver el primer elemento
    • Me parece bien que haya una opción más rápida cuando no te importa exactamente cuál coincidencia sea
    • A mí me parece que devuelve la primera coincidencia
      Me da curiosidad por qué piensas que no

  • Ojalá todas las publicaciones de blog empezaran como esta: “Seguro están ocupados, así que voy directo al grano. Aquí está la implementación de búsqueda binaria en C++ más rápida, general y simple”

  • La biblioteca estándar de Zig no llama a C++ para hacer búsqueda binaria
    La búsqueda binaria actual está aquí: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • No lo entiendo bien
    El problema de la búsqueda binaria y las ramas no es la rama en sí, sino que hasta terminar la comparación no sabes qué ubicación de memoria del arreglo traer después
    Da igual si usas una rama u otra cosa; al final el problema es qué quieres que haga el procesador
    Hay una dependencia de datos
    Antes de leer el índice del medio, no sabes si buscar en la mitad superior o en la inferior
    Puedes especular y emitir lecturas para ambos lados, y eso resuelve la dependencia, pero aumenta el tráfico de memoria
    La clave es si ese es el compromiso correcto; simplemente eliminar las ramas no es la respuesta

    • Para arreglos grandes, la precarga sí es el compromiso correcto
      Se trata al final del artículo: https://mhdm.dev/posts/sb_lower_bound/#prefetching
    • Correcto
      Por eso una búsqueda binaria correctamente más rápida usa la disposición de arreglo de Eytzinger: https://algorithmica.org/en/eytzinger
    • Si el arreglo cabe completamente en la caché L1, ¿el costo de una mala predicción de rama no es mucho mayor que traer datos de memoria?

  • En mi procesador Cascade Lake, -mllvm -x86-cmov-converter=false reduce casi a la mitad el rendimiento de la búsqueda binaria
    Las cifras son nanosegundos por bsearch en un arreglo uint32 de 100 MB
    Parece que clang 15.0.7 es mucho peor que gcc 13.2.1 en esta optimización específica de código
    El ensamblador se puede ver aquí: https://godbolt.org/z/cbx5Kdjs6
    El ensamblador de gcc se ve mucho más limpio

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • Entonces hay que ver https://mhdm.dev/posts/sb_lower_bound/#prefetching
      100 MB es lo suficientemente grande como para que la versión con ramas salga ligeramente favorecida, pero no porque sea mejor, sino por las características de la ejecución especulativa de x86

  • ¿Alguien sabe a dónde debía apuntar originalmente el enlace “BUT RUST”?
    Como no estaba fijado a una versión, parece que ya se rompió, y quizá apuntaba a la mitad del comentario de documentación de starts_with

    • Viendo las capturas de archive.org justo antes [1] y justo después [2] de que se publicara el artículo, parece que quería apuntar a esta línea de código, que ahora es la línea 2779 [3]
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Era para enlazar a la implementación de búsqueda binaria de Rust
    Se actualizó a https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

  • Es interesante que el resultado no se mantenga con una función de comparación comp más compleja
    En el artículo se pensó en un escenario de búsqueda binaria algo realista, en el que la función de comparación es lenta, como con IDs, números de teléfono, cuentas o palabras clave, y por eso se probó la búsqueda de cadenas de 8 bytes
    En este caso, std::lower_bound es apenas, pero consistentemente, más rápido que sb_lower_bound; y se dice que, para obtener siempre el mejor rendimiento, la biblioteca debería usar sb_lower_bound cuando trata directamente con tipos primitivos, y std::lower_bound en los demás casos
    Me gustaría ver el análisis de esto

    • Creo que esto ocurre porque, gracias a la predicción de ramas, se pueden poner varias comparaciones en el pipeline al mismo tiempo y deshacerlas cuando el predictor se equivoca
      Si los datos y las entradas son verdaderamente aleatorios, la predicción fallará aproximadamente la mitad de las veces
      El enfoque con CMOV queda bloqueado por la dependencia de datos después de la función de comparación
      En promedio, el enfoque con ramas realiza dos comparaciones a la vez, mientras que CMOV realiza una, así que se esperaría que haya un punto de cruce cuando el tiempo de comparación supere la penalización por fallo de predicción de ramas
    • Si es así, probablemente exista una versión de búsqueda binaria mucho mejor para tipos primitivos
      Algo que armé rápidamente con SIMD hace tiempo era 3 veces más rápido que std::lower_bound antes de topar con el ancho de banda de memoria: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • En el artículo no encontré ninguna garantía sobre el conjunto de datos de entrada ni sobre el contenido de las claves de búsqueda, salvo que eran “impredecibles”
      Se asume que son puramente aleatorios, pero si esas cadenas de 8 bytes no son información pura, los predictores de ramas modernos pueden rendir fácilmente mejor que cmov

  • Parece que el atributo unpredictable ahora afecta el pase de conversión a cmov
    Es del 1 de junio, así que probablemente entre en clang 17/18: https://reviews.llvm.org/D118118