sort the pending queue according to cost/priority

If multiple pieces of work are waiting in the pending queue, we can sort it according to their priorities: higher priorities should be scheduled sooner. They are more often than not wider than pure chains, and this should create more parallelism opportunities earlier in the pipeline: a high priority piece of work represents more future pieces of work down the line. This is a scheduling tradeoff that behaves differently for each project, machine configuration, amount of available parallelism at a given point in time, etc, but seems to help more often than hinders, at low-core counts and with enough units of work to be done, so that there is jobserver token contention where choosing a "better" piece of work to work on next is possible.
rust-lang · Sep 1, 2022 · c685acd · c685acd
1 parent 04a4081
commit c685acd
Show file tree

Hide file tree

Showing 2 changed files with 16 additions and 1 deletion.
diff --git a/src/cargo/core/compiler/job_queue.rs b/src/cargo/core/compiler/job_queue.rs
@@ -583,11 583,19 @@ impl<'cfg> DrainState<'cfg> {
  }
  }
 
  // If multiple pieces of work are waiting in the pending queue, we can
  // sort it according to their priorities: higher priorities should be
  // scheduled sooner.
  self.pending_queue
  .sort_by_cached_key(|(unit, _)| self.queue.priority(unit));
 
  // Now that we've learned of all possible work that we can execute
  // try to spawn it so long as we've got a jobserver token which says
  // we're able to perform some parallel work.
  // The `pending_queue` is sorted in ascending priority order, and we're
  // removing the highest priority items from its end.
  while self.has_extra_tokens() && !self.pending_queue.is_empty() {
- let (unit, job) = self.pending_queue.remove(0);
  let (unit, job) = self.pending_queue.pop().unwrap();
  *self.counts.get_mut(&unit.pkg.package_id()).unwrap() -= 1;
  if !cx.bcx.build_config.build_plan {
  // Print out some nice progress information.

diff --git a/src/cargo/util/dependency_queue.rs b/src/cargo/util/dependency_queue.rs
@@ -170,6 170,13 @@ impl<N: Hash Eq Clone, E: Eq Hash Clone, V> DependencyQueue<N, E, V> {
  self.dep_map.len()
  }
 
  /// Returns the relative priority of a node. Higher priorities should be scheduled sooner.
  /// Currently computed as the transitive cost of the given node: its own, plus the cost of its
  /// reverse dependencies.
  pub(crate) fn priority(&self, node: &N) -> usize {
  self.priority[node]
  }
 
  /// Indicate that something has finished.
  ///
  /// Calling this function indicates that the `node` has produced `edge`. All