VQSelect/VQSort on aarch64/NEON: 2–4× slower than scalar on near-sorted input
- Dominant language
- C++
- Stars
- 5.8k
- Forks
- 471
- Avg merge
- 1d 6h
- Merged PRs (30d)
- 81
Description
Follow-up from the NaN work in #3098 / #3129:
I'm currently working on wiring `VQSelect` into NumPy's `np.partition` for aarch64/ppc64 (numpy/numpy#31506) and noticed that for near-sorted input `VQSelect` is slower than NumPy's scalar introselect. We are discussing adding a gate which i have prototyped (only call `VQSelect` when not nearsorted) for Numpy but we are wondering if a) this gate would be better suited to live in Highway and b) perhaps there is a better way to address the regression for Neon architectures instead of a gate/probe?
## Measurement
M1 Pro (NEON), `asv bench_function_base.Partition.time_partition`, `ARRAY_SIZE=100000`. **Ratio = VQSelect / scalar-introselect; <1 = VQSelect faster, >1 = slower.**
| dtype | random | reversed | uniform | ordered | sb/10 | sb/100 | sb/1000 |
|---|---|---|---|---|---|---|---|
| int16 | 0.09 | 0.08 | 0.07 | 0.61 | 0.18 | 0.16 | 0.20–0.23 |
| int32 | 0.34 | 0.12 | 0.14 | 1.17 | 0.61 | — | 0.47–0.86 |
| int64 | 0.57 | 0.20 | 0.25 | **2.01–2.07** | 1.05–1.08 | **1.66–1.76** | 0.81–1.42 |
| float32 | 0.45 | 0.25 | 0.35 | **2.71–2.74** | 0.79–0.84 | **1.73–1.78** | 0.78–1.85 |
| float64 | 0.70 | 0.38 | 0.40 | **4.00–4.04** | 1.34–1.42 | **2.55–2.58** | 1.24–2.68 |
(`sb/N` = `sorted_block`, sorted runs of length N.) Big wins on disordered input, but `float64 ordered` is **4×** slower and `sorted_block` up to 2.6× slower; float32/int64 show the same shape.
## Why it looks architectural
On NEON, the partition hot loop (`StoreLeftRight` → `CompressStore`) has no hardware compress. Highway emulates it with a shuffle-index table + byte lookup (`arm_neon-inl.h`) and NEON lacks a movemask too. NEON is also 128-bit (`Lanes(double) == 2` vs 8 on AVX-512). So the vector partition does more work per element than on a hardware-compress, wide-vector target, enough that scalar introselect wins on near-sorted input. (I haven't isolated width vs compress-emulation)
I don't see how to close NEON's raw throughput. It can't be widened, Apple Silicon has no SVE, and Highway's vqsort disables itself on scalable SVE anyway (only fixed 128-bit `SVE2_128` stays vectorized, per `shared-inl.h`). But may be wrong...
Contributor guide
Research direction
Start by reproducing the reported ratios with asv bench_function_base.Partition.time_partition across the listed near-sorted inputs. Trace VQSelect through StoreLeftRight and CompressStore, then inspect the NEON shuffle and byte-lookup path in arm_neon-inl.h and the target behavior described in shared-inl.h. Done means determining whether a Highway change or a caller-side gate is appropriate and measuring its effect without losing the disordered-input gains.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100