La compilación de software, especialmente en proyectos con grafos de dependencias complejos, es un problema fundamental de programación de tareas en sistemas distribuidos. La eficiencia del scheduler que orquesta estas tareas impacta directamente la productividad del desarrollador y los ciclos de CI/CD. Este artículo aborda la cuestión de si el scheduler de Cargo, la herramienta de compilación por defecto de Rust, puede ser mejorado mediante la aplicación de principios de programación de tareas clásicos. La hipótesis es que un algoritmo de programación consciente de la ruta crítica, como el b-level, puede superar al enfoque actual de Cargo, incluso bajo incertidumbre sobre la duración de las tareas.

El problema de programar tareas con dependencias en un número limitado de procesadores es un problema NP-hard conocido como 'Job Shop Scheduling' o 'Project Scheduling with Resource Constraints'. En el contexto de la compilación, cada crate es una tarea, y las dependencias entre crates forman un grafo dirigido acíclico (DAG). La meta es minimizar el 'makespan' (tiempo total de compilación). La relevancia de este problema ha crecido con la complejidad de los proyectos de software y la necesidad de compilaciones rápidas en entornos de desarrollo y CI/CD.

Arquitectura del Sistema

El análisis se basa en la observación externa del comportamiento de Cargo, sin acceso a su código fuente. Para ello, se utiliza el rastreo de syscalls para monitorizar las operaciones de lectura y escritura de archivos realizadas por los procesos rustc y sus hijos durante la compilación. Esta información permite reconstruir un grafo de dependencias preciso, donde cada tarea de compilación de un crate se descompone en dos nodos: 'frontend' (que produce metadatos .rmeta) y 'rest' (que completa la compilación, incluyendo codegen y linking). Las dependencias entre crates solo requieren la finalización del nodo 'frontend' de sus dependencias, lo que permite un mayor paralelismo. El nodo 'rest' está 'forzado' a ejecutarse inmediatamente después de su 'frontend' en el mismo worker, ya que es la continuación del mismo proceso del sistema operativo.

El scheduler propuesto, basado en 'b-level' (bottom level), calcula para cada tarea la longitud de la cadena más larga de tareas dependientes que aún deben ejecutarse hasta el final de la compilación. Cuando un worker queda libre, el scheduler selecciona la tarea lista con el 'b-level' más alto. Esta heurística prioriza las tareas que se encuentran en la ruta crítica o cerca de ella, minimizando así el 'makespan' total. Se compara con el scheduler de Cargo (línea base) y otras heurísticas como 'fan-out' y 'shortest/longest-job-first', así como búsquedas locales (simulated annealing) para aproximar el óptimo.

Reconstrucción del Grafo de Dependencias de Compilación

  1. 1 Inicio Compilación Cargo Ejecución de `cargo build --timings` y rastreo de syscalls.
  2. 2 Monitorización Syscalls Registro de operaciones de lectura/escritura de archivos por `rustc`.
  3. 3 Identificación Tareas Cada invocación de `rustc` es una tarea de compilación.
  4. 4 Descomposición Tarea Tarea de crate dividida en 'frontend' (.rmeta) y 'rest' (codegen/linking).
  5. 5 Derivación Dependencias Dependencias entre crates basadas en archivos `.rmeta`.
  6. 6 Construcción Grafo DAG Creación de un grafo dirigido acíclico con nodos (tareas) y aristas (dependen...

Flujo de Decisión del Scheduler B-Level

  1. 1 Worker Libre Un core de CPU o slot de compilación queda disponible.
  2. 2 Identificar Tareas Listas Listar todas las tareas cuyas dependencias 'frontend' han sido satisfechas.
  3. 3 Calcular B-Level Para cada tarea lista, calcular la longitud de la ruta crítica restante.
  4. 4 Seleccionar Tarea Elegir la tarea lista con el b-level más alto.
  5. 5 Asignar Tarea Asignar la tarea seleccionada al worker libre.
  6. 6 Ejecutar Tarea Simular la ejecución de la tarea con su duración real.

Trade-offs

Ganancias
  • ▲ Tiempo de compilación (makespan)
  • ▲ Robustez a la imprecisión de estimaciones de duración
  • ▲ Simplicidad del algoritmo vs. rendimiento
Costes
  • △ Necesidad de estimar duraciones de tareas (aunque sea de forma rudimentaria)
  • △ Overhead de cálculo del b-level (bajo para grafos de compilación)

Fundamentos Teóricos

El problema de la programación de tareas con dependencias es un campo de estudio clásico en la investigación de operaciones y la informática, con raíces en la teoría de grafos y la optimización combinatoria. El concepto de 'b-level' o 'bottom level' es una heurística bien establecida en la programación de proyectos, a menudo asociada con métodos como CPM (Critical Path Method) y PERT (Program Evaluation and Review Technique), desarrollados en las décadas de 1950 y 1960. Estos métodos buscan identificar la secuencia de actividades que determina la duración total de un proyecto.

La complejidad NP-hard de este problema fue formalizada por Karp en 1972 con su lista de 21 problemas NP-completos, incluyendo variantes del 'Job Shop Scheduling'. La aplicación de heurísticas como el b-level es una estrategia común para obtener soluciones eficientes en tiempo polinomial que se aproximan al óptimo, especialmente en escenarios donde la búsqueda exhaustiva es inviable. La robustez del b-level frente a la incertidumbre en la duración de las tareas es un tema recurrente en la literatura sobre programación estocástica y programación con información incompleta.