use std::any::{Any, TypeId};
use std::collections::{BTreeMap, HashMap};
use std::hash::{BuildHasher, Hash};
use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
use std::sync::{Arc, OnceLock, RwLock, RwLockReadGuard, RwLockWriteGuard, TryLockError};
use crate::bh::Rat;
use crate::coeff::Ring;
use crate::fasthash;
use crate::frac::Frac;
use crate::guard::GuardedRat;
use crate::partition::{partitions_of, Partition};
use crate::qt::QtPoly;
use crate::sym::{PowerSum, Schur, SymFn};
pub(crate) trait HeapSize {
fn heap_bytes(&self) -> usize;
}
macro_rules! inline_heap {
($($t:ty),*) => {$(
impl HeapSize for $t {
#[inline]
fn heap_bytes(&self) -> usize {
0
}
}
)*};
}
inline_heap!(u32, u64, u128, i64, i128, TypeId, GuardedRat);
impl<A: HeapSize, B: HeapSize> HeapSize for (A, B) {
#[inline]
fn heap_bytes(&self) -> usize {
self.0.heap_bytes() + self.1.heap_bytes()
}
}
impl<A: HeapSize, B: HeapSize, C: HeapSize> HeapSize for (A, B, C) {
#[inline]
fn heap_bytes(&self) -> usize {
self.0.heap_bytes() + self.1.heap_bytes() + self.2.heap_bytes()
}
}
impl<T: HeapSize> HeapSize for Vec<T> {
fn heap_bytes(&self) -> usize {
self.capacity() * std::mem::size_of::<T>()
+ self.iter().map(HeapSize::heap_bytes).sum::<usize>()
}
}
impl<T: HeapSize> HeapSize for Arc<T> {
fn heap_bytes(&self) -> usize {
2 * std::mem::size_of::<usize>() + std::mem::size_of::<T>() + (**self).heap_bytes()
}
}
impl<K: HeapSize, V: HeapSize> HeapSize for BTreeMap<K, V> {
fn heap_bytes(&self) -> usize {
btree_node_bytes::<K, V>(self.len())
+ self
.iter()
.map(|(k, v)| k.heap_bytes() + v.heap_bytes())
.sum::<usize>()
}
}
fn btree_node_bytes<K, V>(len: usize) -> usize {
let leaf = 11 * (std::mem::size_of::<K>() + std::mem::size_of::<V>()) + 16;
len.div_ceil(8) * leaf
}
pub(crate) fn coeff_heap_bytes<C: 'static>(c: &C) -> usize {
let any: &dyn Any = c;
#[cfg(feature = "bignum")]
{
if let Some(b) = any.downcast_ref::<num_bigint::BigInt>() {
return bigint_heap_bytes(b);
}
if let Some(r) = any.downcast_ref::<num_rational::BigRational>() {
return bigint_heap_bytes(r.numer()) + bigint_heap_bytes(r.denom());
}
}
let _ = any;
0
}
#[cfg(feature = "bignum")]
fn bigint_heap_bytes(b: &num_bigint::BigInt) -> usize {
usize::try_from(b.bits().div_ceil(64) * 8).unwrap_or(usize::MAX)
}
impl HeapSize for Schur<QtPoly<i128>> {
fn heap_bytes(&self) -> usize {
self.terms().heap_bytes()
}
}
impl HeapSize for PowerSum<GuardedRat> {
fn heap_bytes(&self) -> usize {
self.terms().heap_bytes()
}
}
impl HeapSize for Arc<dyn Any + Send + Sync> {
fn heap_bytes(&self) -> usize {
0
}
}
pub(crate) struct Table<K, V, S = std::hash::RandomState> {
map: OnceLock<RwLock<HashMap<K, V, S>>>,
heap: AtomicUsize,
slots: AtomicUsize,
}
impl<K, V, S: Default + BuildHasher> Table<K, V, S> {
const fn new() -> Self {
Table {
map: OnceLock::new(),
heap: AtomicUsize::new(0),
slots: AtomicUsize::new(0),
}
}
fn map(&self) -> &RwLock<HashMap<K, V, S>> {
self.map
.get_or_init(|| RwLock::new(HashMap::with_hasher(S::default())))
}
fn bytes(&self) -> usize {
self.heap.load(Relaxed) + self.slots.load(Relaxed)
}
fn entries(&self) -> usize {
rd(self).len()
}
fn slot_bytes(capacity: usize) -> usize {
if capacity == 0 {
return 0;
}
let buckets = (capacity * 8).div_ceil(7).next_power_of_two();
buckets * (std::mem::size_of::<(K, V)>() + 1)
}
fn note_insert(&self, heap: usize, capacity: usize) {
self.heap.fetch_add(heap, Relaxed);
self.slots.store(Self::slot_bytes(capacity), Relaxed);
}
fn insert(&self, key: K, value: V, heap: usize)
where
K: Eq + Hash,
{
let mut m = wr(self);
m.insert(key, value);
let capacity = m.capacity();
drop(m);
self.note_insert(heap, capacity);
enforce_budget();
}
fn clear_locked(&self, m: &mut HashMap<K, V, S>) {
*m = HashMap::with_hasher(S::default());
self.heap.store(0, Relaxed);
self.slots.store(0, Relaxed);
}
fn clear_blocking(&self) {
let mut m = wr(self);
self.clear_locked(&mut m);
}
fn clear(&self) -> bool {
match self.map().try_write() {
Ok(mut m) => {
self.clear_locked(&mut m);
true
}
Err(TryLockError::Poisoned(p)) => {
self.clear_locked(&mut p.into_inner());
true
}
Err(TryLockError::WouldBlock) => false,
}
}
}
fn rd<K, V, S: Default + BuildHasher>(t: &Table<K, V, S>) -> RwLockReadGuard<'_, HashMap<K, V, S>> {
t.map().read().unwrap_or_else(|e| e.into_inner())
}
fn wr<K, V, S: Default + BuildHasher>(
t: &Table<K, V, S>,
) -> RwLockWriteGuard<'_, HashMap<K, V, S>> {
t.map().write().unwrap_or_else(|e| e.into_inner())
}
fn lookup<K, V>(table: &Table<K, V>, key: &K, compute: impl FnOnce() -> V) -> V
where
K: Eq + Hash + Clone + HeapSize,
V: Clone + HeapSize,
{
if let Some(v) = rd(table).get(key) {
return v.clone();
}
let v = compute();
let key = key.clone();
let heap = key.heap_bytes() + v.heap_bytes();
table.insert(key, v.clone(), heap);
v
}
#[derive(Clone, Copy)]
struct TableInfo {
name: &'static str,
tier: u8,
bytes: fn() -> usize,
entries: fn() -> usize,
clear_blocking: fn(),
clear: fn() -> bool,
}
macro_rules! hasher {
() => {
std::hash::RandomState
};
($h:ty) => {
$h
};
}
macro_rules! tables {
($($tier:literal $label:literal $name:ident : $key:ty => $val:ty $(, $hasher:ty)?;)*) => {
$(
fn $name() -> &'static Table<$key, $val, hasher!($($hasher)?)> {
static T: Table<$key, $val, hasher!($($hasher)?)> = Table::new();
&T
}
)*
static REGISTRY: &[TableInfo] = &[$(TableInfo {
name: $label,
tier: $tier,
bytes: || $name().bytes(),
entries: || $name().entries(),
clear_blocking: || $name().clear_blocking(),
clear: || $name().clear(),
}),*];
};
}
tables! {
0 "flip_rows" flip_row_table: u32 => Arc<Vec<(Partition, i64)>>;
0 "lex_partitions" lex_parts_table: u32 => Arc<Vec<Partition>>;
0 "partitions" partitions_table: u32 => Arc<Vec<Partition>>;
0 "power_in_h_rows" power_in_h_row_table: u32 => Arc<Vec<(Partition, i128)>>;
1 "bh_ell" bh_ell_table: (Partition, Partition) => Rat<i128>;
1 "bh_pieri" bh_pieri_table: (Partition, Partition) => Rat<i128>;
1 "character" character_table: (Partition, Partition) => i128;
1 "character_masks" character_mask_table: (u64, u64) => i128,
std::hash::BuildHasherDefault<fasthash::MixHasher>;
1 "character_wide_masks" character_wide_mask_table: (u128, u128) => i128,
std::hash::BuildHasherDefault<fasthash::MixHasher>;
1 "kostka" kostka_table: (Partition, Partition) => u128;
1 "lr" lr_table: (Partition, Partition, Partition) => u128;
2 "bold_p" bold_p_table: Partition => Arc<PowerSum<GuardedRat>>;
2 "ht_to_st" ht_to_st_table: Partition => Arc<Vec<(Partition, i128)>>;
2 "htilde" htilde_table: u32 => Arc<Vec<(Partition, Schur<QtPoly<i128>>)>>;
2 "inverse_kostka_rows" inverse_kostka_row_table: Partition => Arc<Vec<i128>>;
2 "jt_rows" jt_row_table: Partition => Arc<Vec<(Partition, i64)>>;
2 "products" product_table: (Partition, Partition) => Arc<Vec<(Partition, u128)>>;
2 "reduced_kronecker" reduced_kronecker_table: (Partition, Partition)
=> Arc<Vec<(Partition, i128)>>;
2 "schur_to_st" schur_to_st_table: Partition => Arc<Vec<(Partition, i128)>>;
2 "skews" skew_table: (Partition, Partition) => Arc<Vec<(Partition, u128)>>;
2 "st_to_ht" st_to_ht_table: Partition => Arc<Vec<(Partition, i128)>>;
2 "st_to_schur" st_to_schur_table: Partition => Arc<Vec<(Partition, i128)>>;
3 "transitions" transition_store: (TypeId, u32) => Arc<dyn Any + Send + Sync>;
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct CacheStat {
pub name: &'static str,
pub tier: u8,
pub entries: usize,
pub bytes: usize,
}
pub fn cache_stats() -> Vec<CacheStat> {
REGISTRY
.iter()
.map(|t| CacheStat {
name: t.name,
tier: t.tier,
entries: (t.entries)(),
bytes: (t.bytes)(),
})
.collect()
}
static BUDGET: AtomicUsize = AtomicUsize::new(usize::MAX);
const EVICTION_ORDER: [u8; 3] = [2, 3, 1];
pub fn cache_budget() -> Option<usize> {
match BUDGET.load(Relaxed) {
usize::MAX => None,
b => Some(b),
}
}
pub fn set_cache_budget(budget: Option<usize>) {
BUDGET.store(budget.unwrap_or(usize::MAX), Relaxed);
}
fn total_bytes() -> usize {
REGISTRY.iter().map(|t| (t.bytes)()).sum()
}
fn enforce_budget() {
let budget = BUDGET.load(Relaxed);
if budget == usize::MAX || total_bytes() <= budget {
return;
}
for tier in EVICTION_ORDER {
loop {
let largest = REGISTRY
.iter()
.filter(|t| t.tier == tier)
.map(|t| (t, (t.bytes)()))
.filter(|(_, b)| *b > 0)
.max_by_key(|(_, b)| *b);
let Some((table, _)) = largest else {
break;
};
if !(table.clear)() {
break;
}
if total_bytes() <= budget {
return;
}
}
}
}
pub fn flip_row_cached(
n: u32,
compute: impl FnOnce() -> Vec<(Partition, i64)>,
) -> Arc<Vec<(Partition, i64)>> {
lookup(flip_row_table(), &n, || Arc::new(compute()))
}
pub fn power_in_h_row_cached(
n: u32,
compute: impl FnOnce() -> Vec<(Partition, i128)>,
) -> Arc<Vec<(Partition, i128)>> {
lookup(power_in_h_row_table(), &n, || Arc::new(compute()))
}
pub fn htilde_cached(
n: u32,
compute: impl FnOnce() -> Vec<(Partition, Schur<QtPoly<i128>>)>,
) -> Arc<Vec<(Partition, Schur<QtPoly<i128>>)>> {
lookup(htilde_table(), &n, || Arc::new(compute()))
}
pub fn schur_in_j_cached<C: Ring + Send + Sync + 'static>(
n: u32,
compute: impl FnOnce() -> Vec<Vec<Frac<C>>>,
) -> Arc<Vec<Vec<Frac<C>>>> {
transition_cached(n, compute)
}
pub fn mac_p_inverse_cached<C: Ring + Send + Sync + 'static>(
n: u32,
compute: impl FnOnce() -> Vec<std::collections::BTreeMap<Partition, Frac<C>>>,
) -> Arc<Vec<std::collections::BTreeMap<Partition, Frac<C>>>> {
transition_cached(n, compute)
}
pub fn jack_p_inverse_cached<C: crate::coeff::Integral + Send + Sync + 'static>(
n: u32,
compute: impl FnOnce() -> Vec<std::collections::BTreeMap<Partition, crate::AFrac<C>>>,
) -> Arc<Vec<std::collections::BTreeMap<Partition, crate::AFrac<C>>>> {
transition_cached(n, compute)
}
fn transition_cached<T: HeapSize + Send + Sync + 'static>(
n: u32,
compute: impl FnOnce() -> T,
) -> Arc<T> {
let key = (TypeId::of::<T>(), n);
if let Some(v) = rd(transition_store()).get(&key) {
return Arc::clone(v)
.downcast::<T>()
.expect("a transition cache is keyed by the type it stores");
}
let before = crate::guard::overflow_count();
let value = Arc::new(compute());
if crate::guard::overflow_count() == before {
let heap = value.heap_bytes();
transition_store().insert(key, Arc::clone(&value) as Arc<dyn Any + Send + Sync>, heap);
}
value
}
pub fn bh_pieri_cached(
key: &(Partition, Partition),
compute: impl FnOnce() -> Rat<i128>,
) -> Rat<i128> {
lookup(bh_pieri_table(), key, compute)
}
pub fn bh_ell_cached(
key: &(Partition, Partition),
compute: impl FnOnce() -> Rat<i128>,
) -> Rat<i128> {
lookup(bh_ell_table(), key, compute)
}
pub fn partitions_cached(n: u32) -> Arc<Vec<Partition>> {
lookup(partitions_table(), &n, || Arc::new(partitions_of(n)))
}
pub fn character_cached(
lambda: &Partition,
mu: &Partition,
compute: impl FnOnce() -> Option<i128>,
) -> Option<i128> {
let key = (lambda.clone(), mu.clone());
if let Some(&v) = rd(character_table()).get(&key) {
return Some(v);
}
let v = compute()?;
let heap = key.heap_bytes();
character_table().insert(key, v, heap);
Some(v)
}
pub(crate) trait MaskKey: crate::convert::Beta {
fn table(
) -> &'static Table<(Self, Self), i128, std::hash::BuildHasherDefault<fasthash::MixHasher>>;
}
impl MaskKey for u64 {
fn table(
) -> &'static Table<(u64, u64), i128, std::hash::BuildHasherDefault<fasthash::MixHasher>> {
character_mask_table()
}
}
impl MaskKey for u128 {
fn table(
) -> &'static Table<(u128, u128), i128, std::hash::BuildHasherDefault<fasthash::MixHasher>>
{
character_wide_mask_table()
}
}
pub(crate) fn character_masks_read<M: MaskKey>(
) -> RwLockReadGuard<'static, fasthash::Map<(M, M), i128>> {
rd(M::table())
}
pub(crate) fn character_masks_store<M: MaskKey>(entries: fasthash::Map<(M, M), i128>) {
let table = M::table();
let mut t = wr(table);
t.reserve(entries.len());
t.extend(entries);
let capacity = t.capacity();
drop(t);
table.note_insert(0, capacity);
enforce_budget();
}
pub fn kostka_cached(
lambda: &Partition,
mu: &Partition,
compute: impl FnOnce() -> Option<u128>,
) -> Option<u128> {
let table = kostka_table();
let key = (lambda.clone(), mu.clone());
if let Some(v) = rd(table).get(&key) {
return Some(*v);
}
let v = compute()?;
let heap = key.heap_bytes();
table.insert(key, v, heap);
Some(v)
}
pub fn lr_cached(
lambda: &Partition,
mu: &Partition,
nu: &Partition,
compute: impl FnOnce() -> u128,
) -> u128 {
lookup(
lr_table(),
&(lambda.clone(), mu.clone(), nu.clone()),
compute,
)
}
pub fn lex_parts_cached(n: u32) -> Arc<Vec<Partition>> {
lookup(lex_parts_table(), &n, || {
let mut v = partitions_of(n);
v.sort_by(|a, b| b.parts().cmp(a.parts()));
Arc::new(v)
})
}
pub fn inverse_kostka_row_cached(
mu: &Partition,
compute: impl FnOnce() -> Vec<i128>,
) -> Arc<Vec<i128>> {
lookup(inverse_kostka_row_table(), mu, || Arc::new(compute()))
}
pub fn jt_row_cached(
index: &Partition,
compute: impl FnOnce() -> Vec<(Partition, i64)>,
) -> Arc<Vec<(Partition, i64)>> {
lookup(jt_row_table(), index, || Arc::new(compute()))
}
pub fn bold_p_peek(gamma: &Partition) -> Option<Arc<PowerSum<GuardedRat>>> {
rd(bold_p_table()).get(gamma).cloned()
}
pub fn bold_p_store(gamma: &Partition, value: PowerSum<GuardedRat>) {
let value = Arc::new(value);
let heap = gamma.heap_bytes() + value.heap_bytes();
bold_p_table().insert(gamma.clone(), value, heap);
}
pub fn st_to_schur_cached(
lambda: &Partition,
compute: impl FnOnce() -> Vec<(Partition, i128)>,
) -> Arc<Vec<(Partition, i128)>> {
lookup(st_to_schur_table(), lambda, || Arc::new(compute()))
}
pub fn schur_to_st_cached(
nu: &Partition,
compute: impl FnOnce() -> Vec<(Partition, i128)>,
) -> Arc<Vec<(Partition, i128)>> {
lookup(schur_to_st_table(), nu, || Arc::new(compute()))
}
pub fn ht_to_st_cached(
mu: &Partition,
compute: impl FnOnce() -> Vec<(Partition, i128)>,
) -> Arc<Vec<(Partition, i128)>> {
lookup(ht_to_st_table(), mu, || Arc::new(compute()))
}
pub fn st_to_ht_cached(
lambda: &Partition,
compute: impl FnOnce() -> Vec<(Partition, i128)>,
) -> Arc<Vec<(Partition, i128)>> {
lookup(st_to_ht_table(), lambda, || Arc::new(compute()))
}
pub fn reduced_kronecker_cached(
lambda: &Partition,
mu: &Partition,
compute: impl FnOnce() -> Vec<(Partition, i128)>,
) -> Arc<Vec<(Partition, i128)>> {
lookup(
reduced_kronecker_table(),
&(lambda.clone(), mu.clone()),
|| Arc::new(compute()),
)
}
pub fn product_cached(
mu: &Partition,
nu: &Partition,
compute: impl FnOnce() -> Vec<(Partition, u128)>,
) -> Arc<Vec<(Partition, u128)>> {
lookup(product_table(), &(mu.clone(), nu.clone()), || {
Arc::new(compute())
})
}
pub fn skew_cached(
outer: &Partition,
inner: &Partition,
compute: impl FnOnce() -> Vec<(Partition, u128)>,
) -> Arc<Vec<(Partition, u128)>> {
lookup(skew_table(), &(outer.clone(), inner.clone()), || {
Arc::new(compute())
})
}
pub fn skew_cache_peek(
outer: &Partition,
inner: &Partition,
) -> Option<Arc<Vec<(Partition, u128)>>> {
rd(skew_table())
.get(&(outer.clone(), inner.clone()))
.cloned()
}
pub fn clear_caches() {
for t in REGISTRY {
(t.clear_blocking)();
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_reported_overflow_is_not_cached() {
use crate::guard::Guarded;
let _lock = crate::guard::serial();
let calls = std::cell::Cell::new(0);
let clean = || {
calls.set(calls.get() + 1);
vec![vec![Frac::<Guarded>::from_poly(QtPoly::zero())]]
};
let dirty = || {
calls.set(calls.get() + 1);
let _ = Guarded(i128::MAX).mul(&Guarded(2));
vec![vec![Frac::<Guarded>::from_poly(QtPoly::zero())]]
};
schur_in_j_cached(u32::MAX, clean);
schur_in_j_cached(u32::MAX, clean);
assert_eq!(calls.get(), 1, "a clean table was not cached");
calls.set(0);
schur_in_j_cached(u32::MAX - 1, dirty);
schur_in_j_cached(u32::MAX - 1, dirty);
assert_eq!(calls.get(), 2, "a table computed past the width was cached");
wr(transition_store()).clear();
}
#[test]
fn stats_rows_come_by_tier_then_name_and_cover_every_table() {
let rows = cache_stats();
assert_eq!(rows.len(), REGISTRY.len());
let order: Vec<(u8, &str)> = rows.iter().map(|r| (r.tier, r.name)).collect();
let mut sorted = order.clone();
sorted.sort();
assert_eq!(order, sorted, "registry order is tier, then name");
assert!(rows.iter().any(|r| r.name == "flip_rows" && r.tier == 0));
assert!(rows.iter().any(|r| r.name == "transitions" && r.tier == 3));
}
#[test]
fn an_insert_charges_the_key_and_value_and_the_buckets() {
static OWN: Table<(Partition, Partition), u128> = Table::new();
let lam = Partition::new([13, 11, 9, 7, 5, 3, 1]);
let mu = Partition::new([7, 7, 7, 7, 7, 7, 7]);
assert_eq!((OWN.entries(), OWN.bytes()), (0, 0));
lookup(&OWN, &(lam.clone(), mu.clone()), || 12345);
let keys = lam.heap_bytes() + mu.heap_bytes();
let slot = std::mem::size_of::<((Partition, Partition), u128)>() + 1;
assert_eq!(OWN.entries(), 1);
assert!(
OWN.bytes() >= keys + slot,
"{} bytes charged for {keys} of keys and at least one {slot}-byte slot",
OWN.bytes()
);
lookup(&OWN, &(lam.clone(), mu.clone()), || 0);
assert_eq!(OWN.entries(), 1, "a hit inserts nothing");
OWN.clear_blocking();
assert_eq!(
(OWN.entries(), OWN.bytes()),
(0, 0),
"clear releases the buckets too"
);
}
#[test]
fn partitions_are_shared_and_correct() {
let a = partitions_cached(6);
let b = partitions_cached(6);
assert_eq!(a.len(), 11); assert!(
Arc::ptr_eq(&a, &b),
"second call should reuse the cached Arc"
);
}
#[test]
fn lookup_computes_once_then_reuses() {
use std::sync::atomic::{AtomicUsize, Ordering};
let calls = AtomicUsize::new(0);
let lam = Partition::new([9, 7, 5, 3, 1]);
let mu = Partition::new([5, 5, 5, 5, 5]);
for _ in 0..5 {
kostka_cached(&lam, &mu, || {
calls.fetch_add(1, Ordering::SeqCst);
Some(12345)
});
}
assert_eq!(
calls.load(Ordering::SeqCst),
1,
"should compute exactly once"
);
}
}