Stream Compaction on NEON: Hand-Vectorizing copy_if
NEON lacks a compress instruction, so compilers can't vectorize copy_if. This piece shows how tbl-based lookup tables restore SIMD throughput with a 30x speedup.
Copying only the elements of an array that satisfy a condition (copy_if) sounds trivial, but it defeats compilers: because the output cursor is data-dependent, clang can't classify it as an induction or reduction variable, so the loop stays scalar. Benchmarks on Apple M5 show that an unconditional copy hits 112 GB/s, while a poorly-predicted (50/50) branch inside the loop collapses throughput to as low as 2.6 GB/s.
The root cause is that NEON, unlike x86 SIMD, has no compress instruction to pack selected elements without gaps. This piece walks through building one by hand using the tbl (table lookup) instruction: the mask register is first turned into a small integer index, then a precomputed set of 16 index and count tables (generated at compile time) is used to permute bytes so selected floats end up packed at the front of the register — effectively emulating x86's pshufb-based compress trick, but on NEON's more limited instruction set.
The resulting compress_neon routine returns both the packed register and the number of valid elements, letting the copy_if loop become fully vectorizable and reclaim most of the lost throughput (up to 30x versus the naive scalar branch). It's a concrete, low-level reference for systems programmers optimizing branch-heavy filtering code on Apple Silicon and other ARM/NEON cores.