Skip to main content

qualia_core_db/query/graph_accel/
cpu.rs

1//! CPU floors — always present, never broken. GPU paths must match these results
2//! (permutation of equal keys may differ; join pairs are compared as sets).
3
4use crate::NQuin;
5
6/// LSD radix sort of `items` by `key`. Unstable. Exact for all `u64` keys.
7pub 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
29/// Sort `indices` so `keys[indices[i]]` is non-decreasing. `indices` must be a
30/// permutation of `0..keys.len()` (caller may pass identity).
31pub 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
66/// CPU sort by object.
67pub fn sort_quins_by_object_cpu(quins: &mut [NQuin]) {
68    radix_sort_by_key(quins, |q| q.object);
69}
70
71/// Compact Quins whose `field` equals `needle`. Returns count written to `out`.
72pub 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
86/// Write matching *indices* (not Quins) into `out`.
87pub 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    /// `QuinField::get`.
119    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
130/// Sort-merge join on `u64` keys. Writes `(probe_idx, build_idx)` pairs.
131/// Equal keys emit the cartesian product, fail-closed when `out` fills
132/// (returns the count written; caller sees truncation if count == out.len()
133/// and more matches exist — use a larger buffer).
134pub 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
145/// Merges two sorted pair lists.
146pub 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}