Could Cargo's scheduler be better?

The author, who has been working with schedulers for around ten years, has recently added a new scheduler to HyperQueue. This new scheduler is based on Integer Linear Programming (ILP) and uses HiGHS as its implementation, which has become quite large in terms of compilation time. The author began to wonder if Cargo's build scheduling could be improved.

To investigate, the author selected 15 well-known Rust projects along with two projects they maintain, HyperQueue and FairyFlow. The build times of these projects varied significantly, making it a suitable starting point for the experiment. The author noted that they would only consider plain debug builds (cargo build), and not cargo check or release builds.

To experiment with scheduling, the author first recorded the dependency graph between individual build tasks (invocations of rustc and friends). This graph was essential to replay the same build under a different schedule. They used Cargo's build-timing feature (cargo build --timings) to trace the syscalls made by Cargo and its children processes.

By analyzing the read and write operations of the rustc processes, the author was able to derive the dependencies and precise start/end times for each build task. However, there was a challenge in representing the compilation of a single crate. The author decided to represent running rustc on a single crate as two nodes in the graph: frontend, which produces the metadata, and rest, which finishes the compilation.

The frontend node had to be completed before the rest node could run, but the rest node had to follow right after its frontend on the same worker due to being the same OS process.

To illustrate the scale of the dependency graph, the author provided an example of the graph for HyperQueue, which had 471 nodes and 821 edges. The author then proceeded to compare the scheduling decisions made by Cargo (used as the baseline) with several other schedulers they implemented, including a b-level scheduler. The b-level scheduler prioritized tasks that were on or close to the critical path, as delaying them would delay everything that depended on them.

The author also tried fan-out (prioritizing tasks that unblock the most other tasks), shortest/longest-job-first, several b-level variants combined with fan-out, and local search (simulated annealing) for comparison. The results showed that the b-level scheduler generally outperformed the other approaches, and often outperformed Cargo's own scheduling in 15 out of 17 cases, saving a median of about 8% of the wall time.

At a higher parallelism level (n=16), the b-level scheduler still outperformed Cargo's schedule in 14 out of 17 cases, with a median gain of about 2%.