DAG-level incremental caching via Merkle subtree hashing
- Dominant language
- Rust
- Stars
- 2
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
## Summary
Add a `Session` abstraction that automatically caches intermediate pipeline results using Merkle-style subtree hashing on the DAG. When only downstream nodes change (e.g., tweaking a filter in an editor), the engine detects unchanged upstream subtrees and resumes from cached materializations — no decode, no geometry recomputation, no caller-managed splitting.
## Motivation
The current `cache_prefix` / `stream_from_cache` API (added in `2b33274`) works but requires callers to:
- Manually split node lists into prefix and suffix
- Build two separate configs
- Manage cache lifetime and invalidation
- Provide a prefix key
For an editor where the user is tweaking filters repeatedly, the caching should be transparent. The DAG already encodes the full dependency structure — the engine should use it.
## Design
### Merkle subtree hashing
Every node gets a deterministic identity during compilation:
```
source_hash = caller-provided (e.g., hash(path, mtime, size))
node_hash(i) = fnv(schema.id, schema.version, params, [node_hash(input) for input in inputs])
```
The DAG is in topological order, so this is one forward pass. `ParamMap` is `BTreeMap` — deterministic iteration. Floats hashed via `to_bits()`.
When the user changes a parameter, only that node's hash changes, cascading downstream but leaving the upstream subtree unchanged:
```
DAG 1: source(abc) → orient(1) → resize(800) → exposure(+0.5) → encode
DAG 2: source(abc) → orient(1) → resize(800) → exposure(+1.0) → encode
↑
identical subtree hash → cache hit
```
### Session
```rust
pub struct Session {
/// Content-addressed cache: subtree_hash → materialized pixels + metadata.
cache: HashMap,
/// Memory budget for cached pixels (bytes). LRU eviction when exceeded.
memory_budget: u64,
}
struct CacheEntry {
pixels: CachedPixels, // Arc> — cheap to produce sources from
metadata: Option,
sidecar: Option,
width: u32,
height: u32,
format: PixelFormat,
last_used: Instant, // for LRU eviction
}
```
### Caller API
```rust
let mut session = Session::new();
// First render — full execution, caches at materialization points:
let output = session.stream(decoded_source, &config, sidecar, source_hash)?;
// Filter tweak — no source needed, cache hit is automatic:
let output = session.stream(None, &config2, None, source_hash)?;
```
`stream()` takes `Option>` — `None` means "expect a cache hit." Returns an error if the source is needed but not provided.
### Cache point selection
Not every node gets cached. The engine materializes at:
1. **After geometry fusion** — always worth it (decode + resize is the expensive prefix)
2. **Existing materialization barriers** — orient-with-transpose, CropWhitespace, Analyze already materialize; just retain the buffer instead of dropping it
3. **Fan-out points** — TeeSource already materializes here
Rule: if the node already materializes during normal execution, cache the result at zero extra cost. For the geometry case, insert one explicit materialization as the cache point.
### Compile-time integration
During `PipelineGraph::compile()`, which walks backward from Output to Source:
1. Compute subtree hashes (one forward pass over the topological order)
2. At each node, check `session.cache.get(subtree_hash)`
3. On hit: inject `CacheSource` at that node, skip compiling everything upstream
4. On miss: compile normally, materialize at designated cache points, store in cache
### What metadata is cached
Each `CacheEntry` stores everything the suffix pipeline and encoder need:
- **Pixels**: post-geometry, in working colorspace (`Arc>`)
- **Metadata**: `zencodec::Metadata` (ICC, EXIF, XMP, CICP, HDR) — for encoder passthrough
- **Sidecar**: `ProcessedSidecar` (gain map, proportionally resized)
- **Dimensions + format**: post-cache-point width, height, PixelFormat
Since there's no decode on resume, the cache is the sole source of truth for all of these.
### Multi-image support
The content-addressed cache naturally handles multiple images — each has a different source hash, so their subtree hashes diverge at the root. An LRU eviction policy bounded by `memory_budget` keeps memory under control.
### Relationship to existing code
The manual `cache_prefix` / `stream_from_cache` / `SuffixConfig` API from `2b33274` becomes the internal implementation of `Session`'s cache-miss path. It remains public as a power-user escape hatch for callers who want explicit control over splitting and caching.
## Tasks
- [ ] Add subtree hash computation to DAG compilation (forward pass over topological order)
- [ ] Add `Session` type with content-addressed `HashMap`
- [ ] Add `Session::stream()` with automatic cache hit/miss detection
- [ ] Integrate cache lookup into `PipelineGraph::compile()` (inject CacheSource on hit)
- [ ] Retain existing materialization buffers (orient-transpose, fan-out) as cache entries
- [ ] Add LRU eviction bounded by memory budget
- [ ] Tests: DAG diff detection, cache hit/miss, multi-image, memory eviction
- [ ] Document Session API with editor usage example
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading the existing cache_prefix, stream_from_cache, and SuffixConfig implementation, then inspect PipelineGraph::compile and the topological DAG representation. Define the Session cache and subtree-hash flow around those entry points, preserving the existing APIs. Done means cache hits resume without decoding, cache misses populate designated materialization points, eviction respects the memory budget, and the listed DAG, multi-image, and eviction tests pass.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100