nordisk/znippy

plugins/native/znippy-plugin-git/examples/forest_stats.rs

//! **How skewed is a real pack's delta forest?** — the number that decides how
//! far the resolver's ordered emitter can be made to run ahead.
//!
//! For every root it prints the subtree's **size** (objects) and its **index
//! span** (the highest entry index in the subtree minus the root's). The span
//! is the one that matters: the ordered emitter releases objects in entry
//! order, so a subtree whose span is a million entries holds the cursor for as
//! long as it takes to walk, and every other worker's output buffers behind it.
//!
//! ```text
//! cargo run --release --example forest_stats -- <pack>
//! ```

use anyhow::{Result, anyhow};
use znippy_plugin_git::forest::DeltaForest;
use znippy_plugin_git::object::GitHashKind;

fn main() -> Result<()> {
    let path = std::env::args()
        .nth(1)
        .ok_or_else(|| anyhow!("usage: forest_stats <pack>"))?;
    let f = std::fs::File::open(&path)?;
    let map = unsafe { memmap2::Mmap::map(&f)? };
    let w = znippy_plugin_git::pack_walk::walk(&map, GitHashKind::Sha1.oid_len())?;
    let forest = DeltaForest::build(&w)?;
    let n = w.entries.len();
    println!("{path}\n  {n} entries, {} roots", forest.whole_roots().len() + forest.ref_roots().len());

    // One sweep, no stack: a parent's index is always lower than its child's,
    // so `root_of` and the running maximum are both decided in entry order.
    let mut root_of = vec![u32::MAX; n];
    let mut size = vec![0u64; n];
    let mut hi = vec![0u32; n];
    for i in 0..n {
        let p = forest.parent(i as u32);
        let r = if p == znippy_plugin_git::forest::NO_PARENT {
            i as u32
        } else {
            root_of[p as usize]
        };
        root_of[i] = r;
        size[r as usize] += 1;
        hi[r as usize] = hi[r as usize].max(i as u32);
    }
    let mut sizes: Vec<(u64, u32)> = (0..n as u32)
        .filter(|r| size[*r as usize] > 0)
        .map(|r| (size[r as usize], r))
        .collect();
    sizes.sort_unstable();
    let total: u64 = sizes.iter().map(|(s, _)| *s).sum();
    let pick = |q: f64| sizes[((sizes.len() - 1) as f64 * q) as usize];
    println!(
        "  subtree size: min {} · p50 {} · p90 {} · p99 {} · p99.9 {} · MAX {}   (sum {total})",
        sizes[0].0,
        pick(0.5).0,
        pick(0.9).0,
        pick(0.99).0,
        pick(0.999).0,
        sizes[sizes.len() - 1].0
    );
    let mut spans: Vec<u64> = sizes
        .iter()
        .map(|(_, r)| (hi[*r as usize] - *r) as u64)
        .collect();
    spans.sort_unstable();
    let pk = |q: f64| spans[((spans.len() - 1) as f64 * q) as usize];
    println!(
        "  index span:   p50 {} · p90 {} · p99 {} · p99.9 {} · MAX {}",
        pk(0.5),
        pk(0.9),
        pk(0.99),
        pk(0.999),
        spans[spans.len() - 1]
    );
    // The ten biggest subtrees, with the span each one pins the cursor across.
    println!("  the ten biggest subtrees (root, objects, span):");
    for (s, r) in sizes.iter().rev().take(10) {
        println!("    root {r:>10}  {s:>9} objects  span {}", hi[*r as usize] - *r);
    }
    // What the emitter would have to hold: for each root in ascending order,
    // how many entries above it belong to OTHER roots and would be buffered
    // while this one is walked.
    let worst = sizes.iter().rev().take(1).map(|(_, r)| *r).next().unwrap_or(0);
    let above = (0..n).filter(|i| *i as u32 > worst && root_of[*i] != worst).count();
    println!(
        "  the worst root is {worst}; {above} entries above it belong to other roots — that is \
         what an entry-ordered emitter must buffer while it is walked"
    );
    Ok(())
}