google / google/highway

VQSelect/VQSort on aarch64/NEON: 2–4× slower than scalar on near-sorted input

Open
#3,139 4 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.