From e54b5f875d0f2127a5daf8402557d058c9a3e652 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Wed, 28 Feb 2018 22:04:54 -0800 Subject: [PATCH] Improve Cargo's scheduling of builds Historically Cargo has been pretty naive about scheduling builds, basically just greedily scheduling as much work as possible. As pointed out in #5014, however, this isn't guaranteed to always have the best results. If we've got a very deep dependency tree that would otherwise fill up our CPUs Cargo should ideally schedule these dependencies first. That way when we reach higher up in the dependency tree we should have more work available to fill in the cracks if there's spare cpus. Closes #5014 --- src/cargo/ops/cargo_rustc/job_queue.rs | 1 + src/cargo/util/dependency_queue.rs | 87 +++++++++++++++++++++++++- 2 files changed, 85 insertions(+), 3 deletions(-) diff --git a/src/cargo/ops/cargo_rustc/job_queue.rs b/src/cargo/ops/cargo_rustc/job_queue.rs index 6613404cd..b8867ef76 100644 --- a/src/cargo/ops/cargo_rustc/job_queue.rs +++ b/src/cargo/ops/cargo_rustc/job_queue.rs @@ -111,6 +111,7 @@ impl<'a> JobQueue<'a> { /// possible along each dependency chain. pub fn execute(&mut self, cx: &mut Context) -> CargoResult<()> { let _p = profile::start("executing the job graph"); + self.queue.queue_finished(); // We need to give a handle to the send half of our message queue to the // jobserver helper thread. Unfortunately though we need the handle to be diff --git a/src/cargo/util/dependency_queue.rs b/src/cargo/util/dependency_queue.rs index efe3cba9d..b614985a6 100644 --- a/src/cargo/util/dependency_queue.rs +++ b/src/cargo/util/dependency_queue.rs @@ -34,6 +34,9 @@ pub struct DependencyQueue { /// The packages which are currently being built, waiting for a call to /// `finish`. pending: HashSet, + + /// Topological depth of each key + depth: HashMap, } /// Indication of the freshness of a package. @@ -66,6 +69,7 @@ impl DependencyQueue { reverse_dep_map: HashMap::new(), dirty: HashSet::new(), pending: HashSet::new(), + depth: HashMap::new(), } } @@ -97,14 +101,60 @@ impl DependencyQueue { &mut slot.insert((my_dependencies, value)).1 } + /// All nodes have been added, calculate some internal metadata and prepare + /// for `dequeue`. + pub fn queue_finished(&mut self) { + for key in self.dep_map.keys() { + depth(key, &self.reverse_dep_map, &mut self.depth); + } + + fn depth( + key: &K, + map: &HashMap>, + results: &mut HashMap, + ) -> usize { + const IN_PROGRESS: usize = !0; + + if let Some(&depth) = results.get(key) { + assert_ne!(depth, IN_PROGRESS, "cycle in DependencyQueue"); + return depth; + } + + results.insert(key.clone(), IN_PROGRESS); + + let depth = 1 + map.get(&key) + .into_iter() + .flat_map(|it| it) + .map(|dep| depth(dep, map, results)) + .max() + .unwrap_or(0); + + *results.get_mut(key).unwrap() = depth; + + depth + } + } + /// Dequeues a package that is ready to be built. /// /// A package is ready to be built when it has 0 un-built dependencies. If /// `None` is returned then no packages are ready to be built. pub fn dequeue(&mut self) -> Option<(Freshness, K, V)> { - let key = match self.dep_map.iter() - .find(|&(_, &(ref deps, _))| deps.is_empty()) - .map(|(key, _)| key.clone()) { + // Look at all our crates and find everything that's ready to build (no + // deps). After we've got that candidate set select the one which has + // the maximum depth in the dependency graph. This way we should + // hopefully keep CPUs hottest the longest by ensuring that long + // dependency chains are scheduled early on in the build process and the + // leafs higher in the tree can fill in the cracks later. + // + // TODO: it'd be best here to throw in a heuristic of crate size as + // well. For example how long did this crate historically take to + // compile? How large is its source code? etc. + let next = self.dep_map.iter() + .filter(|&(_, &(ref deps, _))| deps.is_empty()) + .map(|(key, _)| key.clone()) + .max_by_key(|k| self.depth[k]); + let key = match next { Some(key) => key, None => return None }; @@ -142,3 +192,34 @@ impl DependencyQueue { } } } + +#[cfg(test)] +mod test { + use super::{DependencyQueue, Freshness}; + + #[test] + fn deep_first() { + let mut q = DependencyQueue::new(); + + q.queue(Freshness::Fresh, 1, (), &[]); + q.queue(Freshness::Fresh, 2, (), &[1]); + q.queue(Freshness::Fresh, 3, (), &[]); + q.queue(Freshness::Fresh, 4, (), &[2, 3]); + q.queue(Freshness::Fresh, 5, (), &[4, 3]); + q.queue_finished(); + + assert_eq!(q.dequeue(), Some((Freshness::Fresh, 1, ()))); + assert_eq!(q.dequeue(), Some((Freshness::Fresh, 3, ()))); + assert_eq!(q.dequeue(), None); + q.finish(&3, Freshness::Fresh); + assert_eq!(q.dequeue(), None); + q.finish(&1, Freshness::Fresh); + assert_eq!(q.dequeue(), Some((Freshness::Fresh, 2, ()))); + assert_eq!(q.dequeue(), None); + q.finish(&2, Freshness::Fresh); + assert_eq!(q.dequeue(), Some((Freshness::Fresh, 4, ()))); + assert_eq!(q.dequeue(), None); + q.finish(&4, Freshness::Fresh); + assert_eq!(q.dequeue(), Some((Freshness::Fresh, 5, ()))); + } +} -- 2.30.2