Skip to main content

simulate

Function simulate 

Source
pub fn simulate(
    graph: &BuildGraph,
    executors: NonZeroU32,
    policy: Policy,
) -> Schedule
Expand 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}