Parallel radix sort for large render queues
authorSvjatoslav Agejenko <svjatoslav@svjatoslav.eu>
Sun, 20 Sep 2026 02:29:37 +0000 (05:29 +0300)
committerSvjatoslav Agejenko <svjatoslav@svjatoslav.eu>
Sun, 20 Sep 2026 02:29:37 +0000 (05:29 +0300)
commit618ff60e06a2a91c3caffe58ac19d9ff45b61190
tree4539e2418a7849647a2f3dcaa9fb6393d9f52f24
parent766d099fa2299cb31851eb4c791063e68db1a464
Parallel radix sort for large render queues

The radix path now uses the paint executor: key build, the 8 LSD passes
(per-chunk histograms, digit-major/chunk-minor offsets, per-chunk
scatter) and the final permute all run chunked in parallel. Stability is
preserved exactly, so the output is bit-identical to the serial sort for
any chunk count (pinned by a new RadixLongSortTest property test over
sizes 0..250k x chunk counts 1..8) — golden-image determinism intact.

Also deletes the now-unreachable parallelMergeSort/runSortTasks/
mergeRuns (~100 LOC) and routes the no-executor (headless) path through
the serial radix instead of Arrays.parallelSort.

Measured on a 24-core desktop (450k pairs, SortBench/SortSweep harnesses):
sort phase ~7 ms serial -> ~4-5 ms parallel (1.2-1.8x; bandwidth-bound,
frequency-capped test machine). Key-build/permute parallelization comes
on top in the full pipeline.
src/main/java/eu/svjatoslav/aukio/e3d/renderer/raster/RadixLongSort.java
src/main/java/eu/svjatoslav/aukio/e3d/renderer/raster/RenderAggregator.java
src/test/java/eu/svjatoslav/aukio/e3d/renderer/raster/RadixLongSortTest.java