Este artículo del blog narra la fascinante y a menudo frustrante búsqueda de optimización de algoritmos de ordenamiento. El objetivo era simple: hacer que la implementación de ordenamiento de Pystd (una implementación de Python) fuera más rápida que la de stdlibc++ (la biblioteca estándar de C++), una tarea que inicialmente parecía trivial pero que resultó ser un desafío considerable.
La primera victoria llegó con el ordenamiento estable (stable sort), donde, tras algunas modificaciones menores, Pystd logró superar a std::stable_sort de C++ en un modesto 5%. El ordenamiento inestable (unstable sort), sin embargo, demostró ser mucho más complicado. El autor sospecha que los desarrolladores de stdlibc++ han dedicado una cantidad significativa de tiempo a optimizar std::sort debido a su uso más frecuente.
La optimización de std::sort implicó una serie de experimentos que, en su mayoría, resultaron contraproducentes. Se probaron diversas técnicas, incluyendo la emulación de la estrategia de movimiento de elementos utilizada por stdlibc++ (usando memmove en lugar de copias directas) e incluso la implementación de algoritmos alternativos como Shellsort y Radix Sort, todos sin éxito. Incluso se intentó mejorar la selección del pivote, con resultados neutrales.
Un punto crucial fue la aparición de un error que solo se manifestaba con conjuntos de datos muy grandes. Para depurar, se redujo el límite de cambio de algoritmo (de qsort a insertion sort), lo que ralentizó el proceso. Sorprendentemente, aumentar este límite (de 16 a 32 elementos) provocó una mejora significativa en el rendimiento. Aumentarlo aún más (a 64) afectó negativamente a otros algoritmos, por lo que se estableció en 32 como un compromiso.
Finalmente, después de numerosos ajustes, Pystd logró superar a stdlibc++ en una única ejecución, con una diferencia de solo 0.001 segundos (0.754 segundos contra 0.755 segundos). Aunque la diferencia es mínima, el artículo ilustra la complejidad de la optimización de algoritmos, donde incluso pequeños cambios pueden tener un impacto significativo, y cómo la comprensión del código de referencia (en este caso, stdlibc++) puede proporcionar pistas valiosas, aunque no siempre directas, para la mejora del rendimiento. El artículo también destaca la importancia de la depuración y cómo las soluciones temporales para la depuración pueden, a veces, revelar optimizaciones inesperadas.