Problem
The pure fn memoization cache in ndc_vm uses HashMap<u64, Value> — it hashes the arguments to a u64 and uses that directly as the map key. Two different argument sets that hash to the same u64 will silently return each other's cached values.
This was a deliberate tradeoff for performance (avoiding storing full argument vectors), but the collision probability grows with cache size and could produce incorrect results in real programs.
Possible mitigations
- Store full args: Use
HashMap<Vec<Value>, Value> — correct but allocates per call
- Double hashing: Use two independent hashers and a
(u64, u64) key — dramatically reduces collision probability without storing args
- Bounded cache + collision counter: Keep the
u64 key but track collisions and evict on suspicion
- Hybrid: Store args only when the cache exceeds a size threshold
Related
Relates to #112
Location
ndc_vm/src/vm.rs — dispatch_call method, and ndc_vm/src/value/function.rs — Function::Memoized variant.
Problem
The
pure fnmemoization cache inndc_vmusesHashMap<u64, Value>— it hashes the arguments to au64and uses that directly as the map key. Two different argument sets that hash to the sameu64will silently return each other's cached values.This was a deliberate tradeoff for performance (avoiding storing full argument vectors), but the collision probability grows with cache size and could produce incorrect results in real programs.
Possible mitigations
HashMap<Vec<Value>, Value>— correct but allocates per call(u64, u64)key — dramatically reduces collision probability without storing argsu64key but track collisions and evict on suspicionRelated
Relates to #112
Location
ndc_vm/src/vm.rs—dispatch_callmethod, andndc_vm/src/value/function.rs—Function::Memoizedvariant.