La búsqueda binaria sin ramas más rápida

• Este artículo analiza una implementación general de búsqueda binaria en C++ que es el doble de rápida y más corta que la función estándar std::lower_bound.
• La nueva implementación es "sin ramas" porque se compila usando instrucciones de movimiento condicional en lugar de ramas/saltos condicionales.
• La búsqueda binaria funciona dividiendo una lista ordenada en dos partes en el elemento medio y comparando el valor medio con un valor dado. Según el resultado de la comparación, decide en cuál de las dos sublistas seguir buscando.
• El artículo también analiza el concepto de predicción de ramas, una técnica con la que el procesador ejecuta instrucciones en paralelo para aumentar la velocidad. Sin embargo, como la búsqueda binaria es impredecible, la predicción de ramas no es ideal.
• El autor presenta una nueva implementación de búsqueda binaria, sb_lower_bound, que es más rápida que la implementación estándar y que la versión branchless_lower_bound. Es más rápida porque tiene muchas menos instrucciones dentro del bucle.
• El autor también presenta una versión aún más rápida, bb_lower_bound, que usa otro método para dividir la lista de búsqueda.
• El artículo concluye sugiriendo que, si la parte más lenta de tu programa incluye búsquedas y/o comparaciones que el procesador no puede predecir, pruebes clang con -mllvm -x86-cmov-converter=false. Si necesitas una búsqueda binaria más rápida, prueba sb_lower_bound.
• El autor también proporciona código para las nuevas implementaciones de búsqueda binaria y analiza en detalle el rendimiento de cada una.
• El artículo fue actualizado con una versión refactorizada de sb_lower_bound que reduce la cantidad de instrucciones de ensamblador en el bucle crítico de 9 a 8, lo que mejora ligeramente la velocidad.
• El autor también analiza el concepto de prefetching, que consiste en traer ciertas partes de la memoria a la caché para que, cuando los datos precargados realmente se necesiten, solo haya latencia de caché L1/L2. También se ofrece una versión de sb_lower_bound con prefetching agregado para 256 KB o más.
• El artículo fue escrito por Mihail Dumitrescu y publicado el 24 de junio de 2023.

[GN⁺]

Opiniones en Hacker News

• El artículo analiza el concepto de la búsqueda binaria sin ramas y sus posibles ventajas.
• Un comentario cuestiona la necesidad de eliminar ramas y sugiere que los bloqueos del pipeline causados por fallos en la predicción de ramas no son una parte inherente de la arquitectura.
• El comentario explica además que, en esencia, todas las operaciones son ramas, y que la razón por la que estas ramas no perjudican el rendimiento es que no son ramas en el pipeline principal.
• Otro comentario propone usar el lenguaje Nim, que compila a un lenguaje "bare-metal", para implementar lowerBound.
• Hay una discusión sobre si el código devuelve la primera coincidencia o cualquier coincidencia, y se enfatiza la importancia de entender la funcionalidad del código.
• Un comentario elogia la introducción intuitiva de la publicación del blog, que presenta rápidamente la implementación en C++ de búsqueda binaria general más rápida.
• En los comentarios se señala que la stdlib de Zig no llama a C++ para la búsqueda binaria y se proporciona un enlace a la búsqueda binaria de la stdlib de Zig.
• Hay una discusión sobre la búsqueda binaria y el problema de las ramas, y se sugiere que el problema no son las ramas en sí, sino la dependencia de datos que impide saber qué ubicación de memoria traer después hasta que termine la comparación.
• Los comentarios comparten resultados de rendimiento de búsqueda binaria en procesadores Cascade Lake y sugieren que clang es peor que gcc para optimizar este código en particular.
• Un comentario cuestiona el destino del enlace "BUT RUST" y dice que ese enlace parece estar desactualizado.
• Los comentarios señalan que los resultados no se mantienen con funciones de comparación más complejas y sugieren que el mejor rendimiento puede lograrse usando sb_lower_bound para tipos básicos y std::lower_bound para todo lo demás.
• El comentario final menciona que la propiedad de impredecible ahora afecta el pase de conversión a cmov y proporciona un enlace para más información.