Repository navigation
Provide scheduling hints? #7437
Description
When more crates are ready to start compiling than there is available parallelism, how does Cargo pick which ones to start first? Are there ways to influence this scheduling? (For example, does the order of declarations of dependencies in a given Cargo.toml file matter? Or, what effect would it have to add an otherwise unnecessary edge to the dependency graph?) Should we add a new mechanism to influence it?
Here is the output of cargo build -Z timings for Servo: (with "Min unit time" set to 10 seconds)
If we start from the end of the graph, (part of) a critical path is very apparent: the final executable only starts to build after the script crate has finished. The script crate in turns only starts after the build script for the mozjs_sys has finished.
Additionally, CPU utilization drops while script is compiling because Cargo runs out of other tasks to do and rustc only has limited intra-crate parallelism. (Though I expected codegen-units to provide some more parallelism during codegen, but that’s a separate issue.)
It seems that if we could start mozjs_sys and script and earlier, the total time could be significantly reduced. Specifically: cargo build -p mozjs_sys && cargo build -p script && cargo build might lead to better scheduling. A way to achieve that scheduling with more parallelism could be to assign priorities. mozjs_sys and its recursive dependencies have priority 2 (more urgent), script and its dependencies that don’t already have a priority have priority 1, and everything else has priority 1.
Literally this mechanism with numeric priority levels is probably not the UX we want for Cargo. But how does it sound to add some way to influence the scheduling? Maybe call it “hints” to avoid setting in stone the current algorithm.
CC #5125 which is on the more general topic of scheduling
Activity
SimonSapin commentedon Sep 26, 2019
(Looks like
codegen-unitsdefaults to 2, not ncpu.)alexcrichton commentedon Sep 26, 2019
Scheduling has come up from time to time, but generally hasn't received a ton of love unfortunately! Some history is:
The tl;dr is that Cargo only has limited judgement when scheduling things. This only comes up when Cargo has multiple candidates to schedule for an available jobserver token. The "waiting" red line in the graph you have, when it's nonzero, is the only chance where Cargo actually has a scheduling decision to make.
When Cargo has a scheduling decision, it currently sorts the list of candidates to scheduled based on the number of transitive crates which depend on the crate. The thinking is that this schedules things that will hopefully unlock the most parallelism later in the graph. The previous behavior after the "first fix" was sorting based on depth in the graph.
That being said I definitely agree that we should have some way of providing hints to scheduling. For example Servo should be able to codify "when you compile the
scriptcrate, it's like you compile 15 crates serially" or something like that, and Cargo could use that to prioritize scheduling ofscript's transitive dependencies.If you zoom out though on your graph, do you know if Cargo could have actually scheduled better here? Did dependencies of
scriptget held back by accident?ehuss commentedon Sep 26, 2019
I'm pretty sure it is 16?
Eh2406 commentedon Sep 26, 2019
At a meetup last night we realized that that can be answered with a small addition to the data stored in the
-Ztimings(cc #7396 (comment)). I think it will be very motivating to "know" the performance we are leaving on the table.SimonSapin commentedon Sep 26, 2019
Oh, interesting. Any guess why this machine’s 4 cores / 8 threads are not saturated during codegen for the
scriptcrate in the timings above, then?If I run
cargo cleanthencargo build -p script, the total time is 319 seconds whereas in the full build graph thescriptcrate finishes after second 560. So as far as I can tell that’s ~240 seconds worth of work that is not a dependency ofscript, and that could (with different scheduling) be done in parallel with it.JoshMcguigan commentedon Nov 28, 2020
Is it practical to use the json output from
cargo build -Ztimings=json(or something similar) as a kind of profile guided optimization to determine the optimal build order automatically?In any case, I've submitted #8908 which attempts to take a small step toward allowing some weighting to be considered when determining build order. I think this should be useful for either allowing a user to provide scheduling hints as requested in this issue, or in implementing a system which uses actual timing data from a previous build.
Auto merge of #8908 - JoshMcguigan:dependency-queue-cost, r=alexcrichton
luser commentedon Feb 9, 2021
That's #7396.
epage commentedon Nov 2, 2023
#11032 looked at adding more heuristics to improve build order but they were a mixed bag. Something that came up in that discussion was a (presumed) perma-unstable way of configuring the priority of every package to explore what heuristics could be used. #7396 could then build on this to create a feedback loop for your own system to improve.
ariasanovsky commentedon Nov 10, 2023
Now that nightly supports parallel front-end compilation, I propose we develop an algorithm$A = A_\alpha$ with an adjustable configuration $\alpha$ and follow a data-driven approach to optimize $\alpha$ for different build environments. Guessing an optimal schedule should run $o(\text{compilation time})$ , but may be used to reduce overall compilation time.
Notes:
weihanglo commentedon Nov 10, 2023
FWIW, not exactly the same issue but could share some ideas in between regarding parallelism — #12912.
weihanglo commentedon Mar 1, 2024
Similarly, protobuf generation (via
prost) is usually assigned to a lower priority but takes relatively longer time to build. Here is a case in risingwave:Since we have integrated SQLite into Cargo, it is a good time to evaluate how to persist timings data as a first step.