diff --git a/Cargo.toml b/Cargo.toml index c559f5856..fe4cb67e4 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -73,6 +73,7 @@ pest_derive = "2" [target.'cfg(not(target_arch = "wasm32"))'.dev-dependencies] tempfile = "3" criterion = { version = "0.8", features = ["html_reports"] } +wide = "0.7" [target.'cfg(all(target_arch = "wasm32", not(target_os = "wasi")))'.dev-dependencies] wasm-bindgen-test = "0.3" diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index 5936ff60c..813d859d0 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -19,7 +19,10 @@ mod helpers; -use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main}; +#[cfg(not(target_arch = "wasm32"))] +mod simd_helpers; + +use criterion::{BenchmarkId, Criterion, Throughput, black_box, criterion_group, criterion_main}; use minigraf::OpenOptions; // ── Task 3: insert/ ─────────────────────────────────────────────────────────── @@ -1537,6 +1540,117 @@ fn bench_predicate_pushdown(c: &mut Criterion) { group.finish(); } +// ── SIMD kernel benchmarks (Issue #229) ────────────────────────────────────── +// +// Both scalar and SIMD variants operate on synthetic Vec/Vec data. +// Fact internals (valid_from, valid_to, tx_count) are pub(crate) and unavailable +// from bench code; benchmarks isolate the hot loop rather than the full query path. +// Cross-reference the existing time_travel/ and aggregation/ groups for full-query costs. + +fn bench_simd(c: &mut Criterion) { + const SCALES: &[(&str, usize)] = &[ + ("100", 100), + ("1k", 1_000), + ("10k", 10_000), + ("100k", 100_000), + ("1m", 1_000_000), + ]; + + // ── simd_temporal: valid-time range filter ────────────────────────────── + // + // Synthetic data: valid_from[i] = i, valid_to[i] = i + n/2. + // ts = n/4 → ~50% of facts are valid at ts (those with valid_from ≤ n/4 < valid_to). + { + let mut group = c.benchmark_group("simd_temporal"); + group.sample_size(10); + + for &(label, n) in SCALES { + let n_i64 = i64::try_from(n).unwrap_or(i64::MAX); + let valid_from: Vec = (0_i64..n_i64).collect(); + let valid_to: Vec = valid_from.iter().map(|&vf| vf + n_i64 / 2).collect(); + let ts = n_i64 / 4; + + group.bench_with_input(BenchmarkId::new("scalar", label), &n, |b, _| { + b.iter(|| { + valid_from + .iter() + .zip(valid_to.iter()) + .filter(|&(&vf, &vt)| vf <= black_box(ts) && black_box(ts) < vt) + .count() + }) + }); + + group.bench_with_input(BenchmarkId::new("simd", label), &n, |b, _| { + b.iter(|| { + simd_helpers::valid_time_filter_simd( + black_box(&valid_from), + black_box(&valid_to), + black_box(ts), + ) + }) + }); + } + + group.finish(); + } + + // ── simd_as_of: tx-time as-of filter ─────────────────────────────────── + // + // Synthetic data: tx_counts = 1..=n (monotonic counter). + // threshold = n/2 → 50% of facts pass the filter. + { + let mut group = c.benchmark_group("simd_as_of"); + group.sample_size(10); + + for &(label, n) in SCALES { + let n_u64 = u64::try_from(n).unwrap_or(u64::MAX); + let tx_counts: Vec = (1..=n_u64).collect(); + let threshold = n_u64 / 2; + + group.bench_with_input(BenchmarkId::new("scalar", label), &n, |b, _| { + b.iter(|| { + tx_counts + .iter() + .filter(|&&tc| tc <= black_box(threshold)) + .count() + }) + }); + + group.bench_with_input(BenchmarkId::new("simd", label), &n, |b, _| { + b.iter(|| { + simd_helpers::as_of_filter_simd(black_box(&tx_counts), black_box(threshold)) + }) + }); + } + + group.finish(); + } + + // ── simd_aggregate: i64 horizontal sum ───────────────────────────────── + // + // Synthetic data: values = 0..n as i64. + // Measures horizontal reduction performance. + { + let mut group = c.benchmark_group("simd_aggregate"); + group.sample_size(10); + + for &(label, n) in SCALES { + let n_i64 = i64::try_from(n).unwrap_or(i64::MAX); + let values: Vec = (0_i64..n_i64).collect(); + + group.bench_with_input(BenchmarkId::new("scalar", label), &n, |b, _| { + b.iter(|| black_box(&values).iter().copied().sum::()) + }); + + group.bench_with_input(BenchmarkId::new("simd", label), &n, |b, _| { + b.iter(|| simd_helpers::sum_simd_i64(black_box(&values))) + }); + } + + group.finish(); + } +} + criterion_group!( benches, bench_insert, @@ -1562,5 +1676,6 @@ criterion_group!( bench_retract, bench_btree_lookup, bench_predicate_pushdown, + bench_simd, // Issue #229 ); criterion_main!(benches); diff --git a/benches/simd_helpers.rs b/benches/simd_helpers.rs new file mode 100644 index 000000000..fe0ec174f --- /dev/null +++ b/benches/simd_helpers.rs @@ -0,0 +1,224 @@ +//! SIMD kernel benchmarks for issue #229. +//! +//! All three functions operate on pre-extracted numeric slices. +//! `Fact` internals are `pub(crate)` and unavailable from bench code; +//! benchmarks use synthetic data to isolate the hot loop. +//! +//! `wide` API notes (verified against wide 0.7.33 source): +//! - `i64x4::new([a, b, c, d])` — construct from array +//! - `i64x4::splat(v)` — broadcast scalar to all lanes +//! - `a.cmp_gt(b)` — i64x4 mask: all-bits-1 (= -1) where a > b, 0 elsewhere +//! - `a.cmp_lt(b)` — i64x4 mask: all-bits-1 where a < b, 0 elsewhere +//! - `!mask` — bitwise NOT (flips -1↔0) +//! - `a.move_mask()` — i32 bitmask of sign bits; non-zero lane = matched +//! - `a.to_array()` — extract [i64; 4] lanes +//! - `u64x4` (not u64x2) is the 4-wide unsigned-64 type; no move_mask, use to_array + +#![allow(clippy::cast_possible_truncation)] // synthetic bench data: N ≤ 1M fits in i64 +#![allow(clippy::cast_sign_loss)] // tx_count cast: monotonic counter, always positive + +use wide::{CmpGt, i64x4, u64x4}; + +/// Count facts where `valid_from[i] <= ts && ts < valid_to[i]`. +/// +/// Processes 4 facts per SIMD step using `i64x4`. Scalar tail handles remainder. +/// Both slices must be the same length. +pub fn valid_time_filter_simd(valid_from: &[i64], valid_to: &[i64], ts: i64) -> usize { + let ts_v = i64x4::splat(ts); + let mut count = 0usize; + + for (vf_chunk, vt_chunk) in valid_from.chunks_exact(4).zip(valid_to.chunks_exact(4)) { + let [vf0, vf1, vf2, vf3] = *vf_chunk else { + unreachable!() + }; + let [vt0, vt1, vt2, vt3] = *vt_chunk else { + unreachable!() + }; + + let vf = i64x4::new([vf0, vf1, vf2, vf3]); + let vt = i64x4::new([vt0, vt1, vt2, vt3]); + + // vf <= ts ≡ NOT (vf > ts) + let lo = !vf.cmp_gt(ts_v); + // ts < vt ≡ vt > ts + let hi = vt.cmp_gt(ts_v); + let mask = lo & hi; + + // move_mask sets bit i if lane i has its sign bit set (i.e. value is -1) + count += mask.move_mask().count_ones() as usize; + } + + let rem = (valid_from.len() / 4) * 4; + for (&vf, &vt) in valid_from + .get(rem..) + .unwrap_or(&[]) + .iter() + .zip(valid_to.get(rem..).unwrap_or(&[]).iter()) + { + if vf <= ts && ts < vt { + count += 1; + } + } + + count +} + +/// Count facts where `tx_counts[i] <= threshold`. +/// +/// Processes 4 facts per SIMD step using `u64x4`. +/// Scalar tail handles remainder. +pub fn as_of_filter_simd(tx_counts: &[u64], threshold: u64) -> usize { + let thr_v = u64x4::splat(threshold); + let mut count = 0usize; + + for chunk in tx_counts.chunks_exact(4) { + let [a, b, c, d] = *chunk else { unreachable!() }; + let v = u64x4::new([a, b, c, d]); + + // tc <= threshold ≡ NOT (tc > threshold) + // cmp_gt gives u64::MAX where true, 0 where false + // !mask gives u64::MAX where tc <= threshold, 0 elsewhere + let mask = !v.cmp_gt(thr_v); + let arr: [u64; 4] = mask.to_array(); + count += arr.iter().filter(|&&x| x != 0).count(); + } + + let rem = (tx_counts.len() / 4) * 4; + for &tc in tx_counts.get(rem..).unwrap_or(&[]) { + if tc <= threshold { + count += 1; + } + } + + count +} + +/// Sum all values using `i64x4` horizontal reduction. +/// +/// Accumulates 4 lanes in parallel; reduces to scalar at the end. +/// Wrapping arithmetic matches Rust's default release-mode overflow behaviour. +pub fn sum_simd_i64(values: &[i64]) -> i64 { + let mut acc = i64x4::splat(0_i64); + + for chunk in values.chunks_exact(4) { + let [a, b, c, d] = *chunk else { unreachable!() }; + acc = acc + i64x4::new([a, b, c, d]); + } + + let lanes: [i64; 4] = acc.to_array(); + let mut sum: i64 = lanes.iter().fold(0_i64, |acc, &x| acc.wrapping_add(x)); + + let rem = (values.len() / 4) * 4; + for &v in values.get(rem..).unwrap_or(&[]) { + sum = sum.wrapping_add(v); + } + + sum +} + +#[cfg(test)] +mod tests { + use super::*; + + // ── valid_time_filter_simd ──────────────────────────────────────────────── + + #[test] + fn test_valid_time_filter_matches_scalar_partial() { + // 6 facts (non-multiple of 4 to exercise tail path) + // valid window: [i, i + 3]; ts = 2; facts 0,1,2 pass, facts 3,4,5 fail + let valid_from: Vec = (0_i64..6).collect(); + let valid_to: Vec = valid_from.iter().map(|&vf| vf + 3).collect(); + let ts = 2_i64; + + let scalar = valid_from + .iter() + .zip(valid_to.iter()) + .filter(|&(&vf, &vt)| vf <= ts && ts < vt) + .count(); + + assert_eq!(valid_time_filter_simd(&valid_from, &valid_to, ts), scalar); + } + + #[test] + fn test_valid_time_filter_matches_scalar_exact_chunk() { + // 8 facts (exactly two SIMD chunks) + let valid_from: Vec = (0_i64..8).collect(); + let valid_to: Vec = valid_from.iter().map(|&vf| vf + 4).collect(); + let ts = 3_i64; + + let scalar = valid_from + .iter() + .zip(valid_to.iter()) + .filter(|&(&vf, &vt)| vf <= ts && ts < vt) + .count(); + + assert_eq!(valid_time_filter_simd(&valid_from, &valid_to, ts), scalar); + } + + #[test] + fn test_valid_time_filter_empty() { + assert_eq!(valid_time_filter_simd(&[], &[], 0), 0); + } + + // ── as_of_filter_simd ───────────────────────────────────────────────────── + + #[test] + fn test_as_of_filter_matches_scalar_partial() { + // 9 tx_counts (non-multiple of 4 to exercise tail) + let tx_counts: Vec = (1..=9).collect(); + let threshold = 5_u64; + + let scalar = tx_counts.iter().filter(|&&tc| tc <= threshold).count(); + + assert_eq!(as_of_filter_simd(&tx_counts, threshold), scalar); + } + + #[test] + fn test_as_of_filter_matches_scalar_exact_chunk() { + // 10 tx_counts (exercises two 4-wide chunks + 2 scalar tail) + let tx_counts: Vec = (1..=10).collect(); + let threshold = 7_u64; + + let scalar = tx_counts.iter().filter(|&&tc| tc <= threshold).count(); + + assert_eq!(as_of_filter_simd(&tx_counts, threshold), scalar); + } + + #[test] + fn test_as_of_filter_empty() { + assert_eq!(as_of_filter_simd(&[], 100), 0); + } + + // ── sum_simd_i64 ────────────────────────────────────────────────────────── + + #[test] + fn test_sum_simd_matches_scalar_partial() { + // 9 values (non-multiple of 4 to exercise tail) + let values: Vec = (1_i64..=9).collect(); + let scalar: i64 = values.iter().sum(); + + assert_eq!(sum_simd_i64(&values), scalar); + } + + #[test] + fn test_sum_simd_matches_scalar_exact_chunk() { + // 8 values (exactly two 4-wide chunks) + let values: Vec = (1_i64..=8).collect(); + let scalar: i64 = values.iter().sum(); + + assert_eq!(sum_simd_i64(&values), scalar); + } + + #[test] + fn test_sum_simd_empty() { + assert_eq!(sum_simd_i64(&[]), 0); + } + + #[test] + fn test_sum_simd_negatives() { + let values = vec![-3_i64, -2, -1, 0, 1, 2, 3]; + let scalar: i64 = values.iter().sum(); + + assert_eq!(sum_simd_i64(&values), scalar); + } +} diff --git a/docs/simd-analysis.md b/docs/simd-analysis.md new file mode 100644 index 000000000..5fbbe8b6a --- /dev/null +++ b/docs/simd-analysis.md @@ -0,0 +1,113 @@ +# SIMD Benchmarking Analysis (Issue #229) + +**Date:** 2026-05-16 +**Environment:** Intel Core i7-1065G7 @ 1.30GHz (Ice Lake, SSE4.2/AVX2/AVX512), Linux 6.12.85-1-MANJARO, rustc 1.94.0 (4a4ef493e 2026-03-02), wide 0.7.33 +**Branch:** feature/issue-229-simd-benchmarking + +--- + +## Method + +Both scalar and SIMD benchmarks operate on synthetic numeric slices (not live DB facts — `Fact` internals are `pub(crate)`). The benchmarks isolate the hot kernel loop; extraction overhead is identical for both paths (none). For full-query costs, see the `time_travel/` group results below. + +Three benchmark groups: +- **`simd_temporal`** — valid-time range filter: `valid_from[i] <= ts && ts < valid_to[i]`, ~50% selectivity +- **`simd_as_of`** — tx-time as-of filter: `tx_count[i] <= threshold`, 50% selectivity, using `u64x4` +- **`simd_aggregate`** — i64 horizontal sum via `i64x4` 4-wide reduction + +All sizes: 100, 1k, 10k, 100k, 1M elements. Criterion 10-sample runs, bench profile (LTO enabled). + +--- + +## Results: simd_temporal (valid-time range filter) + +`valid_from[i] <= ts && ts < valid_to[i]` — ~50% selectivity + +| Size | Scalar (ns) | SIMD (ns) | Speedup (scalar/simd) | +|--------|------------|-----------|----------------------| +| 100 | 92.9 | 126.5 | 0.73x (SIMD slower) | +| 1k | 670.9 | 1,092.6 | 0.61x (SIMD slower) | +| 10k | 7,439.8 | 10,856.0 | 0.69x (SIMD slower) | +| 100k | 73,833 | 108,850 | 0.68x (SIMD slower) | +| 1M | 860,100 | 1,175,500 | 0.73x (SIMD slower) | + +**Crossover point:** None observed at any tested size. Scalar is consistently ~30–40% faster than SIMD across all sizes. + +**Analysis:** The range filter (`valid_from[i] <= ts && ts < valid_to[i]`) involves two `i64` comparisons per element. LLVM autovectorization (enabled via `lto = true` in the bench profile) already vectorizes the scalar iterator effectively. The `wide` crate's `i64x4` path introduces overhead — likely from the count-matches bookkeeping (the benchmark counts passing elements to prevent dead-code elimination) — that outweighs the SIMD lane benefit. + +--- + +## Results: simd_as_of (tx-time as-of filter) + +`tx_count[i] <= threshold` — 50% selectivity. Uses `u64x4` (wide 0.7 `u64x4`). + +| Size | Scalar (ns) | SIMD (ns) | Speedup (scalar/simd) | +|--------|------------|-----------|----------------------| +| 100 | 54.3 | 100.7 | 0.54x (SIMD slower) | +| 1k | 464.6 | 894.2 | 0.52x (SIMD slower) | +| 10k | 4,680.9 | 8,855.0 | 0.53x (SIMD slower) | +| 100k | 46,367 | 88,418 | 0.52x (SIMD slower) | +| 1M | 611,000 | 980,130 | 0.62x (SIMD slower) | + +**Crossover point:** None observed at any tested size. Scalar is consistently ~50% faster than SIMD across all sizes. + +**Analysis:** The single-comparison filter (`tx_count[i] <= threshold`) is the simplest possible loop body. LLVM autovectorizes this aggressively. The `u64x4` path from the `wide` crate is consistently 1.9x slower than scalar — indicating the abstraction overhead of the `wide` API exceeds the SIMD lane gain for this operation on this architecture. + +--- + +## Results: simd_aggregate (i64 horizontal sum) + +Sum of N `i64` values via `i64x4` 4-wide reduction. + +| Size | Scalar (ns) | SIMD (ns) | Speedup (scalar/simd) | +|--------|------------|-----------|----------------------| +| 100 | 47.3 | 21.8 | **2.17x** | +| 1k | 419.9 | 151.5 | **2.77x** | +| 10k | 4,125.9 | 1,538.4 | **2.68x** | +| 100k | 40,863 | 16,507 | **2.47x** | +| 1M | 493,980 | 256,820 | **1.92x** | + +**Crossover point:** SIMD wins at all tested sizes (100 through 1M). The speedup is consistent and significant — approximately 2–2.8x across the range. + +**Analysis:** Horizontal sum is where SIMD excels. The `i64x4` reduction performs 4 additions per cycle vs 1 for scalar. LLVM's autovectorizer does not fully capture the same gain here because the horizontal reduction pattern is harder to autovectorize than a simple comparison filter. The `wide` crate's explicit SIMD path achieves a reliable 2–2.8x improvement at all practical sizes. + +--- + +## Post-#208 Residual Analysis + +After the B+Tree selective lookup introduced in #208, queries with bound entity or entity+attribute patterns route through index-backed lookups rather than full fact scans. This significantly reduces the number of facts reaching the temporal filter: + +- **Selective lookup queries** (entity or entity+attribute bound): residual fact counts are typically O(attributes per entity) or O(facts per entity+attribute), often 1–100 facts. At these sizes, the temporal filter benchmarks show scalar is already sub-microsecond — SIMD overhead would make things worse. +- **Unbound queries** (full scans): all N facts reach the temporal filter. These are the cases where SIMD temporal filtering would theoretically help, but the benchmark results show scalar autovectorization already wins. +- **Aggregate queries** (e.g., summing numeric values across many facts): the `simd_aggregate` results are directly applicable. A 2–2.8x improvement in the summation kernel is achievable when aggregate operations are applied to large result sets. + +The practical conclusion: for the current array-of-structs `Fact` storage layout, SIMD temporal filtering is not beneficial. SIMD aggregation is beneficial but requires extracting numeric values into a contiguous slice first — an O(N) copy that partially offsets the gain. + +--- + +## Full-Query Context + +From `time_travel/as_of_counter` and `time_travel/valid_at` (full Minigraf query stack, including parsing, transaction overhead, and fact materialization): + +| Benchmark | 1k facts | 10k facts | 100k facts | 1M facts | +|------------------------------------|------------|------------|------------|------------| +| `time_travel/as_of_counter` | 867.1 µs | 9.99 ms | 109.3 ms | 1,729 ms | +| `time_travel/valid_at` | 1,194 µs | 12.60 ms | 108.5 ms | 356.9 ms | + +The full-query cost is orders of magnitude above the raw filter kernel. For example, the `simd_as_of` scalar kernel at 10k facts takes 4.7 µs, but the full `as_of_counter` query at 10k facts costs ~10 ms — a 2000x overhead from transaction, parsing, and fact materialization layers. This confirms that optimizing the filter kernel alone would have negligible impact on end-to-end query latency. + +--- + +## Recommendation + +**Skip (filter kernels) / Revisit with SoA layout (aggregates).** + +**For temporal filtering (`simd_temporal`, `simd_as_of`):** SIMD is slower than scalar at all tested sizes (100 to 1M). LLVM autovectorization with `lto = true` already captures the available vectorization opportunity in the scalar iterator path. Integrating the `wide`-based filter helpers into production code would be a net regression. Recommend closing the filter SIMD work in #229 without further action. + +**For aggregation (`simd_aggregate`):** SIMD wins at all sizes with a consistent 2–2.8x improvement. However, the current array-of-structs `Fact` storage layout means that reaching the `i64` values requires either: +1. An O(N) extraction pass to build a contiguous slice (partially negating the gain), or +2. A struct-of-arrays storage redesign (a much larger change). + +The `pub(crate)` field restriction in `Fact` also means the SIMD helpers cannot access field data directly from production code paths without an API change. + +**Action:** Close #229 with this analysis. Open a separate issue for struct-of-arrays storage layout if aggregate performance becomes a measured bottleneck. The `wide` dependency and `simd_helpers` module introduced in this branch provide a validated foundation for future SoA work. diff --git a/docs/superpowers/plans/2026-05-15-cost-based-optimizer.md b/docs/superpowers/plans/2026-05-15-cost-based-optimizer.md new file mode 100644 index 000000000..4281810d0 --- /dev/null +++ b/docs/superpowers/plans/2026-05-15-cost-based-optimizer.md @@ -0,0 +1,678 @@ +# Cost-Based Optimizer Extensions Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Add `pattern_cost`, `clause_cost`, and `branch_cost` to `optimizer.rs`, then use them to sort `not`/`not-join` clauses and `or`/`or-join` branches by cost ascending so cheap filters run first. + +**Architecture:** Three new cost functions land in `optimizer.rs` (unconditional — available on all targets). The sorting call-sites in `executor.rs` and `evaluator.rs` are gated behind `#[cfg(not(feature = "wasm"))]`, matching the existing pattern-ordering gate. No change to `plan()` signature or return type. + +**Tech Stack:** Rust, Cargo, `cargo test`, `cargo clippy` + +--- + +## File Structure + +| File | Change | +|------|--------| +| `src/query/datalog/optimizer.rs` | Add private `pattern_cost()`, pub `clause_cost()`, pub `branch_cost()` before the `#[cfg(test)]` block at line 199 | +| `src/query/datalog/executor.rs` | Sort `not_clauses`/`not_join_clauses` after line 592 (execute_query) and after line 1060 (execute_query_with_rules); sort branches in `apply_or_clauses()` before the `for branch in branches` loops | +| `src/query/datalog/evaluator.rs` | Sort `not_clauses`/`not_join_clauses` after line 787 (StratifiedEvaluator mixed-rules loop) | + +--- + +### Task 1: Git worktree + +**Files:** +- No file changes — worktree setup only + +- [ ] **Step 1: Invoke the using-git-worktrees skill** + +``` +Use superpowers:using-git-worktrees to create a worktree for branch feature/issue-205-cost-based-optimizer +``` + +Expected: worktree created at `.worktrees/issue-205-cost-based-optimizer`, checked out to new branch `feature/issue-205-cost-based-optimizer`. + +--- + +### Task 2: Failing unit tests for cost functions + +**Files:** +- Modify: `src/query/datalog/optimizer.rs:199` (append to existing `#[cfg(test)]` module) + +The existing test module starts at line 199. Add new tests at the end of it (before the closing `}`). + +- [ ] **Step 1: Read the end of the existing test module** + +```bash +tail -n 30 src/query/datalog/optimizer.rs +``` + +Note the exact closing `}` line number so you can insert before it. + +- [ ] **Step 2: Add failing tests for the three cost functions** + +Append the following test functions inside the existing `#[cfg(test)] mod tests { ... }` block, before its closing `}`: + +```rust + // ── cost model tests ────────────────────────────────────────────────── + + fn sym(s: &str) -> EdnValue { + EdnValue::Symbol(s.to_string()) + } + + fn lit_str(s: &str) -> EdnValue { + EdnValue::Str(s.to_string()) + } + + fn attr(s: &str) -> AttributeSpec { + use crate::query::datalog::types::AttributeSpec; + AttributeSpec::Real(EdnValue::Keyword(s.to_string())) + } + + fn attr_var() -> AttributeSpec { + use crate::query::datalog::types::AttributeSpec; + AttributeSpec::Real(EdnValue::Symbol("?a".to_string())) + } + + fn make_cost_pattern( + entity: EdnValue, + attribute: AttributeSpec, + value: EdnValue, + ) -> Pattern { + use crate::query::datalog::types::AttributeSpec; + Pattern::new(entity, attribute.into_edn(), value) + } + + #[test] + fn test_pattern_cost_fully_bound() { + // entity bound (UUID), attribute real keyword, value bound literal — 3 bound → cost 1 + let p = Pattern::new( + EdnValue::Uuid(Uuid::new_v4()), + EdnValue::Keyword(":person/name".to_string()), + lit_str("Alice"), + ); + assert_eq!(pattern_cost(&p), 1); + } + + #[test] + fn test_pattern_cost_two_bound() { + // attribute + value bound, entity variable — 2 bound → cost 10 + let p = Pattern::new( + sym("?e"), + EdnValue::Keyword(":person/name".to_string()), + lit_str("Alice"), + ); + assert_eq!(pattern_cost(&p), 10); + } + + #[test] + fn test_pattern_cost_one_bound() { + // only attribute bound — 1 bound → cost 100 + let p = Pattern::new( + sym("?e"), + EdnValue::Keyword(":person/name".to_string()), + sym("?v"), + ); + assert_eq!(pattern_cost(&p), 100); + } + + #[test] + fn test_pattern_cost_unbound() { + // all variables — 0 bound → cost 10_000 + let p = Pattern::new( + sym("?e"), + EdnValue::Symbol("?a".to_string()), + sym("?v"), + ); + assert_eq!(pattern_cost(&p), 10_000); + } + + #[test] + fn test_clause_cost_pattern() { + // clause_cost delegates to pattern_cost for Pattern variant + let p = Pattern::new( + sym("?e"), + EdnValue::Keyword(":person/name".to_string()), + lit_str("Alice"), + ); + let clause = WhereClause::Pattern(p); + assert_eq!(clause_cost(&clause), 10); // attr + value bound = 2 → 10 + } + + #[test] + fn test_clause_cost_expr() { + // Expr is pure computation — cost 0 + let clause = WhereClause::Expr { + var: "?x".to_string(), + expr: Expr::Lit(crate::graph::types::Value::Integer(42)), + }; + assert_eq!(clause_cost(&clause), 0); + } + + #[test] + fn test_clause_cost_not_body_uses_min() { + // Not body: one selective pattern (cost 10) + one full-scan pattern (cost 10_000) + // clause_cost → min = 10 + let selective = Pattern::new( + sym("?e"), + EdnValue::Keyword(":person/name".to_string()), + lit_str("Alice"), + ); + let full_scan = Pattern::new(sym("?x"), EdnValue::Symbol("?a".to_string()), sym("?v")); + let clause = WhereClause::Not(vec![ + WhereClause::Pattern(selective), + WhereClause::Pattern(full_scan), + ]); + assert_eq!(clause_cost(&clause), 10); + } + + #[test] + fn test_clause_cost_not_body_expr_only() { + // Not body with no patterns (expr only) → cost 0 + let clause = WhereClause::Not(vec![WhereClause::Expr { + var: "?x".to_string(), + expr: Expr::Lit(crate::graph::types::Value::Integer(1)), + }]); + assert_eq!(clause_cost(&clause), 0); + } + + #[test] + fn test_branch_cost_empty_branch() { + // Empty branch → 0 + assert_eq!(branch_cost(&[]), 0); + } + + #[test] + fn test_branch_cost_no_patterns() { + // Branch with only Expr clauses → 0 + let branch = vec![WhereClause::Expr { + var: "?x".to_string(), + expr: Expr::Lit(crate::graph::types::Value::Integer(99)), + }]; + assert_eq!(branch_cost(&branch), 0); + } + + #[test] + fn test_clause_cost_or_sums_branch_costs() { + // Or with two branches: + // branch 1: one pattern with cost 10 + // branch 2: one pattern with cost 100 + // clause_cost(Or) = sum = 110 + let b1 = vec![WhereClause::Pattern(Pattern::new( + sym("?e"), + EdnValue::Keyword(":person/name".to_string()), + lit_str("Alice"), + ))]; + let b2 = vec![WhereClause::Pattern(Pattern::new( + sym("?e"), + EdnValue::Keyword(":person/age".to_string()), + sym("?v"), + ))]; + let clause = WhereClause::Or(vec![b1, b2]); + assert_eq!(clause_cost(&clause), 110); // 10 + 100 + } +``` + +- [ ] **Step 3: Run the tests and verify they fail with "not found" errors** + +```bash +cargo test -p minigraf pattern_cost branch_cost clause_cost -- --nocapture 2>&1 | head -40 +``` + +Expected: compile errors — `pattern_cost`, `clause_cost`, `branch_cost` not found. This is the TDD red phase. + +--- + +### Task 3: Implement cost functions in optimizer.rs + +**Files:** +- Modify: `src/query/datalog/optimizer.rs` (insert before line 199) + +- [ ] **Step 1: Insert the three cost functions before the `#[cfg(test)]` block** + +Open `src/query/datalog/optimizer.rs`. Find line 199 (`#[cfg(test)]`). Insert the following block immediately before it (after line 197, which is the closing `}` of `plan()`): + +```rust +/// Static 4-tier cardinality estimate for a single pattern. +/// +/// Derived from selectivity_score but returns u64 cost (lower = cheaper) rather +/// than a selectivity score. Unconditional: available on all targets including WASM. +fn pattern_cost(p: &Pattern) -> u64 { + let e = !is_variable(&p.entity); + let a = attr_is_index_bound(&p.attribute); + let v = !is_variable(&p.value); + match (e as u8) + (a as u8) + (v as u8) { + 3 => 1, + 2 => 10, + 1 => 100, + _ => 10_000, + } +} + +/// Estimated cost for a body/branch slice — the minimum `pattern_cost` across all +/// Pattern clauses, or 0 if the body contains no patterns (expr-only bodies are +/// cheap pure computation). +/// +/// Rationale for `min`: In a multi-pattern join the most selective pattern dominates — +/// the join cannot produce more rows than the smallest input. +/// +/// Unconditional: available on all targets including WASM. +pub fn branch_cost(branch: &[WhereClause]) -> u64 { + branch + .iter() + .filter_map(|c| { + if let WhereClause::Pattern(p) = c { + Some(pattern_cost(p)) + } else { + None + } + }) + .min() + .unwrap_or(0) +} + +/// Estimated evaluation cost for any `WhereClause`. +/// +/// | Clause type | Cost | +/// |--------------------|------| +/// | `Pattern` | `pattern_cost(p)` | +/// | `Expr` | 0 (pure computation) | +/// | `Not(body)` | `branch_cost(body)` | +/// | `NotJoin{clauses}` | `branch_cost(clauses)` | +/// | `Or(branches)` | sum of `branch_cost` per branch | +/// | `OrJoin{branches}` | sum of `branch_cost` per branch | +/// | other | `u64::MAX` (defensive; not expected in practice) | +/// +/// Unconditional: available on all targets including WASM. The *sorting* call-sites +/// that consume this function are gated behind `#[cfg(not(feature = "wasm"))]`. +pub fn clause_cost(clause: &WhereClause) -> u64 { + match clause { + WhereClause::Pattern(p) => pattern_cost(p), + WhereClause::Expr { .. } => 0, + WhereClause::Not(body) => branch_cost(body), + WhereClause::NotJoin { clauses, .. } => branch_cost(clauses), + WhereClause::Or(branches) => branches.iter().map(|b| branch_cost(b)).sum(), + WhereClause::OrJoin { branches, .. } => branches.iter().map(|b| branch_cost(b)).sum(), + _ => u64::MAX, + } +} + +``` + +- [ ] **Step 2: Run cost-function unit tests to verify they pass** + +```bash +cargo test -p minigraf pattern_cost branch_cost clause_cost -- --nocapture 2>&1 | tail -20 +``` + +Expected: all new tests PASS. No compile errors. + +- [ ] **Step 3: Run full test suite to check for regressions** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all existing tests still pass. + +- [ ] **Step 4: Commit** + +```bash +git add src/query/datalog/optimizer.rs +git commit -m "feat(optimizer): add pattern_cost, branch_cost, clause_cost (#205) + +Static 4-tier cardinality cost model. Unconditional (all targets). +Sorting call-sites gated on cfg(not(feature = \"wasm\")) added in next commit." +``` + +--- + +### Task 4: Sort not-clauses in executor.rs (both query functions) + +**Files:** +- Modify: `src/query/datalog/executor.rs:592` and `src/query/datalog/executor.rs:1060` + +- [ ] **Step 1: Write integration tests for not-clause ordering** + +Add the following test at the end of `executor.rs`'s `#[cfg(test)] mod tests { ... }` block: + +```rust + #[test] + fn test_not_clause_ordering_correctness() { + // Two `not` clauses in expensive-first source order; results must be + // identical to cheap-first order — the sorting is semantics-preserving. + use crate::graph::types::Value; + use crate::storage::backend::memory::MemoryBackend; + use crate::db::Minigraf; + + let db = Minigraf::open_with_backend(MemoryBackend::new()).unwrap(); + db.execute( + r#"(transact [ + [:db/add "e1" :item/name "widget" :item/tag "cheap"] + [:db/add "e2" :item/name "gadget" :item/tag "cheap"] + [:db/add "e3" :item/name "doohickey"] + ])"#, + ) + .unwrap(); + + // Query: items that are NOT named "widget" AND NOT named "gadget" + // Only "doohickey" survives both filters. + let result = db + .execute( + r#"(query {:find [?name] + :where [[?e :item/name ?name] + (not [?e :item/name "widget"]) + (not [?e :item/name "gadget"])]})"#, + ) + .unwrap(); + assert_eq!(result.len(), 1, "expected exactly one result"); + assert_eq!( + result[0].get("name").cloned().or_else(|| result[0].get("?name").cloned()), + Some(Value::String("doohickey".to_string())) + ); + } +``` + +- [ ] **Step 2: Run the test to verify it passes (behaviour baseline)** + +```bash +cargo test -p minigraf test_not_clause_ordering_correctness -- --nocapture +``` + +Expected: PASS — this is a correctness regression guard, not a TDD new-feature test. + +- [ ] **Step 3: Add not-clause sorting after line 592 in execute_query()** + +In `src/query/datalog/executor.rs`, find the block ending at line 592 (`.collect();` closing `not_join_clauses`). Insert the following two lines immediately after it: + +```rust + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_clauses.sort_by_key(|body| optimizer::branch_cost(body)); + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_join_clauses.sort_by_key(|(_, clauses)| optimizer::branch_cost(clauses)); +``` + +- [ ] **Step 4: Add not-clause sorting after line 1060 in execute_query_with_rules()** + +Find the second `.collect();` closing `not_join_clauses` (around line 1060). Insert the same block: + +```rust + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_clauses.sort_by_key(|body| optimizer::branch_cost(body)); + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_join_clauses.sort_by_key(|(_, clauses)| optimizer::branch_cost(clauses)); +``` + +- [ ] **Step 5: Run full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 6: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "feat(executor): sort not/not-join clauses by cost ascending (#205) + +Cheap filters run first; bindings rejected early never reach expensive filters. +Gated on cfg(not(feature = \"wasm\")) — small datasets + determinism on WASM." +``` + +--- + +### Task 5: Sort or/or-join branches in apply_or_clauses() + +**Files:** +- Modify: `src/query/datalog/executor.rs` — `apply_or_clauses()` function + +`apply_or_clauses()` starts at line 1821. There are two `for branch in branches` loops: +- **Slow path** (seeded, has Not): loop at line 1846 +- **Fast path** (no Not, hash-join): loop at line 1880 + +Both operate on the same `branches` binding. We introduce a sorted copy before both paths. + +- [ ] **Step 1: Find the `any_branch_has_not` binding inside the `WhereClause::Or` arm** + +Read `src/query/datalog/executor.rs` lines 1832–1845. The structure is: + +```rust +WhereClause::Or(branches) => { + let any_branch_has_not = branches.iter().any(|b| { ... }); + + if any_branch_has_not { + // slow path: for branch in branches { ... } + ... + } + // fast path: for branch in branches { ... } +``` + +- [ ] **Step 2: Add branch sorting before the `any_branch_has_not` check** + +Insert immediately after the opening `WhereClause::Or(branches) => {` line: + +```rust + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + // Note: all branches are still evaluated (no short-circuit); this ordering + // is infrastructure for issue #250. See that issue for short-circuit optimization. + #[cfg(not(feature = "wasm"))] + let branches: Vec<_> = { + let mut b: Vec<_> = branches.iter().collect(); + b.sort_by_key(|br| optimizer::branch_cost(br)); + b.into_iter().map(|br| br.as_slice()).collect() + }; + #[cfg(not(feature = "wasm"))] + let branches: &[_] = &branches; + #[cfg(feature = "wasm")] + let branches: Vec<_> = branches.iter().map(|b| b.as_slice()).collect(); + #[cfg(feature = "wasm")] + let branches: &[_] = &branches; +``` + +Wait — this approach is overly complex because `branches` is already a `&Vec>` from the match arm. A simpler approach: introduce a locally-sorted `Vec` that shadows `branches` as a `Vec<&Vec>`, and replace the two loop references. + +**Revised Step 2**: Insert immediately after `WhereClause::Or(branches) => {`: + +```rust + // Sort branches by cost ascending so cheaper branches evaluate first. + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + // Note: all branches still evaluated (no short-circuit); ordering is + // infrastructure for issue #250. + let sorted_branches: Vec<&Vec>; + #[cfg(not(feature = "wasm"))] + { + let mut b: Vec<&Vec> = branches.iter().collect(); + b.sort_by_key(|br| optimizer::branch_cost(br)); + sorted_branches = b; + } + #[cfg(feature = "wasm")] + { + sorted_branches = branches.iter().collect(); + } +``` + +Then replace `for branch in branches {` in the **slow path** (line ~1846) with `for branch in &sorted_branches {`. + +And replace `for branch in branches {` in the **fast path** (line ~1880) with `for branch in &sorted_branches {`. + +In each loop, `branch` was a `&Vec`. After the replacement it is a `&&Vec`, so add a `*` dereference or use `branch` directly — Rust auto-derefs in most call positions so it should compile unchanged, but verify. + +- [ ] **Step 3: Do the same for the `WhereClause::OrJoin` arm** + +Find the `WhereClause::OrJoin { join_vars, branches }` arm (around line 1974). The loop is `for branch in branches` (around line 1995). Apply the same sorted_branches pattern. + +Insert immediately after `WhereClause::OrJoin { join_vars, branches } => {`: + +```rust + let sorted_oj_branches: Vec<&Vec>; + #[cfg(not(feature = "wasm"))] + { + let mut b: Vec<&Vec> = branches.iter().collect(); + b.sort_by_key(|br| optimizer::branch_cost(br)); + sorted_oj_branches = b; + } + #[cfg(feature = "wasm")] + { + sorted_oj_branches = branches.iter().collect(); + } +``` + +Replace `for branch in branches {` (around line 1995) with `for branch in &sorted_oj_branches {`. + +- [ ] **Step 4: Run full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 5: Clippy** + +```bash +cargo clippy -- -D warnings 2>&1 | grep -v "^$" | head -30 +``` + +Expected: no warnings. If clippy flags unused variable warnings for `sorted_branches` in a cfg branch, use `let _ =` or restructure so both branches use the same name. + +- [ ] **Step 6: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "feat(executor): sort or/or-join branches by cost ascending (#205) + +Infrastructure for issue #250 (or short-circuit). All branches still evaluated. +Gated on cfg(not(feature = \"wasm\"))." +``` + +--- + +### Task 6: Sort not-clauses in evaluator.rs (StratifiedEvaluator) + +**Files:** +- Modify: `src/query/datalog/evaluator.rs:787` + +The `not_join_clauses` collection ends at line 787 (`.collect();`). Insert sorting immediately after. + +- [ ] **Step 1: Insert not-clause sorting after line 787** + +In `src/query/datalog/evaluator.rs`, after the `.collect();` that closes `not_join_clauses`: + +```rust + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_clauses.sort_by_key(|body| crate::query::datalog::optimizer::branch_cost(body)); + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_join_clauses + .sort_by_key(|(_, clauses)| crate::query::datalog::optimizer::branch_cost(clauses)); +``` + +Note: `evaluator.rs` uses the full path `crate::query::datalog::optimizer` rather than a short `optimizer` alias (verify the existing imports in the file before deciding whether to add a `use` line or use the full path). + +- [ ] **Step 2: Run full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 3: Run clippy** + +```bash +cargo clippy -- -D warnings 2>&1 | grep -v "^$" | head -30 +``` + +Expected: no warnings. + +- [ ] **Step 4: Commit** + +```bash +git add src/query/datalog/evaluator.rs +git commit -m "feat(evaluator): sort not/not-join clauses by cost in StratifiedEvaluator (#205) + +Consistent with executor.rs; cheap filters run first in mixed-rules loop. +Gated on cfg(not(feature = \"wasm\"))." +``` + +--- + +### Task 7: Full verification and PR + +**Files:** +- No new file changes + +- [ ] **Step 1: Run the complete test suite** + +```bash +cargo test 2>&1 | tail -10 +``` + +Expected: all tests pass (currently ~850+). + +- [ ] **Step 2: Run clippy clean** + +```bash +cargo clippy -- -D warnings 2>&1 | grep -E "^error" | wc -l +``` + +Expected: 0. + +- [ ] **Step 3: Run cargo fmt check** + +```bash +cargo fmt --check +``` + +Expected: no diff. If there is a diff, run `cargo fmt` and commit the style fix. + +- [ ] **Step 4: Verify WASM build compiles** + +```bash +cargo build --features wasm --target wasm32-unknown-unknown 2>&1 | tail -5 +``` + +Expected: compiles without errors. (If the `wasm32-unknown-unknown` target is not installed, run `rustup target add wasm32-unknown-unknown` first.) + +- [ ] **Step 5: Open the PR** + +```bash +gh pr create \ + --title "feat: cost-based not/or ordering (#205)" \ + --body "$(cat <<'EOF' +## Summary +- Adds `pattern_cost`, `branch_cost`, `clause_cost` to `optimizer.rs` (unconditional, all targets) +- Sorts `not`/`not-join` clauses cheapest-first in `execute_query`, `execute_query_with_rules`, and `StratifiedEvaluator` +- Sorts `or`/`or-join` branches cheapest-first in `apply_or_clauses` (infrastructure for #250) +- Sorting gated on `#[cfg(not(feature = "wasm"))]` — small datasets + determinism on WASM + +Closes #205 + +## Test plan +- [ ] All existing tests pass (`cargo test`) +- [ ] New unit tests for all cost tiers in `optimizer.rs` +- [ ] New integration test: not-clause ordering produces correct results +- [ ] `cargo clippy -- -D warnings` clean +- [ ] `cargo fmt --check` clean +- [ ] WASM build compiles + +🤖 Generated with [Claude Code](https://claude.com/claude-code) +EOF +)" +``` + +- [ ] **Step 6: Monitor CI until green** + +```bash +gh pr checks --watch +``` + +Expected: all checks green. Fix any failures before proceeding. diff --git a/docs/superpowers/plans/2026-05-16-simd-benchmarking.md b/docs/superpowers/plans/2026-05-16-simd-benchmarking.md new file mode 100644 index 000000000..67211469b --- /dev/null +++ b/docs/superpowers/plans/2026-05-16-simd-benchmarking.md @@ -0,0 +1,861 @@ +# SIMD Benchmarking Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Add three Criterion benchmark groups comparing scalar vs explicit SIMD (via `wide`) for valid-time filter, tx-time as-of filter, and aggregation sum, then write a crossover analysis and recommendation. + +**Architecture:** All SIMD code lives in `benches/simd_helpers.rs` (a new file). Both scalar and SIMD benchmarks operate on synthetic `Vec`/`Vec` data — `Fact` internals are `pub(crate)` and inaccessible from bench code, so we benchmark the kernel loops directly. `wide` is added to the non-WASM `[dev-dependencies]` block only (zero binary size impact). A single `bench_simd` function registers all three groups. + +**Tech Stack:** Rust stable, `criterion 0.8`, `wide 0.7`, `cargo bench` + +--- + +## File Structure + +| File | Change | +|---|---| +| `Cargo.toml` | Add `wide = "0.7"` to non-WASM dev-deps | +| `benches/simd_helpers.rs` | New: `valid_time_filter_simd`, `as_of_filter_simd`, `sum_simd_i64` + unit tests | +| `benches/minigraf_bench.rs` | Add `mod simd_helpers;`, `bench_simd` function, register in `criterion_group!` | +| `docs/simd-analysis.md` | New: benchmark results table, crossover analysis, recommendation | + +--- + +### Task 1: Git worktree + +**Files:** None + +- [ ] **Step 1: Create worktree** + +```bash +git worktree add .worktrees/issue-229-simd-benchmarking -b feature/issue-229-simd-benchmarking +cd .worktrees/issue-229-simd-benchmarking +``` + +Expected: `.worktrees/issue-229-simd-benchmarking` created on new branch `feature/issue-229-simd-benchmarking`. + +--- + +### Task 2: Add `wide` to Cargo.toml + +**Files:** +- Modify: `Cargo.toml` + +`wide` must live in the same cfg-gated dev-dep block as `criterion` so it is not compiled for WASM targets. + +- [ ] **Step 1: Add `wide` to the non-WASM dev-dependencies block** + +Open `Cargo.toml`. Find the block: +```toml +[target.'cfg(not(target_arch = "wasm32"))'.dev-dependencies] +tempfile = "3" +criterion = { version = "0.8", features = ["html_reports"] } +``` + +Add `wide` on the line after `criterion`: +```toml +[target.'cfg(not(target_arch = "wasm32"))'.dev-dependencies] +tempfile = "3" +criterion = { version = "0.8", features = ["html_reports"] } +wide = "0.7" +``` + +- [ ] **Step 2: Verify the build** + +```bash +cargo check --benches 2>&1 | tail -5 +``` + +Expected: `Finished` — no errors. `wide` resolves successfully. + +- [ ] **Step 3: Commit** + +```bash +git add Cargo.toml Cargo.lock +git commit -m "chore: add wide 0.7 to non-WASM dev-dependencies (#229)" +``` + +--- + +### Task 3: Failing unit tests for SIMD helpers + +**Files:** +- Create: `benches/simd_helpers.rs` + +Write the file skeleton and unit tests only — the three functions are declared but bodies are `todo!()`. Tests verify that SIMD output matches scalar output, so they will fail at runtime (panic on `todo!()`). The file also needs allow attributes for clippy lints that fire in benchmark/helper code. + +- [ ] **Step 1: Create `benches/simd_helpers.rs` with stubs and tests** + +```rust +//! SIMD kernel benchmarks for issue #229. +//! +//! All three functions operate on pre-extracted numeric slices. +//! `Fact` internals are `pub(crate)` and unavailable from bench code; +//! benchmarks use synthetic data to isolate the hot loop. +//! +//! `wide` API notes (verify against docs.rs/wide/0.7): +//! - `i64x4::new([a, b, c, d])` — construct from array +//! - `i64x4::splat(v)` — broadcast scalar to all lanes +//! - `a.cmp_le(b)` — returns i64x4 with all-bits-1 where ≤, 0 elsewhere +//! - `a.cmp_gt(b)` — returns i64x4 with all-bits-1 where >, 0 elsewhere +//! - `let arr: [i64; 4] = simd_val.into()` — extract lanes +//! - `u64x2` is the widest unsigned-64 type in wide 0.7 (no u64x4) + +#![allow(clippy::cast_possible_truncation)] // synthetic bench data: N ≤ 1M fits in i64 +#![allow(clippy::cast_sign_loss)] // tx_count cast: monotonic counter, always positive + +use wide::{i64x4, u64x2}; + +/// Count facts where `valid_from[i] <= ts && ts < valid_to[i]`. +/// +/// Processes 4 facts per SIMD step using `i64x4`. Scalar tail handles remainder. +/// Both slices must be the same length. +pub fn valid_time_filter_simd(valid_from: &[i64], valid_to: &[i64], ts: i64) -> usize { + todo!("implement in Task 4") +} + +/// Count facts where `tx_counts[i] <= threshold`. +/// +/// Processes 2 facts per SIMD step using `u64x2` (widest unsigned-64 in wide 0.7). +/// Scalar tail handles remainder. +pub fn as_of_filter_simd(tx_counts: &[u64], threshold: u64) -> usize { + todo!("implement in Task 4") +} + +/// Sum all values using `i64x4` horizontal reduction. +/// +/// Accumulates 4 lanes in parallel; reduces to scalar at the end. +/// Wrapping arithmetic matches Rust's default release-mode overflow behaviour. +pub fn sum_simd_i64(values: &[i64]) -> i64 { + todo!("implement in Task 4") +} + +#[cfg(test)] +mod tests { + use super::*; + + // ── valid_time_filter_simd ──────────────────────────────────────────────── + + #[test] + fn test_valid_time_filter_matches_scalar_partial() { + // 6 facts (non-multiple of 4 to exercise tail path) + // valid window: [i, i + 3]; ts = 2; facts 0,1,2 pass, facts 3,4,5 fail + let valid_from: Vec = (0_i64..6).collect(); + let valid_to: Vec = valid_from.iter().map(|&vf| vf + 3).collect(); + let ts = 2_i64; + + let scalar = valid_from + .iter() + .zip(valid_to.iter()) + .filter(|(&vf, &vt)| vf <= ts && ts < vt) + .count(); + + assert_eq!(valid_time_filter_simd(&valid_from, &valid_to, ts), scalar); + } + + #[test] + fn test_valid_time_filter_matches_scalar_exact_chunk() { + // 8 facts (exactly two SIMD chunks) + let valid_from: Vec = (0_i64..8).collect(); + let valid_to: Vec = valid_from.iter().map(|&vf| vf + 4).collect(); + let ts = 3_i64; + + let scalar = valid_from + .iter() + .zip(valid_to.iter()) + .filter(|(&vf, &vt)| vf <= ts && ts < vt) + .count(); + + assert_eq!(valid_time_filter_simd(&valid_from, &valid_to, ts), scalar); + } + + #[test] + fn test_valid_time_filter_empty() { + assert_eq!(valid_time_filter_simd(&[], &[], 0), 0); + } + + // ── as_of_filter_simd ───────────────────────────────────────────────────── + + #[test] + fn test_as_of_filter_matches_scalar_partial() { + // 9 tx_counts (non-multiple of 2 to exercise tail) + let tx_counts: Vec = (1..=9).collect(); + let threshold = 5_u64; + + let scalar = tx_counts.iter().filter(|&&tc| tc <= threshold).count(); + + assert_eq!(as_of_filter_simd(&tx_counts, threshold), scalar); + } + + #[test] + fn test_as_of_filter_matches_scalar_exact_chunk() { + // 10 tx_counts (exactly five 2-wide chunks) + let tx_counts: Vec = (1..=10).collect(); + let threshold = 7_u64; + + let scalar = tx_counts.iter().filter(|&&tc| tc <= threshold).count(); + + assert_eq!(as_of_filter_simd(&tx_counts, threshold), scalar); + } + + #[test] + fn test_as_of_filter_empty() { + assert_eq!(as_of_filter_simd(&[], 100), 0); + } + + // ── sum_simd_i64 ────────────────────────────────────────────────────────── + + #[test] + fn test_sum_simd_matches_scalar_partial() { + // 9 values (non-multiple of 4 to exercise tail) + let values: Vec = (1_i64..=9).collect(); + let scalar: i64 = values.iter().sum(); + + assert_eq!(sum_simd_i64(&values), scalar); + } + + #[test] + fn test_sum_simd_matches_scalar_exact_chunk() { + // 8 values (exactly two 4-wide chunks) + let values: Vec = (1_i64..=8).collect(); + let scalar: i64 = values.iter().sum(); + + assert_eq!(sum_simd_i64(&values), scalar); + } + + #[test] + fn test_sum_simd_empty() { + assert_eq!(sum_simd_i64(&[]), 0); + } + + #[test] + fn test_sum_simd_negatives() { + let values = vec![-3_i64, -2, -1, 0, 1, 2, 3]; + let scalar: i64 = values.iter().sum(); + + assert_eq!(sum_simd_i64(&values), scalar); + } +} +``` + +- [ ] **Step 2: Run the tests and confirm they panic on `todo!()`** + +```bash +cargo test -p minigraf simd_helpers 2>&1 | head -20 +``` + +Expected: tests panic with `not yet implemented: implement in Task 4`. This is the TDD red phase. + +--- + +### Task 4: Implement SIMD helper functions + +**Files:** +- Modify: `benches/simd_helpers.rs` + +Replace each `todo!()` body with the real implementation. Use `chunks_exact` for SIMD iteration (avoids `clippy::indexing_slicing`). Use `get(rem..).unwrap_or(&[])` for the scalar tail (avoids `clippy::indexing_slicing` and `clippy::unwrap_used`). + +Before writing, verify the exact `wide 0.7` API at `https://docs.rs/wide/0.7` — specifically: +- Is `cmp_le` the correct method name for ≤ comparison on `i64x4`? +- Does `cmp_gt` exist for `i64x4`? +- Does `u64x2` support `cmp_le`? +- Can you extract lanes with `let arr: [i64; 4] = v.into()` or is it `v.to_array()`? + +- [ ] **Step 1: Implement `valid_time_filter_simd`** + +Replace the `todo!()` in `valid_time_filter_simd` with: + +```rust +pub fn valid_time_filter_simd(valid_from: &[i64], valid_to: &[i64], ts: i64) -> usize { + let ts_v = i64x4::splat(ts); + let mut count = 0usize; + + for (vf_chunk, vt_chunk) in valid_from + .chunks_exact(4) + .zip(valid_to.chunks_exact(4)) + { + // Slice patterns: chunks_exact guarantees len == 4, so the else branch + // is unreachable (unreachable = "allow" in workspace lints) + let [vf0, vf1, vf2, vf3] = *vf_chunk else { unreachable!() }; + let [vt0, vt1, vt2, vt3] = *vt_chunk else { unreachable!() }; + + let vf = i64x4::new([vf0, vf1, vf2, vf3]); + let vt = i64x4::new([vt0, vt1, vt2, vt3]); + + // vf <= ts AND ts < vt (i.e., vt > ts) + // Note: verify method names against docs.rs/wide/0.7 before finalising + let lo = vf.cmp_le(ts_v); + let hi = vt.cmp_gt(ts_v); + let mask = lo & hi; + + // All-bits-1 = true lane (i64 = -1); 0 = false lane + let arr: [i64; 4] = mask.into(); + count += arr.iter().filter(|&&x| x != 0).count(); + } + + // Scalar tail for remaining facts (0–3 elements) + let rem = (valid_from.len() / 4) * 4; + for (&vf, &vt) in valid_from + .get(rem..) + .unwrap_or(&[]) + .iter() + .zip(valid_to.get(rem..).unwrap_or(&[]).iter()) + { + if vf <= ts && ts < vt { + count += 1; + } + } + + count +} +``` + +- [ ] **Step 2: Implement `as_of_filter_simd`** + +Replace the `todo!()` in `as_of_filter_simd` with: + +```rust +pub fn as_of_filter_simd(tx_counts: &[u64], threshold: u64) -> usize { + let thr_v = u64x2::splat(threshold); + let mut count = 0usize; + + for chunk in tx_counts.chunks_exact(2) { + // Slice pattern: chunks_exact guarantees len == 2 + let [a, b] = *chunk else { unreachable!() }; + let v = u64x2::new([a, b]); + + // Note: verify u64x2::cmp_le exists in wide 0.7; if not, use manual comparison: + // let mask = u64x2::new([(if a <= threshold { u64::MAX } else { 0 }), (if b <= threshold { u64::MAX } else { 0 })]); + let mask = v.cmp_le(thr_v); + let arr: [u64; 2] = mask.into(); + count += arr.iter().filter(|&&x| x != 0).count(); + } + + let rem = (tx_counts.len() / 2) * 2; + for &tc in tx_counts.get(rem..).unwrap_or(&[]) { + if tc <= threshold { + count += 1; + } + } + + count +} +``` + +**Note:** `u64x2` is only 2-wide (wide 0.7 has no `u64x4`). If `u64x2::cmp_le` does not exist, replace the SIMD comparison with the manual mask construction shown in the comment above. + +- [ ] **Step 3: Implement `sum_simd_i64`** + +Replace the `todo!()` in `sum_simd_i64` with: + +```rust +pub fn sum_simd_i64(values: &[i64]) -> i64 { + let mut acc = i64x4::splat(0_i64); + + for chunk in values.chunks_exact(4) { + let [a, b, c, d] = *chunk else { unreachable!() }; + acc += i64x4::new([a, b, c, d]); + } + + // Horizontal reduction: sum the 4 lanes + let lanes: [i64; 4] = acc.into(); + let mut sum: i64 = lanes.iter().sum(); + + // Scalar tail + let rem = (values.len() / 4) * 4; + for &v in values.get(rem..).unwrap_or(&[]) { + sum = sum.wrapping_add(v); + } + + sum +} +``` + +- [ ] **Step 4: Run the tests — verify all pass** + +```bash +cargo test -p minigraf simd_helpers 2>&1 | tail -15 +``` + +Expected: all 10 tests PASS. If the `wide` API differs from the pseudocode (e.g., method not found), read `cargo test` errors, check `https://docs.rs/wide/0.7`, adapt accordingly. + +- [ ] **Step 5: Run clippy to confirm no new lint errors** + +```bash +cargo clippy -- -D warnings 2>&1 | grep "^error" | wc -l +``` + +Expected: 0. + +- [ ] **Step 6: Commit** + +```bash +git add benches/simd_helpers.rs +git commit -m "feat(bench): add SIMD helper kernels for temporal filter and sum (#229)" +``` + +--- + +### Task 5: Add `bench_simd` to the benchmark file + +**Files:** +- Modify: `benches/minigraf_bench.rs` + +Add `mod simd_helpers;` at the top, add the `bench_simd` function, and register it in `criterion_group!`. + +- [ ] **Step 1: Add `mod simd_helpers;` after the existing `mod helpers;` line** + +Open `benches/minigraf_bench.rs`. Line 20 is `mod helpers;`. Insert immediately after it: + +```rust +#[cfg(not(target_arch = "wasm32"))] +mod simd_helpers; +``` + +The `cfg` gate is needed because `wide` is only in the non-WASM dev-deps. + +- [ ] **Step 2: Add `use criterion::black_box;` to the imports** + +Find the existing use statement: +```rust +use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main}; +``` + +Replace with: +```rust +use criterion::{BenchmarkId, Criterion, Throughput, black_box, criterion_group, criterion_main}; +``` + +- [ ] **Step 3: Add the `bench_simd` function** + +Add the following before the `criterion_group!` macro (after `bench_predicate_pushdown`): + +```rust +// ── SIMD kernel benchmarks (Issue #229) ────────────────────────────────────── +// +// Both scalar and SIMD variants operate on synthetic Vec/Vec data. +// Fact internals (valid_from, valid_to, tx_count) are pub(crate) and unavailable +// from bench code; benchmarks isolate the hot loop rather than the full query path. +// Cross-reference the existing time_travel/ and aggregation/ groups for full-query costs. + +#[cfg(not(target_arch = "wasm32"))] +fn bench_simd(c: &mut Criterion) { + const SCALES: &[(&str, usize)] = &[ + ("100", 100), + ("1k", 1_000), + ("10k", 10_000), + ("100k", 100_000), + ("1m", 1_000_000), + ]; + + // ── simd_temporal: valid-time range filter ────────────────────────────── + // + // Synthetic data: valid_from[i] = i, valid_to[i] = i + n/2. + // ts = n/4 → ~50% of facts are valid at ts (those with valid_from ≤ n/4 < valid_to). + { + let mut group = c.benchmark_group("simd_temporal"); + group.sample_size(10); + + for &(label, n) in SCALES { + let n_i64 = i64::try_from(n).unwrap_or(i64::MAX); + let valid_from: Vec = (0_i64..n_i64).collect(); + let valid_to: Vec = valid_from.iter().map(|&vf| vf + n_i64 / 2).collect(); + let ts = n_i64 / 4; + + group.bench_with_input(BenchmarkId::new("scalar", label), &n, |b, _| { + b.iter(|| { + valid_from + .iter() + .zip(valid_to.iter()) + .filter(|(&vf, &vt)| vf <= black_box(ts) && black_box(ts) < vt) + .count() + }) + }); + + group.bench_with_input(BenchmarkId::new("simd", label), &n, |b, _| { + b.iter(|| { + simd_helpers::valid_time_filter_simd( + black_box(&valid_from), + black_box(&valid_to), + black_box(ts), + ) + }) + }); + } + + group.finish(); + } + + // ── simd_as_of: tx-time as-of filter ─────────────────────────────────── + // + // Synthetic data: tx_counts = 1..=n (monotonic counter). + // threshold = n/2 → 50% of facts pass the filter. + { + let mut group = c.benchmark_group("simd_as_of"); + group.sample_size(10); + + for &(label, n) in SCALES { + let n_u64 = u64::try_from(n).unwrap_or(u64::MAX); + let tx_counts: Vec = (1..=n_u64).collect(); + let threshold = n_u64 / 2; + + group.bench_with_input(BenchmarkId::new("scalar", label), &n, |b, _| { + b.iter(|| { + tx_counts + .iter() + .filter(|&&tc| tc <= black_box(threshold)) + .count() + }) + }); + + group.bench_with_input(BenchmarkId::new("simd", label), &n, |b, _| { + b.iter(|| { + simd_helpers::as_of_filter_simd( + black_box(&tx_counts), + black_box(threshold), + ) + }) + }); + } + + group.finish(); + } + + // ── simd_aggregate: i64 horizontal sum ───────────────────────────────── + // + // Synthetic data: values = 0..n as i64. + // Measures horizontal reduction performance. + { + let mut group = c.benchmark_group("simd_aggregate"); + group.sample_size(10); + + for &(label, n) in SCALES { + let n_i64 = i64::try_from(n).unwrap_or(i64::MAX); + let values: Vec = (0_i64..n_i64).collect(); + + group.bench_with_input(BenchmarkId::new("scalar", label), &n, |b, _| { + b.iter(|| black_box(&values).iter().copied().sum::()) + }); + + group.bench_with_input(BenchmarkId::new("simd", label), &n, |b, _| { + b.iter(|| simd_helpers::sum_simd_i64(black_box(&values))) + }); + } + + group.finish(); + } +} +``` + +- [ ] **Step 4: Register `bench_simd` in `criterion_group!`** + +Find the `criterion_group!` macro at the end of the file. Add `bench_simd` after `bench_predicate_pushdown`: + +```rust +criterion_group!( + benches, + bench_insert, + bench_insert_file, + bench_query, + bench_time_travel, + bench_recursion, + bench_negation, + bench_disjunction, + bench_aggregation, + bench_expr, + bench_window, + bench_temporal_metadata, + bench_udf, + bench_aggregation_extras, + bench_query_extras, + bench_open, + bench_checkpoint, + bench_concurrent, + bench_concurrent_file, + bench_concurrent_btree_scan, + bench_prepared, + bench_retract, + bench_btree_lookup, + bench_predicate_pushdown, + bench_simd, // Issue #229 +); +``` + +**Note:** `bench_simd` is defined under `#[cfg(not(target_arch = "wasm32"))]`. If the compiler complains about the `bench_simd` reference in `criterion_group!` being absent on WASM, wrap the entire criterion_group!/criterion_main! with the same cfg — but this is unlikely since `criterion` itself is already WASM-gated. + +- [ ] **Step 5: Verify the bench binary compiles** + +```bash +cargo build --benches 2>&1 | tail -5 +``` + +Expected: `Finished` with no errors. + +- [ ] **Step 6: Run just the SIMD benchmarks to verify they execute** + +```bash +cargo bench -- simd 2>&1 | grep -E "simd_|Benchmarking|error" | head -30 +``` + +Expected: Groups `simd_temporal`, `simd_as_of`, `simd_aggregate` all run and report timing numbers. No errors. + +- [ ] **Step 7: Run the full test suite to check for regressions** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 8: Commit** + +```bash +git add benches/minigraf_bench.rs +git commit -m "feat(bench): add simd_temporal, simd_as_of, simd_aggregate benchmark groups (#229)" +``` + +--- + +### Task 6: Run benchmarks and write `docs/simd-analysis.md` + +**Files:** +- Create: `docs/simd-analysis.md` + +Run the full benchmark suite for the new SIMD groups, collect results, and write the analysis document. This is the deliverable that closes issue #229. + +- [ ] **Step 1: Run all three SIMD benchmark groups** + +```bash +cargo bench -- simd 2>&1 | tee /tmp/simd_bench_results.txt +``` + +This will take several minutes (5 dataset sizes × 2 variants × 3 groups × ~10 samples each). Let it complete fully. + +- [ ] **Step 2: Also collect the existing time_travel results for comparison context** + +```bash +cargo bench -- time_travel 2>&1 | tee /tmp/time_travel_results.txt +``` + +These give the full-query costs for context. + +- [ ] **Step 3: Extract the mean ns/iter values from the output** + +From `/tmp/simd_bench_results.txt`, find lines like: +``` +simd_temporal/scalar/100 time: [XXX ns XXX ns XXX ns] +simd_temporal/simd/100 time: [XXX ns XXX ns XXX ns] +``` + +Record the middle (mean) value for each. Build a table with columns: group, variant, size, mean_ns. + +- [ ] **Step 4: Write `docs/simd-analysis.md`** + +Use the template below, filling in actual numbers from Step 3: + +```markdown +# SIMD Benchmarking Analysis (Issue #229) + +**Date:** 2026-05-16 +**Environment:** [fill in: CPU model, OS, Rust toolchain, wide version] +**Branch:** feature/issue-229-simd-benchmarking + +--- + +## Method + +Both scalar and SIMD benchmarks operate on synthetic numeric slices (not live DB facts — `Fact` internals are `pub(crate)`). The benchmarks isolate the hot kernel loop; extraction overhead is identical for both paths (none). For full-query costs, see the `time_travel/` group results below. + +--- + +## Results: simd_temporal (valid-time range filter) + +`valid_from[i] <= ts && ts < valid_to[i]` — ~50% selectivity + +| Size | Scalar (ns) | SIMD (ns) | Speedup | +|------|------------|-----------|---------| +| 100 | XXX | XXX | X.Xx | +| 1K | XXX | XXX | X.Xx | +| 10K | XXX | XXX | X.Xx | +| 100K | XXX | XXX | X.Xx | +| 1M | XXX | XXX | X.Xx | + +**Crossover point:** [first size where SIMD is faster, or "none observed at any tested size"] + +--- + +## Results: simd_as_of (tx-time as-of filter) + +`tx_count[i] <= threshold` — 50% selectivity. Note: uses `u64x2` (2-wide) — wide 0.7 has no `u64x4`. + +| Size | Scalar (ns) | SIMD (ns) | Speedup | +|------|------------|-----------|---------| +| 100 | XXX | XXX | X.Xx | +| 1K | XXX | XXX | X.Xx | +| 10K | XXX | XXX | X.Xx | +| 100K | XXX | XXX | X.Xx | +| 1M | XXX | XXX | X.Xx | + +**Crossover point:** [first size where SIMD is faster, or "none observed"] + +--- + +## Results: simd_aggregate (i64 horizontal sum) + +Sum of N i64 values via `i64x4` 4-wide reduction. + +| Size | Scalar (ns) | SIMD (ns) | Speedup | +|------|------------|-----------|---------| +| 100 | XXX | XXX | X.Xx | +| 1K | XXX | XXX | X.Xx | +| 10K | XXX | XXX | X.Xx | +| 100K | XXX | XXX | X.Xx | +| 1M | XXX | XXX | X.Xx | + +**Crossover point:** [first size where SIMD is faster, or "none observed"] + +--- + +## Post-#208 Residual Analysis + +After B+Tree selective lookup (#208), queries with bound entity or entity+attribute patterns +route through index-backed lookups rather than full fact scans. Typical residual fact counts +reaching the temporal filter after selective lookup (from `btree_lookup/entity_point` data): + +- Entity-point query on 1K facts: ~1 fact residual (index lookup, no filter needed) +- Entity-point query on 100K facts: ~1 fact residual +- Full-attribute scan on 100K facts: [N facts from btree_lookup/attribute_scan] + +For unbound queries (no selective lookup), all N facts reach the temporal filter. +SIMD gains apply to this case. + +--- + +## Full-Query Context + +From `time_travel/as_of_counter` and `time_travel/valid_at` (existing benchmarks): + +| Size | as_of_counter (ns) | valid_at (ns) | +|------|-------------------|---------------| +| 1K | XXX | XXX | +| 10K | XXX | XXX | +| 100K | XXX | XXX | +| 1M | XXX | XXX | + +The full query cost includes: fact loading, temporal filtering, pattern matching, result projection. +If temporal filtering is Z% of query cost, SIMD speedup of Sx translates to ~Z*(S-1)/S % query improvement. + +--- + +## Recommendation + +[Fill in ONE of the following:] + +**Integrate:** SIMD wins at sizes ≥ [N] which covers typical unbound-query workloads. Recommend +opening a follow-up issue to promote `simd_helpers` functions into production code paths in +`src/graph/storage.rs` (temporal filters) and `src/query/datalog/functions.rs` (sum aggregation). +Prerequisite: a struct-of-arrays storage layout change would allow zero-copy slice extraction. + +**Skip:** SIMD is slower or provides < 10% gain at all practical embedded sizes (≤ 100K facts). +LLVM autovectorization (enabled by `lto = true` and `codegen-units = 1` in release profile) already +captures most of the available gain. Recommend closing #229 without further SIMD work. + +**Revisit with SoA layout:** SIMD wins at ≥ [N] facts but extraction overhead (not measured here — +facts are struct-of-arrays-inaccessible from bench code) would dominate in production. A +struct-of-arrays storage layout change is a prerequisite for SIMD to pay off. Recommend opening +a separate issue to evaluate SoA storage before revisiting SIMD. +``` + +- [ ] **Step 5: Commit the analysis document** + +```bash +git add docs/simd-analysis.md +git commit -m "docs: SIMD benchmarking analysis and recommendation (#229)" +``` + +--- + +### Task 7: Full verification and PR + +**Files:** None (no new code changes unless a check fails) + +- [ ] **Step 1: Full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 2: Clippy clean** + +```bash +cargo clippy -- -D warnings 2>&1 | grep "^error" | wc -l +``` + +Expected: 0. + +- [ ] **Step 3: Format check** + +```bash +cargo fmt --check +``` + +Expected: no output. If there is a diff, run `cargo fmt` and commit `style: cargo fmt (#229)`. + +- [ ] **Step 4: Verify WASM build is unaffected** + +```bash +cargo build --features wasm --target wasm32-unknown-unknown 2>&1 | grep "^error" | wc -l +``` + +Expected: 0. (`wide` is in the non-WASM dev-deps only; WASM build should not even see it.) + +- [ ] **Step 5: Check commit log** + +```bash +git log main..HEAD --oneline +``` + +Expected: 5 commits (worktree excluded): +``` +docs: SIMD benchmarking analysis and recommendation (#229) +feat(bench): add simd_temporal, simd_as_of, simd_aggregate benchmark groups (#229) +feat(bench): add SIMD helper kernels for temporal filter and sum (#229) +chore: add wide 0.7 to non-WASM dev-dependencies (#229) +``` + +- [ ] **Step 6: Open PR** + +```bash +gh pr create \ + --title "feat(bench): SIMD benchmarking and crossover analysis (#229)" \ + --body "$(cat <<'EOF' +## Summary +- Adds `wide 0.7` as a non-WASM dev-dependency (zero production binary size impact) +- New `benches/simd_helpers.rs`: `valid_time_filter_simd`, `as_of_filter_simd`, `sum_simd_i64` with 10 unit tests +- Three new Criterion benchmark groups: `simd_temporal`, `simd_as_of`, `simd_aggregate` — each at 5 dataset sizes (100 → 1M), scalar vs SIMD side-by-side +- `docs/simd-analysis.md`: crossover findings and final recommendation + +Closes #229 + +## Test plan +- [ ] All existing tests pass (`cargo test`) +- [ ] 10 new unit tests for SIMD helpers (scalar equivalence) +- [ ] SIMD benchmark groups compile and run (`cargo bench -- simd`) +- [ ] `cargo clippy -- -D warnings` clean +- [ ] `cargo fmt --check` clean +- [ ] WASM build unaffected + +🤖 Generated with [Claude Code](https://claude.com/claude-code) +EOF +)" +``` + +- [ ] **Step 7: Monitor CI until green** + +```bash +gh pr checks --watch +``` + +Expected: all checks green. diff --git a/docs/superpowers/specs/2026-05-16-simd-benchmarking-design.md b/docs/superpowers/specs/2026-05-16-simd-benchmarking-design.md new file mode 100644 index 000000000..cb33350a7 --- /dev/null +++ b/docs/superpowers/specs/2026-05-16-simd-benchmarking-design.md @@ -0,0 +1,222 @@ +# Design: SIMD Benchmarking (Issue #229) + +**Issue**: #229 (SIMD vectorization evaluation) +**Date**: 2026-05-16 +**Branch**: single worktree + PR +**Prerequisite**: #208 (B+Tree selective lookup) — closed + +--- + +## Summary + +Evaluate whether explicit SIMD vectorization at the three highest-impact hot paths yields meaningful performance gains over the current scalar implementation, given Minigraf's embedded/small-dataset profile. The deliverable is benchmarks + a minimal SIMD prototype (bench-only) + a written crossover analysis and recommendation. + +**What ships:** +- `benches/simd_helpers.rs` — three SIMD functions using `wide` (dev-dependency) +- `benches/minigraf_bench.rs` — three new Criterion groups at 5 dataset sizes +- `docs/simd-analysis.md` — crossover findings and final recommendation (written after running benchmarks locally) + +**What does NOT ship:** +- No changes to any `src/` file +- No production SIMD code +- No feature flags + +--- + +## Targets + +Three hot paths identified after #208 (selective lookup reduces residual filter workload): + +| Target | Location | Pattern | +|---|---|---| +| Valid-time range filter | `src/graph/storage.rs` `get_facts_valid_at` | `valid_from <= ts && ts < valid_to` per fact | +| Tx-time as-of filter | `src/graph/storage.rs` `get_facts_as_of` | `tx_count <= n` per fact | +| Aggregation sum | `src/query/datalog/functions.rs` `apply_builtin_aggregate` | horizontal `i64`/`f64` reduction | + +--- + +## SIMD Helpers — `benches/simd_helpers.rs` + +All three functions use `wide` (added to `[dev-dependencies]` only — no binary size impact). + +> **Note for implementer**: Verify the exact `wide 0.7` API before coding — specifically `cmp_le`, `cmp_gt`, mask extraction via `Into<[T; 4]>`, and whether `u64x4` is available at that version. The pseudocode below shows intent; adapt to the actual API as needed. + +### `valid_time_filter_simd(valid_from: &[i64], valid_to: &[i64], ts: i64) -> Vec` + +Processes 4 facts at a time using `i64x4`. Returns indices of facts where `valid_from[i] <= ts && ts < valid_to[i]`. Scalar tail handles remainder when `len % 4 != 0`. + +```rust +pub fn valid_time_filter_simd(valid_from: &[i64], valid_to: &[i64], ts: i64) -> Vec { + use wide::i64x4; + let ts_v = i64x4::splat(ts); + let mut result = Vec::new(); + let chunks = valid_from.len() / 4; + for i in 0..chunks { + let base = i * 4; + let vf = i64x4::new([valid_from[base], valid_from[base+1], valid_from[base+2], valid_from[base+3]]); + let vt = i64x4::new([valid_to[base], valid_to[base+1], valid_to[base+2], valid_to[base+3]]); + // vf <= ts && ts < vt ↔ vf <= ts && vt > ts + let mask_lo = vf.cmp_le(ts_v); + let mask_hi = vt.cmp_gt(ts_v); + let mask = mask_lo & mask_hi; + let bits: [i64; 4] = mask.into(); + for (j, &b) in bits.iter().enumerate() { + if b != 0 { result.push(base + j); } + } + } + // scalar tail + for i in (chunks * 4)..valid_from.len() { + if valid_from[i] <= ts && ts < valid_to[i] { result.push(i); } + } + result +} +``` + +### `as_of_filter_simd(tx_counts: &[u64], threshold: u64) -> Vec` + +Processes 4 facts at a time using `u64x4`. Returns indices where `tx_counts[i] <= threshold`. + +```rust +pub fn as_of_filter_simd(tx_counts: &[u64], threshold: u64) -> Vec { + use wide::u64x4; + let thr_v = u64x4::splat(threshold); + let mut result = Vec::new(); + let chunks = tx_counts.len() / 4; + for i in 0..chunks { + let base = i * 4; + let tc = u64x4::new([tx_counts[base], tx_counts[base+1], tx_counts[base+2], tx_counts[base+3]]); + let mask = tc.cmp_le(thr_v); + let bits: [u64; 4] = mask.into(); + for (j, &b) in bits.iter().enumerate() { + if b != 0 { result.push(base + j); } + } + } + for i in (chunks * 4)..tx_counts.len() { + if tx_counts[i] <= threshold { result.push(i); } + } + result +} +``` + +### `sum_simd_i64(values: &[i64]) -> i64` + +Horizontal reduction using `i64x4` with wrapping add (matching Rust's default integer overflow behaviour in release mode). Accumulates 4 lanes in parallel, reduces at the end. + +```rust +pub fn sum_simd_i64(values: &[i64]) -> i64 { + use wide::i64x4; + let mut acc = i64x4::splat(0); + let chunks = values.len() / 4; + for i in 0..chunks { + let base = i * 4; + let v = i64x4::new([values[base], values[base+1], values[base+2], values[base+3]]); + acc += v; + } + let lanes: [i64; 4] = acc.into(); + let mut sum: i64 = lanes.iter().sum(); + for i in (chunks * 4)..values.len() { + sum = sum.wrapping_add(values[i]); + } + sum +} +``` + +--- + +## Benchmark Groups — `benches/minigraf_bench.rs` + +Three new groups, each with 5 dataset sizes: 100, 1K, 10K, 100K, 1M facts. + +### Timing scope (critical) + +- **Scalar baseline**: calls the production function directly (e.g. `storage.get_facts_valid_at(ts)`). The production function's internal extraction is measured as part of its cost. +- **SIMD variant**: field extraction from `Vec` into numeric slices **plus** the SIMD helper, all timed together inside the measurement loop. This reflects the full cost a production SIMD path would pay — if extraction overhead makes SIMD slower, that is the correct finding. + +### `bench_simd_temporal` + +`helpers::populate_temporal(n)` is a new benchmark helper (added in this PR) that inserts `n` facts with staggered `valid_from`/`valid_to` windows so roughly half pass a midpoint timestamp filter — realistic selectivity. `helpers::midpoint_timestamp` returns the median `valid_from` value. + +```rust +fn bench_simd_temporal(c: &mut Criterion) { + let mut group = c.benchmark_group("simd_temporal"); + for &n in &[100usize, 1_000, 10_000, 100_000, 1_000_000] { + let storage = helpers::populate_temporal(n); // new helper: staggered valid-time windows + let ts = helpers::midpoint_timestamp(&storage); + + group.bench_with_input(BenchmarkId::new("scalar", n), &n, |b, _| { + b.iter(|| storage.get_facts_valid_at(black_box(ts))) + }); + + group.bench_with_input(BenchmarkId::new("simd", n), &n, |b, _| { + b.iter(|| { + let facts = storage.get_all_facts(); + let vf: Vec = facts.iter().map(|f| f.valid_from).collect(); + let vt: Vec = facts.iter().map(|f| f.valid_to).collect(); + simd_helpers::valid_time_filter_simd(&vf, &vt, black_box(ts)) + }) + }); + } + group.finish(); +} +``` + +### `bench_simd_as_of` + +Mirrors `bench_simd_temporal` but: +- Scalar: `storage.get_facts_as_of(AsOf::Counter(black_box(threshold)))` +- SIMD: extract `tx_count` field into `Vec` + `as_of_filter_simd` +- `threshold` = median `tx_count` value (50th percentile — realistic as-of query) + +### `bench_simd_aggregate` + +- Dataset: N facts with `Value::Integer` attributes, pre-queried to `Vec` +- Scalar: production `apply_builtin_aggregate("sum", &values)` +- SIMD: extract `i64` values from `Vec` + `sum_simd_i64` +- Both timed including extraction (same rationale as above) + +--- + +## Analysis Document — `docs/simd-analysis.md` + +Written after running benchmarks locally on the development machine. Sections: + +1. **Environment**: CPU, OS, Rust toolchain, `wide` version +2. **Results table**: ns/iter (scalar vs SIMD) at each dataset size, per target +3. **Crossover point**: first dataset size where SIMD is faster, or "none observed" +4. **Post-#208 residual analysis**: typical fact counts reaching these filters after selective lookup (from `btree_lookup` benchmark data); contextualises the crossover within real workloads +5. **Recommendation**: one of: + - **Integrate**: SIMD wins at realistic dataset sizes → follow-up issue to promote helpers into `src/` + - **Skip**: SIMD slower or negligible at all practical sizes → close as not worth it + - **Revisit with SoA layout**: SIMD wins only at large N but extraction overhead dominates → document struct-of-arrays as prerequisite for SIMD to pay off + +--- + +## Cargo.toml change + +```toml +[dev-dependencies] +wide = "0.7" +# ... existing dev-dependencies +``` + +No change to `[dependencies]` — zero binary size impact. + +--- + +## Files Changed + +| File | Change | +|---|---| +| `Cargo.toml` | Add `wide` to `[dev-dependencies]` | +| `benches/simd_helpers.rs` | New: three SIMD functions | +| `benches/minigraf_bench.rs` | Add `bench_simd_temporal`, `bench_simd_as_of`, `bench_simd_aggregate` groups | +| `docs/simd-analysis.md` | New: crossover findings and recommendation (written last) | + +--- + +## Invariants + +- **No production code changes**: all SIMD code is in `benches/` +- **No feature flags**: `wide` is a dev-dependency; it never enters the release build +- **WASM portability unaffected**: `wide` has scalar fallbacks; since it's dev-only, WASM builds are unaffected +- **Existing benchmarks unchanged**: new groups are additive only