cleep 0.1.0

Clocksweep Cache implementation in Rust
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

/// A key type that can be stored and looked up in a cache slot array.
pub trait CacheKey: Copy + PartialEq {
    const GUARD: Self;

    fn find_key<const CAP: usize>(keys: &[Self; CAP], key: &Self) -> Option<usize>;
}

/// A value type that can be stored in a cache slot.
pub trait CacheValue: Copy + Default {}
impl<T> CacheValue for T where T: Copy + Default {}

#[cfg(feature = "nightly_simd")]
use std::simd::prelude::*;

#[cfg(feature = "nightly_simd")]
macro_rules! impl_simd_cache_key {
    ($( ($t:ty, $lanes:expr) ),*) => {
        $(
            impl $crate::kv::CacheKey for $t {
                const GUARD: Self = <$t>::MAX;

                #[inline(always)]
                fn find_key<const CAP: usize>(keys: &[Self; CAP], key: &Self) -> Option<usize> {
                    const LANES: usize = $lanes;

                    let target = Simd::<Self, LANES>::splat(*key);
                    let mut chunks = keys.chunks_exact(LANES);
                    let mut base = 0;

                    for chunk in chunks.by_ref() {
                        let data = Simd::from_slice(chunk);
                        let mask = data.simd_eq(target);

                        if mask.any() {
                            return Some(base + mask.first_set().unwrap());
                        }

                        base += LANES;
                    }

                    for (i, &k) in chunks.remainder().iter().enumerate() {
                        if k == *key {
                            return Some(base + i);
                        }
                    }

                    None
                }
            }
        )*
    };
}

#[cfg(feature = "nightly_simd")]
impl_simd_cache_key!(
    (usize, 4),
    (isize, 4),
    (f64, 4),
    (u64, 4),
    (i64, 4),
    (f32, 8),
    (u32, 8),
    (i32, 8),
    (u16, 16),
    (i16, 16),
    (u8, 32),
    (i8, 32)
);

#[cfg(not(feature = "nightly_simd"))]
macro_rules! impl_default_cache_key {
    ($( ($t:ty, $guard:expr) ),*) => {
        $(
            impl $crate::kv::CacheKey for $t {
                const GUARD: Self = $guard;

                #[inline(always)]
                fn find_key<const CAP: usize>(keys: &[Self; CAP], key: &Self) -> Option<usize> {
                    let mut chunks = keys.chunks_exact(16);
                    let mut base = 0;

                    for chunk in chunks.by_ref() {
                        if chunk[0] == *key { return Some(base); }
                        if chunk[1] == *key { return Some(base + 1); }
                        if chunk[2] == *key { return Some(base + 2); }
                        if chunk[3] == *key { return Some(base + 3); }
                        if chunk[4] == *key { return Some(base + 4); }
                        if chunk[5] == *key { return Some(base + 5); }
                        if chunk[6] == *key { return Some(base + 6); }
                        if chunk[7] == *key { return Some(base + 7); }
                        if chunk[8] == *key { return Some(base + 8); }
                        if chunk[9] == *key { return Some(base + 9); }
                        if chunk[10] == *key { return Some(base + 10); }
                        if chunk[11] == *key { return Some(base + 11); }
                        if chunk[12] == *key { return Some(base + 12); }
                        if chunk[13] == *key {return Some(base + 13); }
                        if chunk[14] == *key { return Some(base + 14); }
                        if chunk[15] == *key { return Some(base + 15); }
                        base += 16;
                    }

                    for (i, &k) in chunks.remainder().iter().enumerate() {
                        if k == *key {
                            return Some(base + i);
                        }
                    }

                    None
                }
            }
        )*
    };
}

#[cfg(not(feature = "nightly_simd"))]
impl_default_cache_key!(
    (f32, f32::MAX),
    (f64, f64::MAX),
    (usize, usize::MAX),
    (isize, isize::MAX),
    (u64, u64::MAX),
    (i64, i64::MAX),
    (u32, u32::MAX),
    (i32, i32::MAX),
    (u16, u16::MAX),
    (i16, i16::MAX),
    (u8, u8::MAX),
    (i8, i8::MAX)
);