Skip to main content

scaling/
scaling.rs

1//! Measures how the analysis scales, so that any claim about it has a number behind it.
2//!
3//! Run with `cargo run --release --example scaling -p critpath-core`.
4//!
5//! The synthetic graphs are shaped like a real build rather than like a random DAG: most units are
6//! libraries joined by metadata edges, and roughly one unit in seventeen is a proc-macro that emits
7//! no metadata and requires its whole transitive closure, which is the case the closure recurrence
8//! has to handle.
9
10// An example exists to print its measurements, and reporting a setup failure by returning it from
11// main is clearer here than threading a Result through the reporting itself.
12#![allow(clippy::print_stdout)]
13
14use std::error::Error;
15use std::num::{NonZeroU32, NonZeroU64};
16use std::time::Instant;
17
18use critpath_core::{
19    analyze, simulate, BuildGraph, EdgeKind, GraphBuilder, Millis, Policy, Unit, UnitKind,
20};
21
22/// One unit in seventeen is a proc-macro: it emits no metadata and needs its full closure.
23fn is_opaque(i: usize) -> bool {
24    i % 17 == 0
25}
26
27fn weight(i: usize) -> u64 {
28    (i.wrapping_mul(37) % 900 + 100) as u64
29}
30
31fn build(units: usize, fan_in: usize) -> Result<BuildGraph, Box<dyn Error>> {
32    let tenths = NonZeroU64::new(10).ok_or("ten is not zero")?;
33    let mut builder = GraphBuilder::with_capacity(units);
34    let mut ids = Vec::with_capacity(units);
35    for i in 0..units {
36        let total = weight(i);
37        let unit = Unit {
38            package: format!("p{i}"),
39            version: "1.0.0".to_owned(),
40            target: format!("t{i}"),
41            kind: if is_opaque(i) {
42                UnitKind::ProcMacro
43            } else {
44                UnitKind::Lib
45            },
46            total: Millis::new(total),
47            // A library emits metadata about seven tenths of the way through, which is what the
48            // dev-profile builds measured in docs/validation.md do.
49            metadata_at: if is_opaque(i) {
50                None
51            } else {
52                Some(Millis::new(total).scaled(7, tenths))
53            },
54            requires_full_closure: is_opaque(i),
55        };
56        ids.push(builder.add_unit(unit)?);
57    }
58    for i in 0..units {
59        for k in 1..=fan_in {
60            let Some(back) = i.checked_sub(k * 3) else {
61                continue;
62            };
63            let (Some(&from), Some(&to)) = (ids.get(back), ids.get(i)) else {
64                continue;
65            };
66            // A metadata edge requires the producer to emit metadata and the consumer not to link.
67            let kind = if !is_opaque(back) && !is_opaque(i) {
68                EdgeKind::Metadata
69            } else {
70                EdgeKind::Full
71            };
72            builder.add_edge(from, to, kind)?;
73        }
74    }
75    Ok(builder.build()?)
76}
77
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}