Template Class CacheManager¶

Defined in File cache_manager.hpp

Nested Relationships¶

Nested Types¶

Class Documentation¶

template<typename TreeNode, bool force_hash_collisions> class CacheManager¶

This class implements a cache manager useful for the cases when the number of times the cached objects will be accessed is known.

Template Parameters:

TreeNode – The evaluation tree node type used as the cache key.
force_hash_collisions – If true, forces all hash values to 0 (for testing collision safety).

Public Types

using key_type = TreeNode ¶: The node type. Used for everything node-facing: the custom evaluator, the multiroot driver, the persistence predicate, and for_each_key — all of which see plain forest nodes, distinct from the cache-map key (cache_key_type, see below).

using cache_key_type = eval::CachedValue<TreeNode>¶: The cache-map key. CachedValue wraps a node; its identity on the forest-descent path is the node’s canonical hash (hash::value). The batched (table-driven) executor never uses this map for values — it keys by cell id instead. CachedValue is implicitly constructible from a node, so every call site that passes a bare node keeps compiling.

using custom_evaluator_type = std::function<ResultPtr(key_type const&, CacheManager&)>¶

A custom evaluator type. evaluate() consults the cache’s custom evaluator (if set) before applying its standard recursive scheme to each non-leaf node, invoking it as custom_evaluator(node, cache):

a non-null ResultPtr means “I evaluated this subtree myself” (e.g. blocked over a contracted index to bound peak memory) and is used (and cached) as-is;
a null result means “decline”, and the standard scheme evaluates the node (its children are in turn consulted via the threaded cache). The leaf evaluator is captured by the callable. A custom evaluator that (re)evaluates the subtree by the standard scheme on a transformed operand set should do so on a scratch cache (e.g. CacheManager::empty()) to avoid both re-interception and polluting this cache with partial results.

using shaped_product_hook_type = std::function<ResultPtr(std::any const &node, Result const &left, Result const &right, std::array<std::any, 3> const &annot)>¶

A shaped-product hook type. evaluate() consults the cache’s shaped- product hook (if set) at each binary-Product node before the product is computed. It receives the node (wrapped in a std::any as a std::reference_wrapper<key_type const>) plus the already-evaluated left/right operands and the [left, right, result] annotations. It returns a non-null ResultPtr to replace the normal product (e.g. a shape- constrained emission of it), or a null ResultPtr to decline (the standard prod() then runs). Empty (default) => never consulted, and every product takes the standard path.

All backend-specific types (TA shapes, tranges, set_shape) stay inside the hook’s closure (built by the backend, e.g. TAEvalContext::make_hook()); the generic CacheManager and eval see only Result/ResultPtr/std::any.

using multiroot_driver_type = std::function<container::svector<ResultPtr>(container::svector<key_type> const &roots, container::svector<std::string> const &layouts, CacheManager&)>¶: A multi-root driver type. When set, the free function evaluate_multiroot(roots, layouts, leaf, cache) (eval.hpp) routes the whole set of independent roots through this driver instead of evaluating each root as its own separate forest. This driver returns a map: one result per root, in input order, with no cross-root summation — the roots need not even be commensurate in shape (e.g. independent CC residual equations). layouts holds one layout string per root, in the same order as roots, so heterogeneous roots (e.g. distinct CC residual annotations like R1 {a;i} vs R2 {ab;ij}) can each be permuted to their own result layout. The intended installer (ordered_executor.hpp) concatenates roots into one schedule so a subexpression shared across roots is built once (the same CSE compute_dag_boulevard already gives a concatenated node list), then returns each root’s own (unsummed) value_result. The captured leaf evaluator and any batching policy live inside the closure, which is built at the call site that owns those concrete types (e.g. MPQC’s batched CSV-CCk residual install). Empty (default) => evaluate_multiroot throws: there is no per-root fallback, so a multi-root caller must explicitly wire a driver that understands the cross-root CSE contract.

using BatchContext = container::svector<BatchContextEntry>¶: The batch context: an ordered stack (outermost-first) of the enclosing realized batch loops, one entry per loop (see BatchContextEntry: axis K, its DAG-scope level, and the current {block_lo, block_hi} element range). Set on the per-block scratch by the batched evaluator before it re-enters evaluate(); read by the Enter-stage slice-on-use so a cached intermediate fetched from an ancestor scope is sliced to the modes of the loops the fetch crossed (see eval.hpp). Empty (default) => no enclosing batch loop, so slice-on-use is inert and a fetched value is served whole.

Public Functions

inline void set_strict_fill_once(bool strict) noexcept¶: Sets the cache-fill-once strictness (see strict_fill_once_).

inline bool strict_fill_once() const noexcept¶

Returns:: the cache-fill-once strictness (see strict_fill_once_).

inline void set_custom_evaluator(custom_evaluator_type fn) noexcept¶: Sets the custom evaluator (see custom_evaluator_type). Pass an empty std::function to clear it.

inline custom_evaluator_type const &custom_evaluator() const noexcept¶

Returns:: the custom evaluator (empty if none is set).

inline void set_shaped_product_hook(shaped_product_hook_type fn) noexcept¶: Sets the shaped-product hook (see shaped_product_hook_). Pass an empty std::function to clear it.

inline shaped_product_hook_type const &shaped_product_hook() const noexcept¶

Returns:: the shaped-product hook: this cache’s own, or, when none is set here, the nearest ancestor’s (a batch-scope cache is created empty under its parent, and the products evaluated inside a batch block must see the same hook as those evaluated at root); empty if no cache on the chain has one.

inline void set_multiroot_driver(multiroot_driver_type fn) noexcept¶: Sets the multi-root driver (see multiroot_driver_type). Pass an empty std::function to clear it.

inline multiroot_driver_type const &multiroot_driver() const noexcept¶

Returns:: the multi-root driver (empty if none is set).

inline void set_batch_context(BatchContext c) noexcept¶: Sets the batch context (see batch_context_). Pass an empty context to clear it.

inline BatchContext const &batch_context() const noexcept¶

Returns:: the batch context (empty if none is set).

inline void set_parent(CacheManager *p) noexcept¶: Sets the scope-chain parent (see parent_). Pass nullptr to detach.

inline CacheManager *parent() const noexcept¶

Returns:: the scope-chain parent (see parent_), or nullptr if this is a standalone / chain-root cache. Used by the batched evaluator to walk up to a target ancestor level when hoisting an invariant.

inline void set_peak_monitor(eval::PeakMonitor *m) noexcept¶: Sets the local peak monitor (see peak_monitor_). Pass nullptr to detach. Non-owning; the pointee must outlive this cache.

inline eval::PeakMonitor *peak_monitor() const noexcept¶

Returns:: the local peak monitor if set, else the one inherited from parent_ (only the root cache is wired in practice); nullptr if none is wired anywhere along the chain. Non-owning.

inline void set_schedule_sink(eval::ScheduleSink *s) noexcept¶: Sets the schedule-dump sink (see schedule_sink_). Pass nullptr to detach. Non-owning; the pointee (and its os) must outlive this cache.

inline eval::ScheduleSink *schedule_sink() const noexcept¶

Returns:: the local schedule sink if set, else the one inherited from parent_ (only the root cache is wired in practice); nullptr if none is wired anywhere along the chain. Non-owning.

inline void set_array_ops(BackendArrayOps const *a) noexcept¶: Sets the backend array-ops (see BackendArrayOps). Non-owning; the pointee must outlive this cache. Absent (nullptr) anywhere along the chain means a batched external-axis scatter has no way to build its destination.

inline BackendArrayOps const *array_ops() const noexcept¶

Returns:: the local array-ops if set, else the one inherited from parent_ (only the root cache is wired in practice); nullptr if none is wired anywhere along the chain. Non-owning.

inline eval::PersistentValueStore &persistent_values() noexcept¶

Returns:: the persistent value store local to this handle (see persistent_values_). Not inherited from parent_ — each handle’s store is its own.

inline eval::PersistentValueStore const &persistent_values() const noexcept¶

inline void clear_persistent_values() noexcept¶: Explicitly drop every value in the persistent store (see persistent_values_). reset() does not do this by design: the persistent store outlives repeated evaluations of this handle.

inline void set_cell_read_resolver(eval::CellReadResolver *r) noexcept¶: Publishes the ordered run’s cell-read resolver (see cell_read_resolver_ — a test-only observation seam with no production reader, not a read path of this cache). Pass nullptr to detach. Non-owning; the pointee must outlive this cache.

inline eval::CellReadResolver *cell_read_resolver() const noexcept¶

Returns:: the local cell-read resolver if set, else the one inherited from parent_ (only the top-level cache of a table-driven run is wired); nullptr if none is wired anywhere along the chain — i.e. no ordered run is in flight. Non-owning.

inline void set_external_residency(std::function<std::size_t()> f) noexcept¶

Sets the external residency source (see external_residency_). Pass an empty std::function to detach.

Installed on the chain-root handle only, and asserted so: chain_residency() folds the hook in exactly where its parent walk bottoms out (parent_ == nullptr), and the lookup that finds it walks upward, so a hook installed on a child would never be folded in at all — its bytes would silently vanish from every residency and peak figure.

inline std::function<std::size_t()> const &external_residency_hook() const noexcept¶

Returns:: the raw external-residency hook visible from this cache (local if set, else parent_'s, like array_ops() / cell_read_resolver()) — an empty std::function if none is wired anywhere along the chain. chain_residency() invokes this only where its own recursion bottoms out (parent_ == nullptr), so whichever single frame the hook resolves to is folded in exactly once per chain_residency() call regardless of which scope in the chain that call started from. Also lets a caller (e.g. an RAII install guard) save the hook currently in effect before overriding it locally and restore exactly that afterward, the same way CellReadResolverGuard saves/restores cell_read_resolver().

inline void set_external_liveset(std::function<void(std::function<void(std::size_t hash, std::size_t bytes)>)> f) noexcept¶: Sets the external liveset source (see external_liveset_). Pass an empty std::function to detach. Installed on the chain-root handle only, and asserted so, for the same reason set_external_residency is.

inline std::function<void(std::function<void(std::size_t hash, std::size_t bytes)>)> const &external_liveset() const noexcept¶

Returns:: the local external-liveset source if set, else the one inherited from parent_; an empty std::function if none is wired anywhere along the chain. Looked up like external_residency() / array_ops().

inline void ensure_hoist_slot(key_type const &key)¶: Ensure a scope-hoist slot exists for key so a loop-invariant intermediate can be stored here (store_and_access() is a no-op for an unregistered key). The slot is non-persistent with an effectively unbounded life, so it is never drained by access() and lives until the next reset() — per-batch for a batch scratch (rebuilt for the next batch of the loop it is scoped to), per-term for the real cache (rebuilt for the next term). Idempotent: an existing entry (with any stored data) is left untouched. The unbounded life — rather than the emitted effective_count — is deliberate: a whole-nest invariant’s escaped-outer set is empty, so its emitted effective_count is 1, which as a life would drain the entry on first use; reset() is the correct lifetime boundary for a hoisted invariant.

template<typename Iterable, typename PersistencePred = all_non_persistent> inline explicit CacheManager(Iterable &&decaying, PersistencePred is_persistent = {}) noexcept¶

Note

P nodes should be registered with whatever use-count is convenient (it is not consulted for P entries) and may have a count of 1 even though NP caching only registers nodes repeated min_repeats times.

Parameters:

decaying – iterable of (node, use-count) pairs to register for caching.
is_persistent – predicate classifying each node as persistent (P, never released on access, survives reset()) or non-persistent (NP, released after its last use and by reset()). Defaults to all-NP.

inline void reset() noexcept¶

Resets all cached data.

Does not touch persistent_values_ (see persistent_values()): that store is a separate, explicitly-managed handle-local cache meant to survive repeated evaluations; use clear_persistent_values() to drop it deliberately.

inline size_t note_working_set(size_t current_bytes, size_t op_hash = 0) noexcept¶: Fold the per-op live working set current_bytes into the running high-water mark and return the updated mark. Reported as hw= in the per-op eval trace; monotonically non-decreasing until reset(). op_hash (default 0) identifies the op node being evaluated at the call site (0 when no node is in scope there); forwarded to peak_monitor()'s observe() so a wired PeakMonitor can report where its hierarchy- wide high-water was observed.

inline size_t working_set_hwmark() const noexcept¶: Current running high-water mark (bytes) of the live working set.

inline void tally_build(key_type const &key, std::string const &slice_sig, double flops, double exec) noexcept¶

Diagnostic: record one product build of key at slice slice_sig costing flops (this build’s actual, realized-extent cost). slice_sig is the enclosing batch context projected onto the modes key carries (empty when the value is invariant to every live loop), so repeats of one slice fold (recompute) while distinct slices stay separate (tiling). Routes to the scope-chain root so every build — from any per-batch scratch — accumulates in one map keyed by node identity (see recompute_tally_). Called only in the dry-run costing replay.

Parameters:: key – the node whose build is tallied. A node (not a cache_key_type): converting at the call boundary would copy the node — deep-copying its whole subtree — on every build, including on the wet path where the tally is disabled.

inline void set_recompute_tally_enabled(bool on) noexcept¶: Enable/disable the per-node recompute tally (see recompute_tally_enabled_). Set on the root cache by the dry-run costing replay; left false everywhere else so tally_build() is a no-op on the wet eval path.

inline std::unordered_map<TreeNode, BuildTally, TreeNodeHasher<TreeNode, force_hash_collisions>, TreeNodeEqualityComparator<TreeNode>> const &recompute_tally() const noexcept¶

Returns:: the per-distinct-value build tally accumulated by tally_build() on this (root) cache (see recompute_tally_). Read after the replay to roll up avoidable recompute per node identity.

inline size_t current_residency() const noexcept¶: Sum over alive entries of this cache’s own residency (bytes). Unlike working_set_hwmark() (a high-water max over time), this is the current live residency at the instant of the call.

inline size_t chain_residency() const noexcept¶: current_residency() of this cache plus every ancestor along the scope chain (parent_), plus — exactly where the chain walk bottoms out (parent_ == nullptr) — the external residency hook’s bytes: the total live residency visible at this scope at one instant, table-owned storage (the CellRegistry, once wired via set_external_residency) included. Adding it only at the walk’s base, rather than at every recursive level, is what keeps a single external total from being folded in once per scope on the chain — see external_residency_hook()'s own doc comment.

inline bool chain_holds(ResultPtr const &value) const noexcept¶

Returns:: true iff some alive entry on this cache or any ancestor along the scope chain physically holds value (pointer identity). Read-only: unlike access_at() it decays no lifetime. The peak trace uses it to skip an operand whose bytes are already counted — locally in bytes(cache,...) or up-chain in chain_residency() — because the operand aliases that resident buffer. A sliced (or permuted, or phase-shifted) read of a resident value is a distinct buffer with a different pointer, so it is correctly not skipped.

inline bool chain_holds_shared(ResultPtr const &value) const noexcept¶

This is the runtime safety gate the in-place Sum accumulation (eval.hpp) needs, and is strictly the “the accumulator is shared” test: a private single-use buffer is not reported here, so in-place still fires for it. Two cases yield a private (unshared) accumulator, both correctly returning false:

a transient running total (freshly allocated by a prior sum() / prod(), never store'd) is held by no entry at all; and
a single-use CSE entry (max_life == 1) moves its buffer out on its sole entry::access() (decay() reaches 0 -> std::move(data_p)), so once it has been read as an operand it no longer holds() it — and even were it somehow still alive, max_life > 1 excludes it. A value with a genuine multi-use count (max_life > 1, e.g. a subexpression shared across two roots) is never drained by a single read, so it stays held and is reported here — the case the elided SEQUANT_ASSERT could not catch at runtime. A persistent entry (registered via the CacheManager(Iterable&&, PersistencePred) ctor, e.g. the make_batched_scratch path) is also reported even when its max_life == 1: entry::access() never drains a persistent entry, so it stays resident-forever and is shared across the batched replays — mutating it in place would corrupt every later read. Hence the guard is persistent() or max_life > 1, not max_life alone. A held non-persistent single-use entry (max_life == 1) is not reported (it drained its buffer out on its sole read, so it no longer holds it), keeping in-place enabled for the private common case.

Returns:: true iff some alive entry on this cache or any ancestor along the scope chain physically holds value (pointer identity) and that entry is either persistent (persistent(), never drained — survives across evaluations) or has more than one consumer (max_life_count() > 1) — i.e. value is a shared buffer with at least one read still pending (or a resident/persistent home read by every consumer), so mutating it in place would corrupt those other reads.

inline AccessResult access_at(key_type const &key) noexcept¶

Access cached data.

A local entry only “hits” if it is currently holding data; a key registered locally but never (yet) stored here — e.g. a hoisted loop-invariant node whose value lives only at an ancestor level — is a local miss just like an unregistered key, and must fall through the same way. Standalone (parent_ == nullptr) behavior is unchanged: a total miss returns {nullptr, 0}. The hop distance surfaces the value’s lifetime scope so the caller (Enter-stage slice-on-use) can slice it to exactly the batch loops the fetch crossed.

Parameters:

key – The key that identifies the cached data.
key – the node to look up. Taken as a node (not a cache_key_type) on purpose: the map is probed heterogeneously, so a lookup never materializes a CachedValue — which would copy the node, i.e. deep-copy its whole subtree (see CachedValueHasher).

Returns:

the fetched pointer plus the hop distance (number of parent links crossed) to the scope that held it; {nullptr, 0} on a total miss.

inline ResultPtr access(key_type const &key) noexcept¶

Parameters:: key – The key that identifies the cached data.
Returns:: ResultPtr to Result. Thin forwarder to access_at() that drops the hop distance, for the non-batched callers that do not slice.

inline ResultPtr store_and_access(key_type const &key, ResultPtr data)¶

Parameters:

key – The key to identify the cached data.
data – The data to be cached.

Returns:

Pointer to the stored data. Implictly accesses the stored data, hence, decays the lifetime if the key accesses a decaying cache entry. Passing key that was not present during construction of this CacheManager object, stores nothing, but still returns a valid pointer to data.

inline bool exists(key_type const &key) const noexcept¶: Check if the key exists in the database: does not check if cache exists.

template<typename F> inline void for_each_key(F &&fn) const¶

Invokes fn with a const reference to every registered key.

Keys are the canonical evaluation-tree nodes registered at construction; iteration order is unspecified. Use together with persistent()/alive() to enumerate, e.g., persistent entries that have not been populated yet.

inline int life(key_type const &key) const noexcept¶: if the key exists in the database, return the current lifetime count of the cached data otherwise return -1

inline int max_life(key_type const &key) const noexcept¶: if the key exists in the database, return the maximum lifetime count of the cached data that implies the maximum number of accesses allowed for this key before the cache is released. This value was set by the c’tor.

inline bool alive(key_type const &key) const noexcept¶

Returns:: true iff the key is registered for caching and currently holds stored data (i.e. has been stored and not yet drained by its final access).

inline bool resident_in_chain(key_type const &key) const noexcept¶

Returns:: true iff key is alive (holding data) at this cache or any ancestor scope up the parent chain. Non-decrementing (unlike access_at): a pure residency probe. Used by make_batched_scratch to decide that a batch-invariant value already resident at its home is read from there each batch (the parent-chain fall-through), so it is neither registered nor rebuilt in the per-batch scratch.

inline bool persistent(key_type const &key) const noexcept¶

Returns:: true iff the key is registered for caching and classified persistent (P: never released on access, survives reset()).

inline size_t entry_size_in_bytes(key_type const &key) const noexcept¶

Returns:: size in bytes of the data currently held for key, or 0 if the key is not registered or no data is currently stored.

inline size_t alive_count() const noexcept¶

Returns:: The number of entries with life_count greater than zero.

inline size_t size_in_bytes() const noexcept¶

Returns:: Returns the sum of Result::size_in_bytes of alive entries.

Public Static Functions

static inline CacheManager empty() noexcept¶: Get an empty cache manager.

Friends

friend struct access_by

template<typename T> struct access_by¶

struct AccessResult¶

Result of access_at(): the fetched pointer plus the hop distance (number of parent links crossed) to the scope that held it. hops == 0 means a local hit; a null ptr carries hops == 0.

Public Members

ResultPtr ptr¶

std::size_t hops¶

struct all_non_persistent¶

Default persistence classifier: every entry is non-persistent (NP).

Public Functions

inline bool operator()(key_type const&) const noexcept¶

struct BuildRecord¶

Diagnostic (dry-run costing): per-distinct-value build tally for the avoidable-recompute rollup, keyed by the same node identity the cache dedups on (TreeNodeHasher + TreeNodeEqualityComparator = topological hash bin + Bliss connectivity 3-way cmp + recursive child compare), so two topologically-distinct nodes sharing a 64-bit hash are not folded and per-block / alpha-renamed builds of one value are folded.

Recompute is measured with actual replay FLOPs, deduped at the (value, slice) granularity — not against a build-once “full extent” denominator, which is ill-defined when slicing is non-uniform. slices maps a slice signature — the enclosing batch context projected onto the modes this value actually carries (empty for a value invariant to every live loop) — to that slice’s {build count, one build’s actual cost}. Then: total = sum over slices of builds*cost (== the replay’s dryrun sum) build-once = sum over slices of cost (each distinct slice once) avoidable = sum over slices of (builds-1)*cost. A value tiled over distinct slices (different blocks) has builds==1 per slice -> 0 avoidable (tiling is not recompute, even if the blocks are unequal). A value rebuilt at the same slice — e.g. a node invariant to an enclosing loop, whose projected signature is identical every block — has builds>1 at one slice -> (builds-1)*cost avoidable. Costs need not be uniform across slices; each slice carries its own realized cost.

Public Members

std::size_t count = 0¶

double flops = 0¶

double exec = 0¶

struct BuildTally¶

Public Members

std::unordered_map<std::string, BuildRecord> slices¶