Skip to main content

tensor4all_core/cached_function/
mod.rs

1//! Cached function wrapper for expensive function evaluations.
2//!
3//! [`CachedFunction`] wraps a user-supplied function `Fn(&[I]) -> V` with
4//! thread-safe memoization. On first call for a given multi-index, the
5//! function is evaluated and the result is cached; subsequent calls return
6//! the cached value.
7//!
8//! The internal cache key type is automatically selected based on the total
9//! index space size (up to 1024 bits by default). For larger index spaces,
10//! use [`CachedFunction::with_key_type`] with a custom [`CacheKey`]
11//! implementation.
12//!
13//! # Examples
14//!
15//! ```
16//! use tensor4all_core::CachedFunction;
17//!
18//! let cf = CachedFunction::new(
19//!     |idx: &[usize]| idx[0] + idx[1],
20//!     &[3, 4],
21//! ).unwrap();
22//!
23//! assert_eq!(cf.eval(&[1, 2]).unwrap(), 3);
24//! assert_eq!(cf.num_evals(), 1);
25//! assert_eq!(cf.eval(&[1, 2]).unwrap(), 3);
26//! assert_eq!(cf.num_cache_hits(), 1);
27//! ```
28
29pub mod cache_key;
30pub mod error;
31pub mod index_int;
32mod memo_table;
33pub mod multi_index_cache;
34
35use memo_table::MemoTable;
36use rustc_hash::FxHashMap;
37use std::sync::atomic::{AtomicUsize, Ordering};
38use std::sync::{RwLock, RwLockReadGuard, RwLockWriteGuard};
39
40use bnum::types::{U1024, U256, U512};
41
42use cache_key::CacheKey;
43use index_int::IndexInt;
44use multi_index_cache::SideKeyValues;
45
46/// Compute total bits needed to represent the index space.
47pub(crate) fn total_bits(local_dims: &[usize]) -> u32 {
48    local_dims
49        .iter()
50        .map(|&d| {
51            if d <= 1 {
52                0
53            } else {
54                ((d - 1) as u64).ilog2() + 1
55            }
56        })
57        .sum()
58}
59
60/// Compute mixed-radix coefficients for flat index computation.
61///
62/// Returns `Err(CacheKeyError::Overflow)` if the index space overflows key type `K`.
63pub(crate) fn compute_coeffs<K: CacheKey>(
64    local_dims: &[usize],
65) -> Result<Vec<K>, error::CacheKeyError> {
66    let bits = total_bits(local_dims);
67    if bits > K::BITS_COUNT {
68        return Err(error::CacheKeyError::Overflow {
69            total_bits: bits,
70            max_bits: K::BITS_COUNT,
71            key_type: std::any::type_name::<K>(),
72        });
73    }
74
75    // INVARIANT: for an index space with cardinality greater than one, each
76    // coefficient consumed by a valid multi-index is at most `cardinality / 2`
77    // and the trailing coordinates only ever contribute zero; the `bits` guard
78    // above caps the cardinality at `2^K`.
79    let last_bond = local_dims.iter().rposition(|&d| d > 1);
80    let mut coeffs = Vec::with_capacity(local_dims.len());
81    let mut prod = K::ONE;
82    for (i, &d) in local_dims.iter().enumerate() {
83        coeffs.push(prod.clone());
84        if Some(i) < last_bond {
85            // Detects coefficient overflow if `total_bits` ever stops bounding
86            // the coefficients this loop produces.
87            let dim = K::from_usize(d);
88            prod = prod
89                .checked_mul(dim)
90                .ok_or_else(|| error::CacheKeyError::Overflow {
91                    total_bits: bits,
92                    max_bits: K::BITS_COUNT,
93                    key_type: std::any::type_name::<K>(),
94                })?;
95        }
96    }
97
98    Ok(coeffs)
99}
100
101fn read_lock<T>(lock: &RwLock<T>) -> RwLockReadGuard<'_, T> {
102    lock.read().unwrap_or_else(|poisoned| poisoned.into_inner())
103}
104
105fn write_lock<T>(lock: &RwLock<T>) -> RwLockWriteGuard<'_, T> {
106    lock.write()
107        .unwrap_or_else(|poisoned| poisoned.into_inner())
108}
109
110/// Compute flat index from multi-index and coefficients.
111fn flat_index<K: CacheKey, I: IndexInt>(idx: &[I], coeffs: &[K]) -> K {
112    idx.iter().zip(coeffs).fold(K::ZERO, |acc, (&i, c)| {
113        acc.wrapping_add(
114            c.clone()
115                .checked_mul(K::from_usize(i.to_usize()))
116                .unwrap_or(K::ZERO),
117        )
118    })
119}
120
121/// Internal cache with automatically selected key type.
122enum InnerCache<V> {
123    U64 {
124        cache: RwLock<MemoTable<u64, V>>,
125        coeffs: Vec<u64>,
126    },
127    U128 {
128        cache: RwLock<MemoTable<u128, V>>,
129        coeffs: Vec<u128>,
130    },
131    U256 {
132        cache: RwLock<MemoTable<U256, V>>,
133        coeffs: Vec<U256>,
134    },
135    U512 {
136        cache: RwLock<MemoTable<U512, V>>,
137        coeffs: Vec<U512>,
138    },
139    U1024 {
140        cache: RwLock<MemoTable<U1024, V>>,
141        coeffs: Vec<U1024>,
142    },
143}
144
145impl<V: Clone + Send + Sync> InnerCache<V> {
146    /// Create a new cache, automatically selecting the key type.
147    fn new(local_dims: &[usize]) -> Result<Self, error::CacheKeyError> {
148        let bits = total_bits(local_dims);
149        if bits <= 64 {
150            Ok(Self::U64 {
151                cache: RwLock::new(MemoTable::default()),
152                coeffs: compute_coeffs::<u64>(local_dims)?,
153            })
154        } else if bits <= 128 {
155            Ok(Self::U128 {
156                cache: RwLock::new(MemoTable::default()),
157                coeffs: compute_coeffs::<u128>(local_dims)?,
158            })
159        } else if bits <= 256 {
160            Ok(Self::U256 {
161                cache: RwLock::new(MemoTable::default()),
162                coeffs: compute_coeffs::<U256>(local_dims)?,
163            })
164        } else if bits <= 512 {
165            Ok(Self::U512 {
166                cache: RwLock::new(MemoTable::default()),
167                coeffs: compute_coeffs::<U512>(local_dims)?,
168            })
169        } else if bits <= 1024 {
170            Ok(Self::U1024 {
171                cache: RwLock::new(MemoTable::default()),
172                coeffs: compute_coeffs::<U1024>(local_dims)?,
173            })
174        } else {
175            Err(error::CacheKeyError::Overflow {
176                total_bits: bits,
177                max_bits: 1024,
178                key_type: "auto",
179            })
180        }
181    }
182
183    fn get<I: IndexInt>(&self, idx: &[I]) -> Option<V> {
184        match self {
185            Self::U64 { cache, coeffs } => read_lock(cache).get(&flat_index(idx, coeffs)).cloned(),
186            Self::U128 { cache, coeffs } => read_lock(cache).get(&flat_index(idx, coeffs)).cloned(),
187            Self::U256 { cache, coeffs } => read_lock(cache).get(&flat_index(idx, coeffs)).cloned(),
188            Self::U512 { cache, coeffs } => read_lock(cache).get(&flat_index(idx, coeffs)).cloned(),
189            Self::U1024 { cache, coeffs } => {
190                read_lock(cache).get(&flat_index(idx, coeffs)).cloned()
191            }
192        }
193    }
194
195    fn insert<I: IndexInt>(&self, idx: &[I], value: V) {
196        match self {
197            Self::U64 { cache, coeffs } => {
198                write_lock(cache).insert(flat_index(idx, coeffs), value, usize::MAX);
199            }
200            Self::U128 { cache, coeffs } => {
201                write_lock(cache).insert(flat_index(idx, coeffs), value, usize::MAX);
202            }
203            Self::U256 { cache, coeffs } => {
204                write_lock(cache).insert(flat_index(idx, coeffs), value, usize::MAX);
205            }
206            Self::U512 { cache, coeffs } => {
207                write_lock(cache).insert(flat_index(idx, coeffs), value, usize::MAX);
208            }
209            Self::U1024 { cache, coeffs } => {
210                write_lock(cache).insert(flat_index(idx, coeffs), value, usize::MAX);
211            }
212        }
213    }
214
215    /// Insert within `limit` bytes of table (see [`MemoTable::insert`]).
216    fn insert_bounded<I: IndexInt>(
217        &self,
218        idx: &[I],
219        value: V,
220        limit: usize,
221    ) -> memo_table::Inserted {
222        match self {
223            Self::U64 { cache, coeffs } => {
224                write_lock(cache).insert(flat_index(idx, coeffs), value, limit)
225            }
226            Self::U128 { cache, coeffs } => {
227                write_lock(cache).insert(flat_index(idx, coeffs), value, limit)
228            }
229            Self::U256 { cache, coeffs } => {
230                write_lock(cache).insert(flat_index(idx, coeffs), value, limit)
231            }
232            Self::U512 { cache, coeffs } => {
233                write_lock(cache).insert(flat_index(idx, coeffs), value, limit)
234            }
235            Self::U1024 { cache, coeffs } => {
236                write_lock(cache).insert(flat_index(idx, coeffs), value, limit)
237            }
238        }
239    }
240
241    /// Bytes of the tables (see [`MemoTable::bytes`]).
242    fn bytes(&self) -> usize {
243        match self {
244            Self::U64 { cache, .. } => read_lock(cache).bytes(),
245            Self::U128 { cache, .. } => read_lock(cache).bytes(),
246            Self::U256 { cache, .. } => read_lock(cache).bytes(),
247            Self::U512 { cache, .. } => read_lock(cache).bytes(),
248            Self::U1024 { cache, .. } => read_lock(cache).bytes(),
249        }
250    }
251
252    fn contains<I: IndexInt>(&self, idx: &[I]) -> bool {
253        match self {
254            Self::U64 { cache, coeffs } => read_lock(cache).contains_key(&flat_index(idx, coeffs)),
255            Self::U128 { cache, coeffs } => read_lock(cache).contains_key(&flat_index(idx, coeffs)),
256            Self::U256 { cache, coeffs } => read_lock(cache).contains_key(&flat_index(idx, coeffs)),
257            Self::U512 { cache, coeffs } => read_lock(cache).contains_key(&flat_index(idx, coeffs)),
258            Self::U1024 { cache, coeffs } => {
259                read_lock(cache).contains_key(&flat_index(idx, coeffs))
260            }
261        }
262    }
263
264    fn len(&self) -> usize {
265        match self {
266            Self::U64 { cache, .. } => read_lock(cache).len(),
267            Self::U128 { cache, .. } => read_lock(cache).len(),
268            Self::U256 { cache, .. } => read_lock(cache).len(),
269            Self::U512 { cache, .. } => read_lock(cache).len(),
270            Self::U1024 { cache, .. } => read_lock(cache).len(),
271        }
272    }
273
274    fn clear(&self) {
275        match self {
276            Self::U64 { cache, .. } => write_lock(cache).clear(),
277            Self::U128 { cache, .. } => write_lock(cache).clear(),
278            Self::U256 { cache, .. } => write_lock(cache).clear(),
279            Self::U512 { cache, .. } => write_lock(cache).clear(),
280            Self::U1024 { cache, .. } => write_lock(cache).clear(),
281        }
282    }
283
284    fn key_type_name(&self) -> &'static str {
285        match self {
286            Self::U64 { .. } => "u64",
287            Self::U128 { .. } => "u128",
288            Self::U256 { .. } => "U256",
289            Self::U512 { .. } => "U512",
290            Self::U1024 { .. } => "U1024",
291        }
292    }
293
294    /// Whether this key width can encode one side of an additive site split.
295    fn supports_side_keys(&self) -> bool {
296        matches!(self, Self::U64 { .. } | Self::U128 { .. })
297    }
298
299    /// Encode one side of an additive site split with this cache's coefficients.
300    ///
301    /// Returns `None` for the key widths that have no side-key support. The
302    /// caller has already checked that `sites` are distinct and in range and
303    /// that every fragment matches its site list.
304    fn side_key_values<I: IndexInt>(
305        &self,
306        sites: &[usize],
307        fragments: &[Vec<I>],
308    ) -> Option<SideKeyValues> {
309        match self {
310            Self::U64 { coeffs, .. } => {
311                let side = select_coeffs(coeffs, sites);
312                Some(SideKeyValues::U64(
313                    fragments
314                        .iter()
315                        .map(|fragment| flat_index(fragment, &side))
316                        .collect(),
317                ))
318            }
319            Self::U128 { coeffs, .. } => {
320                let side = select_coeffs(coeffs, sites);
321                Some(SideKeyValues::U128(
322                    fragments
323                        .iter()
324                        .map(|fragment| flat_index(fragment, &side))
325                        .collect(),
326                ))
327            }
328            _ => None,
329        }
330    }
331}
332
333/// The coefficients of `sites`, in the order the fragments carry them.
334fn select_coeffs<K: Clone>(coeffs: &[K], sites: &[usize]) -> Vec<K> {
335    sites.iter().map(|&site| coeffs[site].clone()).collect()
336}
337
338/// Type-erased cache interface for custom key types.
339trait DynCache<V>: Send + Sync {
340    fn get(&self, idx: &[usize]) -> Option<V>;
341    fn insert(&self, idx: &[usize], value: V);
342    fn contains(&self, idx: &[usize]) -> bool;
343    fn len(&self) -> usize;
344    fn clear(&self);
345}
346
347/// Generic cache for user-specified key types.
348struct GenericCache<K: CacheKey, V> {
349    cache: RwLock<FxHashMap<K, V>>,
350    coeffs: Vec<K>,
351}
352
353impl<K: CacheKey, V: Clone + Send + Sync> GenericCache<K, V> {
354    fn new(local_dims: &[usize]) -> Result<Self, error::CacheKeyError> {
355        Ok(Self {
356            cache: RwLock::new(FxHashMap::default()),
357            coeffs: compute_coeffs::<K>(local_dims)?,
358        })
359    }
360}
361
362impl<K: CacheKey, V: Clone + Send + Sync> DynCache<V> for GenericCache<K, V> {
363    fn get(&self, idx: &[usize]) -> Option<V> {
364        let key = flat_index::<K, usize>(idx, &self.coeffs);
365        read_lock(&self.cache).get(&key).cloned()
366    }
367
368    fn insert(&self, idx: &[usize], value: V) {
369        let key = flat_index::<K, usize>(idx, &self.coeffs);
370        write_lock(&self.cache).insert(key, value);
371    }
372
373    fn contains(&self, idx: &[usize]) -> bool {
374        let key = flat_index::<K, usize>(idx, &self.coeffs);
375        read_lock(&self.cache).contains_key(&key)
376    }
377
378    fn len(&self) -> usize {
379        read_lock(&self.cache).len()
380    }
381
382    fn clear(&self) {
383        write_lock(&self.cache).clear();
384    }
385}
386
387/// Internal backend: auto-selected enum or custom type-erased cache.
388enum CacheBackend<V: Clone + Send + Sync + 'static> {
389    Auto(InnerCache<V>),
390    Custom(Box<dyn DynCache<V>>),
391}
392
393impl<V: Clone + Send + Sync + 'static> CacheBackend<V> {
394    fn get<I: IndexInt>(&self, idx: &[I]) -> Option<V> {
395        match self {
396            Self::Auto(inner) => inner.get(idx),
397            Self::Custom(cache) => {
398                let usize_idx: Vec<usize> = idx.iter().map(|&i| i.to_usize()).collect();
399                cache.get(&usize_idx)
400            }
401        }
402    }
403
404    fn insert<I: IndexInt>(&self, idx: &[I], value: V) {
405        match self {
406            Self::Auto(inner) => inner.insert(idx, value),
407            Self::Custom(cache) => {
408                let usize_idx: Vec<usize> = idx.iter().map(|&i| i.to_usize()).collect();
409                cache.insert(&usize_idx, value);
410            }
411        }
412    }
413
414    fn contains<I: IndexInt>(&self, idx: &[I]) -> bool {
415        match self {
416            Self::Auto(inner) => inner.contains(idx),
417            Self::Custom(cache) => {
418                let usize_idx: Vec<usize> = idx.iter().map(|&i| i.to_usize()).collect();
419                cache.contains(&usize_idx)
420            }
421        }
422    }
423
424    fn len(&self) -> usize {
425        match self {
426            Self::Auto(inner) => inner.len(),
427            Self::Custom(cache) => cache.len(),
428        }
429    }
430
431    fn clear(&self) {
432        match self {
433            Self::Auto(inner) => inner.clear(),
434            Self::Custom(cache) => cache.clear(),
435        }
436    }
437
438    fn key_type_name(&self) -> &'static str {
439        match self {
440            Self::Auto(inner) => inner.key_type_name(),
441            Self::Custom(_) => "custom",
442        }
443    }
444}
445
446type BatchFunc<I, V> = dyn Fn(&[Vec<I>]) -> Vec<V> + Send + Sync;
447
448/// A wrapper that caches function evaluations for multi-index inputs.
449///
450/// Thread-safe: all methods take `&self`. Multiple threads can call `eval`
451/// concurrently.
452///
453/// # Type parameters
454///
455/// - `V` - cached value type
456/// - `F` - single-evaluation function `Fn(&[I]) -> V`
457/// - `I` - index element type (default `usize`); use `u8` for quantics
458///
459/// # Examples
460///
461/// ```
462/// use tensor4all_core::CachedFunction;
463///
464/// // Cache a 2-site function with local dimensions [3, 4]
465/// let cf = CachedFunction::new(
466///     |idx: &[usize]| (idx[0] * 4 + idx[1]) as f64,
467///     &[3, 4],
468/// ).unwrap();
469///
470/// // First call evaluates and caches
471/// let v00 = cf.eval(&[0, 0]).unwrap();
472/// assert_eq!(v00, 0.0);
473/// assert_eq!(cf.num_evals(), 1);
474/// assert_eq!(cf.num_cache_hits(), 0);
475///
476/// // Second call uses cache
477/// let v00_again = cf.eval(&[0, 0]).unwrap();
478/// assert_eq!(v00_again, 0.0);
479/// assert_eq!(cf.num_cache_hits(), 1);
480///
481/// let v12 = cf.eval(&[1, 2]).unwrap();
482/// assert_eq!(v12, 6.0); // 1*4 + 2
483/// ```
484pub struct CachedFunction<V, F, I = usize>
485where
486    I: IndexInt,
487    V: Clone + Send + Sync + 'static,
488    F: Fn(&[I]) -> V + Send + Sync,
489{
490    func: F,
491    batch_func: Option<Box<BatchFunc<I, V>>>,
492    cache: CacheBackend<V>,
493    local_dims: Vec<usize>,
494    num_evals: AtomicUsize,
495    num_cache_hits: AtomicUsize,
496    _phantom: std::marker::PhantomData<I>,
497}
498
499impl<V, F, I> CachedFunction<V, F, I>
500where
501    I: IndexInt,
502    V: Clone + Send + Sync + 'static,
503    F: Fn(&[I]) -> V + Send + Sync,
504{
505    /// Create a new cached function with automatic key selection (up to 1024 bits).
506    ///
507    /// # Errors
508    ///
509    /// Returns [`error::CacheKeyError::Overflow`] when the index space requires
510    /// more than the automatic 1024-bit key width.
511    ///
512    /// # Examples
513    ///
514    /// ```
515    /// use tensor4all_core::CachedFunction;
516    ///
517    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0] + idx[1], &[2, 3]).unwrap();
518    /// assert_eq!(cf.eval(&[1, 2]).unwrap(), 3);
519    /// assert_eq!(cf.num_sites(), 2);
520    /// assert_eq!(cf.local_dims(), &[2, 3]);
521    /// ```
522    pub fn new(func: F, local_dims: &[usize]) -> Result<Self, error::CacheKeyError> {
523        Ok(Self {
524            func,
525            batch_func: None,
526            cache: CacheBackend::Auto(InnerCache::new(local_dims)?),
527            local_dims: local_dims.to_vec(),
528            num_evals: AtomicUsize::new(0),
529            num_cache_hits: AtomicUsize::new(0),
530            _phantom: std::marker::PhantomData,
531        })
532    }
533
534    /// Create with a batch function for efficient multi-point evaluation.
535    ///
536    /// The batch function is used for cache misses during [`eval_batch`](Self::eval_batch)
537    /// calls, enabling amortized cost when evaluating many indices at once
538    /// (e.g., batch FFI calls or vectorized computations).
539    ///
540    /// # Errors
541    ///
542    /// Returns [`error::CacheKeyError::Overflow`] when the index space requires
543    /// more than the automatic 1024-bit key width.
544    ///
545    /// # Examples
546    ///
547    /// ```
548    /// use tensor4all_core::CachedFunction;
549    ///
550    /// let cf = CachedFunction::with_batch(
551    ///     |idx: &[usize]| idx[0] * 10 + idx[1],
552    ///     |indices: &[Vec<usize>]| indices.iter().map(|idx| idx[0] * 10 + idx[1]).collect(),
553    ///     &[3, 4],
554    /// ).unwrap();
555    ///
556    /// let results = cf.eval_batch(&[vec![0, 1], vec![2, 3]]).unwrap();
557    /// assert_eq!(results, vec![1, 23]);
558    /// assert_eq!(cf.num_evals(), 2);
559    /// ```
560    pub fn with_batch<B>(
561        func: F,
562        batch_func: B,
563        local_dims: &[usize],
564    ) -> Result<Self, error::CacheKeyError>
565    where
566        B: Fn(&[Vec<I>]) -> Vec<V> + Send + Sync + 'static,
567    {
568        Ok(Self {
569            func,
570            batch_func: Some(Box::new(batch_func)),
571            cache: CacheBackend::Auto(InnerCache::new(local_dims)?),
572            local_dims: local_dims.to_vec(),
573            num_evals: AtomicUsize::new(0),
574            num_cache_hits: AtomicUsize::new(0),
575            _phantom: std::marker::PhantomData,
576        })
577    }
578
579    /// Create with an explicit key type for index spaces larger than 1024 bits.
580    ///
581    /// # Errors
582    ///
583    /// Returns [`error::CacheKeyError::Overflow`] when the index space requires
584    /// more bits than `K` supports.
585    ///
586    /// # Example
587    ///
588    /// ```
589    /// use bnum::types::U2048;
590    /// use tensor4all_core::{CacheKey, CachedFunction};
591    ///
592    /// #[derive(Clone, Hash, PartialEq, Eq)]
593    /// struct U2048Key(U2048);
594    ///
595    /// impl CacheKey for U2048Key {
596    ///     const BITS_COUNT: u32 = 2048;
597    ///     const ZERO: Self = Self(U2048::ZERO);
598    ///     const ONE: Self = Self(U2048::ONE);
599    ///
600    ///     fn from_usize(v: usize) -> Self {
601    ///         Self(U2048::from(v as u64))
602    ///     }
603    ///
604    ///     fn checked_mul(self, rhs: Self) -> Option<Self> {
605    ///         self.0.checked_mul(rhs.0).map(Self)
606    ///     }
607    ///
608    ///     fn wrapping_add(self, rhs: Self) -> Self {
609    ///         Self(self.0.wrapping_add(rhs.0))
610    ///     }
611    /// }
612    ///
613    /// let local_dims = vec![2usize; 1025];
614    /// let cf = CachedFunction::with_key_type::<U2048Key>(
615    ///     |idx: &[usize]| idx.iter().sum::<usize>(),
616    ///     &local_dims,
617    /// ).unwrap();
618    /// let zeros = vec![0usize; 1025];
619    ///
620    /// assert_eq!(cf.eval(&zeros).unwrap(), 0);
621    /// assert_eq!(cf.key_type(), "custom");
622    /// ```
623    pub fn with_key_type<K: CacheKey>(
624        func: F,
625        local_dims: &[usize],
626    ) -> Result<Self, error::CacheKeyError> {
627        Ok(Self {
628            func,
629            batch_func: None,
630            cache: CacheBackend::Custom(Box::new(GenericCache::<K, V>::new(local_dims)?)),
631            local_dims: local_dims.to_vec(),
632            num_evals: AtomicUsize::new(0),
633            num_cache_hits: AtomicUsize::new(0),
634            _phantom: std::marker::PhantomData,
635        })
636    }
637
638    /// Create with explicit key type and batch function.
639    ///
640    /// Combines [`with_key_type`](Self::with_key_type) and
641    /// [`with_batch`](Self::with_batch) for index spaces larger than 1024
642    /// bits that also benefit from batch evaluation.
643    ///
644    /// # Errors
645    ///
646    /// Returns [`error::CacheKeyError::Overflow`] when the index space requires
647    /// more bits than `K` supports.
648    ///
649    /// # Examples
650    ///
651    /// ```
652    /// use tensor4all_core::CachedFunction;
653    ///
654    /// // Use u128 key type with batch support
655    /// let cf = CachedFunction::with_key_type_and_batch::<u128, _>(
656    ///     |idx: &[usize]| idx.iter().sum::<usize>(),
657    ///     |indices: &[Vec<usize>]| indices.iter().map(|idx| idx.iter().sum()).collect(),
658    ///     &[2, 3, 4],
659    /// ).unwrap();
660    ///
661    /// let results = cf.eval_batch(&[vec![0, 0, 0], vec![1, 2, 3]]).unwrap();
662    /// assert_eq!(results, vec![0, 6]);
663    /// ```
664    pub fn with_key_type_and_batch<K: CacheKey, B>(
665        func: F,
666        batch_func: B,
667        local_dims: &[usize],
668    ) -> Result<Self, error::CacheKeyError>
669    where
670        B: Fn(&[Vec<I>]) -> Vec<V> + Send + Sync + 'static,
671    {
672        Ok(Self {
673            func,
674            batch_func: Some(Box::new(batch_func)),
675            cache: CacheBackend::Custom(Box::new(GenericCache::<K, V>::new(local_dims)?)),
676            local_dims: local_dims.to_vec(),
677            num_evals: AtomicUsize::new(0),
678            num_cache_hits: AtomicUsize::new(0),
679            _phantom: std::marker::PhantomData,
680        })
681    }
682
683    /// Evaluate at a given index, using cache if available.
684    ///
685    /// On the first call for a given index, the wrapped function is invoked and
686    /// the result is cached. Subsequent calls with the same index return the
687    /// cached value. This method is thread-safe.
688    ///
689    /// # Errors
690    /// Returns [`error::CacheKeyError::InvalidIndexLength`] for a wrong-rank index or
691    /// [`error::CacheKeyError::IndexOutOfBounds`] for an invalid coordinate.
692    ///
693    /// # Examples
694    ///
695    /// ```
696    /// use tensor4all_core::CachedFunction;
697    ///
698    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0] * idx[1], &[5, 5]).unwrap();
699    /// assert_eq!(cf.eval(&[3, 4]).unwrap(), 12);
700    /// assert_eq!(cf.num_evals(), 1);
701    ///
702    /// // Cache hit
703    /// assert_eq!(cf.eval(&[3, 4]).unwrap(), 12);
704    /// assert_eq!(cf.num_evals(), 1);
705    /// assert_eq!(cf.num_cache_hits(), 1);
706    /// ```
707    pub fn eval(&self, idx: &[I]) -> Result<V, error::CacheKeyError> {
708        self.validate_index(idx)?;
709        if let Some(value) = self.cache.get(idx) {
710            self.num_cache_hits.fetch_add(1, Ordering::Relaxed);
711            return Ok(value);
712        }
713
714        self.num_evals.fetch_add(1, Ordering::Relaxed);
715        let value = (self.func)(idx);
716        self.cache.insert(idx, value.clone());
717        Ok(value)
718    }
719
720    /// Evaluate bypassing the cache.
721    ///
722    /// The result is neither read from nor stored in the cache, and
723    /// evaluation counters are not updated. Useful for verification or
724    /// when the caller intentionally wants a fresh evaluation.
725    ///
726    /// # Errors
727    /// Returns [`error::CacheKeyError::InvalidIndexLength`] for a wrong-rank index or
728    /// [`error::CacheKeyError::IndexOutOfBounds`] for an invalid coordinate.
729    ///
730    /// # Examples
731    ///
732    /// ```
733    /// use tensor4all_core::CachedFunction;
734    ///
735    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0] + 1, &[4]).unwrap();
736    /// assert_eq!(cf.eval_no_cache(&[2]).unwrap(), 3);
737    /// assert_eq!(cf.cache_size(), 0);
738    /// assert_eq!(cf.num_evals(), 0);
739    /// ```
740    pub fn eval_no_cache(&self, idx: &[I]) -> Result<V, error::CacheKeyError> {
741        self.validate_index(idx)?;
742        Ok((self.func)(idx))
743    }
744
745    /// Evaluate at multiple indices. Uses batch function for cache misses if available.
746    ///
747    /// Returns results in the same order as the input indices.
748    ///
749    /// # Errors
750    /// Returns an index validation error for malformed coordinates or
751    /// [`error::CacheKeyError::BatchResultLength`] when a batch callback returns the
752    /// wrong number of values.
753    ///
754    /// # Examples
755    ///
756    /// ```
757    /// use tensor4all_core::CachedFunction;
758    ///
759    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0] * 2 + idx[1], &[2, 2]).unwrap();
760    /// let results = cf.eval_batch(&[vec![0, 0], vec![0, 1], vec![1, 0]]).unwrap();
761    /// assert_eq!(results, vec![0, 1, 2]);
762    /// ```
763    pub fn eval_batch(&self, indices: &[Vec<I>]) -> Result<Vec<V>, error::CacheKeyError> {
764        if indices.is_empty() {
765            return Ok(Vec::new());
766        }
767        for index in indices {
768            self.validate_index(index)?;
769        }
770
771        let mut results: Vec<Option<V>> = Vec::with_capacity(indices.len());
772        let mut miss_positions: Vec<usize> = Vec::new();
773        let mut miss_indices: Vec<Vec<I>> = Vec::new();
774
775        for (pos, idx) in indices.iter().enumerate() {
776            if let Some(value) = self.cache.get(idx) {
777                self.num_cache_hits.fetch_add(1, Ordering::Relaxed);
778                results.push(Some(value));
779            } else {
780                results.push(None);
781                miss_positions.push(pos);
782                miss_indices.push(idx.clone());
783            }
784        }
785
786        if miss_indices.is_empty() {
787            return Ok(results.into_iter().flatten().collect());
788        }
789
790        self.num_evals
791            .fetch_add(miss_indices.len(), Ordering::Relaxed);
792        let miss_values = if let Some(batch_func) = self.batch_func.as_ref() {
793            batch_func(&miss_indices)
794        } else {
795            miss_indices.iter().map(|idx| (self.func)(idx)).collect()
796        };
797        if miss_values.len() != miss_indices.len() {
798            return Err(error::CacheKeyError::BatchResultLength {
799                expected: miss_indices.len(),
800                got: miss_values.len(),
801            });
802        }
803
804        for (i, pos) in miss_positions.iter().enumerate() {
805            self.cache.insert(&miss_indices[i], miss_values[i].clone());
806            results[*pos] = Some(miss_values[i].clone());
807        }
808
809        Ok(results.into_iter().flatten().collect())
810    }
811
812    fn validate_index(&self, idx: &[I]) -> std::result::Result<(), error::CacheKeyError> {
813        if idx.len() != self.local_dims.len() {
814            return Err(error::CacheKeyError::InvalidIndexLength {
815                expected: self.local_dims.len(),
816                got: idx.len(),
817            });
818        }
819        for (axis, (&value, &dim)) in idx.iter().zip(&self.local_dims).enumerate() {
820            let value = value.to_usize();
821            if value >= dim {
822                return Err(error::CacheKeyError::IndexOutOfBounds {
823                    axis,
824                    index: value,
825                    dim,
826                });
827            }
828        }
829        Ok(())
830    }
831
832    /// Get the local dimensions.
833    ///
834    /// # Examples
835    ///
836    /// ```
837    /// use tensor4all_core::CachedFunction;
838    ///
839    /// let cf = CachedFunction::new(|idx: &[usize]| 0, &[3, 4, 5]).unwrap();
840    /// assert_eq!(cf.local_dims(), &[3, 4, 5]);
841    /// ```
842    pub fn local_dims(&self) -> &[usize] {
843        &self.local_dims
844    }
845
846    /// Get the number of sites (length of the multi-index).
847    ///
848    /// # Examples
849    ///
850    /// ```
851    /// use tensor4all_core::CachedFunction;
852    ///
853    /// let cf = CachedFunction::new(|idx: &[usize]| 0, &[2, 3]).unwrap();
854    /// assert_eq!(cf.num_sites(), 2);
855    /// ```
856    pub fn num_sites(&self) -> usize {
857        self.local_dims.len()
858    }
859
860    /// Get the number of function evaluations (cache misses).
861    ///
862    /// # Examples
863    ///
864    /// ```
865    /// use tensor4all_core::CachedFunction;
866    ///
867    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
868    /// cf.eval(&[0]).unwrap();
869    /// cf.eval(&[1]).unwrap();
870    /// cf.eval(&[0]).unwrap(); // cache hit, not a new eval
871    /// assert_eq!(cf.num_evals(), 2);
872    /// ```
873    pub fn num_evals(&self) -> usize {
874        self.num_evals.load(Ordering::Relaxed)
875    }
876
877    /// Get the number of cache hits.
878    ///
879    /// # Examples
880    ///
881    /// ```
882    /// use tensor4all_core::CachedFunction;
883    ///
884    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
885    /// cf.eval(&[0]).unwrap();
886    /// assert_eq!(cf.num_cache_hits(), 0);
887    /// cf.eval(&[0]).unwrap();
888    /// assert_eq!(cf.num_cache_hits(), 1);
889    /// ```
890    pub fn num_cache_hits(&self) -> usize {
891        self.num_cache_hits.load(Ordering::Relaxed)
892    }
893
894    /// Get total calls (evaluations + cache hits).
895    ///
896    /// # Examples
897    ///
898    /// ```
899    /// use tensor4all_core::CachedFunction;
900    ///
901    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
902    /// cf.eval(&[0]).unwrap();
903    /// cf.eval(&[1]).unwrap();
904    /// cf.eval(&[0]).unwrap(); // cache hit
905    /// assert_eq!(cf.total_calls(), 3);
906    /// assert_eq!(cf.total_calls(), cf.num_evals() + cf.num_cache_hits());
907    /// ```
908    pub fn total_calls(&self) -> usize {
909        self.num_evals() + self.num_cache_hits()
910    }
911
912    /// Get cache hit ratio (0.0 when no calls have been made).
913    ///
914    /// Returns `num_cache_hits() / total_calls()` as a value in `[0.0, 1.0]`.
915    ///
916    /// # Examples
917    ///
918    /// ```
919    /// use tensor4all_core::CachedFunction;
920    ///
921    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
922    /// assert_eq!(cf.cache_hit_ratio(), 0.0); // no calls yet
923    ///
924    /// cf.eval(&[0]).unwrap();
925    /// cf.eval(&[0]).unwrap(); // cache hit
926    /// assert!((cf.cache_hit_ratio() - 0.5).abs() < 1e-10);
927    /// ```
928    pub fn cache_hit_ratio(&self) -> f64 {
929        let total = self.total_calls();
930        if total == 0 {
931            0.0
932        } else {
933            self.num_cache_hits() as f64 / total as f64
934        }
935    }
936
937    /// Clear the cache.
938    ///
939    /// # Examples
940    ///
941    /// ```
942    /// use tensor4all_core::CachedFunction;
943    ///
944    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
945    /// cf.eval(&[2]).unwrap();
946    /// assert_eq!(cf.cache_size(), 1);
947    /// cf.clear_cache();
948    /// assert_eq!(cf.cache_size(), 0);
949    /// ```
950    pub fn clear_cache(&self) {
951        self.cache.clear();
952    }
953
954    /// Number of cached entries.
955    ///
956    /// # Examples
957    ///
958    /// ```
959    /// use tensor4all_core::CachedFunction;
960    ///
961    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
962    /// assert_eq!(cf.cache_size(), 0);
963    /// cf.eval(&[0]).unwrap();
964    /// cf.eval(&[1]).unwrap();
965    /// assert_eq!(cf.cache_size(), 2);
966    /// cf.eval(&[0]).unwrap(); // cache hit, no new entry
967    /// assert_eq!(cf.cache_size(), 2);
968    /// ```
969    pub fn cache_size(&self) -> usize {
970        self.cache.len()
971    }
972
973    /// Check if an index is cached.
974    ///
975    /// # Examples
976    ///
977    /// ```
978    /// use tensor4all_core::CachedFunction;
979    ///
980    /// let cf = CachedFunction::new(|idx: &[usize]| idx[0], &[4]).unwrap();
981    /// assert!(!cf.is_cached(&[1]));
982    /// cf.eval(&[1]).unwrap();
983    /// assert!(cf.is_cached(&[1]));
984    /// ```
985    pub fn is_cached(&self, idx: &[I]) -> bool {
986        self.cache.contains(idx)
987    }
988
989    /// Internal key type name (for debugging).
990    ///
991    /// Returns `"u64"`, `"u128"`, `"U256"`, `"U512"`, `"U1024"` for
992    /// automatically selected types, or `"custom"` when constructed with
993    /// [`with_key_type`](Self::with_key_type).
994    ///
995    /// # Examples
996    ///
997    /// ```
998    /// use tensor4all_core::CachedFunction;
999    ///
1000    /// // Small index space uses u64
1001    /// let cf = CachedFunction::new(|idx: &[usize]| 0, &[2, 3]).unwrap();
1002    /// assert_eq!(cf.key_type(), "u64");
1003    /// ```
1004    pub fn key_type(&self) -> &'static str {
1005        self.cache.key_type_name()
1006    }
1007}
1008
1009#[cfg(test)]
1010mod tests;