nordisk/gunnar

crates/gunnar-wire/tests/want_cost.rs

//! What a `want` list costs the object store.
//!
//! `commit_wants` peeled **every** `want` line, and `peel` is an object read.
//! The want list is whatever the peer sent, and nothing deduplicates it, so a
//! client naming the same reference ten thousand times bought ten thousand
//! store reads for one answer — a cost the peer chooses, on a list the peer
//! also sizes.
//!
//! # Why this counts reads rather than timing anything
//!
//! The same reason `connectivity_cost.rs` gives: a wall clock passes on a small
//! fixture whatever the complexity is, and a single-N bound passes on anything
//! if the bound is generous. So the assertion is **`cost(N) == cost(1)`**,
//! exactly. A path that peels per line cannot produce the same number twice.
//!
//! # What this does NOT cover, said plainly
//!
//! The other half is `commit_wants`' `Vec::contains` over the answer so
//! far, quadratic in *distinct* wants. That one is fixed in the same function
//! and **is not guarded here, because it cannot be**: the two spellings return
//! identical output and touch the store identically, so only wall-clock time
//! separates them, and this crate does not assert on wall clock. Counting a
//! guard that does not exist would be worse than naming the gap.

mod common;

use std::sync::Arc;

use gix_hash::Kind;
use gunnar_wire::upload_pack::{Config, FetchRequest, WantPolicy};
use gunnar_wire::UploadPack;

use common::{Counting, Fixture};

/// Ask for `fixture.four` `repeats` times in one request, and report how many
/// times the server touched the object store.
fn touches_for_repeated_wants(repeats: usize) -> usize {
    let fixture = Fixture::build(Kind::Sha1);
    let counting = Arc::new(Counting::new(fixture.git.inner.clone()));

    let request = FetchRequest {
        // The same want over and over. A real client does this by naming a tag
        // and its peeled target, or by listing a ref twice under two prefixes;
        // an unfriendly one does it because nothing stops it.
        wants: vec![fixture.four; repeats],
        done: true,
        thin_pack: true,
        ofs_delta: true,
        ..Default::default()
    };

    // `WantPolicy::Any` keeps `check_wants` from doing its own reachability
    // walk, so what is being counted is the want-peeling path and not a
    // policy check that happens to scale the same way.
    let upload = UploadPack::new(counting.as_ref(), fixture.kind).with_config(Config {
        want_policy: WantPolicy::Any,
        ..Default::default()
    });

    counting.reset();
    let mut out = Vec::new();
    upload.fetch(&request, &mut out).expect("the fetch");
    counting.touches()
}

/// Repeating a `want` must not repeat the work behind it.
///
/// Exact equality, not a bound: a server that peels per line cannot answer the
/// same number for one want and for a thousand.
#[test]
fn repeating_a_want_costs_the_same_as_naming_it_once() {
    let one = touches_for_repeated_wants(1);
    let many = touches_for_repeated_wants(1000);

    // The floor first. A `commit_wants` stubbed to return nothing, or a fetch
    // that never read an object, would satisfy any equality above and prove
    // nothing at all.
    assert!(
        one > 0,
        "a fetch that touched the store zero times cannot be measuring the \
         want path"
    );
    assert_eq!(
        many, one,
        "1000 copies of one want cost {many} store touches and a single want \
         costs {one}; the want list is the peer's to size, so per-line work in \
         it is per-line work the peer buys"
    );
}