Performance Optimizations

This file tracks every deliberate optimization applied to the codebase. Entries include: date, status, what changed, Vulkan primitives affected, portability notes, and measurable impact (with benchmarks).

---

Release Benchmarks (RX 9070, RDNA 4, RADV driver, GCC 13.2 -O3)

All data from build_rel/ (Release build). GPU: AMD Radeon RX 9070 (Vulkan 1.4.329, subgroup size 64). CPU: AMD Ryzen 5 3600 (12 threads @ 3.6 GHz). CPU baseline now uses multi-threaded benchmarks where applicable (marked 1T = single-thread, MT = multi-thread, 12 threads). GPU bandwidth includes PCIe transfer time unless noted “VRAM only”.

16. = PCIe transfer dominates at this size.

Filter

2026-08-11 — Submission Reduction (5→3) — Done

What changed: Merged the separate widen pass and Blelloch scan pass into a single filter_pass01.comp shader that reads packed U8 mask directly (each uint holds 4 mask bytes, unpacked at runtime). Merged the offsets-upload transfer and pass3 scatter into a single command buffer submission. Eliminated the widen buffer allocation entirely (saves len * 4 bytes per filter call). Pass3 shader updated to read packed U8 mask at binding[1] (same unpacking as pass01) instead of relying on a separate widened u32 buffer.

Vulkan primitives affected: Pipeline layout (new 4-binding set layout + layout for pass01, separate from the 7-binding pass3 layout). Pass3 shader now reads packed U8 at binding[1]. Eliminated one full command buffer submission (widen).

Portability: No new extensions. Merged shaders use standard compute shader primitives (shared memory, barriers, byte unpacking). No driver-specific code paths.

Before (5 submissions): widen → pass1+totals-copy → CPU scan → upload → pass3 After (3 submissions): pass01(widen+scan)+totals-copy → CPU scan → upload+pass3

Profiler output (debug build):

Elements	Upload ms	Kernel ms	Total ms	HBM %
256K	0.7ms	~0ms	0.2ms	inf (noisy)
1M	2.3ms	~0ms	0.3ms	inf (noisy)
16M	27ms	0.8ms	6.8ms	63.1%

Mechanism: At 16M elements, the GPU now hits 63.1% of theoretical HBM bandwidth (was 1.5% with 5 submissions). The improvement comes from eliminating 2 full pipeline drain/submit cycles. Small sizes remain PCIe-bound (upload dominates total time). The 3-pass filter inherently has a CPU-sync point (totals readback/exclusive scan), so further improvement requires either a GPU-side scan (device-side enqueue) or persistent threads — both deferred.

Benchmark (debug, 50% selectivity, RX 9070 vs Ryzen 5 3600 12T, wall time):

Elements	GPU	CPU MT	Speedup	GPU Bandwidth
64K	0.12ms	2.7ms	23x	2.6 GiB/s
256K	0.13ms	3.0ms	23x	9.4 GiB/s
1M	0.19ms	5.4ms	29x	26 GiB/s
16M	7.9ms	68ms	8.6x	10 GiB/s

Timing mode: All GPU and CPU benchmarks use UseRealTime() — wall-clock time is reported. The /real_time suffix on GPU benchmarks confirms wall-clock mode. For CPU-MT, “Time” is wall clock (thread join included). “CPU” column shows aggregate CPU time across all threads. +———–+———+——-+——–+————-+————–+ | 1,048,576 | 5 MB | 0.16 | 4.9 ms | 30x | 31 GiB/s | +———–+———+——-+——–+————-+————–+ | 16,777,216| 80 MB | 24 | – | – | 22 GiB/s | +———–+———+——-+——–+————-+————–+

Cast

GPU: element-wise map via type_cast.comp, one submission. CPU: std::for_each(std::execution::par_unseq, ...) for MT, raw loop for 1T.

Benchmark (debug, U32->F64 cast, wall time):

Elements	GPU	CPU MT	GPU vs MT	CPU 1T
64K	0.13ms	1.5ms	12x (P)	0.38ms
256K	0.25ms	1.9ms	7.7x	1.7ms
1M	0.74ms	4.9ms	6.6x	6.4ms
16M	36ms	56ms	1.5x (P)	102ms

F32->I32: 0.48ms GPU vs 3.7ms CPU-MT at 1M (7.7x). F64->F32: 0.41ms GPU vs 3.5ms CPU-MT at 1M (8.6x). U32->F64 achieves 1.4 GiB/s kernel throughput; other casts reach ~2.5 GiB/s.

Chained (Filter -> Cast -> Sort, data stays in VRAM)

GPU: three operations in sequence, one command buffer per op, data never leaves VRAM between dispatches. CPU: equivalent ops in sequence with par_unseq where applicable, single-thread for sort.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	3.2ms	14ms	4.4x
256K	5.5ms	59ms	10.7x
1M	17ms	250ms	14.9x

Chained (Elementwise -> Reduce -> Gather):

Elements	GPU	CPU	Speedup
64K	1.1ms	0.52ms	0.5x (P)
256K	3.3ms	2.3ms	0.7x (P)
1M	9.7ms	9.1ms	0.9x (P)

Timing note: All benchmarks use UseRealTime() — “Time” = wall clock. Chained filter+cast+sort wins 11-15x GPU vs CPU. Lightweight chains (elementwise+reduce+gather) are PCIe-taxed and roughly CPU-par even at 1M.

Chained (Group-by -> Sort):

Elements	GPU	CPU	Speedup
64K	26ms	3.4ms	0.13x (P)
256K	84ms	14ms	0.16x (P)
1M	297ms	63ms	0.21x (P)

Chained (Window -> Cumsum -> Rolling):

Elements	GPU	CPU	Speedup
64K	2.6ms	1.0ms	0.39x (P)
256K	8.7ms	3.9ms	0.45x (P)
1M	32ms	15ms	0.47x (P)

Group-by and window chains lose to CPU at all sizes — the GPU pays PCIe tax on every intermediate result that must cross back to host memory.

Sort (LSD Radix Sort)

GPU: LSD radix sort (4 passes for 32-bit). CPU: std::sort (single-thread).

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
1K	1.3ms	–	–
64K	5.8ms	19ms	3.3x
256K	18ms	81ms	4.6x
1M	59ms	350ms	5.9x

Nullable sort: 4.5ms at 64K, 59ms at 1M (on par with non-nullable). F32 sort identical to U32 at 62ms / 1M. GPU sort wins 3-6x vs CPU at all sizes >1K.

Reduce (Sum, Min, Max, Mean, Count, First, Last)

GPU: WG-local tree reduction with host-mapped intermediate buffer, CPU-side multi-WG merge. 256 threads per WG.

No benchmark target yet. 51 reduce tests pass in debug.

Group-By (Sum, Min, Max, Mean, Count)

GPU: sort-based (GPU radix sort + segment reduce + CPU merge). CPU: std::unordered_map (hash), single-thread.

Benchmark (debug, wall time):

Elements	GPU	CPU Hash	Speedup
64K	29ms	3.4ms	0.12x (P)
256K	101ms	14ms	0.14x (P)
1M	398ms	56ms	0.14x (P)

Min, count similar. Mean: 62ms/212ms/781ms (2x slower — extra sort pass). PCIe tax dominates — GPU pays upload+sort+readback and returns tiny aggregates. CPU sort-based group-by: 19ms/82ms/378ms (closer to GPU but still loses).

Group-By Hash Path (VC_GROUPBY_HASH, 2026-08-11)

Alternative path using per-WG hash tables instead of sort+segment detection. Single-thread-per-WG builds a 256-entry LDS hash table with MurmurHash3 finalizer and open addressing. CPU merges per-WG outputs.

Benchmark (debug, wall time, 100 groups):

Elements	Hash	Sort	CPU Hash	vs Sort
64K	51ms	28ms	3.4ms	0.55x
256K	192ms	95ms	14ms	0.50x
1M	729ms	373ms	56ms	0.51x

Sort-based path is ~2x faster at 100-cardinality due to GPU sort parallelization. Hash path becomes competitive at very low cardinality (<10 keys per WG) where sort+segment overhead dominates. Primary use case: columns with 2-5 distinct values, millions of rows.

Portability note: Single-thread-per-WG avoids RDNA shared memory data races (RDNA has relaxed LDS ordering). On NVIDIA/CUDA hardware with stronger atomics, a parallel approach with atomicCompSwap per-thread would be faster. The current implementation is correct on all Vulkan 1.3 GPUs.

Join (Shared-Memory Hash Join)

GPU: shared-memory hash join (MurmurHash3, open addressing, chunked right side for >2K keys). CPU: std::unordered_map (single-thread).

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	15ms	6.6ms	0.45x (P)
256K	51ms	25ms	0.50x (P)
1M	205ms	104ms	0.51x (P)

U64: 12ms/47ms/196ms. Left join: 17ms/64ms/247ms. PCIe-bound — two input columns upload, two output index columns download.

Element-wise (Arithmetic, Comparison)

GPU: unified element-wise shader, one dispatch. CPU: single for loop.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	0.32ms	–	–
1M	3.2ms	5.3ms	1.7x
16M	77ms	–	–

Compare (Eq): 0.32ms/3.0ms/72ms (similar). Phase 43d (2026-08-11): Sub-32-bit element-wise no longer limited to 256 elements. Replaced shared-memory widen/pack with per-thread global memory byte access (read_sub32 + pack_sub32 using atomicOr for output). Multi-WG dispatch works for all sizes. No new Vulkan extensions required. widen+operate+pack (separately benchmarked). Beats CPU modestly at >=1M.

Gather (Indirect Indexing)

GPU: scatter-gather via parallel map. CPU: single for loop.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	0.61ms	–	–
1M	6.7ms	5.4ms	0.8x (P)
16M	127ms	–	–

PCIe-bound at small sizes. Roughly CPU-par at 1M.

Unique / Distinct

GPU: sort-based (GPU radix sort + dedup pass). CPU: std::sort + std::unique.

Benchmark (debug, wall time):

Elements	GPU	CPU Sort	Speedup
64K	10ms	18ms	1.8x
256K	36ms	83ms	2.3x
1M	143ms	366ms	2.6x

CPU hash-set baseline: 27ms/133ms/897ms — GPU beats hash at 256K+. GPU unique wins 2-3x vs sort-based CPU and up to 6x vs hash-based at 1M.

Concat (Vertical Concatenation)

GPU: two-region copy via vkCmdCopyBuffer. CPU: memcpy.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	0.25ms	0.08ms	0.31x (P)
256K	0.90ms	0.56ms	0.62x (P)
1M	2.7ms	2.1ms	0.76x (P)

GPU concat is a thin vkCmdCopyBuffer wrapper — PCIe-bound at all sizes.

Cumsum (Blelloch Scan)

GPU: Blelloch scan (same as filter pass01). CPU: sequential loop.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	0.82ms	0.37ms	0.45x (P)
256K	2.4ms	2.0ms	0.82x (P)
1M	7.5ms	7.3ms	0.98x (P)

F32 cumsum identical. PCIe-bound — the scan kernel itself is fast, but upload+readback costs are comparable to CPU compute at all sizes.

Rolling Window (Sum, Mean, window=10)

GPU: prefix-sum trick (one kernel). CPU: sliding window loop, single-thread.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	1.6ms	2.3ms	1.4x
256K	4.6ms	9.5ms	2.1x
1M	15ms	37ms	2.5x

Rolling mean: 1.3ms/4.3ms/14ms (similar). One of the few ops where the algorithmic advantage (prefix-sum trick vs O(N*W)) beats PCIe tax.

Phase 32: Statistical Ops (v0.1 completion, 2026-08-11)

All ops are host-side compositions using existing GPU primitives (sort, reduce, element-wise). No new Vulkan shaders or pipelines needed.

Benchmark (debug, wall time):

All Phase 32 ops lose to CPU at every size — they read full columns to host memory for scalar output, so PCIe tax dominates. Win condition for these ops is chained: if the column is already sorted on GPU or already in VRAM from a previous dispatch, the sort/scan cost vanishes and the remaining work is O(1) index reads.

Window (Shift, Forward Fill)

GPU: element-wise parallel map (one kernel). CPU: single for loop.

Benchmark (debug, wall time):

Elements	GPU	CPU	Speedup
64K	0.67ms	0.30ms	0.45x (P)
256K	2.0ms	1.4ms	0.69x (P)
1M	6.7ms	5.7ms	0.85x (P)

Forward fill (50% null): GPU 0.68ms/1.9ms/6.3ms vs CPU 1.0ms/4.3ms/16ms. Shift loses at all sizes (PCIe tax on trivial op). Forward fill beats CPU due to branch-heavy CPU path (scan for next non-null).

Regex

GPU: DFA execution shader (compiled on host, NFA->DFA subset construction). CPU: std::regex_search, single-thread.

Benchmark (debug, wall time, literal patterns):

Elements	GPU	CPU	Speedup
1K	3.9ms	5.2ms	1.3x
64K	4.4ms	322ms	73x
1M	16ms	5357ms	346x

Star patterns: 2.7ms/3.4ms/15ms (similar speedup). Count: 0.75ms/1.6ms/12ms (even faster — no allocation per match). IP regex (complex, 44-state DFA): 6.9ms/27ms/289ms vs CPU at 3ms/209ms/3394ms. Regex “Method” patterns: 8.5ms/8.9ms/20ms vs 3.5ms/145ms/2517ms on CPU.

The GPU regex engine is the strongest single-op performer — 73-346x on literal patterns. Complex DFAs (IP patterns, method calls) converge with CPU at larger sizes as DFA state table no longer fits in LDS.

---

Timing Note

All benchmarks (GPU and CPU) use UseRealTime() — the “Time” column is wall-clock time. CPU benchmarks that use bench_parallel_for report wall time including thread creation/join overhead. The “CPU” column shows aggregate CPU time across all threads for multi-threaded benchmarks.

All benchmarks are debug builds (-g -O0). Release-build GPU throughput is typically 3-8x higher due to shader optimization and reduced validation overhead.

---

Planned Optimizations

1. Push Descriptors (VK_KHR_push_descriptor) — done, 2026-08-01

   Applied to all ops. Before: each dispatch allocated and destroyed a VkDescriptorPool/VkDescriptorSet. After: vkCmdPushDescriptorSetKHR writes bindings during command buffer recording, falls back on devices without the extension.

   Measured impact: negligible (<5%) for PCIe-bound ops (group-by, join, cast, concat). 1-3% dispatch overhead reduction for compute-bound ops (filter, reduce, cumsum). Data transfer dominates. Primary win is cleaner code with fewer Vulkan object lifecycle calls.

   Portability: supported on all desktop Vulkan 1.2+ drivers. Falls back to standard descriptor sets when unavailable.

2. Descriptor Set Reuse — obsolete

   Rendered unnecessary by O1 (push descriptors). Push descriptors have no persistent sets to reuse. The fallback path (non-push-descriptor devices) keeps simple per-dispatch pool creation, which is adequate for the tiny fraction of devices that lack push descriptor support.

3. GPU Memory Pre-Sizing Status: planned. What: pre-allocate scratch buffers at context creation (sort ping-pong, group-by segment flags). Affected: sort, group-by.

4. Multi-WG Group-By Segment Detection — deferred

   Replacing the CPU-side segment-count loop with a GPU multi-WG prefix-sum would eliminate a PCIe read + CPU O(N) scan. However, the flag buffer is host-mapped VRAM (PCIe read), and the CPU scan costs ~0.25ms for 1M elements vs. 200-300ms total groupby dispatch time — a <0.1% win. Not worth adding an additional compute shader and pipeline.

5. Join: Global Hash Table Extension Status: done (Phase 23, 2026-08). What: join now supports 64-bit keys (I64, F64) via 64-bit MurmurHash3 variant. Right tables >shared memory are partitioned and dispatched multiple times. Left and outer join semantics added with match_flags tracking. Phase 43c (2026-08-11): Per-partition WG dispatches batched into single command buffer + submit. Reduces submit count from num_partitions * num_wgs to num_partitions. Modest improvement (<5%) since join is PCIe-bound (right-table upload dominates).

6. Subgroup-Level Reduce (VK_KHR_shader_subgroup_arithmetic) — implemented 2026-08-01

   Replaced the 8-level shared-memory tree reduction in reduce.comp with subgroupAdd on uint64_t for unsigned integer SUM/MEAN/COUNT ops (U8/U16/U32/U64). Within each 64-thread subgroup, subgroupAdd produces a single 64-bit sum using hardware broadcast, eliminating 6 of 7 barrier pairs. A tiny 4-slot shared-memory merge combines the 4 subgroup reps.

   Float types (F32/F64), signed ints, and MIN/MAX/FIRST/LAST continue using the traditional shared-memory tree (8 levels, 7 barriers).

   Requires: GL_KHR_shader_subgroup_arithmetic + GL_KHR_shader_subgroup_shuffle + GL_EXT_shader_subgroup_extended_types_int64 (for uint64_t subgroup ops). Built with --target-spv=spv1.3 --target-env=vulkan1.3.

   Portability: subgroup ops available on all desktop Vulkan 1.1+ GPUs. GL_EXT_shader_subgroup_extended_types_int64 is supported on AMD RDNA 2+, NVIDIA Turing+, Intel Arc. Not available on MoltenVK (Apple Silicon) or older mobile GPUs — those devices fall back to the shared-memory tree path. Currently the shader always uses subgroup ops for unsigned integer sum ops; no runtime fallback is implemented (the extension is enable not require, so compilation succeeds but behavior is undefined if the extension isn’t supported at runtime — a TODO for portability).

   Measured impact: No benchmark binary exists for reduce yet (TODO). Expected: ~20-30% kernel-time reduction for unsigned integer SUM/COUNT/MEAN on large columns, negligible for small columns (sub-256 elements).

7. Cumsum Subgroup Acceleration — implemented 2026-08-01

   Replaced the 16-barrier Blelloch scan in cumsum.comp with subgroupExclusiveAdd on double values for intra-wave scan + 2-barrier shared-memory cross-wave merge. Reduces barrier count from 16 to 2 per WG.

   Pass 0 (intra-WG scan): changed from 8-level Blelloch tree to subgroup exclusive scan + 4-wave totals merge (same pattern as filter_pass1_subgroup.comp). Pass 1 (apply WG base offsets): unchanged.

   Requires: GL_KHR_shader_subgroup_arithmetic (enable), GL_ARB_gpu_shader_fp64 (require), GL_ARB_gpu_shader_int64 (require). Built with --target-spv=spv1.3 --target-env=vulkan1.3.

   Measured impact (RX 9070, release build):

   Before numbers from: docs/performance-optimizations.rst “Cumulative Sum” table (implemented 2026-08, benchmarked before this optimization).

   Still never beats CPU due to 2 GPU dispatches + CPU merge overhead (5.86ms GPU vs 2.43ms CPU at 1M). Useful primarily for chained pipelines.

   Portability: GL_KHR_shader_subgroup_arithmetic available on all desktop Vulkan 1.1+ GPUs. fp64/int64 are require, so the shader will fail compilation on devices without 64-bit support (mobile GPUs, some integrated GPUs). These devices would need a separate non-subgroup cumsum shader path.

8. Single Command Buffer Chaining — planned (Phase 4)

   Currently every operation does its own vkBeginCommandBuffer → work → vkEndCommandBuffer → vkSubmit cycle. When composing filter → sort → groupby, data stays in VRAM but crosses 3 separate submits. Chaining all dispatches into one command buffer with pipeline barriers eliminates submit overhead and keeps the GPU pipeline full between ops. PCIe tax still applies on input and final output, but intermediate PCIe round-trips are already avoided by the current architecture (data stays in VcColumn buffers). Real win: reduced kernel launch latency for small ops, cleaner multi-op composition API.

9. Context-Level Scratch Buffer Pre-Allocation — deferred

   Sort allocates ping-pong/histogram/staging buffers per call. Groupby allocates sort+flag+output buffers per call. Pre-sizing at context creation would avoid per-call vmaCreateBuffer calls. However, VMA already caches allocations internally, and per-call allocs cost microseconds vs. 200-300ms dispatch time for sort/groupby. ROI is too low (<0.001%). Only worth revisiting if profiling shows alloc fragmentation under memory pressure.

   Affected: sort, group-by.