Búsqueda binaria 6 veces más rápida: del código compilado a la simpatía mecánica

Este artículo técnico explica cómo acelerar una búsqueda binaria escrita en un lenguaje compilado hasta multiplicar por seis su rendimiento, dejando a un lado el paralelismo y centrándose en la llamada "simpatía mecánica": adaptar el código al funcionamiento interno de la CPU moderna. El autor parte de un problema real presente en el algoritmo de gradient histogram boosting de scikit-learn: asignar un millón de valores en coma flotante a 255 buckets均匀 distribuidos mediante búsqueda binaria sobre un array ordenado de fronteras. La implementación inicial en Rust, análoga a la versión en Cython de scikit-learn, sufre un 16,6% de fallos de predicción de saltos y ejecuta cerca de 27 millones de instrucciones de bifurcación, lo que lastra el rendimiento incluso siendo código compilado. A partir de ahí, el texto desgrana una serie de optimizaciones progresivas —branchless code, desenrollado de bucles, uso de SIMD y de cachés de memoria— que reducen los saltos impredecibles, aumentan el paralelismo a nivel de instrucción y bajan el tiempo de ejecución desde unos 45.870 microsegundos hasta una versión final cerca de 7.600 microsegundos. Cada optimización se acompaña de mediciones con contadores hardware obtenidas mediante py-perf-event, tablas comparativas y fragmentos de código en Rust. El autor advierte de que el artículo solo introduce nociones básicas de predicción de saltos, SIMD, jerarquía de memoria e ILP, y remite a recursos adicionales al final. Se trata, en definitiva, de una guía práctica y didáctica sobre optimización de bajo nivel en Python a través de extensiones compiladas, con un caso de estudio concreto, reproducible y medible.