dualcache-ff 1.0.1

A wait-free, high-performance concurrent cache optimized for extreme read-to-write ratios.
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
50
51
52
53
54
55
56
57
58
59

use crate::componant::slot::Slot;
use ::core::sync::atomic::Ordering;

pub trait EvictionPolicy: Send + Sync {
    fn find_victim<'a, K, V>(&self, set: &'a [Slot<K, V>], hash: usize) -> &'a Slot<K, V>;
}

/// The default Pseudo-LFU with Ring-Clock decay policy from v0.2.0
pub struct DefaultEvictionPolicy;

impl DefaultEvictionPolicy {
    pub const fn new() -> Self {
        Self
    }
}

impl Default for DefaultEvictionPolicy {
    fn default() -> Self {
        Self::new()
    }
}

impl EvictionPolicy for DefaultEvictionPolicy {
    #[inline(always)]
    fn find_victim<'a, K, V>(&self, set: &'a [Slot<K, V>], hash: usize) -> &'a Slot<K, V> {
        let mut min_hits = u16::MAX;
        let mut candidates = [0; 8]; // Assumes WAYS is at most 8
        let mut candidates_len = 0;
        
        for (i, slot) in set.iter().enumerate() {
            let hits = slot.hits.load(Ordering::Relaxed);
            if hits < min_hits {
                min_hits = hits;
                candidates_len = 0;
                candidates[candidates_len] = i;
                candidates_len += 1;
            } else if hits == min_hits && candidates_len < 8 {
                candidates[candidates_len] = i;
                candidates_len += 1;
            }
        }

        let victim_idx = if candidates_len > 1 {
            candidates[hash % candidates_len]
        } else {
            candidates[0]
        };

        // Clock-like decay
        if min_hits > 0 {
            for slot in set {
                let h = slot.hits.load(Ordering::Relaxed);
                slot.hits.store(h.saturating_sub(1), Ordering::Relaxed);
            }
        }

        unsafe { set.get_unchecked(victim_idx) }
    }
}