Skip to main content

Analysis

Struct Analysis 

Source
pub struct Analysis { /* private fields */ }
Expand description

Earliest and latest times for every unit of one graph, and the critical path through it.

Produced by analyze. An identifier from a different graph is not detected: identifiers are dense indices, so a foreign one reads as None only when it points past the end, and otherwise returns another unit’s numbers. Do not mix identifiers between graphs.

use critpath_core::{analyze, EdgeKind, GraphBuilder, Millis, Unit, UnitKind};

let mut builder = GraphBuilder::new();
let lib = builder.add_unit(Unit {
    package: "leaf".to_owned(),
    version: "1.0.0".to_owned(),
    target: "leaf".to_owned(),
    kind: UnitKind::Lib,
    total: Millis::new(800),
    metadata_at: Some(Millis::new(600)),
    requires_full_closure: false,
})?;
let bin = builder.add_unit(Unit {
    package: "app".to_owned(),
    version: "1.0.0".to_owned(),
    target: "app".to_owned(),
    kind: UnitKind::Bin,
    total: Millis::new(200),
    metadata_at: None,
    requires_full_closure: true,
})?;
builder.add_edge(lib, bin, EdgeKind::Metadata)?;
let graph = builder.build()?;

let analysis = analyze(&graph);
// The edge offers metadata at 600, but a binary has to link, so it waits for all 800.
assert_eq!(analysis.earliest_start(bin), Some(Millis::new(800)));
assert_eq!(analysis.critical_path_len(), Millis::new(1_000));
assert_eq!(analysis.critical_path(), &[lib, bin]);

Implementations§

Source§

impl Analysis

Source

pub fn critical_path_len(&self) -> Millis

The critical path length: how long the build takes with as many executors as it wants.

Zero for an empty graph. Never depends on the executor count or on a scheduling policy (I10), which is why it is the number to lead with.

Examples found in repository?
examples/scaling.rs (line 104)
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}
Source

pub fn critical_path(&self) -> &[UnitId]

One longest path, from a unit with no dependencies to the unit that finishes last.

Empty for an empty graph. Where several paths are equally long, the reported one is fixed by identifier order so that output is reproducible (I1).

Consecutive units need not be joined by an edge: a unit that requires its whole closure is preceded on the path by the unit in that closure which held it back, which section 3.1 of docs/model.md shows need not be a direct dependency.

Source

pub fn total_work(&self) -> Millis

The total work the analysed graph holds: the sum of every unit’s duration.

Source

pub fn earliest_start(&self, id: UnitId) -> Option<Millis>

The earliest a unit could start, or None if the index is outside this analysis.

An identifier belonging to a different graph is not detected. Identifiers are dense indices, so a foreign one reads as None only when it happens to point past the end, and otherwise names a different unit. Do not mix identifiers between graphs.

Source

pub fn earliest_finish(&self, id: UnitId) -> Option<Millis>

The earliest a unit could finish, or None if the index is outside this analysis.

Source

pub fn latest_finish(&self, id: UnitId) -> Option<Millis>

The latest a unit may finish without lengthening the critical path, or None if the index is outside this analysis.

Source

pub fn slack(&self, id: UnitId) -> Option<Millis>

How much later than its earliest finish a unit may finish, or None if the index is outside this analysis.

Zero exactly for the units that cannot move at all (I9). Note that this is room in the finish time: lengthening a pipelined producer by its slack is safe, but so is lengthening it further, because a consumer released by metadata never waited for the finish anyway.

Source

pub fn is_critical(&self, id: UnitId) -> bool

Whether a unit has no slack at all, so that delaying it lengthens the whole build.

True for every unit of critical_path, and also for units on any other equally long path.

Source

pub fn critical_contribution(&self, id: UnitId) -> Option<Millis>

What a unit adds to the length of critical_path.

A unit traversed over a metadata edge adds only its metadata offset, because that is all the path waited for; otherwise it adds its whole duration. The contributions of the units on the path sum to exactly critical_path_len, which makes them the right quantity to rank candidates for change by.

None for a unit that is not on the reported path, and for an index outside this analysis. A unit off the path adds nothing to it, but that does not mean the build would not notice its absence: check is_critical for units on an equally long path elsewhere.

Trait Implementations§

Source§

impl Clone for Analysis

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for Analysis

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.