xlog_cuda_tests/harness/
validators.rs

1//! CPU reference implementations for validating GPU results.
2
3/// CPU reference implementations for all kernel operations.
4pub mod reference {
5    use std::collections::HashMap;
6
7    use xlog_core::f64_total_order_key;
8
9    /// Hash join returning (left_idx, right_idx) pairs.
10    pub fn hash_join_u32(left: &[u32], right: &[u32]) -> Vec<(usize, usize)> {
11        let mut result = Vec::new();
12        let right_map: HashMap<u32, Vec<usize>> =
13            right
14                .iter()
15                .enumerate()
16                .fold(HashMap::new(), |mut acc, (idx, val)| {
17                    acc.entry(*val).or_default().push(idx);
18                    acc
19                });
20
21        for (left_idx, left_val) in left.iter().enumerate() {
22            if let Some(right_indices) = right_map.get(left_val) {
23                for &right_idx in right_indices {
24                    result.push((left_idx, right_idx));
25                }
26            }
27        }
28        result
29    }
30
31    /// Multi-column hash join.
32    pub fn hash_join_multi(left_cols: &[&[u32]], right_cols: &[&[u32]]) -> Vec<(usize, usize)> {
33        if left_cols.is_empty() || right_cols.is_empty() {
34            return Vec::new();
35        }
36
37        let left_len = left_cols[0].len();
38        let right_len = right_cols[0].len();
39
40        // Build hash map on right side
41        let mut right_map: HashMap<Vec<u32>, Vec<usize>> = HashMap::new();
42        for i in 0..right_len {
43            let key: Vec<u32> = right_cols.iter().map(|col| col[i]).collect();
44            right_map.entry(key).or_default().push(i);
45        }
46
47        // Probe with left side
48        let mut result = Vec::new();
49        for i in 0..left_len {
50            let key: Vec<u32> = left_cols.iter().map(|col| col[i]).collect();
51            if let Some(right_indices) = right_map.get(&key) {
52                for &right_idx in right_indices {
53                    result.push((i, right_idx));
54                }
55            }
56        }
57        result
58    }
59
60    /// Semi join - returns left indices that have a match in right.
61    pub fn semi_join_u32(left: &[u32], right: &[u32]) -> Vec<usize> {
62        let right_set: std::collections::HashSet<u32> = right.iter().copied().collect();
63        left.iter()
64            .enumerate()
65            .filter(|(_, val)| right_set.contains(val))
66            .map(|(idx, _)| idx)
67            .collect()
68    }
69
70    /// Anti join - returns left indices that have NO match in right.
71    pub fn anti_join_u32(left: &[u32], right: &[u32]) -> Vec<usize> {
72        let right_set: std::collections::HashSet<u32> = right.iter().copied().collect();
73        left.iter()
74            .enumerate()
75            .filter(|(_, val)| !right_set.contains(val))
76            .map(|(idx, _)| idx)
77            .collect()
78    }
79
80    /// Filter by comparison operation.
81    pub fn filter_compare_u32(data: &[u32], op: CompareOp, val: u32) -> Vec<usize> {
82        data.iter()
83            .enumerate()
84            .filter(|(_, d)| op.apply(**d, val))
85            .map(|(idx, _)| idx)
86            .collect()
87    }
88
89    /// Filter by comparison operation for i64.
90    pub fn filter_compare_i64(data: &[i64], op: CompareOp, val: i64) -> Vec<usize> {
91        data.iter()
92            .enumerate()
93            .filter(|(_, d)| op.apply(**d, val))
94            .map(|(idx, _)| idx)
95            .collect()
96    }
97
98    /// Filter by comparison operation for f64.
99    pub fn filter_compare_f64(data: &[f64], op: CompareOp, val: f64) -> Vec<f64> {
100        data.iter()
101            .filter(|d| op.apply_f64(**d, val))
102            .copied()
103            .collect()
104    }
105
106    /// Compact by mask.
107    pub fn compact_by_mask<T: Copy>(data: &[T], mask: &[u8]) -> Vec<T> {
108        data.iter()
109            .zip(mask.iter())
110            .filter(|(_, m)| **m != 0)
111            .map(|(d, _)| *d)
112            .collect()
113    }
114
115    /// Stable radix sort returning (sorted_data, permutation).
116    pub fn radix_sort_u32(keys: &[u32]) -> (Vec<u32>, Vec<u32>) {
117        let mut indexed: Vec<(u32, u32)> = keys
118            .iter()
119            .enumerate()
120            .map(|(i, &k)| (k, i as u32))
121            .collect();
122
123        // Stable sort
124        indexed.sort_by_key(|(k, _)| *k);
125
126        let sorted: Vec<u32> = indexed.iter().map(|(k, _)| *k).collect();
127        let perm: Vec<u32> = indexed.iter().map(|(_, i)| *i).collect();
128
129        (sorted, perm)
130    }
131
132    /// Apply permutation to data.
133    pub fn apply_permutation<T: Copy>(data: &[T], perm: &[u32]) -> Vec<T> {
134        perm.iter().map(|&i| data[i as usize]).collect()
135    }
136
137    /// Inclusive prefix sum.
138    pub fn inclusive_scan(data: &[u32]) -> Vec<u32> {
139        let mut result = Vec::with_capacity(data.len());
140        let mut sum = 0u32;
141        for &val in data {
142            sum = sum.wrapping_add(val);
143            result.push(sum);
144        }
145        result
146    }
147
148    /// Exclusive prefix sum.
149    pub fn exclusive_scan(data: &[u32]) -> Vec<u32> {
150        let mut result = Vec::with_capacity(data.len());
151        let mut sum = 0u32;
152        for &val in data {
153            result.push(sum);
154            sum = sum.wrapping_add(val);
155        }
156        result
157    }
158
159    /// Group by count (assumes sorted input).
160    pub fn groupby_count_sorted(keys: &[u32]) -> Vec<(u32, u64)> {
161        if keys.is_empty() {
162            return Vec::new();
163        }
164
165        let mut result = Vec::new();
166        let mut current_key = keys[0];
167        let mut count = 1u64;
168
169        for &key in &keys[1..] {
170            if key == current_key {
171                count += 1;
172            } else {
173                result.push((current_key, count));
174                current_key = key;
175                count = 1;
176            }
177        }
178        result.push((current_key, count));
179        result
180    }
181
182    /// Group by sum (assumes sorted input).
183    pub fn groupby_sum_sorted(keys: &[u32], vals: &[u32]) -> Vec<(u32, u64)> {
184        if keys.is_empty() {
185            return Vec::new();
186        }
187
188        let mut result = Vec::new();
189        let mut current_key = keys[0];
190        let mut sum = vals[0] as u64;
191
192        for i in 1..keys.len() {
193            if keys[i] == current_key {
194                sum += vals[i] as u64;
195            } else {
196                result.push((current_key, sum));
197                current_key = keys[i];
198                sum = vals[i] as u64;
199            }
200        }
201        result.push((current_key, sum));
202        result
203    }
204
205    /// Group by min (assumes sorted input).
206    pub fn groupby_min_sorted(keys: &[u32], vals: &[u32]) -> Vec<(u32, u32)> {
207        if keys.is_empty() {
208            return Vec::new();
209        }
210
211        let mut result = Vec::new();
212        let mut current_key = keys[0];
213        let mut min_val = vals[0];
214
215        for i in 1..keys.len() {
216            if keys[i] == current_key {
217                min_val = min_val.min(vals[i]);
218            } else {
219                result.push((current_key, min_val));
220                current_key = keys[i];
221                min_val = vals[i];
222            }
223        }
224        result.push((current_key, min_val));
225        result
226    }
227
228    /// Group by max (assumes sorted input).
229    pub fn groupby_max_sorted(keys: &[u32], vals: &[u32]) -> Vec<(u32, u32)> {
230        if keys.is_empty() {
231            return Vec::new();
232        }
233
234        let mut result = Vec::new();
235        let mut current_key = keys[0];
236        let mut max_val = vals[0];
237
238        for i in 1..keys.len() {
239            if keys[i] == current_key {
240                max_val = max_val.max(vals[i]);
241            } else {
242                result.push((current_key, max_val));
243                current_key = keys[i];
244                max_val = vals[i];
245            }
246        }
247        result.push((current_key, max_val));
248        result
249    }
250
251    /// Dedup sorted data.
252    pub fn dedup_sorted<T: Eq + Copy>(data: &[T]) -> Vec<T> {
253        if data.is_empty() {
254            return Vec::new();
255        }
256
257        let mut result = vec![data[0]];
258        for &val in &data[1..] {
259            if val != *result.last().unwrap() {
260                result.push(val);
261            }
262        }
263        result
264    }
265
266    /// Mark duplicates in sorted data (true = unique, false = duplicate).
267    pub fn mark_duplicates<T: Eq>(sorted: &[T]) -> Vec<bool> {
268        if sorted.is_empty() {
269            return Vec::new();
270        }
271
272        let mut result = vec![true]; // First element is always unique
273        for i in 1..sorted.len() {
274            result.push(sorted[i] != sorted[i - 1]);
275        }
276        result
277    }
278
279    /// Sorted set union.
280    pub fn sorted_union<T: Ord + Copy>(a: &[T], b: &[T]) -> Vec<T> {
281        let mut result = Vec::new();
282        let mut i = 0;
283        let mut j = 0;
284
285        while i < a.len() && j < b.len() {
286            if a[i] < b[j] {
287                if result.last() != Some(&a[i]) {
288                    result.push(a[i]);
289                }
290                i += 1;
291            } else if a[i] > b[j] {
292                if result.last() != Some(&b[j]) {
293                    result.push(b[j]);
294                }
295                j += 1;
296            } else {
297                if result.last() != Some(&a[i]) {
298                    result.push(a[i]);
299                }
300                i += 1;
301                j += 1;
302            }
303        }
304
305        while i < a.len() {
306            if result.last() != Some(&a[i]) {
307                result.push(a[i]);
308            }
309            i += 1;
310        }
311
312        while j < b.len() {
313            if result.last() != Some(&b[j]) {
314                result.push(b[j]);
315            }
316            j += 1;
317        }
318
319        result
320    }
321
322    /// Sorted set difference (a - b).
323    pub fn sorted_diff<T: Ord + Copy>(a: &[T], b: &[T]) -> Vec<T> {
324        let mut result = Vec::new();
325        let mut i = 0;
326        let mut j = 0;
327
328        while i < a.len() && j < b.len() {
329            if a[i] < b[j] {
330                result.push(a[i]);
331                i += 1;
332            } else if a[i] > b[j] {
333                j += 1;
334            } else {
335                i += 1;
336                j += 1;
337            }
338        }
339
340        while i < a.len() {
341            result.push(a[i]);
342            i += 1;
343        }
344
345        result
346    }
347
348    /// Pack columns into row-major byte array.
349    pub fn pack_keys(cols: &[&[u8]], col_sizes: &[usize], num_rows: usize) -> Vec<u8> {
350        let row_size: usize = col_sizes.iter().sum();
351        let mut result = vec![0u8; row_size * num_rows];
352
353        for row in 0..num_rows {
354            let mut offset = 0;
355            for (col_idx, &col_size) in col_sizes.iter().enumerate() {
356                let src_start = row * col_size;
357                let src_end = src_start + col_size;
358                let dst_start = row * row_size + offset;
359                let dst_end = dst_start + col_size;
360                result[dst_start..dst_end].copy_from_slice(&cols[col_idx][src_start..src_end]);
361                offset += col_size;
362            }
363        }
364        result
365    }
366
367    /// FNV-1a hash.
368    pub fn hash_fnv1a(data: &[u8]) -> u32 {
369        const FNV_PRIME: u32 = 16777619;
370        const FNV_OFFSET: u32 = 2166136261;
371
372        let mut hash = FNV_OFFSET;
373        for &byte in data {
374            hash ^= byte as u32;
375            hash = hash.wrapping_mul(FNV_PRIME);
376        }
377        hash
378    }
379
380    /// Unpack a column from packed rows.
381    pub fn unpack_column(
382        packed: &[u8],
383        row_size: usize,
384        col_offset: usize,
385        col_size: usize,
386        num_rows: usize,
387    ) -> Vec<u8> {
388        let mut result = vec![0u8; col_size * num_rows];
389
390        for row in 0..num_rows {
391            let src_start = row * row_size + col_offset;
392            let src_end = src_start + col_size;
393            let dst_start = row * col_size;
394            let dst_end = dst_start + col_size;
395            result[dst_start..dst_end].copy_from_slice(&packed[src_start..src_end]);
396        }
397        result
398    }
399
400    /// Comparison operation enum.
401    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
402    pub enum CompareOp {
403        Eq,
404        Ne,
405        Lt,
406        Le,
407        Gt,
408        Ge,
409    }
410
411    impl CompareOp {
412        pub fn apply<T: PartialOrd>(&self, a: T, b: T) -> bool {
413            match self {
414                CompareOp::Eq => a == b,
415                CompareOp::Ne => a != b,
416                CompareOp::Lt => a < b,
417                CompareOp::Le => a <= b,
418                CompareOp::Gt => a > b,
419                CompareOp::Ge => a >= b,
420            }
421        }
422
423        pub fn apply_f64(&self, a: f64, b: f64) -> bool {
424            let a = f64_total_order_key(a);
425            let b = f64_total_order_key(b);
426            match self {
427                CompareOp::Eq => a == b,
428                CompareOp::Ne => a != b,
429                CompareOp::Lt => a < b,
430                CompareOp::Le => a <= b,
431                CompareOp::Gt => a > b,
432                CompareOp::Ge => a >= b,
433            }
434        }
435    }
436}
437
438/// Comparison utilities for GPU vs CPU result validation.
439pub mod compare {
440    /// Assert u32 slices are equal with detailed diff on failure.
441    pub fn assert_eq_u32(gpu: &[u32], cpu: &[u32], context: &str) {
442        if gpu.len() != cpu.len() {
443            panic!(
444                "{}: length mismatch: GPU={}, CPU={}",
445                context,
446                gpu.len(),
447                cpu.len()
448            );
449        }
450
451        let mut first_diff = None;
452        let mut diff_count = 0;
453
454        for (i, (g, c)) in gpu.iter().zip(cpu.iter()).enumerate() {
455            if g != c {
456                if first_diff.is_none() {
457                    first_diff = Some((i, *g, *c));
458                }
459                diff_count += 1;
460            }
461        }
462
463        if let Some((idx, gpu_val, cpu_val)) = first_diff {
464            panic!(
465                "{}: {} differences found. First at index {}: GPU={}, CPU={}",
466                context, diff_count, idx, gpu_val, cpu_val
467            );
468        }
469    }
470
471    /// Assert i64 slices are equal with detailed diff on failure.
472    pub fn assert_eq_i64(gpu: &[i64], cpu: &[i64], context: &str) {
473        if gpu.len() != cpu.len() {
474            panic!(
475                "{}: length mismatch: GPU={}, CPU={}",
476                context,
477                gpu.len(),
478                cpu.len()
479            );
480        }
481
482        let mut first_diff = None;
483        let mut diff_count = 0;
484
485        for (i, (g, c)) in gpu.iter().zip(cpu.iter()).enumerate() {
486            if g != c {
487                if first_diff.is_none() {
488                    first_diff = Some((i, *g, *c));
489                }
490                diff_count += 1;
491            }
492        }
493
494        if let Some((idx, gpu_val, cpu_val)) = first_diff {
495            panic!(
496                "{}: {} differences found. First at index {}: GPU={}, CPU={}",
497                context, diff_count, idx, gpu_val, cpu_val
498            );
499        }
500    }
501
502    /// Assert u64 slices are equal with detailed diff on failure.
503    pub fn assert_eq_u64(gpu: &[u64], cpu: &[u64], context: &str) {
504        if gpu.len() != cpu.len() {
505            panic!(
506                "{}: length mismatch: GPU={}, CPU={}",
507                context,
508                gpu.len(),
509                cpu.len()
510            );
511        }
512
513        let mut first_diff = None;
514        let mut diff_count = 0;
515
516        for (i, (g, c)) in gpu.iter().zip(cpu.iter()).enumerate() {
517            if g != c {
518                if first_diff.is_none() {
519                    first_diff = Some((i, *g, *c));
520                }
521                diff_count += 1;
522            }
523        }
524
525        if let Some((idx, gpu_val, cpu_val)) = first_diff {
526            panic!(
527                "{}: {} differences found. First at index {}: GPU={}, CPU={}",
528                context, diff_count, idx, gpu_val, cpu_val
529            );
530        }
531    }
532
533    /// Assert f64 slices are equal within ULP tolerance.
534    pub fn assert_eq_f64_ulp(gpu: &[f64], cpu: &[f64], max_ulp: u64, context: &str) {
535        if gpu.len() != cpu.len() {
536            panic!(
537                "{}: length mismatch: GPU={}, CPU={}",
538                context,
539                gpu.len(),
540                cpu.len()
541            );
542        }
543
544        let mut first_diff = None;
545        let mut diff_count = 0;
546
547        for (i, (g, c)) in gpu.iter().zip(cpu.iter()).enumerate() {
548            let ulp_diff = ulp_distance(*g, *c);
549            if ulp_diff > max_ulp {
550                if first_diff.is_none() {
551                    first_diff = Some((i, *g, *c, ulp_diff));
552                }
553                diff_count += 1;
554            }
555        }
556
557        if let Some((idx, gpu_val, cpu_val, ulp)) = first_diff {
558            panic!(
559                "{}: {} ULP violations (max={}). First at index {}: GPU={}, CPU={}, ULP={}",
560                context, diff_count, max_ulp, idx, gpu_val, cpu_val, ulp
561            );
562        }
563    }
564
565    /// Assert f64 slices are equal within relative tolerance.
566    pub fn assert_eq_f64_rel(gpu: &[f64], cpu: &[f64], rel_tol: f64, context: &str) {
567        if gpu.len() != cpu.len() {
568            panic!(
569                "{}: length mismatch: GPU={}, CPU={}",
570                context,
571                gpu.len(),
572                cpu.len()
573            );
574        }
575
576        let mut first_diff = None;
577        let mut diff_count = 0;
578
579        for (i, (g, c)) in gpu.iter().zip(cpu.iter()).enumerate() {
580            let rel_diff = if *c == 0.0 {
581                g.abs()
582            } else {
583                ((g - c) / c).abs()
584            };
585
586            if rel_diff > rel_tol && !g.is_nan() && !c.is_nan() {
587                if first_diff.is_none() {
588                    first_diff = Some((i, *g, *c, rel_diff));
589                }
590                diff_count += 1;
591            }
592        }
593
594        if let Some((idx, gpu_val, cpu_val, rel)) = first_diff {
595            panic!(
596                "{}: {} relative tolerance violations (max={}). First at index {}: GPU={}, CPU={}, rel_diff={}",
597                context, diff_count, rel_tol, idx, gpu_val, cpu_val, rel
598            );
599        }
600    }
601
602    /// Compute ULP distance between two f64 values.
603    fn ulp_distance(a: f64, b: f64) -> u64 {
604        if a.is_nan() || b.is_nan() {
605            return u64::MAX;
606        }
607        if a == b {
608            return 0;
609        }
610        if a.is_infinite() || b.is_infinite() {
611            return u64::MAX;
612        }
613
614        let a_bits = a.to_bits() as i64;
615        let b_bits = b.to_bits() as i64;
616
617        (a_bits - b_bits).unsigned_abs()
618    }
619
620    /// Assert sets are equal (order-independent).
621    pub fn assert_set_eq_u32(gpu: &[u32], cpu: &[u32], context: &str) {
622        let mut gpu_sorted = gpu.to_vec();
623        let mut cpu_sorted = cpu.to_vec();
624        gpu_sorted.sort();
625        cpu_sorted.sort();
626
627        if gpu_sorted != cpu_sorted {
628            panic!(
629                "{}: set mismatch. GPU (sorted): {:?}, CPU (sorted): {:?}",
630                context,
631                &gpu_sorted[..gpu_sorted.len().min(10)],
632                &cpu_sorted[..cpu_sorted.len().min(10)]
633            );
634        }
635    }
636
637    /// Assert permutation is valid.
638    pub fn assert_valid_permutation(perm: &[u32], len: usize, context: &str) {
639        if perm.len() != len {
640            panic!(
641                "{}: permutation length {} != expected {}",
642                context,
643                perm.len(),
644                len
645            );
646        }
647
648        let mut seen = vec![false; len];
649        for (i, &idx) in perm.iter().enumerate() {
650            if idx as usize >= len {
651                panic!(
652                    "{}: permutation index {} out of bounds at position {}",
653                    context, idx, i
654                );
655            }
656            if seen[idx as usize] {
657                panic!(
658                    "{}: duplicate permutation index {} at position {}",
659                    context, idx, i
660                );
661            }
662            seen[idx as usize] = true;
663        }
664    }
665
666    /// Assert sort is stable (equal keys maintain relative order).
667    pub fn assert_stable_sort(
668        original_keys: &[u32],
669        original_vals: &[u32],
670        sorted_keys: &[u32],
671        sorted_vals: &[u32],
672        context: &str,
673    ) {
674        // Group by key in original order
675        let mut key_to_vals: std::collections::HashMap<u32, Vec<u32>> =
676            std::collections::HashMap::new();
677        for (&k, &v) in original_keys.iter().zip(original_vals.iter()) {
678            key_to_vals.entry(k).or_default().push(v);
679        }
680
681        // Check sorted result maintains relative order within each key group
682        let mut key_to_idx: std::collections::HashMap<u32, usize> =
683            std::collections::HashMap::new();
684        for (&k, &v) in sorted_keys.iter().zip(sorted_vals.iter()) {
685            let idx = key_to_idx.entry(k).or_insert(0);
686            let expected_vals = key_to_vals.get(&k).unwrap();
687            if *idx >= expected_vals.len() {
688                panic!("{}: too many values for key {}", context, k);
689            }
690            if v != expected_vals[*idx] {
691                panic!(
692                    "{}: stability violation for key {}. Expected value {} but got {}",
693                    context, k, expected_vals[*idx], v
694                );
695            }
696            *idx += 1;
697        }
698    }
699
700    /// Check if result is sorted.
701    pub fn is_sorted_u32(data: &[u32]) -> bool {
702        data.windows(2).all(|w| w[0] <= w[1])
703    }
704
705    /// Check if result is sorted descending.
706    pub fn is_sorted_desc_u32(data: &[u32]) -> bool {
707        data.windows(2).all(|w| w[0] >= w[1])
708    }
709}
xlog_cuda_tests/harness/validators.rs

xlog_cuda_tests/harness/
validators.rs
