oxilean_kernel/whnf_memo/
types.rs

1//! Types for the memoized WHNF reduction layer.
2//!
3//! Provides cache key/entry/configuration/statistics types for the WHNF memo
4//! table.  Cache correctness is guaranteed by including the current environment
5//! version in every key: when the environment grows (a new declaration is
6//! added), `invalidate_all` bumps `env_version`, rendering all prior entries
7//! stale without requiring an explicit scan.
8
9use std::collections::HashMap;
10
11// ---------------------------------------------------------------------------
12// WhnfKey
13// ---------------------------------------------------------------------------
14
15/// Cache key for a single WHNF reduction result.
16///
17/// Including `env_version` ensures that cached reductions are invalidated
18/// automatically when the environment changes: a key computed under version `v`
19/// will never match an entry stored under version `v'` where `v' != v`.
20#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
21pub struct WhnfKey {
22    /// FNV-1a hash of the expression bytes to be reduced.
23    pub expr_hash: u64,
24    /// Monotonically increasing environment version at query time.
25    pub env_version: u32,
26}
27
28// ---------------------------------------------------------------------------
29// WhnfEntry
30// ---------------------------------------------------------------------------
31
32/// A single cached WHNF reduction result.
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub struct WhnfEntry {
35    /// FNV-1a hash of the WHNF-reduced result expression.
36    pub result_hash: u64,
37    /// Number of reduction steps performed to reach WHNF (used for eviction
38    /// decisions: entries that required few steps are cheap to recompute).
39    pub reduction_steps: u32,
40    /// Number of times this entry has been returned from the cache.
41    pub access_count: u32,
42}
43
44// ---------------------------------------------------------------------------
45// MemoConfig
46// ---------------------------------------------------------------------------
47
48/// Configuration parameters for a [`WhnfMemo`] instance.
49#[derive(Clone, Debug)]
50pub struct MemoConfig {
51    /// Maximum number of entries in the cache before eviction is triggered.
52    pub max_entries: usize,
53    /// Minimum number of reduction steps required before a result is cached.
54    ///
55    /// Results achieved in fewer steps are cheap to recompute and not worth
56    /// the memory overhead.
57    pub min_steps_to_cache: u32,
58    /// Fraction of `max_entries` used as the access-count threshold during
59    /// cold eviction.  Entries whose `access_count` is below
60    /// `floor(max_entries * eviction_threshold)` are considered cold and may
61    /// be removed.
62    pub eviction_threshold: f64,
63}
64
65impl Default for MemoConfig {
66    fn default() -> Self {
67        MemoConfig {
68            max_entries: 4096,
69            min_steps_to_cache: 2,
70            eviction_threshold: 0.1,
71        }
72    }
73}
74
75// ---------------------------------------------------------------------------
76// WhnfMemo
77// ---------------------------------------------------------------------------
78
79/// Memoization table for WHNF reduction results.
80///
81/// # Correctness
82///
83/// Every lookup and insertion is tied to `env_version`.  Calling
84/// `invalidate_all` bumps the version and clears all entries, guaranteeing
85/// that stale results (computed against an older environment) are never
86/// returned.
87///
88/// # Eviction
89///
90/// When the table reaches `config.max_entries`, `evict_cold` is called
91/// automatically during `insert`.  Cold entries — those whose `access_count`
92/// falls below a threshold derived from `config.eviction_threshold` — are
93/// removed.  If no cold entries exist the oldest-inserted entry is dropped.
94pub struct WhnfMemo {
95    /// Cached entries, keyed by (expression hash, env version).
96    pub(crate) entries: HashMap<WhnfKey, WhnfEntry>,
97    /// Total number of successful cache lookups.
98    pub hits: u64,
99    /// Total number of cache misses.
100    pub misses: u64,
101    /// Total number of entries removed by eviction.
102    pub evictions: u64,
103    /// Current environment version.
104    pub env_version: u32,
105    /// Configuration controlling capacity, caching threshold, and eviction.
106    pub(crate) config: MemoConfig,
107    /// Monotonically increasing insertion counter (used to implement FIFO
108    /// fallback eviction when no cold entries are found).
109    pub(crate) insert_order: Vec<WhnfKey>,
110}
111
112// ---------------------------------------------------------------------------
113// MemoStats
114// ---------------------------------------------------------------------------
115
116/// A snapshot of [`WhnfMemo`] performance statistics.
117#[derive(Clone, Debug)]
118pub struct MemoStats {
119    /// Total cache hits.
120    pub hits: u64,
121    /// Total cache misses.
122    pub misses: u64,
123    /// Total evictions.
124    pub evictions: u64,
125    /// Hit rate in [0.0, 1.0].
126    pub hit_rate: f64,
127    /// Current number of cached entries.
128    pub size: usize,
129    /// Current environment version.
130    pub env_version: u32,
131}
132
133impl std::fmt::Display for MemoStats {
134    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
135        write!(
136            f,
137            "MemoStats {{ hits: {}, misses: {}, evictions: {}, hit_rate: {:.2}%, size: {}, env_version: {} }}",
138            self.hits,
139            self.misses,
140            self.evictions,
141            self.hit_rate * 100.0,
142            self.size,
143            self.env_version
144        )
145    }
146}
oxilean_kernel/whnf_memo/types.rs

oxilean_kernel/whnf_memo/
types.rs
