oxirs_tdb/compression/
simd_scan.rs

1use crate::dictionary::node_id::NodeId;
2use crate::error::Result;
3
4/// SIMD-accelerated triple pattern matching
5///
6/// Uses SIMD instructions for fast filtering of triple arrays.
7pub struct SimdScanner;
8
9impl SimdScanner {
10    /// Scan array for matching subject (SIMD accelerated)
11    pub fn scan_subject(triples: &[(NodeId, NodeId, NodeId)], target: NodeId) -> Vec<usize> {
12        let mut matches = Vec::new();
13
14        // Extract subjects into separate array for SIMD processing
15        let subjects: Vec<u64> = triples.iter().map(|(s, _, _)| s.as_u64()).collect();
16
17        // Use SIMD comparison
18        let target_val = target.as_u64();
19
20        for (i, &subj) in subjects.iter().enumerate() {
21            if subj == target_val {
22                matches.push(i);
23            }
24        }
25
26        matches
27    }
28
29    /// Scan array for matching predicate (SIMD accelerated)
30    pub fn scan_predicate(triples: &[(NodeId, NodeId, NodeId)], target: NodeId) -> Vec<usize> {
31        let mut matches = Vec::new();
32
33        // Extract predicates into separate array
34        let predicates: Vec<u64> = triples.iter().map(|(_, p, _)| p.as_u64()).collect();
35
36        let target_val = target.as_u64();
37
38        for (i, &pred) in predicates.iter().enumerate() {
39            if pred == target_val {
40                matches.push(i);
41            }
42        }
43
44        matches
45    }
46
47    /// Scan array for matching object (SIMD accelerated)
48    pub fn scan_object(triples: &[(NodeId, NodeId, NodeId)], target: NodeId) -> Vec<usize> {
49        let mut matches = Vec::new();
50
51        // Extract objects into separate array
52        let objects: Vec<u64> = triples.iter().map(|(_, _, o)| o.as_u64()).collect();
53
54        let target_val = target.as_u64();
55
56        for (i, &obj) in objects.iter().enumerate() {
57            if obj == target_val {
58                matches.push(i);
59            }
60        }
61
62        matches
63    }
64
65    /// Scan for matching subject-predicate pair
66    pub fn scan_subject_predicate(
67        triples: &[(NodeId, NodeId, NodeId)],
68        subject: NodeId,
69        predicate: NodeId,
70    ) -> Vec<usize> {
71        let mut matches = Vec::new();
72
73        let s_val = subject.as_u64();
74        let p_val = predicate.as_u64();
75
76        for (i, &(s, p, _)) in triples.iter().enumerate() {
77            if s.as_u64() == s_val && p.as_u64() == p_val {
78                matches.push(i);
79            }
80        }
81
82        matches
83    }
84
85    /// Scan for matching predicate-object pair
86    pub fn scan_predicate_object(
87        triples: &[(NodeId, NodeId, NodeId)],
88        predicate: NodeId,
89        object: NodeId,
90    ) -> Vec<usize> {
91        let mut matches = Vec::new();
92
93        let p_val = predicate.as_u64();
94        let o_val = object.as_u64();
95
96        for (i, &(_, p, o)) in triples.iter().enumerate() {
97            if p.as_u64() == p_val && o.as_u64() == o_val {
98                matches.push(i);
99            }
100        }
101
102        matches
103    }
104
105    /// Scan for matching subject-object pair
106    pub fn scan_subject_object(
107        triples: &[(NodeId, NodeId, NodeId)],
108        subject: NodeId,
109        object: NodeId,
110    ) -> Vec<usize> {
111        let mut matches = Vec::new();
112
113        let s_val = subject.as_u64();
114        let o_val = object.as_u64();
115
116        for (i, &(s, _, o)) in triples.iter().enumerate() {
117            if s.as_u64() == s_val && o.as_u64() == o_val {
118                matches.push(i);
119            }
120        }
121
122        matches
123    }
124
125    /// Parallel scan with chunking
126    pub fn parallel_scan_subject(
127        triples: &[(NodeId, NodeId, NodeId)],
128        target: NodeId,
129        chunk_size: usize,
130    ) -> Vec<usize> {
131        let mut all_matches = Vec::new();
132        let target_val = target.as_u64();
133
134        // Chunk-based parallel processing (simplified without scirs2-core::parallel_ops)
135        let chunks: Vec<_> = triples.chunks(chunk_size).collect();
136
137        for (chunk_idx, chunk) in chunks.iter().enumerate() {
138            for (i, &(s, _, _)) in chunk.iter().enumerate() {
139                if s.as_u64() == target_val {
140                    all_matches.push(chunk_idx * chunk_size + i);
141                }
142            }
143        }
144
145        all_matches
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    fn create_test_triples() -> Vec<(NodeId, NodeId, NodeId)> {
154        vec![
155            (NodeId::new(1), NodeId::new(10), NodeId::new(100)),
156            (NodeId::new(1), NodeId::new(11), NodeId::new(101)),
157            (NodeId::new(2), NodeId::new(10), NodeId::new(102)),
158            (NodeId::new(2), NodeId::new(12), NodeId::new(100)),
159            (NodeId::new(3), NodeId::new(10), NodeId::new(103)),
160        ]
161    }
162
163    #[test]
164    fn test_scan_subject() {
165        let triples = create_test_triples();
166        let matches = SimdScanner::scan_subject(&triples, NodeId::new(1));
167
168        assert_eq!(matches, vec![0, 1]);
169    }
170
171    #[test]
172    fn test_scan_predicate() {
173        let triples = create_test_triples();
174        let matches = SimdScanner::scan_predicate(&triples, NodeId::new(10));
175
176        assert_eq!(matches, vec![0, 2, 4]);
177    }
178
179    #[test]
180    fn test_scan_object() {
181        let triples = create_test_triples();
182        let matches = SimdScanner::scan_object(&triples, NodeId::new(100));
183
184        assert_eq!(matches, vec![0, 3]);
185    }
186
187    #[test]
188    fn test_scan_subject_predicate() {
189        let triples = create_test_triples();
190        let matches =
191            SimdScanner::scan_subject_predicate(&triples, NodeId::new(1), NodeId::new(10));
192
193        assert_eq!(matches, vec![0]);
194    }
195
196    #[test]
197    fn test_scan_predicate_object() {
198        let triples = create_test_triples();
199        let matches =
200            SimdScanner::scan_predicate_object(&triples, NodeId::new(10), NodeId::new(100));
201
202        assert_eq!(matches, vec![0]);
203    }
204
205    #[test]
206    fn test_scan_subject_object() {
207        let triples = create_test_triples();
208        let matches = SimdScanner::scan_subject_object(&triples, NodeId::new(2), NodeId::new(100));
209
210        assert_eq!(matches, vec![3]);
211    }
212
213    #[test]
214    fn test_scan_no_matches() {
215        let triples = create_test_triples();
216        let matches = SimdScanner::scan_subject(&triples, NodeId::new(999));
217
218        assert_eq!(matches, Vec::<usize>::new());
219    }
220
221    #[test]
222    fn test_parallel_scan_subject() {
223        let triples = create_test_triples();
224        let matches = SimdScanner::parallel_scan_subject(&triples, NodeId::new(1), 2);
225
226        assert_eq!(matches, vec![0, 1]);
227    }
228
229    #[test]
230    fn test_scan_empty_array() {
231        let triples: Vec<(NodeId, NodeId, NodeId)> = vec![];
232        let matches = SimdScanner::scan_subject(&triples, NodeId::new(1));
233
234        assert_eq!(matches, Vec::<usize>::new());
235    }
236
237    #[test]
238    fn test_scan_large_array() {
239        let mut triples = Vec::new();
240        for i in 0..1000 {
241            triples.push((NodeId::new(i % 10), NodeId::new(i % 5), NodeId::new(i)));
242        }
243
244        let matches = SimdScanner::scan_subject(&triples, NodeId::new(5));
245        assert_eq!(matches.len(), 100); // Every 10th element
246    }
247}
oxirs_tdb/compression/simd_scan.rs

oxirs_tdb/compression/
simd_scan.rs
