Un programador compara el planificador de Cargo con un algoritmo b-level y le gana

Un programador con una década de experiencia en planificadores de tareas evaluó empíricamente el planificador interno de Cargo, el sistema de construcción de Rust, y comprobó que un sencillo algoritmo greedy basado en el b-level (longitud de la cadena crítica pendiente) lo supera de forma consistente. Para ello registró el grafo de dependencias entre invocaciones de rustc trazando las llamadas al sistema, distinguió dos fases por crate —frontend, que produce los metadatos .rmeta, y rest, que completa codegen y enlazado— y reprodujo el orden de ejecución real de Cargo sobre 17 proyectos conocidos con rustc 1.97.1 en un portátil Linux de 16 núcleos Intel, probando paralelismos de n=4 y n=16. Probó además otras heurísticas (fan-out, shortest/longest-job-first, b-level combinado con fan-out y búsqueda local con simulated annealing) y un pseudo-óptimo construido con 10 000 iteraciones de búsqueda aleatoria, ya que el problema es NP-hard. Resultado: el b-level gana en 15 de 17 proyectos con n=4, con una mediana de ahorro del 8 % del tiempo de pared y un máximo del 16 %; con n=16 vence en 14 de 17, con mediana del 2 % y máximo del 15 %. Frente al pseudo-óptimo, b-level queda a una mediana del 1,3 % (n=4) y del 0,4 % (n=16), mientras que Cargo se aleja un 9,6 % y un 2,3 % respectivamente. El autor señala una limitación evidente: b-level requiere conocer de antemano la duración de cada tarea, así que prueba la sensibilidad a estimaciones ruidosas (texto cortado).