use std::collections::HashMap;
use super::*;
const LIMITS: Limits = Limits {
budget: 100,
ceiling: 200,
};
#[derive(Default)]
struct Frames {
misses: Vec<Vec<u64>>,
uncached: Vec<Vec<u64>>,
evicted: Vec<u64>,
}
impl Frames {
fn draw(&mut self, cache: &mut FrameCache<u64>, keys: impl IntoIterator<Item = u64>, bytes: usize) {
let (mut misses, mut uncached) = (Vec::new(), Vec::new());
for key in keys {
if cache.get(key).is_some() {
continue;
}
misses.push(key);
if cache.insert(key, key, bytes, |value| self.evicted.push(value)).is_err() {
uncached.push(key);
}
}
cache.close_frame(|value| self.evicted.push(value));
self.misses.push(misses);
self.uncached.push(uncached);
}
}
#[test]
fn a_frame_larger_than_the_budget_is_kept_whole_from_the_second_frame() {
let mut cache = FrameCache::framed(LIMITS);
let mut frames = Frames::default();
for _ in 0..5 {
frames.draw(&mut cache, 0..15, 10);
}
assert_eq!(frames.misses[0], (0..15).collect::<Vec<_>>());
assert!(frames.misses[1..].iter().all(Vec::is_empty), "{:?}", frames.misses);
assert!(frames.evicted.is_empty());
assert_eq!((cache.len(), cache.bytes()), (15, 150));
}
#[test]
fn below_the_budget_nothing_is_evicted() {
let mut cache = FrameCache::framed(LIMITS);
let mut frames = Frames::default();
for frame in 0..6u64 {
frames.draw(&mut cache, (0..10).filter(|key| (key + frame) % 3 != 0), 10);
}
assert!(frames.evicted.is_empty());
assert_eq!(cache.bytes(), 100);
assert!(frames.misses[3..].iter().all(Vec::is_empty));
}
#[test]
fn beyond_the_ceiling_the_overflow_is_not_cached_and_the_rest_stays() {
let mut cache = FrameCache::framed(LIMITS);
let mut frames = Frames::default();
for _ in 0..5 {
frames.draw(&mut cache, 0..30, 10);
}
let overflow: Vec<_> = (20..30).collect();
assert_eq!(frames.uncached, vec![overflow.clone(); 5]);
assert!(
frames.misses[1..].iter().all(|misses| *misses == overflow),
"the 20 cached entries stay cached: {:?}",
frames.misses
);
assert!(frames.evicted.is_empty(), "nothing thrashes: {:?}", frames.evicted);
assert_eq!((cache.len(), cache.bytes()), (20, 200));
}
#[test]
fn the_cache_returns_to_its_budget_once_frames_need_less() {
let mut cache = FrameCache::framed(LIMITS);
let mut frames = Frames::default();
frames.draw(&mut cache, 0..15, 10);
assert_eq!(cache.bytes(), 150);
frames.draw(&mut cache, 0..2, 10);
assert_eq!(cache.bytes(), 150, "entries of the previous frame stay");
frames.draw(&mut cache, 0..2, 10);
assert_eq!(cache.bytes(), 100);
assert_eq!(frames.evicted, (2..7).collect::<Vec<_>>(), "oldest first");
for _ in 0..3 {
cache.close_frame(|value| frames.evicted.push(value));
}
assert_eq!(frames.evicted.len(), 5);
frames.draw(&mut cache, 0..2, 10);
assert!(frames.misses[3].is_empty());
}
#[test]
fn eviction_never_takes_an_entry_of_the_current_or_previous_frame_and_stays_bounded() {
let mut cache = FrameCache::framed(LIMITS);
let mut used: HashMap<u64, usize> = HashMap::new();
let mut charged: HashMap<u64, usize> = HashMap::new();
let mut random = 0x2545_f491_4f6c_dd1du64;
let mut next = |bound: u64| {
random ^= random << 13;
random ^= random >> 7;
random ^= random << 17;
random % bound
};
for frame in 2..400usize {
let start = next(60);
let count = 1 + next(25);
for key in start..start + count {
used.insert(key, frame);
if cache.get(key).is_some() {
continue;
}
let bytes = 1 + (key as usize * 7) % 13;
let mut evicted = Vec::new();
let kept = cache.insert(key, key, bytes, |value| evicted.push(value)).is_ok();
for value in evicted {
assert!(
used[&value] + 1 < frame,
"frame {frame} evicted {value}, used in {}",
used[&value]
);
charged.remove(&value);
}
if kept {
charged.insert(key, bytes);
}
assert!(cache.bytes() <= LIMITS.ceiling);
}
let mut evicted = Vec::new();
cache.close_frame(|value| evicted.push(value));
for value in evicted {
assert!(
used[&value] + 1 < frame,
"closing {frame} evicted {value}, used in {}",
used[&value]
);
charged.remove(&value);
}
assert_eq!(cache.bytes(), charged.values().sum::<usize>());
let recent: usize = charged
.iter()
.filter(|(key, _)| used[*key] + 1 >= frame)
.map(|(_, b)| b)
.sum();
assert!(
cache.bytes() <= LIMITS.budget.max(recent),
"frame {frame}: {} bytes",
cache.bytes()
);
}
}
#[test]
fn before_its_first_frame_closes_the_cache_is_lru_within_the_budget() {
let mut cache = FrameCache::new(LIMITS);
let mut evicted = Vec::new();
for key in 0..10 {
cache.insert(key, key, 10, |value| evicted.push(value)).unwrap();
}
assert!(cache.get(0).is_some());
cache.insert(10, 10, 10, |value| evicted.push(value)).unwrap();
cache.insert(11, 11, 10, |value| evicted.push(value)).unwrap();
assert_eq!(evicted, [1, 2], "least recently used first, never above the budget");
assert!(cache.insert(12, 12, 101, |value| evicted.push(value)).is_err());
assert_eq!(cache.bytes(), 100);
}
#[test]
fn a_replaced_key_hands_its_old_value_to_evict() {
let mut cache = FrameCache::framed(LIMITS);
let mut evicted = Vec::new();
cache.insert(1, 10, 10, |value| evicted.push(value)).unwrap();
cache.insert(1, 11, 20, |value| evicted.push(value)).unwrap();
assert_eq!(evicted, [10]);
assert_eq!((cache.peek(1), cache.bytes()), (Some(&11), 20));
}
#[test]
fn the_access_queue_stays_proportional_to_the_entries() {
let mut cache = FrameCache::framed(LIMITS);
for frame in 0..1000 {
for key in 0..8 {
if cache.get(key).is_none() {
cache.insert(key, frame, 10, drop).unwrap();
}
}
cache.close_frame(drop);
}
assert!(cache.order.len() <= 2 * cache.len() + 64);
}