imazen / imazen/zenpipe

DAG-level incremental caching via Merkle subtree hashing

Open
#3 1 comment 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.