sassi 0.1.0-beta.1

Typed in-memory pool with composable predicate algebra and cross-runtime trait queries.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

//! Sampled eviction helpers for snapshot L1 state.

// Task 12A lands the substrate before Task 12B starts consuming it.
#![allow(dead_code)]

use crate::cacheable::Cacheable;
use crate::punnu::state::L1State;

pub(crate) const SAMPLE_SIZE: usize = 5;

/// Choose the lowest-access-epoch id from a random sample.
pub(crate) fn choose_sampled_lru_victim<T: Cacheable>(
    state: &L1State<T>,
    rng: &mut fastrand::Rng,
) -> Option<T::Id> {
    if state.is_empty() {
        return None;
    }

    let sample_size = state.len().min(SAMPLE_SIZE);
    let mut indices = Vec::with_capacity(sample_size);
    while indices.len() < sample_size {
        let index = rng.usize(..state.len());
        if !indices.contains(&index) {
            indices.push(index);
        }
    }

    let mut victim = None;
    let mut victim_epoch = u64::MAX;

    for index in indices {
        let id = state
            .keys
            .get(index)
            .expect("L1State invariant violated: sampled index missing");
        let entry = state
            .get(id)
            .expect("L1State invariant violated: sampled key missing entry");
        let epoch = entry.access_epoch();

        if victim.is_none() || epoch < victim_epoch {
            victim = Some(id.clone());
            victim_epoch = epoch;
        }
    }

    victim
}