nxs/prefetch/
pattern.rs

1//! Access pattern detector (Adaptive-prefetch-spec §4).
2
3pub const SEQUENTIAL_THRESHOLD: u64 = 10;
4pub const RANDOM_THRESHOLD: u64 = 100;
5pub const MIN_OBSERVATIONS: usize = 8;
6pub const UPGRADE_SEQUENTIAL_THRESHOLD: u32 = 100;
7
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum AccessPattern {
10    Unknown,
11    Sequential,
12    Random,
13    Mixed,
14}
15
16impl AccessPattern {
17    pub fn as_str(self) -> &'static str {
18        match self {
19            Self::Unknown => "unknown",
20            Self::Sequential => "sequential",
21            Self::Random => "random",
22            Self::Mixed => "mixed",
23        }
24    }
25}
26
27/// Observes `record(index)` / seek calls and classifies access patterns.
28#[derive(Debug, Clone)]
29pub struct AccessPatternDetector {
30    sequential_runs: u32,
31    random_jumps: u32,
32    last_index: i64,
33}
34
35impl Default for AccessPatternDetector {
36    fn default() -> Self {
37        Self::new()
38    }
39}
40
41impl AccessPatternDetector {
42    pub fn new() -> Self {
43        Self {
44            sequential_runs: 0,
45            random_jumps: 0,
46            last_index: -1,
47        }
48    }
49
50    pub fn sequential_runs(&self) -> u32 {
51        self.sequential_runs
52    }
53
54    pub fn last_index(&self) -> i64 {
55        self.last_index
56    }
57
58    pub fn observe(&mut self, index: usize) {
59        let idx = index as i64;
60        if self.last_index >= 0 {
61            let delta = idx.abs_diff(self.last_index);
62            if delta <= SEQUENTIAL_THRESHOLD {
63                self.sequential_runs = self.sequential_runs.saturating_add(1);
64            } else if delta > RANDOM_THRESHOLD {
65                self.random_jumps = self.random_jumps.saturating_add(1);
66            }
67        }
68        self.last_index = idx;
69    }
70
71    pub fn pattern(&self) -> AccessPattern {
72        let total = self.sequential_runs + self.random_jumps;
73        if (total as usize) < MIN_OBSERVATIONS {
74            return AccessPattern::Unknown;
75        }
76        if self.sequential_runs > self.random_jumps.saturating_mul(3) {
77            AccessPattern::Sequential
78        } else if self.random_jumps > self.sequential_runs {
79            AccessPattern::Random
80        } else {
81            AccessPattern::Mixed
82        }
83    }
84
85    /// Predicted next record indices when pattern is sequential (§4.4).
86    pub fn predict_next(&self, depth: usize, record_count: usize) -> Vec<usize> {
87        if self.pattern() != AccessPattern::Sequential || self.last_index < 0 {
88            return Vec::new();
89        }
90        let start = self.last_index as usize + 1;
91        (0..depth)
92            .filter_map(|i| {
93                let idx = start + i;
94                if idx < record_count {
95                    Some(idx)
96                } else {
97                    None
98                }
99            })
100            .collect()
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn pattern_unknown_until_min_observations() {
110        let mut d = AccessPatternDetector::new();
111        for i in 0..8 {
112            d.observe(i);
113        }
114        assert_eq!(d.pattern(), AccessPattern::Unknown);
115        d.observe(8);
116        assert_ne!(d.pattern(), AccessPattern::Unknown);
117    }
118
119    #[test]
120    fn pattern_sequential_small_deltas() {
121        let mut d = AccessPatternDetector::new();
122        for i in 0..20 {
123            d.observe(i);
124        }
125        assert_eq!(d.pattern(), AccessPattern::Sequential);
126    }
127
128    #[test]
129    fn pattern_random_large_jumps() {
130        let mut d = AccessPatternDetector::new();
131        for i in 0..8 {
132            d.observe(i);
133        }
134        for j in (0..12).map(|k| k * 200) {
135            d.observe(j);
136        }
137        assert_eq!(d.pattern(), AccessPattern::Random);
138    }
139
140    #[test]
141    fn predict_next_sequential() {
142        let mut d = AccessPatternDetector::new();
143        for i in 0..10 {
144            d.observe(i);
145        }
146        assert_eq!(d.predict_next(4, 100), vec![10, 11, 12, 13]);
147    }
148}
nxs/prefetch/pattern.rs

nxs/prefetch/
pattern.rs
