use core::num::{NonZeroU32, NonZeroU64};
use std::collections::BTreeSet;
use critpath_core::{
analyze, apply, area_bound, simulate, Analysis, BuildGraph, EdgeKind, Millis, Policy,
SplitDependents, Transform, UnitId, UnitKind,
};
use crate::input::{BuildInput, BuildMeta, Diagnostic, Severity};
const SWEEP: [(u64, u64); 5] = [(1, 4), (1, 3), (1, 2), (2, 3), (3, 4)];
const SWEEP_BOUNDS: (u32, u32) = (25, 75);
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Range {
pub low: Millis,
pub high: Millis,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Saving {
pub low: i64,
pub high: i64,
}
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) struct Label {
pub package: String,
pub version: String,
pub target: String,
}
impl Label {
fn of(graph: &BuildGraph, id: UnitId) -> Self {
match graph.unit(id) {
Some(unit) => Self {
package: unit.package.clone(),
version: unit.version.clone(),
target: unit.target.clone(),
},
None => Self {
package: String::new(),
version: String::new(),
target: String::new(),
},
}
}
pub(crate) fn display(&self) -> String {
format!("{} {} ({})", self.package, self.version, self.target)
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct GraphFacts {
pub units: usize,
pub edges: usize,
pub metadata_edges: usize,
pub total_work: Millis,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Baseline {
pub executors: NonZeroU32,
pub critical_path: Millis,
pub area_bound: Millis,
pub lower_bound: Millis,
pub makespan: Millis,
pub policy: Policy,
pub graph_constrained: bool,
pub mean_parallelism: u64,
}
#[derive(Clone, Debug)]
pub(crate) struct Step {
pub unit: usize,
pub label: Label,
pub kind: UnitKind,
pub enter: Millis,
pub exit: Millis,
pub contribution: Millis,
pub incoming: Option<EdgeKind>,
pub total: Millis,
pub metadata_at: Option<Millis>,
}
#[derive(Clone, Debug)]
pub(crate) struct UnitFacts {
pub unit: usize,
pub label: Label,
pub kind: UnitKind,
pub total: Millis,
pub metadata_at: Option<Millis>,
pub earliest_start: Millis,
pub earliest_finish: Millis,
pub latest_finish: Millis,
pub slack: Millis,
pub on_critical_path: bool,
pub dependencies: usize,
pub dependents: usize,
pub contribution: Millis,
pub splittable: bool,
}
#[derive(Clone, Debug)]
pub(crate) enum Target {
Unit(Label),
Executors(u32),
}
#[derive(Clone, Debug)]
pub(crate) struct Scenario {
pub kind: &'static str,
pub target: Target,
pub exact: bool,
pub fraction_swept: Option<(u32, u32)>,
pub overhead: Option<Millis>,
pub assumptions: Vec<String>,
pub critical_path: Range,
pub saving: Saving,
pub makespan: Range,
pub anomaly: bool,
pub notes: Vec<String>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Direction {
Measured,
Optimistic,
Pessimistic,
Unknown,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct ScanPoint {
pub executors: NonZeroU32,
pub area_bound: Millis,
pub lower_bound: Millis,
pub makespan: Millis,
pub graph_constrained: bool,
pub is_knee: bool,
pub direction: Direction,
pub measured_at: Option<u32>,
}
#[derive(Clone, Debug)]
pub(crate) enum Noise {
Unknown,
Measured {
spread: Millis,
samples: Vec<Millis>,
},
}
impl Noise {
pub(crate) fn spread(&self) -> Option<Millis> {
match self {
Self::Unknown => None,
Self::Measured { spread, .. } => Some(*spread),
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct Findings {
pub input: BuildMeta,
pub graph: GraphFacts,
pub baseline: Baseline,
pub path: Vec<Step>,
pub units: Vec<UnitFacts>,
pub ranked: Vec<usize>,
pub scenarios: Vec<Scenario>,
pub unsplittable: Vec<usize>,
pub scan: Vec<ScanPoint>,
pub knee: u32,
pub noise: Noise,
pub diagnostics: Vec<Diagnostic>,
pub top: usize,
}
pub(crate) fn assemble(
build: &BuildInput,
samples: &[Millis],
executors: NonZeroU32,
policy: Policy,
top: usize,
) -> Findings {
let graph = &build.graph;
let analysis = analyze(graph);
let ids: Vec<UnitId> = graph.units().map(|(id, _)| id).collect();
let critical_path = analysis.critical_path_len();
let area = area_bound(graph, executors);
let schedule = simulate(graph, executors, policy);
let makespan = schedule.makespan();
let total_work = graph.total_work();
let baseline = Baseline {
executors,
critical_path,
area_bound: area,
lower_bound: critical_path.max(area),
makespan,
policy,
graph_constrained: critical_path >= area,
mean_parallelism: hundredths(total_work, makespan),
};
let units = unit_facts(graph, &analysis, &ids);
let mut ranked: Vec<usize> = (0..units.len())
.filter(|i| units.get(*i).is_some_and(|u| u.contribution > Millis::ZERO))
.collect();
ranked.sort_by(|a, b| {
let contribution = |i: &usize| units.get(*i).map_or(Millis::ZERO, |u| u.contribution);
contribution(b).cmp(&contribution(a)).then(a.cmp(b))
});
let noise = match samples.len() {
0 | 1 => Noise::Unknown,
_ => {
let low = samples.iter().copied().min().unwrap_or(Millis::ZERO);
let high = samples.iter().copied().max().unwrap_or(Millis::ZERO);
Noise::Measured {
spread: high.saturating_sub(low),
samples: samples.to_vec(),
}
}
};
let knee = knee_of(total_work, critical_path);
let scan = executor_scan(
graph,
critical_path,
executors,
knee,
policy,
build.build.jobs,
);
let mut scenarios: Vec<Scenario> = Vec::new();
let unsplittable: Vec<usize> = ranked
.iter()
.copied()
.filter(|i| units.get(*i).is_some_and(|u| !u.splittable))
.take(top)
.collect();
for index in ranked
.iter()
.copied()
.filter(|i| units.get(*i).is_some_and(|u| u.splittable))
.take(top)
{
let (Some(unit), Some(id)) = (units.get(index), ids.get(index).copied()) else {
continue;
};
if let Some(scenario) = split_scenario(graph, &baseline, id, unit, &noise, policy) {
scenarios.push(scenario);
}
}
scenarios.extend(scan.iter().map(|point| executor_scenario(&baseline, point)));
sort_scenarios(&mut scenarios);
let mut diagnostics = build.diagnostics.clone();
diagnostics.extend(noise_diagnostics(&noise, &scenarios, samples.len()));
diagnostics.sort_by(|a, b| {
a.severity
.cmp(&b.severity)
.then(a.code.cmp(b.code))
.then(a.message.cmp(&b.message))
});
Findings {
input: build.build.clone(),
graph: GraphFacts {
units: graph.len(),
edges: graph.edge_count(),
metadata_edges: metadata_edges(graph, &ids),
total_work,
},
baseline,
path: path_steps(graph, &analysis),
units,
ranked,
scenarios,
unsplittable,
scan,
knee,
noise,
diagnostics,
top,
}
}
fn metadata_edges(graph: &BuildGraph, ids: &[UnitId]) -> usize {
ids.iter()
.filter_map(|id| graph.dependencies(*id))
.flatten()
.filter(|dep| dep.kind == EdgeKind::Metadata)
.count()
}
fn unit_facts(graph: &BuildGraph, analysis: &Analysis, ids: &[UnitId]) -> Vec<UnitFacts> {
ids.iter()
.filter_map(|id| {
let unit = graph.unit(*id)?;
Some(UnitFacts {
unit: id.index(),
label: Label::of(graph, *id),
kind: unit.kind,
total: unit.total,
metadata_at: unit.metadata_at,
earliest_start: analysis.earliest_start(*id).unwrap_or(Millis::ZERO),
earliest_finish: analysis.earliest_finish(*id).unwrap_or(Millis::ZERO),
latest_finish: analysis.latest_finish(*id).unwrap_or(Millis::ZERO),
slack: analysis.slack(*id).unwrap_or(Millis::ZERO),
on_critical_path: analysis.is_critical(*id),
dependencies: graph.dependencies(*id).map_or(0, <[_]>::len),
dependents: graph.dependents(*id).map_or(0, <[_]>::len),
contribution: analysis.critical_contribution(*id).unwrap_or(Millis::ZERO),
splittable: !matches!(
unit.kind,
UnitKind::BuildScriptCompile | UnitKind::BuildScriptRun
),
})
})
.collect()
}
fn path_steps(graph: &BuildGraph, analysis: &Analysis) -> Vec<Step> {
let mut steps: Vec<Step> = Vec::new();
for id in analysis.critical_path() {
let Some(unit) = graph.unit(*id) else {
continue;
};
let contribution = analysis.critical_contribution(*id).unwrap_or(Millis::ZERO);
let incoming = steps.last().map(|previous: &Step| {
if previous.contribution < previous.total {
EdgeKind::Metadata
} else {
EdgeKind::Full
}
});
steps.push(Step {
unit: id.index(),
label: Label::of(graph, *id),
kind: unit.kind,
enter: analysis.earliest_start(*id).unwrap_or(Millis::ZERO),
exit: analysis.earliest_finish(*id).unwrap_or(Millis::ZERO),
contribution,
incoming,
total: unit.total,
metadata_at: unit.metadata_at,
});
}
steps
}
fn knee_of(total_work: Millis, critical_path: Millis) -> u32 {
let dominates = |j: NonZeroU32| critical_path >= total_work.div_ceil_by(NonZeroU64::from(j));
let start = match NonZeroU64::new(critical_path.get()) {
Some(path) => u32::try_from(total_work.div_ceil_by(path).get()).unwrap_or(u32::MAX),
None => 1,
};
let mut candidate = start.max(1);
loop {
let Some(j) = NonZeroU32::new(candidate) else {
return 1;
};
if dominates(j) || candidate == u32::MAX {
return candidate;
}
candidate = candidate.saturating_add(1);
}
}
fn scan_points(executors: NonZeroU32, knee: u32) -> Vec<NonZeroU32> {
let cap = 16
.max(executors.get().saturating_mul(2))
.max(knee.saturating_add(2));
let mut points: BTreeSet<u32> = BTreeSet::new();
let mut doubling = 1u32;
while doubling <= cap {
points.insert(doubling);
let Some(next) = doubling.checked_mul(2) else {
break;
};
doubling = next;
}
points.insert(executors.get());
points.insert(knee.max(1));
points.into_iter().filter_map(NonZeroU32::new).collect()
}
fn executor_scan(
graph: &BuildGraph,
critical_path: Millis,
executors: NonZeroU32,
knee: u32,
policy: Policy,
measured_at: Option<u32>,
) -> Vec<ScanPoint> {
scan_points(executors, knee)
.into_iter()
.map(|j| {
let area = area_bound(graph, j);
ScanPoint {
executors: j,
area_bound: area,
lower_bound: critical_path.max(area),
makespan: simulate(graph, j, policy).makespan(),
graph_constrained: critical_path >= area,
is_knee: j.get() == knee,
direction: match measured_at {
None => Direction::Unknown,
Some(measured) if measured == j.get() => Direction::Measured,
Some(measured) if measured < j.get() => Direction::Optimistic,
Some(_) => Direction::Pessimistic,
},
measured_at,
}
})
.collect()
}
fn executor_scenario(baseline: &Baseline, point: &ScanPoint) -> Scenario {
let mut notes = Vec::new();
if point.is_knee {
notes.push(format!(
"the knee: from {} executors on, the critical path dominates total work divided \
between them, so more executors cannot shorten this build",
point.executors
));
}
notes.push(match point.direction {
Direction::Measured => {
"the per-unit weights were measured at this executor count, so this is the one \
absolute time in the scan that the model was calibrated against"
.to_owned()
}
Direction::Optimistic => format!(
"above the {} executors the weights were measured at, so this makespan is optimistic: \
the same compilations take longer when more of them compete for memory bandwidth",
point.measured_at.unwrap_or_default()
),
Direction::Pessimistic => format!(
"below the {} executors the weights were measured at, so this makespan is pessimistic: \
the same compilations take less time when fewer of them run at once",
point.measured_at.unwrap_or_default()
),
Direction::Unknown => {
"the timing report does not record what executor count the build ran \
with, so how wrong this makespan is cannot be said"
.to_owned()
}
});
Scenario {
kind: "set-executors",
target: Target::Executors(point.executors.get()),
exact: true,
fraction_swept: None,
overhead: None,
assumptions: vec![
"the per-unit weights come from one build at one executor count and are not invariant \
to it: measured elsewhere, total unit work fell 23% to 30% between ten executors and \
two"
.to_owned(),
"one unit occupies one executor, which is not what Cargo does: a rustc holds one \
jobserver token for its lifetime and acquires more for parallel codegen, and a \
build-script execution takes none at all"
.to_owned(),
],
critical_path: Range {
low: baseline.critical_path,
high: baseline.critical_path,
},
saving: Saving { low: 0, high: 0 },
makespan: Range {
low: point.makespan,
high: point.makespan,
},
anomaly: false,
notes,
}
}
fn split_scenario(
graph: &BuildGraph,
baseline: &Baseline,
id: UnitId,
unit: &UnitFacts,
noise: &Noise,
policy: Policy,
) -> Option<Scenario> {
let mut critical: Option<Range> = None;
let mut makespan: Option<Range> = None;
let mut anomaly = false;
for (numerator, denominator) in SWEEP {
let Some(denominator) = NonZeroU64::new(denominator) else {
continue;
};
for dependents in [SplitDependents::Optimistic, SplitDependents::Pessimistic] {
let transform = Transform::SplitUnit {
unit: id,
numerator,
denominator,
dependents,
overhead: Millis::ZERO,
};
let Ok(applied) = apply(graph, &transform) else {
continue;
};
let path = analyze(applied.graph()).critical_path_len();
let span = simulate(applied.graph(), baseline.executors, policy).makespan();
widen(&mut critical, path);
widen(&mut makespan, span);
let path_moved = compare(baseline.critical_path, path);
let span_moved = compare(baseline.makespan, span);
if path_moved != 0 && span_moved != 0 && path_moved != span_moved {
anomaly = true;
}
}
}
let critical = critical?;
let makespan = makespan?;
let saving = Saving {
low: difference(baseline.critical_path, critical.high),
high: difference(baseline.critical_path, critical.low),
};
let mut notes = Vec::new();
if saving.high <= 0 {
notes.push(
"no division in the sweep shortens the critical path, so this crate is not worth \
splitting for build time"
.to_owned(),
);
} else if saving.low == saving.high {
notes.push(
"every division in the sweep gives the same critical path, because what the split \
releases is bounded by something else; a range of zero width here is a degeneracy \
rather than extra confidence in the number"
.to_owned(),
);
}
if let Some(spread) = noise.spread() {
if saving.high < i64::try_from(spread.get()).unwrap_or(i64::MAX) {
notes.push(format!(
"below the noise floor: the most this could save is {}ms, against a run-to-run \
spread of {spread} measured across the supplied timing reports, so it is not \
distinguishable from noise",
saving.high.max(0)
));
}
}
if anomaly {
notes.push(
"somewhere in the sweep the simulated makespan moved opposite to the critical path, \
which greedy list scheduling permits; the interval is anchored on the critical path, \
which is monotone under this change"
.to_owned(),
);
}
Some(Scenario {
kind: "split-crate",
target: Target::Unit(unit.label.clone()),
exact: false,
fraction_swept: Some(SWEEP_BOUNDS),
overhead: Some(Millis::ZERO),
assumptions: vec![
format!(
"the division of work between the halves is swept from 0.{:02} to 0.{:02}; no \
single division is assumed",
SWEEP_BOUNDS.0, SWEEP_BOUNDS.1
),
"each half pays the per-crate overhead given by overhead_ms, which defaults to zero \
because no measurement of it exists"
.to_owned(),
"dependent assignment: optimistic and pessimistic bounds coincide at an even division, \
so the interval is made of the sweep over the division rather than of that pair"
.to_owned(),
"the optimistic bound attaches every dependent to whichever half finishes first, \
which is a limit a plausible refactor cannot beat rather than a shape anyone would \
write"
.to_owned(),
],
critical_path: critical,
saving,
makespan,
anomaly,
notes,
})
}
fn noise_diagnostics(noise: &Noise, scenarios: &[Scenario], reports: usize) -> Vec<Diagnostic> {
let mut out = Vec::new();
match noise {
Noise::Unknown => out.push(Diagnostic {
severity: Severity::Warning,
code: "noise-floor-unknown",
message: format!(
"only {} timing report was supplied, so the run-to-run spread could not be \
measured and no saving can be checked against it; supply --timings once per \
clean build to measure it",
if reports == 1 { "one" } else { "no" }
),
}),
Noise::Measured { spread, samples } => {
for scenario in scenarios {
if scenario.kind != "split-crate" {
continue;
}
if scenario.saving.high >= i64::try_from(spread.get()).unwrap_or(i64::MAX) {
continue;
}
let Target::Unit(label) = &scenario.target else {
continue;
};
out.push(Diagnostic {
severity: Severity::Warning,
code: "saving-below-noise-floor",
message: format!(
"estimated saving of at most {}ms for {} is smaller than the {spread} \
run-to-run spread measured across the {} supplied timing reports",
scenario.saving.high.max(0),
label.display(),
samples.len()
),
});
}
}
}
out
}
fn sort_scenarios(scenarios: &mut [Scenario]) {
scenarios.sort_by(|a, b| {
b.saving
.high
.cmp(&a.saving.high)
.then(a.kind.cmp(b.kind))
.then_with(|| target_key(&a.target).cmp(&target_key(&b.target)))
});
}
fn target_key(target: &Target) -> (Label, u32) {
match target {
Target::Unit(label) => (label.clone(), 0),
Target::Executors(count) => (
Label {
package: String::new(),
version: String::new(),
target: String::new(),
},
*count,
),
}
}
fn widen(range: &mut Option<Range>, value: Millis) {
*range = Some(match *range {
None => Range {
low: value,
high: value,
},
Some(current) => Range {
low: current.low.min(value),
high: current.high.max(value),
},
});
}
fn difference(before: Millis, after: Millis) -> i64 {
let before = i64::try_from(before.get()).unwrap_or(i64::MAX);
let after = i64::try_from(after.get()).unwrap_or(i64::MAX);
before.saturating_sub(after)
}
fn compare(before: Millis, after: Millis) -> i32 {
match before.cmp(&after) {
core::cmp::Ordering::Less => -1,
core::cmp::Ordering::Equal => 0,
core::cmp::Ordering::Greater => 1,
}
}
#[allow(clippy::integer_division)]
fn hundredths(work: Millis, makespan: Millis) -> u64 {
let divisor = makespan.get();
if divisor == 0 {
return 0;
}
work.get()
.saturating_mul(100)
.saturating_add(divisor / 2)
.saturating_div(divisor)
}