qualia_core_db/query/graph_accel/
cpu.rs1use crate::NQuin;
5
6pub fn radix_sort_by_key<T, F>(items: &mut [T], mut key: F)
8where
9 T: Copy,
10 F: FnMut(&T) -> u64,
11{
12 let n = items.len();
13 if n < 2 {
14 return;
15 }
16 let keys: Vec<u64> = items.iter().map(|t| key(t)).collect();
17 let mut idx: Vec<u32> = (0..n as u32).collect();
18 radix_sort_u64_indices(&keys, &mut idx);
19 let mut out = Vec::with_capacity(n);
20 let mut out_keys = Vec::with_capacity(n);
21 for &i in &idx {
22 out.push(items[i as usize]);
23 out_keys.push(keys[i as usize]);
24 }
25 items.copy_from_slice(&out);
26 let _ = out_keys;
27}
28
29pub fn radix_sort_u64_indices(keys: &[u64], indices: &mut [u32]) {
32 let n = keys.len();
33 debug_assert_eq!(n, indices.len());
34 if n < 2 {
35 return;
36 }
37 let mut src_idx = indices.to_vec();
38 let mut dst_idx = vec![0u32; n];
39 let mut src_key: Vec<u64> = src_idx.iter().map(|&i| keys[i as usize]).collect();
40 let mut dst_key = vec![0u64; n];
41 for shift in (0..64).step_by(8) {
42 let mut hist = [0u32; 256];
43 for &k in &src_key {
44 hist[((k >> shift) & 0xff) as usize] += 1;
45 }
46 let mut sum = 0u32;
47 for bin in &mut hist {
48 let c = *bin;
49 *bin = sum;
50 sum += c;
51 }
52 for i in 0..n {
53 let k = src_key[i];
54 let d = ((k >> shift) & 0xff) as usize;
55 let pos = hist[d] as usize;
56 hist[d] += 1;
57 dst_key[pos] = k;
58 dst_idx[pos] = src_idx[i];
59 }
60 std::mem::swap(&mut src_key, &mut dst_key);
61 std::mem::swap(&mut src_idx, &mut dst_idx);
62 }
63 indices.copy_from_slice(&src_idx);
64}
65
66pub fn sort_quins_by_object_cpu(quins: &mut [NQuin]) {
68 radix_sort_by_key(quins, |q| q.object);
69}
70
71pub fn sieve_eq_cpu(quins: &[NQuin], field: QuinField, needle: u64, out: &mut [NQuin]) -> usize {
73 let mut n = 0;
74 for q in quins {
75 if field.get(q) == needle {
76 if n >= out.len() {
77 break;
78 }
79 out[n] = *q;
80 n += 1;
81 }
82 }
83 n
84}
85
86pub fn sieve_eq_indices_cpu(
88 quins: &[NQuin],
89 field: QuinField,
90 needle: u64,
91 out: &mut [u32],
92) -> usize {
93 let mut n = 0;
94 for (i, q) in quins.iter().enumerate() {
95 if field.get(q) == needle {
96 if n >= out.len() {
97 break;
98 }
99 out[n] = i as u32;
100 n += 1;
101 }
102 }
103 n
104}
105
106#[derive(Debug, Clone, Copy, PartialEq, Eq)]
107#[repr(u32)]
108pub enum QuinField {
109 Subject = 0,
110 Predicate = 1,
111 Object = 2,
112 Context = 3,
113 Metadata = 4,
114}
115
116impl QuinField {
117 #[inline]
118 pub fn get(self, q: &NQuin) -> u64 {
120 match self {
121 Self::Subject => q.subject,
122 Self::Predicate => q.predicate,
123 Self::Object => q.object,
124 Self::Context => q.context,
125 Self::Metadata => q.metadata,
126 }
127 }
128}
129
130pub fn sort_merge_join_u64(build: &[u64], probe: &[u64], out: &mut [(u32, u32)]) -> usize {
135 if build.is_empty() || probe.is_empty() || out.is_empty() {
136 return 0;
137 }
138 let mut b_idx: Vec<u32> = (0..build.len() as u32).collect();
139 let mut p_idx: Vec<u32> = (0..probe.len() as u32).collect();
140 radix_sort_u64_indices(build, &mut b_idx);
141 radix_sort_u64_indices(probe, &mut p_idx);
142 merge_sorted_pairs(build, probe, &b_idx, &p_idx, out)
143}
144
145pub fn merge_sorted_pairs(
147 build: &[u64],
148 probe: &[u64],
149 b_idx: &[u32],
150 p_idx: &[u32],
151 out: &mut [(u32, u32)],
152) -> usize {
153 let mut i = 0usize;
154 let mut j = 0usize;
155 let mut n = 0usize;
156 while i < b_idx.len() && j < p_idx.len() && n < out.len() {
157 let bk = build[b_idx[i] as usize];
158 let pk = probe[p_idx[j] as usize];
159 match bk.cmp(&pk) {
160 std::cmp::Ordering::Less => i += 1,
161 std::cmp::Ordering::Greater => j += 1,
162 std::cmp::Ordering::Equal => {
163 let mut i2 = i;
164 while i2 < b_idx.len() && build[b_idx[i2] as usize] == bk {
165 i2 += 1;
166 }
167 let mut j2 = j;
168 while j2 < p_idx.len() && probe[p_idx[j2] as usize] == pk {
169 j2 += 1;
170 }
171 for &bi in &b_idx[i..i2] {
172 for &pj in &p_idx[j..j2] {
173 if n >= out.len() {
174 return n;
175 }
176 out[n] = (pj, bi);
177 n += 1;
178 }
179 }
180 i = i2;
181 j = j2;
182 }
183 }
184 }
185 n
186}