pub fn simulate(
graph: &BuildGraph,
executors: NonZeroU32,
policy: Policy,
) -> ScheduleExpand description
Simulates a build on executors executors.
A non-preemptive list scheduler: whenever an executor is free and some unit’s dependencies have released it, the highest-priority such unit starts and holds that executor for its whole duration. Ties in priority go to the lower identifier, so the result never depends on iteration order.
Costs O((V + E) log V) for Policy::LongestPath, the logarithm being the ready queue.
Policy::CargoLike adds the cost of counting transitive dependents; see Policy.
use core::num::NonZeroU32;
use critpath_core::{simulate, EdgeKind, GraphBuilder, Millis, Policy, Unit, UnitKind};
let mut builder = GraphBuilder::new();
let mut add = |name: &str, total: u64| {
builder.add_unit(Unit {
package: name.to_owned(),
version: "1.0.0".to_owned(),
target: name.to_owned(),
kind: UnitKind::Lib,
total: Millis::new(total),
metadata_at: None,
requires_full_closure: false,
})
};
let slow = add("slow", 300)?;
let quick = add("quick", 100)?;
let last = add("last", 50)?;
builder.add_edge(quick, last, EdgeKind::Full)?;
let graph = builder.build()?;
// Two executors: slow runs 0..300, quick runs 0..100 and last follows it at 100..150.
let two = simulate(&graph, NonZeroU32::new(2).unwrap(), Policy::default());
assert_eq!(two.makespan(), Millis::new(300));
assert_eq!(two.start(last), Some(Millis::new(100)));
// One executor: quick outranks slow, having a dependent. At 100 both slow and last are ready
// and neither has a dependent, so the tie goes to the lower identifier: slow, then last.
let one = simulate(&graph, NonZeroU32::new(1).unwrap(), Policy::default());
assert_eq!(one.start(quick), Some(Millis::ZERO));
assert_eq!(one.start(slow), Some(Millis::new(100)));
assert_eq!(one.start(last), Some(Millis::new(400)));
assert_eq!(one.makespan(), Millis::new(450));Examples found in repository?
examples/scaling.rs (line 94)
78fn main() -> Result<(), Box<dyn Error>> {
79 let executors = NonZeroU32::new(16).ok_or("16 is not zero")?;
80 println!(
81 "{:>7} {:>8} {:>10} {:>10} {:>10}",
82 "units", "edges", "construct", "analyse", "simulate"
83 );
84 for &(units, fan_in) in &[(1_000, 4), (5_000, 4), (20_000, 6), (50_000, 6)] {
85 let start = Instant::now();
86 let graph = build(units, fan_in)?;
87 let constructed = start.elapsed();
88
89 let start = Instant::now();
90 let analysis = analyze(&graph);
91 let analysed = start.elapsed();
92
93 let start = Instant::now();
94 let schedule = simulate(&graph, executors, Policy::CargoLike);
95 let simulated = start.elapsed();
96
97 println!(
98 "{:>7} {:>8} {:>10.1?} {:>10.1?} {:>10.1?} critical path {}, makespan {}",
99 units,
100 graph.edge_count(),
101 constructed,
102 analysed,
103 simulated,
104 analysis.critical_path_len(),
105 schedule.makespan(),
106 );
107 }
108 Ok(())
109}