Skip to main content

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}