🔢 Perf: O(1) memoization keys for containers via generation counters

[timfennis]

Background

pure fn memoization currently hashes all arguments to build the cache key. For container types (Map, List, Deque, etc.) this is O(n) in the number of elements — proportional to the container's size.

This was identified as a significant performance issue when profiling AoC 2025 day 11 part 2: passing a 615-entry Map as an argument to a memoized recursive function added ~115ms of pure hashing overhead across 1283 calls, with zero cache hits (all states were unique).

Proposed fix: generation counters

Attach a generation: u64 field to each heap-allocated container. Increment it on every mutation (insert, push, remove, etc.). The memoization cache key for a container argument becomes (ptr, generation) — two words, O(1) to compute, and correct even across mutations.

cache key: (Rc::as_ptr(rc), container.generation)

• Same pointer + same generation → same logical value → cache hit is valid
• Same pointer + different generation → container was mutated → cache miss (recompute)
• Different pointer → always a cache miss (conservative, correct)

Why not pointer identity alone?

Pointer identity (Rc::as_ptr) was tested and rejected: since containers are mutable, a mutated container would produce a spurious cache hit with a stale result. Generation counters fix this.

Trade-offs

• Cost per container: one u64 field added to Object::Map, Object::List, Object::Deque, Object::MinHeap, Object::MaxHeap
• Cost per mutation: one u64 increment
• Cost per memo lookup: reading two words instead of hashing n elements
• Cache misses: slightly more conservative than deep equality (two equal containers at different addresses won't hit), but this is the same behaviour as today

Related

• Salsa (rust-analyzer's query engine) uses a similar revision counter approach
• Koka/Lean 4 use uniqueness types to achieve the same guarantee at the type level