Experiment with giving higher priority to proc-macros and their dependencies

[Aaron1011]

Currently, the dependency queue uses the number of transitive reverse dependencies to determine how to schedule jobs:

cargo/src/cargo/util/dependency_queue.rs

Lines 34 to 35 in 5847787

	/// The total number of packages that are transitively waiting on this package
	priority: HashMap<N, usize>,

I think it would be a good idea to experiment with 'boosting' the priority of proc-macro crates and their dependencies. Unlike other crates, proc-macro crate building cannot be pipelined - since they are dynamically loaded into the compiler, any reverse-dependencies of proc-macro crates must wait for codegen, not just metadata.

By giving proc-macro crates a higher priority, we increase the likelihood that they will finish codegen by the time we are ready to start building their reverse dependencies. A similar argument applies to dependencies (not reverse-dependencies) of proc-macro crates: until rust-lang/rust#64191 is implemented, we still need to wait for all a proc-macro crates's dependencies to codegen before we can start building the proc-macro crate.

Anecdotally, I've noticed that some proc-macro dependencies (e.g. syn) seem to take a significant fraction of the total build time. By starting to build these crates earlier, we may be able to reduce the impact of their build times on the total build time.

Concretely, I think we could add a flag -Z prioritize-proc-macros to Cargo. When enabled, we could either directly increase the priority entry by a certain factor, or just break ties in priority by proc-macro (or proc-macro-dependency) status.

By using -Z timings, we can gather data on the impact of this change on build times.

[ehuss]

I think it would be great to experiment with this. If you (or someone) wants to prototype it and demonstrate that it is measurably faster on some sampling of projects (and various -j values), I think it could be added without a -Z flag.

[domenicquirl]

To add to this (while being unsure if this is even pursued at the moment): a similar logic applies to build scripts. For example, the now-stabilized --timings on a crate that uses openssl-sys/vendored (and thus has to build openssl from source to statically link it) shows that the critical dependency here (with some hops through openssl crates) is cc, which is built as the 7th crate total out of some hundred.

The build script only starts running about 15 seconds later, however, leading to a very undesirable tail of compiling the handful of crates that use it at then end. The build script takes a very long time to run, so all other crates are well done by that point - if the build script was started earlier, it could have run in parallel for those 15 seconds and the whole build would be faster.