critpath_core/schedule.rs
1//! Simulating a build on a bounded number of executors, and the bounds that hold whatever the
2//! scheduler does.
3//!
4//! Section 5 of [`docs/model.md`](https://github.com/eventvoid/cargo-critpath/blob/main/docs/model.md) defines the simulator and section 6 the two bounds. The bounds are
5//! guarantees; the simulated makespan is an estimate, because the ordering it reproduces is one
6//! Cargo itself only follows up to hash iteration order.
7
8use core::cmp::Reverse;
9use core::num::{NonZeroU32, NonZeroU64};
10use std::collections::BinaryHeap;
11
12use crate::analysis::{analyze, Analysis};
13use crate::graph::{BuildGraph, EdgeKind, UnitId};
14use crate::millis::Millis;
15
16/// Which unit a scheduler picks when several are ready and one executor is free.
17///
18/// More policies may be added, so callers must not assume the set is closed.
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20#[non_exhaustive]
21pub enum Policy {
22 /// Cargo's own ordering, which is blind to how long anything takes.
23 ///
24 /// A unit's priority is one plus the number of units that transitively depend on it. This is
25 /// what Cargo does — it gives every unit the same fixed cost and adds up the costs of the
26 /// transitive reverse-dependencies — and reproducing it is what makes the simulated makespan an
27 /// estimate of Cargo's wall time rather than of a better build system's.
28 CargoLike,
29 /// The longest remaining path to a sink first, the standard critical-path heuristic.
30 ///
31 /// Schedules better than Cargo does. It is offered so that the gap between the two can be read
32 /// off: that gap is what is lost to the ordering alone, as opposed to the shape of the graph.
33 LongestPath,
34}
35
36impl Default for Policy {
37 /// [`Policy::CargoLike`], because the question the tool is asked is how long *this* build
38 /// takes, not how long an ideally scheduled one would.
39 fn default() -> Self {
40 Self::CargoLike
41 }
42}
43
44/// When every unit ran, on a fixed number of executors under a fixed policy.
45///
46/// Produced by [`simulate`]. An identifier from a different graph is not detected; see [`Analysis`].
47#[derive(Clone, Debug)]
48pub struct Schedule {
49 start: Vec<Millis>,
50 finish: Vec<Millis>,
51 makespan: Millis,
52 policy: Policy,
53 executors: NonZeroU32,
54}
55
56impl Schedule {
57 /// When the last unit finished.
58 ///
59 /// Zero for an empty graph. This is an estimate, not a bound: see [`lower_bound`] for the
60 /// numbers that hold whatever the scheduler does.
61 #[must_use]
62 pub fn makespan(&self) -> Millis {
63 self.makespan
64 }
65
66 /// When a unit started, or `None` if the index is outside this schedule.
67 #[must_use]
68 pub fn start(&self, id: UnitId) -> Option<Millis> {
69 self.start.get(id.index()).copied()
70 }
71
72 /// When a unit finished, or `None` if the index is outside this schedule.
73 ///
74 /// Always its start plus its whole duration: a unit is never preempted or migrated.
75 #[must_use]
76 pub fn finish(&self, id: UnitId) -> Option<Millis> {
77 self.finish.get(id.index()).copied()
78 }
79
80 /// The policy this schedule was produced under.
81 #[must_use]
82 pub fn policy(&self) -> Policy {
83 self.policy
84 }
85
86 /// The executor count this schedule was produced for.
87 #[must_use]
88 pub fn executors(&self) -> NonZeroU32 {
89 self.executors
90 }
91}
92
93/// Simulates a build on `executors` executors.
94///
95/// A non-preemptive list scheduler: whenever an executor is free and some unit's dependencies have
96/// released it, the highest-priority such unit starts and holds that executor for its whole
97/// duration. Ties in priority go to the lower identifier, so the result never depends on iteration
98/// order.
99///
100/// Costs `O((V + E) log V)` for [`Policy::LongestPath`], the logarithm being the ready queue.
101/// [`Policy::CargoLike`] adds the cost of counting transitive dependents; see [`Policy`].
102///
103/// ```
104/// use core::num::NonZeroU32;
105/// use critpath_core::{simulate, EdgeKind, GraphBuilder, Millis, Policy, Unit, UnitKind};
106///
107/// let mut builder = GraphBuilder::new();
108/// let mut add = |name: &str, total: u64| {
109/// builder.add_unit(Unit {
110/// package: name.to_owned(),
111/// version: "1.0.0".to_owned(),
112/// target: name.to_owned(),
113/// kind: UnitKind::Lib,
114/// total: Millis::new(total),
115/// metadata_at: None,
116/// requires_full_closure: false,
117/// })
118/// };
119/// let slow = add("slow", 300)?;
120/// let quick = add("quick", 100)?;
121/// let last = add("last", 50)?;
122/// builder.add_edge(quick, last, EdgeKind::Full)?;
123/// let graph = builder.build()?;
124///
125/// // Two executors: slow runs 0..300, quick runs 0..100 and last follows it at 100..150.
126/// let two = simulate(&graph, NonZeroU32::new(2).unwrap(), Policy::default());
127/// assert_eq!(two.makespan(), Millis::new(300));
128/// assert_eq!(two.start(last), Some(Millis::new(100)));
129///
130/// // One executor: quick outranks slow, having a dependent. At 100 both slow and last are ready
131/// // and neither has a dependent, so the tie goes to the lower identifier: slow, then last.
132/// let one = simulate(&graph, NonZeroU32::new(1).unwrap(), Policy::default());
133/// assert_eq!(one.start(quick), Some(Millis::ZERO));
134/// assert_eq!(one.start(slow), Some(Millis::new(100)));
135/// assert_eq!(one.start(last), Some(Millis::new(400)));
136/// assert_eq!(one.makespan(), Millis::new(450));
137/// # Ok::<(), critpath_core::GraphError>(())
138/// ```
139#[must_use]
140pub fn simulate(graph: &BuildGraph, executors: NonZeroU32, policy: Policy) -> Schedule {
141 let count = graph.len();
142 let priority = priorities(graph, policy);
143 let mut state = Readiness::new(graph, count);
144 let mut start = vec![Millis::ZERO; count];
145 let mut finish = vec![Millis::ZERO; count];
146
147 // Units whose release time is settled but has not arrived, earliest first.
148 let mut waiting: Waiting = BinaryHeap::new();
149 // Units that may start now, highest priority first and lowest identifier on a tie.
150 let mut ready: BinaryHeap<(u64, Reverse<UnitId>)> = BinaryHeap::new();
151 // Units in flight, earliest finish first.
152 let mut running: BinaryHeap<Reverse<(Millis, UnitId)>> = BinaryHeap::new();
153
154 for (id, _) in graph.units() {
155 if graph.dependencies(id).unwrap_or(&[]).is_empty() {
156 waiting.push(Reverse((Millis::ZERO, id)));
157 }
158 }
159
160 let mut now = Millis::ZERO;
161 let mut free = u64::from(executors.get());
162 let mut makespan = Millis::ZERO;
163
164 loop {
165 let mut progress = false;
166
167 // Retire everything that has finished by now, which frees executors and may release the
168 // units waiting behind them.
169 while let Some(&Reverse((at, id))) = running.peek() {
170 if at > now {
171 break;
172 }
173 running.pop();
174 free = free.saturating_add(1);
175 progress = true;
176 state.on_finish(graph, id, at, &finish, &mut waiting);
177 }
178
179 // Move everything whose release time has arrived into the ready queue.
180 while let Some(&Reverse((at, id))) = waiting.peek() {
181 if at > now {
182 break;
183 }
184 waiting.pop();
185 let priority = priority.get(id.index()).copied().unwrap_or(0);
186 ready.push((priority, Reverse(id)));
187 progress = true;
188 }
189
190 // Fill the free executors.
191 while free > 0 {
192 let Some((_, Reverse(id))) = ready.pop() else {
193 break;
194 };
195 let Some(unit) = graph.unit(id) else {
196 continue;
197 };
198 let ends = now.saturating_add(unit.total);
199 if let Some(slot) = start.get_mut(id.index()) {
200 *slot = now;
201 }
202 if let Some(slot) = finish.get_mut(id.index()) {
203 *slot = ends;
204 }
205 running.push(Reverse((ends, id)));
206 free = free.saturating_sub(1);
207 makespan = makespan.max(ends);
208 progress = true;
209 state.on_start(graph, id, now, &mut waiting);
210 }
211
212 if progress {
213 continue;
214 }
215
216 // Nothing more can happen at this instant: jump to the next one that matters.
217 let next_finish = running.peek().map(|&Reverse((at, _))| at);
218 let next_release = waiting.peek().map(|&Reverse((at, _))| at);
219 let next = match (next_finish, next_release) {
220 (Some(a), Some(b)) => Some(a.min(b)),
221 (Some(a), None) | (None, Some(a)) => Some(a),
222 (None, None) => None,
223 };
224 match next {
225 Some(at) if at > now => now = at,
226 // Either everything has run, or the queues hold only instants already passed, which
227 // the retire and release steps above would have consumed.
228 _ => break,
229 }
230 }
231
232 Schedule {
233 start,
234 finish,
235 makespan,
236 policy,
237 executors,
238 }
239}
240
241/// The area bound: no schedule on `executors` executors can beat the total work divided between
242/// them, rounded up because a makespan is a whole number of milliseconds.
243///
244/// ```
245/// use core::num::NonZeroU32;
246/// use critpath_core::{area_bound, GraphBuilder, Millis, Unit, UnitKind};
247///
248/// let mut builder = GraphBuilder::new();
249/// for total in [20, 20, 21] {
250/// builder.add_unit(Unit {
251/// package: "p".to_owned(),
252/// version: "1.0.0".to_owned(),
253/// target: "p".to_owned(),
254/// kind: UnitKind::Lib,
255/// total: Millis::new(total),
256/// metadata_at: None,
257/// requires_full_closure: false,
258/// })?;
259/// }
260/// let graph = builder.build()?;
261///
262/// // 61 ms of work on two executors cannot finish in 30 ms, so the bound is 31.
263/// assert_eq!(area_bound(&graph, NonZeroU32::new(2).unwrap()), Millis::new(31));
264/// # Ok::<(), critpath_core::GraphError>(())
265/// ```
266#[must_use]
267pub fn area_bound(graph: &BuildGraph, executors: NonZeroU32) -> Millis {
268 graph.total_work().div_ceil_by(NonZeroU64::from(executors))
269}
270
271/// The larger of the critical path and the area bound: no schedule on `executors` executors can
272/// finish sooner, whatever policy it follows.
273///
274/// Which of the two terms dominates is the diagnosis. When the critical path does, the shape of the
275/// graph is the constraint and more executors cannot help. When the area bound does, the machine is
276/// the constraint and restructuring the graph will not buy much.
277///
278/// Both terms come from the one analysis, so there is no pair of arguments that can disagree about
279/// which graph is being described.
280#[must_use]
281pub fn lower_bound(analysis: &Analysis, executors: NonZeroU32) -> Millis {
282 let area = analysis
283 .total_work()
284 .div_ceil_by(NonZeroU64::from(executors));
285 analysis.critical_path_len().max(area)
286}
287
288/// Units whose release time is known, ordered by that time and then by identifier.
289type Waiting = BinaryHeap<Reverse<(Millis, UnitId)>>;
290
291/// Tracks what still has to happen before each unit may start.
292///
293/// Two independent channels, because the model has two kinds of constraint. Ordinary units count
294/// down their incoming edges, each satisfied when the producer starts (a metadata edge) or finishes
295/// (a full edge). Units that require their whole closure ignore their edges and wait on the second
296/// channel, which counts down direct dependencies that are themselves *settled* — finished, with
297/// everything behind them settled too. That makes the last finish anywhere in a closure available
298/// without ever enumerating the closure, in `O(V + E)` over the whole run.
299struct Readiness {
300 /// Incoming edges not yet satisfied, for units that do not require their closure.
301 unmet_edges: Vec<u32>,
302 /// When the last satisfied incoming edge releases the unit.
303 released_at: Vec<Millis>,
304 /// Direct dependencies not yet settled.
305 unsettled_deps: Vec<u32>,
306 /// The last finish anywhere behind a unit, final once `unsettled_deps` reaches zero.
307 closure_finish: Vec<Millis>,
308 finished: Vec<bool>,
309}
310
311impl Readiness {
312 fn new(graph: &BuildGraph, count: usize) -> Self {
313 let degrees: Vec<u32> = graph
314 .units()
315 .map(|(id, _)| {
316 let deps = graph.dependencies(id).unwrap_or(&[]).len();
317 u32::try_from(deps).unwrap_or(u32::MAX)
318 })
319 .collect();
320 Self {
321 unmet_edges: degrees.clone(),
322 released_at: vec![Millis::ZERO; count],
323 unsettled_deps: degrees,
324 closure_finish: vec![Millis::ZERO; count],
325 finished: vec![false; count],
326 }
327 }
328
329 /// A unit has started: its metadata is now on a known schedule.
330 fn on_start(&mut self, graph: &BuildGraph, id: UnitId, at: Millis, waiting: &mut Waiting) {
331 let Some(unit) = graph.unit(id) else {
332 return;
333 };
334 for dep in graph.dependents(id).unwrap_or(&[]) {
335 if dep.kind != EdgeKind::Metadata || requires_closure(graph, dep.unit) {
336 continue;
337 }
338 // A metadata edge from a unit that emits none is rejected when the graph is built; the
339 // fallback waits for the whole unit rather than releasing the consumer too early.
340 let offset = unit.metadata_at.unwrap_or(unit.total);
341 self.satisfy_edge(dep.unit, at.saturating_add(offset), waiting);
342 }
343 }
344
345 /// A unit has finished: full edges out of it are satisfied, and it may now settle.
346 fn on_finish(
347 &mut self,
348 graph: &BuildGraph,
349 id: UnitId,
350 at: Millis,
351 finish: &[Millis],
352 waiting: &mut Waiting,
353 ) {
354 if let Some(slot) = self.finished.get_mut(id.index()) {
355 *slot = true;
356 }
357 for dep in graph.dependents(id).unwrap_or(&[]) {
358 if dep.kind != EdgeKind::Full || requires_closure(graph, dep.unit) {
359 continue;
360 }
361 self.satisfy_edge(dep.unit, at, waiting);
362 }
363 self.settle(graph, id, finish, waiting);
364 }
365
366 /// Records one satisfied incoming edge, and queues the consumer once all of them are.
367 fn satisfy_edge(&mut self, consumer: UnitId, release: Millis, waiting: &mut Waiting) {
368 if let Some(slot) = self.released_at.get_mut(consumer.index()) {
369 *slot = (*slot).max(release);
370 }
371 let Some(remaining) = self.unmet_edges.get_mut(consumer.index()) else {
372 return;
373 };
374 *remaining = remaining.saturating_sub(1);
375 if *remaining == 0 {
376 let at = self
377 .released_at
378 .get(consumer.index())
379 .copied()
380 .unwrap_or(Millis::ZERO);
381 waiting.push(Reverse((at, consumer)));
382 }
383 }
384
385 /// Propagates "everything behind this unit is done, and so is the unit itself".
386 ///
387 /// Written as a worklist rather than as recursion: a chain of pipelined libraries settles from
388 /// the front all at once, and recursion would make its depth the stack depth.
389 fn settle(&mut self, graph: &BuildGraph, id: UnitId, finish: &[Millis], waiting: &mut Waiting) {
390 let mut worklist = Vec::new();
391 if self.is_settled(id) {
392 worklist.push(id);
393 }
394 while let Some(settled) = worklist.pop() {
395 let behind = finish
396 .get(settled.index())
397 .copied()
398 .unwrap_or(Millis::ZERO)
399 .max(
400 self.closure_finish
401 .get(settled.index())
402 .copied()
403 .unwrap_or(Millis::ZERO),
404 );
405 for dep in graph.dependents(settled).unwrap_or(&[]) {
406 if let Some(slot) = self.closure_finish.get_mut(dep.unit.index()) {
407 *slot = (*slot).max(behind);
408 }
409 let Some(remaining) = self.unsettled_deps.get_mut(dep.unit.index()) else {
410 continue;
411 };
412 *remaining = remaining.saturating_sub(1);
413 if *remaining > 0 {
414 continue;
415 }
416 if requires_closure(graph, dep.unit) {
417 let at = self
418 .closure_finish
419 .get(dep.unit.index())
420 .copied()
421 .unwrap_or(Millis::ZERO);
422 waiting.push(Reverse((at, dep.unit)));
423 }
424 if self.is_settled(dep.unit) {
425 worklist.push(dep.unit);
426 }
427 }
428 }
429 }
430
431 /// Whether a unit has finished and everything behind it has settled.
432 fn is_settled(&self, id: UnitId) -> bool {
433 self.finished.get(id.index()).copied().unwrap_or(false)
434 && self.unsettled_deps.get(id.index()).copied().unwrap_or(0) == 0
435 }
436}
437
438fn requires_closure(graph: &BuildGraph, id: UnitId) -> bool {
439 graph
440 .unit(id)
441 .is_some_and(|unit| unit.requires_full_closure)
442}
443
444/// The scheduling priority of every unit, higher first.
445fn priorities(graph: &BuildGraph, policy: Policy) -> Vec<u64> {
446 match policy {
447 Policy::CargoLike => transitive_dependents(graph)
448 .into_iter()
449 .map(|count| count.saturating_add(1))
450 .collect(),
451 Policy::LongestPath => {
452 let analysis = analyze(graph);
453 let critical_path = analysis.critical_path_len();
454 graph
455 .units()
456 .map(|(id, unit)| {
457 // The longest path from this unit's start to the end of the build. A unit that
458 // may finish as late as `latest_finish` without lengthening the build has
459 // exactly that much less path behind it.
460 let latest_start = analysis
461 .latest_finish(id)
462 .unwrap_or(critical_path)
463 .saturating_sub(unit.total);
464 critical_path.saturating_sub(latest_start).get()
465 })
466 .collect()
467 }
468 }
469}
470
471/// How many distinct units transitively depend on each unit.
472///
473/// Reachability counting, which no linear-time algorithm computes on a general DAG. This walks the
474/// graph once per block of 64 units, propagating a 64-bit membership mask backwards through the
475/// topological order, for `O((V / 64) * (V + E))` time in `O(V)` memory. The alternative, one
476/// bitset per unit, is a single pass but needs `V * V` bits, which a workspace of tens of thousands
477/// of units would not survive.
478fn transitive_dependents(graph: &BuildGraph) -> Vec<u64> {
479 let count = graph.len();
480 let mut totals = vec![0u64; count];
481 let mut reachable = vec![0u64; count];
482 let order = graph.topological_order();
483
484 let mut block = 0usize;
485 while block < count {
486 let end = block.saturating_add(64).min(count);
487 reachable.fill(0);
488 for &id in order.iter().rev() {
489 let mut mask = 0u64;
490 for dep in graph.dependents(id).unwrap_or(&[]) {
491 let index = dep.unit.index();
492 if index >= block && index < end {
493 mask |= 1u64 << (index - block);
494 }
495 mask |= reachable.get(index).copied().unwrap_or(0);
496 }
497 if let Some(slot) = reachable.get_mut(id.index()) {
498 *slot = mask;
499 }
500 }
501 for (index, mask) in reachable.iter().enumerate() {
502 if let Some(total) = totals.get_mut(index) {
503 *total = total.saturating_add(u64::from(mask.count_ones()));
504 }
505 }
506 block = block.saturating_add(64);
507 }
508
509 totals
510}