crates/gunnar-delta/src/window.rs
//! The sliding window over size-sorted objects. The driver.
//!
//! # The order, and what it buys
//!
//! Objects are sorted by kind, then [`Object::name_hash`] descending, then
//! [`Object::epoch`] **ascending**, then **size descending**, then id — git's
//! own `type_size_sort` key with one term git does not have. An object may
//! only be deltified against one that comes *earlier* in that order, which is
//! four properties at once:
//!
//! * bases are at least as **old** as their targets, so a fetch — which sends
//! the new end of the history — ships its objects as deltas against ones the
//! receiver already has, rather than shipping the newest revision of every
//! changed file whole. Worth **2.06×** on a 50-commit fetch of gunnar's own
//! 19-repository corpus; see [`Object::epoch`];
//! * within one epoch, bases are larger than their targets, which is the
//! direction that compresses (a shrinking file is a copy plus nothing; a
//! growing one is a copy plus the new tail either way);
//! * the delta graph is **acyclic by construction**: `base < target` in a total
//! order admits no cycle, so no cycle detection exists here and none can be
//! missing;
//! * the output is already in dependency order, so a pack writer can emit it
//! straight through and every `OFS_DELTA` points backwards.
//!
//! # Zero copy
//!
//! [`Object`] holds `&'a [u8]`. Nothing in this module copies object data:
//! not into the window, not into the index cache, not into a worker. The only
//! bytes allocated are the deltas themselves, which are new bytes by definition.
//!
//! # Zero wait
//!
//! [`gix_parallel::in_parallel_with_slice`] hands out chunks through
//! an atomic index: there is no barrier, and a worker that finishes a chunk
//! takes the next one. Chunks are contiguous runs of the sorted order, so a
//! worker's index cache is a ring that turns over one object at a time.
//!
//! # Determinism
//!
//! **The output bytes are identical at 1 thread and at 32.** Every object's
//! candidate set is `[i - window, i)` in the sorted order and nothing else; no
//! worker observes another's result; chunking changes only *who* computes an
//! answer, never *what* it is. Chain depth is resolved afterwards in one serial
//! pass, so it cannot depend on completion order either.
//! `tests/determinism.rs` asserts it byte-for-byte across thread counts.
//!
//! # The tier this belongs to
//!
//! Delta computation happens at **repack**, the batch tier: offline, one at a
//! time, and what a machine's full core count is for. It is not the
//! serving tier: per-request fan-out at forge concurrency is a measured
//! regression (`P-004` in `.nornir/performance-design.md`), and this crate is
//! not where that mistake gets made. A caller on a serving path should pass
//! `thread_limit: Some(1)`, or better, not be calling this at all.
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use gix_parallel::in_parallel_with_slice;
use gix_utils::progress::{self, Count, Progress};
use gix_hash::ObjectId;
use crate::encode::{delta_into_with_index, Encode};
use crate::error::{Error, Result};
use crate::index::Index;
use crate::limits::Limits;
/// One object offered to the window, borrowed.
#[derive(Debug, Clone, Copy)]
pub struct Object<'a> {
/// The object's id. Carried through to the output; never hashed here.
pub id: ObjectId,
/// Its type. Only objects of the same kind are deltified against each other,
/// as git does. A tree and a blob share no structure worth searching for.
pub kind: gix_object::Kind,
/// A number that means "this object and that object are likely alike".
///
/// The **primary** sort key after the kind, ahead of size, so objects
/// sharing one are adjacent and therefore inside each other's window. This
/// is the single highest-value knob in the whole search: a base that never
/// shares a window with its target cannot be found however good the encoder
/// is. See [`crate::name_hash`] for what to put here and what it is worth
/// (fluentui, `git repack -adf`, 439 MiB → 160 MiB on the key alone).
///
/// **`0` means "no information", and that is the honest default**: every
/// object carrying `0` leaves the order exactly as it was before this field
/// existed — kind, then size descending — so a caller with no paths to hand
/// loses nothing and is told nothing false.
///
/// It is deliberately not a path. A caller that has something better than a
/// hash, such as a dense id per distinct path (which is what git's
/// `--path-walk` reduces to), supplies that instead and the search improves
/// with no change here.
pub name_hash: u32,
/// How **new** this object is, as a rank over the repository's commits.
///
/// Larger is newer. It sorts **ascending** — after the name hash and before
/// the size — so within one group of like-named objects the *oldest*
/// version comes first, and since a base may only be an object earlier in
/// the order, **a base is always at least as old as its target**.
///
/// # This is the transfer, not the archive
///
/// A clone sends the whole history and does not care which way a chain
/// points. A **fetch** sends a suffix, and the two directions are not
/// symmetric at all:
///
/// * base older than target — the base is on the *client's* side of the
/// negotiation cut, so the target ships as a thin delta of a few hundred
/// bytes against an object the receiver already has;
/// * base newer than target — the base is the object being sent, so the
/// *newest* revision of every changed file has to travel whole.
///
/// MEASURED on oden 2026-08-04, 16 of the 19 `workspace_nordisk`
/// repositories, a real negotiated fetch 50 commits behind, stock git 2.53.0
/// as the client, the identical object set in all three columns:
///
/// | pack | bytes |
/// |---|---:|
/// | `git pack-objects --thin` (bases older, on the client) | 6 467 525 |
/// | `git pack-objects` (bases inside the set, i.e. newer) | 13 337 022 |
///
/// **2.06×**, on nothing but which way the chains point. Size-descending
/// alone — git's `type_size_sort`, and this crate's only key before this
/// field — is blind to the difference, because whether the newest revision
/// of a file is the largest one is a fact about the file.
///
/// **`0` means "no information", and every object carrying `0` leaves the
/// order exactly as it was before this field existed.** A caller with no
/// commit graph to hand — every pushing client — loses nothing and is told
/// nothing false.
pub epoch: u32,
/// Its canonical, decompressed bytes. Borrowed for the call's lifetime.
pub data: &'a [u8],
}
/// How to run the window search.
#[derive(Debug, Clone)]
pub struct Options {
/// How many earlier objects each object is compared against. git's default
/// is 10.
pub window: usize,
/// Longest delta chain permitted. git's default is 50. A chain of depth `d`
/// costs a reader `d` object reconstructions.
pub depth: usize,
/// Cap the worker threads. `None` means the machine's core count, correct
/// for the batch tier and wrong for a serving path (see the module docs).
pub thread_limit: Option<usize>,
/// Per-pair encoder settings.
pub encode: Encode,
/// Memory and size caps. See [`Limits`].
pub limits: Limits,
}
impl Default for Options {
fn default() -> Self {
Options {
window: 10,
depth: 50,
thread_limit: None,
encode: Encode::default(),
limits: Limits::default(),
}
}
}
/// One object's outcome, in sorted order.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Deltified {
/// Index into the `objects` slice this came from.
pub source: usize,
/// Index into *this* result vector of the base, always less than this
/// entry's own position. `None` means the object is emitted whole.
pub base: Option<usize>,
/// Chain length: `0` for a base, `base.depth + 1` otherwise.
pub depth: u16,
/// The delta payload, or `None` for a base object.
pub data: Option<Vec<u8>>,
}
impl Deltified {
/// `true` when this entry carries a delta rather than a whole object.
pub fn is_delta(&self) -> bool {
self.data.is_some()
}
}
/// How many improving candidates are remembered per object, so that an object
/// whose best base turns out to be too deep can fall back instead of becoming a
/// base itself.
///
/// Four rather than `window`: the list only ever holds *improving* candidates
/// (each is smaller than the last, because `max_size` shrinks as the search
/// runs), and needing more than four fallbacks means four of the closest objects
/// in size order are all at maximum depth, which the depth limit exists to make
/// rare.
const KEPT_CANDIDATES: usize = 4;
/// What the parallel phase produces per object.
#[derive(Default)]
struct Best {
/// `(delta length, base position in sorted order)`, worst first.
candidates: Vec<(u32, u32)>,
/// Bytes of the last (best) candidate.
data: Option<Vec<u8>>,
}
struct Chunk {
start: usize,
end: usize,
out: Vec<Best>,
}
/// A ring of built indexes, keyed by position in the sorted order.
///
/// Positions enter the window once and leave once, so this is a queue, not a
/// cache with a policy: `retire` drops everything below the window's low edge.
/// The byte budget is the second door: an index that would push the ring over
/// [`Limits::index_memory_per_thread`] evicts from the front, which costs a
/// rebuild rather than an allocation the machine cannot honour.
struct IndexRing {
entries: std::collections::VecDeque<(usize, Option<Index>)>,
bytes: usize,
budget: usize,
}
impl IndexRing {
fn new(budget: usize) -> Self {
IndexRing {
entries: Default::default(),
bytes: 0,
budget,
}
}
fn get(&self, pos: usize) -> Option<&Option<Index>> {
self.entries.iter().find(|(p, _)| *p == pos).map(|(_, i)| i)
}
fn insert(&mut self, pos: usize, index: Option<Index>) {
let cost = index.as_ref().map_or(0, Index::bytes);
while self.bytes + cost > self.budget && !self.entries.is_empty() {
self.evict_front();
}
self.bytes += cost;
self.entries.push_back((pos, index));
}
fn evict_front(&mut self) {
if let Some((_, index)) = self.entries.pop_front() {
self.bytes -= index.as_ref().map_or(0, Index::bytes);
}
}
/// Drop every index for a position below `low`.
fn retire(&mut self, low: usize) {
while self.entries.front().is_some_and(|(p, _)| *p < low) {
self.evict_front();
}
}
}
/// How often the watcher thread wakes.
///
/// It sets the progress refresh rate, and it is a **floor on the whole
/// call**. `in_parallel_with_slice` runs the periodic closure on a scoped thread
/// that sleeps for whatever the closure returns, and `std::thread::scope` waits
/// for that thread, so `deltify` cannot return until the watcher next wakes.
/// gitoxide's own convention here is 50 ms (`gix_pack::cache::delta::traverse`
/// does exactly that), and it showed up as a bench where every wall time was a
/// multiple of 50 ms. A 46 ms search reports 52 ms, and every faster one
/// reporting 51. `tests/latency.rs` is the guard.
///
/// It is also how long `should_interrupt` takes to be noticed, which is reason
/// enough to keep it short quite apart from the measurement.
const WATCH_TICK: std::time::Duration = std::time::Duration::from_millis(1);
/// Push progress every this many ticks, so the *sleep* stays short without the
/// *reporting* becoming a thousand updates a second into a caller's prodash
/// tree. The refresh rate is unchanged at 50 ms; only the floor moved.
const PROGRESS_EVERY: u32 = 50;
/// How many consecutive objects one worker takes at a time.
///
/// Two forces pull against each other. A chunk owns its index ring, so it has to
/// rebuild the `window` indexes sitting to its left before it can start: **long
/// chunks waste less**. But a worker only ever holds one chunk at a time, so
/// with fewer chunks than threads most of the machine is idle: **short chunks
/// parallelise better**. The old rule looked only at the first force, a flat
/// `window * 8`, and on a few hundred objects that is five chunks, so a
/// 32-core box ran five of them.
///
/// The second force wins wherever they conflict, because the two costs are not
/// the same size. Building an index is a single pass over one object; searching
/// for that object's base is up to `window` delta encodes over comparable bytes.
/// A rebuilt index is worth roughly a tenth of an object's own work, so a chunk
/// of `window` objects pays about 10% and buys the rest of the machine.
///
/// This aims for four chunks per thread, enough that one slow chunk cannot
/// leave a core idle at the end. Floored so a chunk is never trivially short,
/// and capped at the old value so a large repack, which has chunks to spare,
/// keeps the efficient long ones. At one thread it yields the previous number
/// exactly.
fn chunk_len(n: usize, opts: &Options) -> usize {
let threads = gix_parallel::num_threads(opts.thread_limit).max(1);
let ideal = n.div_ceil(threads.saturating_mul(4).max(1));
ideal.clamp(opts.window.max(16), (opts.window * 8).max(64))
}
/// Sort key: kind, then [`Object::name_hash`] **descending**, then
/// [`Object::epoch`] **ascending**, then size descending, then id. Total and
/// stable, so the order, and therefore every candidate set, is a pure function
/// of the input.
///
/// This is git's `type_size_sort` (`builtin/pack-objects.c`) with git's own
/// direction on the hash, minus the delta-island term gunnar has no use for
/// (one repository per store, no fork network), plus one term git does not
/// have and does not need.
///
/// # Why the epoch sits above the size and not below it
///
/// Below the size it would be a tie-break, and sizes almost never tie. The
/// whole of what this field is for is deciding **which way a chain points**,
/// and that is decided by which of two revisions of one file sorts first — so
/// it has to outrank the size, and it has to sit inside the group the name hash
/// made, not above it. Above the name hash it would split one file's history
/// into per-epoch buckets that never see each other, which is the one thing
/// worse than the wrong direction.
///
/// git can afford to be blind here because a git server re-runs
/// `pack-objects --thin` over the transfer set at serve time. gunnar's serve
/// path copies pack entries verbatim (`P-001`), so the direction the repacker
/// chose *is* the direction on the wire, for every fetch, until the next `gc`.
///
/// With every `name_hash` and every `epoch` at `0` this reduces exactly to the
/// key this crate started with, which is why adding either field could not
/// change an existing caller's output.
fn sorted_order(objects: &[Object<'_>]) -> Vec<usize> {
let mut order: Vec<usize> = (0..objects.len()).collect();
order.sort_unstable_by(|&a, &b| {
let (x, y) = (&objects[a], &objects[b]);
(x.kind as u8)
.cmp(&(y.kind as u8))
.then(y.name_hash.cmp(&x.name_hash))
.then(x.epoch.cmp(&y.epoch))
.then(y.data.len().cmp(&x.data.len()))
.then(x.id.cmp(&y.id))
});
order
}
/// Search for a delta base for every object and choose one, honouring `depth`.
///
/// Returns one [`Deltified`] per input object, **in sorted order**, with every
/// base appearing before the deltas that reference it.
///
/// Refuses a request outside [`Options::limits`], with [`Error::Refused`], and
/// before allocating anything.
pub fn deltify(
objects: &[Object<'_>],
opts: &Options,
progress: &mut dyn Progress,
should_interrupt: &AtomicBool,
) -> Result<Vec<Deltified>> {
let total_bytes: u64 = objects.iter().map(|o| o.data.len() as u64).sum();
opts.limits
.validate(opts.window, opts.depth, objects.len(), total_bytes)?;
let order = sorted_order(objects);
let n = order.len();
progress.init(Some(n), progress::count("objects"));
if n == 0 {
return Ok(Vec::new());
}
let chunk_len = chunk_len(n, opts);
let mut chunks: Vec<Chunk> = (0..n)
.step_by(chunk_len)
.map(|start| Chunk {
start,
end: (start + chunk_len).min(n),
out: Vec::new(),
})
.collect();
// More threads than chunks is threads spawned to find nothing to do.
let thread_limit =
Some(gix_parallel::num_threads(opts.thread_limit).min(chunks.len().max(1)));
let done = AtomicUsize::new(0);
let mut tick = 0u32;
let ctx = Ctx {
objects,
order: &order,
opts,
done: &done,
};
in_parallel_with_slice(
&mut chunks,
thread_limit,
|_thread| IndexRing::new(opts.limits.index_memory_per_thread),
|chunk, ring, _threads_left, stop| ctx.run_chunk(chunk, ring, stop),
|| {
tick = tick.wrapping_add(1);
if tick % PROGRESS_EVERY == 0 {
progress.set(done.load(Ordering::Relaxed));
}
(!should_interrupt.load(Ordering::Relaxed)).then_some(WATCH_TICK)
},
|_| (),
)?;
if should_interrupt.load(Ordering::Relaxed) {
return Err(Error::Interrupted);
}
progress.set(n);
resolve_chains(objects, &order, chunks, opts)
}
/// Everything a worker reads. Shared immutably, so a chunk's answer depends on
/// nothing but the chunk.
struct Ctx<'a, 'b> {
objects: &'a [Object<'b>],
order: &'a [usize],
opts: &'a Options,
done: &'a AtomicUsize,
}
impl Ctx<'_, '_> {
fn run_chunk(&self, chunk: &mut Chunk, ring: &mut IndexRing, stop: &AtomicBool) -> Result<()> {
// A chunk owns its ring, so the `window` positions to its left have to
// be indexed here too. That is the duplicated work chunking costs, and
// `chunk_len = window * 8` is what holds it near an eighth.
let low = chunk.start.saturating_sub(self.opts.window);
for pos in low..chunk.start {
let index = self.build_index(pos)?;
ring.insert(pos, index);
}
chunk.out = Vec::with_capacity(chunk.end - chunk.start);
let mut buf = Vec::new();
let mut best_buf = Vec::new();
for i in chunk.start..chunk.end {
if stop.load(Ordering::Relaxed) {
return Err(Error::Interrupted);
}
ring.retire(i.saturating_sub(self.opts.window));
chunk
.out
.push(self.search(i, ring, &mut buf, &mut best_buf)?);
// This position is a candidate base for the next objects.
let index = self.build_index(i)?;
ring.insert(i, index);
self.done.fetch_add(1, Ordering::Relaxed);
}
Ok(())
}
fn obj(&self, pos: usize) -> &Object<'_> {
&self.objects[self.order[pos]]
}
fn build_index(&self, pos: usize) -> Result<Option<Index>> {
let o = self.obj(pos);
if o.data.len() > self.opts.limits.max_base_size {
// Too big to index, so it is never a base. Not an error: refusing a
// whole repack because one blob is large would be the wrong call.
return Ok(None);
}
Index::build(o.data, &self.opts.limits)
}
/// Try every candidate in the window for object `i`, keeping the improving ones.
fn search(
&self,
i: usize,
ring: &IndexRing,
buf: &mut Vec<u8>,
best_buf: &mut Vec<u8>,
) -> Result<Best> {
let target = self.obj(i);
let mut best = Best::default();
if target.data.len() > self.opts.limits.max_target_size || target.data.is_empty() {
return Ok(best);
}
// git's rule of thumb: a delta that does not at least halve the object
// is not worth the chain it adds. Shrinks with every improvement, which
// is what makes the window affordable.
let mut budget = target.data.len() / 2;
let lowest = i.saturating_sub(self.opts.window);
// Nearest first: adjacent in size order means most alike, so the budget
// tightens early and later candidates abort sooner.
for j in (lowest..i).rev() {
let base = self.obj(j);
if base.kind != target.kind || base.data.is_empty() {
continue;
}
let Some(index) = ring.get(j) else { continue };
let Some(index) = index.as_ref() else {
continue;
};
let mut enc = self.opts.encode.clone();
enc.max_size = Some(budget);
buf.clear();
if !delta_into_with_index(base.data, target.data, Some(index), buf, &enc)? {
continue;
}
best.candidates.push((buf.len() as u32, j as u32));
if best.candidates.len() > KEPT_CANDIDATES {
best.candidates.remove(0);
}
budget = buf.len();
std::mem::swap(buf, best_buf);
}
if !best.candidates.is_empty() {
best.data = Some(std::mem::take(best_buf));
}
best_buf.clear();
Ok(best)
}
}
/// Pick each object's base under the depth limit, serially and in order.
///
/// Every candidate's position is strictly below its target's, so `depth[j]` is
/// final by the time `i` is reached: one pass, no fixpoint, no cycle to break.
fn resolve_chains(
objects: &[Object<'_>],
order: &[usize],
chunks: Vec<Chunk>,
opts: &Options,
) -> Result<Vec<Deltified>> {
let bests: Vec<Best> = chunks.into_iter().flat_map(|c| c.out).collect();
debug_assert_eq!(bests.len(), order.len());
let mut depth = vec![0u16; order.len()];
let mut out: Vec<Deltified> = Vec::with_capacity(order.len());
for (i, mut best) in bests.into_iter().enumerate() {
// `candidates` is ordered worst-to-best; take them best first.
let chosen = best
.candidates
.iter()
.rev()
.find(|(_, j)| (depth[*j as usize] as usize) < opts.depth)
.copied();
match chosen {
Some((_, j)) => {
let j = j as usize;
let is_best = best
.candidates
.last()
.is_some_and(|(_, bj)| *bj as usize == j);
let data = if is_best {
best.data.take().expect("a candidate implies stored bytes")
} else {
// The best base was too deep. Re-encode against the fallback
// Rare, deterministic, and serial on purpose.
let (base, target) = (&objects[order[j]], &objects[order[i]]);
let mut v = Vec::new();
let mut enc = opts.encode.clone();
enc.max_size = None;
delta_into_with_index(
base.data,
target.data,
Index::build(base.data, &opts.limits)?.as_ref(),
&mut v,
&enc,
)?;
v
};
depth[i] = depth[j] + 1;
out.push(Deltified {
source: order[i],
base: Some(j),
depth: depth[i],
data: Some(data),
});
}
None => out.push(Deltified {
source: order[i],
base: None,
depth: 0,
data: None,
}),
}
}
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
fn oid(byte: u8) -> ObjectId {
ObjectId::from_bytes_or_panic(&[byte; 20])
}
/// Two revisions of one file, the newer one LARGER. Size-descending alone
/// makes the newer revision the base and the older one its delta; the epoch
/// key has to turn that round.
///
/// The applied output is `Deltified::base`, i.e. which object the pack
/// would carry whole — not `is_delta()`, which is `true` for exactly one
/// entry either way and so cannot tell the two directions apart.
///
/// **Red-first**: set both epochs to `0` and the assertion below fails with
/// the base at the new revision, which is the pre-change behaviour and the
/// regression this key exists to remove.
#[test]
fn the_older_revision_is_the_base_even_when_it_is_the_smaller_one() {
let old_bytes = b"line one\nline two\nline three\n".repeat(40);
let mut new_bytes = old_bytes.clone();
new_bytes.extend_from_slice(&b"a tail the older revision does not have\n".repeat(20));
assert!(
new_bytes.len() > old_bytes.len(),
"the fixture only means anything if the newer revision is the larger one"
);
let objects = |old_epoch: u32, new_epoch: u32| {
[
Object {
id: oid(1),
kind: gix_object::Kind::Blob,
name_hash: 0xabcd_1234,
epoch: old_epoch,
data: &old_bytes,
},
Object {
id: oid(2),
kind: gix_object::Kind::Blob,
name_hash: 0xabcd_1234,
epoch: new_epoch,
data: &new_bytes,
},
]
};
let run = |objs: [Object<'_>; 2]| {
let out = deltify(
&objs,
&Options::default(),
&mut progress::Discard,
&AtomicBool::default(),
)
.expect("the encoder refused a two-object window");
// The entry with no base is the object that travels whole.
let base = out
.iter()
.find(|e| e.base.is_none())
.expect("every chain has a base");
objs[base.source].id
};
// No information: the previous behaviour, and the negative control that
// proves the fixture can express the wrong answer at all.
assert_eq!(
run(objects(0, 0)),
oid(2),
"with no epochs this ordering is size-descending, so the LARGER (newer) \
revision must be the base -- if this ever reports the older one the \
positive case below is guarding nothing"
);
// Dated: the older revision is the base, so a fetch sending only the
// newer one sends a delta against something the client already has.
assert_eq!(
run(objects(1, 2)),
oid(1),
"the older revision must be the base once the objects are dated"
);
}
/// The epoch must not outrank the name hash: two different files must stay
/// in different groups however their dates fall, or one file's history is
/// split across buckets that never see each other.
///
/// **Red-first**: move `.then(x.epoch.cmp(&y.epoch))` above the name-hash
/// term in [`sorted_order`] and this fails.
#[test]
fn the_epoch_sorts_inside_a_group_and_not_across_groups() {
let a = vec![b'a'; 64];
let b = vec![b'b'; 64];
let objects = [
// Group 0xff, new.
Object {
id: oid(1),
kind: gix_object::Kind::Blob,
name_hash: 0xff,
epoch: 9,
data: &a,
},
// Group 0x11, old.
Object {
id: oid(2),
kind: gix_object::Kind::Blob,
name_hash: 0x11,
epoch: 1,
data: &b,
},
// Group 0xff, old.
Object {
id: oid(3),
kind: gix_object::Kind::Blob,
name_hash: 0xff,
epoch: 2,
data: &a,
},
];
let order = sorted_order(&objects);
let groups: Vec<u32> = order.iter().map(|&i| objects[i].name_hash).collect();
assert_eq!(
groups,
vec![0xff, 0xff, 0x11],
"the name hash must still be the outer key; got {groups:?}"
);
let epochs: Vec<u32> = order.iter().map(|&i| objects[i].epoch).collect();
assert_eq!(
epochs[0], 2,
"inside a group the OLDER object comes first, so it can be the base"
);
}
}