use std::collections::HashMap;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, OnceLock, RwLock};
pub type CacheKey = (u8, u32);
const ENTRY_OVERHEAD: u64 = 96;
const ARC_HEADER: u64 = 16;
pub fn alloc_footprint(n: u64) -> u64 {
if n <= 64 {
return n.div_ceil(16).max(1) * 16;
}
let k = 63 - (n - 1).leading_zeros() as u64; let step = 1u64 << (k - 2);
n.div_ceil(step) * step
}
pub struct CacheEntry {
body: Arc<[u8]>,
runs: OnceLock<Arc<[usize]>>,
dir: OnceLock<crate::triples::GroupDirectory>,
segs: OnceLock<Option<Arc<[TileSeg]>>>,
}
pub type TileSeg = (u32, u32, u32, u32);
impl CacheEntry {
#[inline]
pub fn body(&self) -> &[u8] {
&self.body
}
#[inline]
pub fn body_arc(&self) -> Arc<[u8]> {
Arc::clone(&self.body)
}
#[inline]
pub fn runs(&self, compute: impl FnOnce(&[u8]) -> Vec<usize>) -> &[usize] {
if self.body.is_empty() {
return &[];
}
&self.runs.get_or_init(|| Arc::from(compute(&self.body)))[..]
}
#[inline]
pub fn group_dir(
&self,
compute: impl FnOnce() -> crate::triples::GroupDirectory,
) -> (&crate::triples::GroupDirectory, bool) {
let mut built = false;
let d = self.dir.get_or_init(|| {
built = true;
compute()
});
(d, built)
}
pub fn segments(
&self,
compute: impl FnOnce(&[u8]) -> Option<Vec<TileSeg>>,
) -> (Option<&[TileSeg]>, bool) {
let mut built = false;
let s = self.segs.get_or_init(|| {
built = true;
compute(&self.body).map(Arc::from)
});
(s.as_deref(), built)
}
#[inline]
fn charge(&self) -> u64 {
alloc_footprint(self.body.len() as u64 + ARC_HEADER) + ENTRY_OVERHEAD
}
}
#[derive(Debug, Clone, Copy, Default)]
pub struct CacheStats {
pub hits: u64,
pub misses: u64,
pub decoded_chunks: u64,
pub decoded_bytes: u64,
pub evictions: u64,
pub resident_bytes: u64,
pub entries: u64,
}
struct Slot {
entry: Arc<CacheEntry>,
seq: AtomicU64,
charge: u64,
}
const PARTS: usize = 64;
#[derive(Default)]
struct Part {
map: RwLock<HashMap<CacheKey, Slot>>,
hits: AtomicU64,
misses: AtomicU64,
}
pub struct ChunkCache {
id: u64,
parts: Box<[Part]>,
resident: AtomicU64,
clock: AtomicU64,
evicting: std::sync::Mutex<()>,
cap: AtomicU64,
decoded_chunks: AtomicU64,
decoded_bytes: AtomicU64,
evictions: AtomicU64,
}
const EXACT_EVICTION_ENTRIES: usize = 64;
const RECENT_SLOTS: usize = 4;
struct Recent {
slots: [Option<(u64, CacheKey, Arc<CacheEntry>)>; RECENT_SLOTS],
next: usize,
}
thread_local! {
static RECENT: std::cell::RefCell<Recent> = const {
std::cell::RefCell::new(Recent {
slots: [None, None, None, None],
next: 0,
})
};
}
static NEXT_CACHE_ID: AtomicU64 = AtomicU64::new(1);
impl std::fmt::Debug for ChunkCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let s = self.stats();
f.debug_struct("ChunkCache")
.field("cap", &self.cap.load(Ordering::Relaxed))
.field("resident_bytes", &s.resident_bytes)
.field("entries", &s.entries)
.finish()
}
}
impl ChunkCache {
pub fn new(cap: u64) -> Self {
ChunkCache {
id: NEXT_CACHE_ID.fetch_add(1, Ordering::Relaxed),
parts: (0..PARTS).map(|_| Part::default()).collect(),
resident: AtomicU64::new(0),
clock: AtomicU64::new(0),
evicting: std::sync::Mutex::new(()),
cap: AtomicU64::new(cap),
decoded_chunks: AtomicU64::new(0),
decoded_bytes: AtomicU64::new(0),
evictions: AtomicU64::new(0),
}
}
fn part(&self, key: CacheKey) -> &Part {
let h = (key.1 as usize).wrapping_mul(0x9E37_79B1) ^ ((key.0 as usize) << 7);
&self.parts[(h >> 8) % PARTS]
}
pub fn unlimited() -> Self {
Self::new(u64::MAX)
}
pub fn unlimited_arc() -> Arc<Self> {
Arc::new(Self::unlimited())
}
pub fn set_cap(&self, cap: u64) {
self.cap.store(cap, Ordering::Relaxed);
self.evict_to_cap();
}
pub fn cap(&self) -> u64 {
self.cap.load(Ordering::Relaxed)
}
pub fn get(&self, key: CacheKey) -> Option<Arc<CacheEntry>> {
let recent = RECENT.with(|r| {
let r = r.try_borrow().ok()?;
r.slots
.iter()
.flatten()
.find(|(id, k, _)| *id == self.id && *k == key)
.map(|(_, _, e)| Arc::clone(e))
});
if recent.is_some() {
return recent;
}
let found = self.get_shared(key);
if let Some(e) = &found {
RECENT.with(|r| {
if let Ok(mut r) = r.try_borrow_mut() {
let at = r.next;
r.slots[at] = Some((self.id, key, Arc::clone(e)));
r.next = (at + 1) % RECENT_SLOTS;
}
});
}
found
}
fn get_shared(&self, key: CacheKey) -> Option<Arc<CacheEntry>> {
let part = self.part(key);
let found = {
let map = part.map.read().unwrap();
map.get(&key).map(|slot| {
let now = self.clock.load(Ordering::Relaxed) + 1;
if slot.seq.load(Ordering::Relaxed) != now {
slot.seq.store(now, Ordering::Relaxed);
}
Arc::clone(&slot.entry)
})
};
match &found {
Some(_) => part.hits.fetch_add(1, Ordering::Relaxed),
None => part.misses.fetch_add(1, Ordering::Relaxed),
};
found
}
pub fn contains(&self, key: CacheKey) -> bool {
self.part(key).map.read().unwrap().contains_key(&key)
}
pub fn insert(&self, key: CacheKey, body: Arc<[u8]>) -> Arc<CacheEntry> {
self.decoded_chunks.fetch_add(1, Ordering::Relaxed);
self.decoded_bytes
.fetch_add(body.len() as u64, Ordering::Relaxed);
let seq = self.clock.fetch_add(1, Ordering::Relaxed) + 1;
let entry = {
let mut map = self.part(key).map.write().unwrap();
if let Some(slot) = map.get(&key) {
slot.seq.store(seq, Ordering::Relaxed);
return Arc::clone(&slot.entry);
}
let entry = Arc::new(CacheEntry {
body,
runs: OnceLock::new(),
dir: OnceLock::new(),
segs: OnceLock::new(),
});
let charge = entry.charge();
map.insert(
key,
Slot {
entry: Arc::clone(&entry),
seq: AtomicU64::new(seq),
charge,
},
);
self.resident.fetch_add(charge, Ordering::Relaxed);
entry
};
self.evict_to_cap();
entry
}
pub fn charge_extra(&self, key: CacheKey, entry: &Arc<CacheEntry>, extra: u64) {
{
let mut map = self.part(key).map.write().unwrap();
let Some(slot) = map.get_mut(&key) else {
return;
};
if !Arc::ptr_eq(&slot.entry, entry) {
return;
}
slot.charge += extra;
self.resident.fetch_add(extra, Ordering::Relaxed);
}
self.evict_to_cap();
}
pub fn get_or_fetch(
&self,
key: CacheKey,
fetch: impl FnOnce() -> Option<Arc<[u8]>>,
) -> Option<Arc<CacheEntry>> {
if let Some(e) = self.get(key) {
return Some(e);
}
let body = fetch()?;
Some(self.insert(key, body))
}
fn evict_to_cap(&self) {
let cap = self.cap.load(Ordering::Relaxed);
if self.resident.load(Ordering::Relaxed) <= cap {
return;
}
let _one = self.evicting.lock().unwrap();
if self.resident.load(Ordering::Relaxed) <= cap {
return;
}
let mut by_age: Vec<(u64, CacheKey)> = Vec::new();
for part in self.parts.iter() {
let map = part.map.read().unwrap();
by_age.extend(
map.iter()
.map(|(k, slot)| (slot.seq.load(Ordering::Relaxed), *k)),
);
}
let target = if by_age.len() > EXACT_EVICTION_ENTRIES {
cap - cap / 32
} else {
cap
};
by_age.sort_unstable();
for (_, key) in by_age {
if self.resident.load(Ordering::Relaxed) <= target {
break;
}
if let Some(slot) = self.part(key).map.write().unwrap().remove(&key) {
self.resident.fetch_sub(slot.charge, Ordering::Relaxed);
self.evictions.fetch_add(1, Ordering::Relaxed);
}
}
}
pub fn stats(&self) -> CacheStats {
let (mut hits, mut misses, mut entries) = (0u64, 0u64, 0u64);
for part in self.parts.iter() {
hits += part.hits.load(Ordering::Relaxed);
misses += part.misses.load(Ordering::Relaxed);
entries += part.map.read().unwrap().len() as u64;
}
CacheStats {
hits,
misses,
decoded_chunks: self.decoded_chunks.load(Ordering::Relaxed),
decoded_bytes: self.decoded_bytes.load(Ordering::Relaxed),
evictions: self.evictions.load(Ordering::Relaxed),
resident_bytes: self.resident.load(Ordering::Relaxed),
entries,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn body(n: usize, fill: u8) -> Arc<[u8]> {
Arc::from(vec![fill; n])
}
fn charge_of(n: u64) -> u64 {
alloc_footprint(n + ARC_HEADER) + ENTRY_OVERHEAD
}
#[test]
fn derived_state_is_charged_and_evicted_with_its_body() {
let one = charge_of(1000);
let cache = ChunkCache::new(2 * one + 10);
let a = cache.insert((0, 1), body(1000, 1));
let b = cache.insert((0, 2), body(1000, 2));
assert_eq!(cache.stats().resident_bytes, 2 * one);
let (dir, built) = b.group_dir(crate::triples::GroupDirectory::empty_for_tests);
assert!(built && dir.is_empty());
let (_, again) = b.group_dir(|| unreachable!("built once"));
assert!(!again);
cache.charge_extra((0, 2), &b, 100);
let st = cache.stats();
assert_eq!(st.entries, 1);
assert_eq!(st.resident_bytes, one + 100);
assert!(cache.get((0, 1)).is_none() && cache.get((0, 2)).is_some());
cache.charge_extra((0, 1), &a, 1 << 20);
cache.charge_extra((0, 2), &a, 1 << 20);
assert_eq!(cache.stats().resident_bytes, one + 100);
}
#[test]
fn a_thread_keeps_the_entries_it_took_last() {
let cache = ChunkCache::new(charge_of(100));
let other = ChunkCache::unlimited();
cache.insert((0, 1), body(100, 1));
let first = cache.get((0, 1)).expect("resident");
cache.insert((0, 2), body(100, 2));
assert!(!cache.contains((0, 1)));
let again = cache.get((0, 1)).expect("remembered by this thread");
assert!(Arc::ptr_eq(&first, &again));
assert!(other.get((0, 1)).is_none(), "another cache, the same key");
std::thread::scope(|s| {
s.spawn(|| assert!(cache.get((0, 1)).is_none()));
});
let wide = ChunkCache::unlimited();
for i in 0..(RECENT_SLOTS as u32 + 1) {
wide.insert((1, i), body(8, i as u8));
assert!(wide.get((1, i)).is_some());
}
assert!(cache.get((0, 1)).is_none(), "pushed out by later entries");
}
#[test]
fn footprint_follows_four_classes_per_doubling() {
assert_eq!(alloc_footprint(1), 16);
assert_eq!(alloc_footprint(64), 64);
assert_eq!(alloc_footprint(65), 80);
assert_eq!(alloc_footprint(65_536), 65_536);
assert_eq!(alloc_footprint(65_537), 81_920);
assert_eq!(alloc_footprint(100_000), 114_688);
for n in [65u64, 1000, 70_000, 1 << 20, 5_000_001] {
let c = alloc_footprint(n);
assert!(c >= n && c - n <= n / 4, "{n} -> {c}");
}
}
#[test]
fn charge_is_the_allocation_class_not_the_length() {
let cache = ChunkCache::unlimited();
cache.insert((0, 0), body(65_600, 1));
assert_eq!(cache.stats().resident_bytes, charge_of(65_600));
assert_eq!(charge_of(65_600), 81_920 + ENTRY_OVERHEAD);
}
#[test]
fn insert_and_get_round_trip() {
let cache = ChunkCache::unlimited();
let e = cache.insert((0, 7), body(32, 0xAB));
assert_eq!(e.body(), &[0xAB; 32]);
let got = cache.get((0, 7)).expect("resident");
assert_eq!(got.body(), &[0xAB; 32]);
assert!(Arc::ptr_eq(&e, &got), "same entry handed out");
assert!(cache.get((0, 8)).is_none(), "absent key misses");
let s = cache.stats();
assert_eq!(s.entries, 1);
assert_eq!(s.evictions, 0);
}
#[test]
fn unlimited_cap_never_evicts() {
let cache = ChunkCache::unlimited();
for i in 0..1000u32 {
cache.insert((1, i), body(4096, i as u8));
}
let s = cache.stats();
assert_eq!(s.entries, 1000, "every insert stays resident");
assert_eq!(s.evictions, 0, "unlimited cap evicts nothing");
for i in 0..1000u32 {
assert!(cache.contains((1, i)), "chunk {i} still resident");
}
}
#[test]
fn arc_stays_valid_across_a_forced_eviction() {
let cache = ChunkCache::new(charge_of(100));
let first = cache.insert((0, 0), body(100, 1));
assert!(cache.contains((0, 0)));
let _second = cache.insert((0, 1), body(100, 2));
assert!(!cache.contains((0, 0)), "LRU key evicted from the map");
assert!(cache.contains((0, 1)), "newest key kept");
assert!(cache.stats().evictions >= 1, "an eviction happened");
assert_eq!(
first.body(),
&[1u8; 100],
"handed-out Arc survives eviction"
);
}
#[test]
fn recency_protects_the_hot_entry() {
let cache = ChunkCache::new(2 * charge_of(100));
cache.insert((0, 0), body(100, 0));
cache.insert((0, 1), body(100, 1));
assert!(cache.get((0, 0)).is_some());
cache.insert((0, 2), body(100, 2)); assert!(cache.contains((0, 0)), "recently used key survives");
assert!(!cache.contains((0, 1)), "LRU key evicted");
assert!(cache.contains((0, 2)), "newest key present");
}
#[test]
fn runs_are_derived_once_and_cached() {
let cache = ChunkCache::unlimited();
let e = cache.insert((0, 0), body(10, 0));
let calls = std::cell::Cell::new(0);
let r1 = e.runs(|_| {
calls.set(calls.get() + 1);
vec![0, 4, 8]
});
assert_eq!(r1, &[0, 4, 8]);
let r2 = e.runs(|_| {
calls.set(calls.get() + 1);
vec![9, 9, 9]
});
assert_eq!(r2, &[0, 4, 8], "cached, not recomputed");
assert_eq!(calls.get(), 1, "compute ran exactly once");
let empty = cache.insert((0, 1), Arc::from(Vec::<u8>::new()));
assert!(empty.runs(|_| vec![1, 2, 3]).is_empty());
}
#[test]
fn get_or_fetch_faults_once_then_hits() {
let cache = ChunkCache::unlimited();
let calls = std::cell::Cell::new(0);
let e1 = cache
.get_or_fetch((2, 5), || {
calls.set(calls.get() + 1);
Some(body(16, 0x11))
})
.unwrap();
assert_eq!(e1.body(), &[0x11; 16]);
let e2 = cache
.get_or_fetch((2, 5), || {
calls.set(calls.get() + 1);
Some(body(16, 0x22))
})
.unwrap();
assert_eq!(e2.body(), &[0x11; 16], "second call hits the cache");
assert_eq!(calls.get(), 1, "fetch ran once");
assert!(cache.get_or_fetch((2, 6), || None).is_none());
assert!(!cache.contains((2, 6)));
}
}