google / google/highway

SVE: is the clang-only Min workaround still needed? it costs 26-40% of VQSort time on SVE2-128

Open
#3,336 2 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

`hwy/ops/arm_sve-inl.h` overrides `Min` for clang only:

```cpp
// Workaround for incorrect results with `svmin`.
#if HWY_COMPILER_CLANG
template
HWY_API V Min(V a, V b) { return IfThenElse(Lt(a, b), a, b); }
template
HWY_API V Min(V a, V b) { return IfThenElse(Or(Lt(a, b), Ne(b, b)), a, b); }
#else
HWY_SVE_FOREACH_I(HWY_SVE_RETV_ARGPVV, Min, min)
HWY_SVE_FOREACH_F(HWY_SVE_RETV_ARGPVV, Min, minnm)
#endif
```

It came in via #2595 (merged 2025-06-16) to fix real SVE test failures under clang. My question
is whether its still needed because its expensive and its
on VQSort's hot path.

I filed llvm/llvm-project#214554 for clang-built VQSort being about 1.5x slower than
gcc-built on SVE2-128. @davemgreen looked at it and pointed at this `Min` difference as part of the
gap.

All of this is on Compiler Explorer with highway trunk from their own library set, so its not my
tree and not my flags. clang trunk 24.0.0git (4c176c47d8be), `-O3 -march=armv9-a+sve2
-msve-vector-bits=128`. Everything below is pasted from those links.

`Min` on its own, with `Max` next to it for contrast: https://godbolt.org/z/earY84xTz

```asm
f64 Min (clang branch) f64 Max (native, not overridden)
ptrue p0.d ptrue p0.d
fcmgt p1.d, p0/z, z1.d, z0.d fmaxnm z0.d, p0/m, z0.d, z1.d
fcmne p0.d, p0/z, z1.d, z1.d ret
mov p0.b, p1/m, p1.b
sel z0.d, p0, z0.d, z1.d
ret

i64 Min (clang branch) i64 svmin_s64_x, same compiler
ptrue p0.d ptrue p0.d
cmpgt p1.d, p0/z, z1.d, z0.d smin z0.d, p0/m, z0.d, z1.d
sel z0.d, p1, z0.d, z1.d ret
ret
```

5 instructions instead of 2 on floats, 3 instead of 2 on ints, and `Max` stays a single `fmaxnm`
either way. f32 and i32 have the same shape. gcc trunk on the same source takes the `#else` branch
and gives you `ptrue` + `fminnm`: https://godbolt.org/z/Yfbd9rend

the float branch builds a 3 deep predicate chain, `fcmgt`
and `fcmne` both feed the combine which feeds `sel`. sorting network nodes are chained so that
latency compounds.

Per-op numbers overstate Sort2 node cost on their own since the surrounding node shares work, so heres the real
`TraitsLane>::Sort2` against the same node written with the `#else` branch's
intrinsics. same compiler, same flags: https://godbolt.org/z/Kz6a74WTq

```asm
Sort2, as highway compiles it today Sort2 with svminnm/svmaxnm
ldr z0, [x0] ldr z0, [x0]
ldr z1, [x1] ldr z1, [x1]
ptrue p0.d ptrue p0.d
fcmgt p1.d, p0/z, z1.d, z0.d movprfx z2, z0
movprfx z2, z0 fminnm z2.d, p0/m, z2.d, z1.d
fmaxnm z2.d, p0/m, z2.d, z1.d fmaxnm z0.d, p0/m, z0.d, z1.d
fcmne p2.d, p0/z, z1.d, z1.d str z2, [x0]
sel p1.b, p1, p1.b, p2.b str z0, [x1]
sel z0.d, p1, z0.d, z1.d ret
str z0, [x0]
str z2, [x1]
ret

12 instructions 9 instructions
```

(both counts include the 2 loads, 2 stores and the ret, which the real inlined node doesnt pay.
theyre identical in both arms so the delta is the same either way.)

`Sort2`'s own comment says "Min/Max are cheaper than compare + blend at least for integers", which
is the premise the clang branch removes. The asymmetry is the part I find interesting, `First` ->
`Min` takes the override and `Last` -> `Max` doesnt, so every node pays for one native op and one
reconstructed one.

end to end cost on the Same highway tree, same clang, one line changed: `#if HWY_COMPILER_CLANG` -> `#if 0` at
`arm_sve-inl.h:2065`, leaving the sibling `svabs` workaround alone. sorting 2,000,000 keys with
`VQSortStatic` on one Cortex-X925 core (NVIDIA GB10, SVE2-128), built with `--no-default-config`
so nothing from a config file is in play, 12 passes with the arm order rotated, 960 timed sorts.

type workaround ON workaround OFF ON is slower by A/A floor
f64 39.295 ms 31.109 ms +26.3 % -0.10 %
f32 18.864 ms 13.453 ms +40.2 % -0.13 %
i64 31.154 ms 29.687 ms +4.9 % -0.14 %
i32 13.746 ms 12.794 ms +7.4 % +0.12 %

The A/A column is the same binary run under two labels in the same interleaved schedule, so the
float effect is a couple hundred times the noise floor. per sample CV was 0.33 to 0.49% on every
arm. I ran the whole thing a second time under a very different optimization pipeline as a cross check, and f64/i64/i32 agree within 0.7 points and f32
comes out at +32.4% there instead of +40.2%, so its not a flag artfact.

Whole binary census across the two arms: 433 `Min` sites and 433 `Max` sites, and disabling the
workaround removes 1014 instructions (11242 -> 10228), `sel` drops from 1361 to 79. the float
penalty is the bigger one because only the float branch adds the `Ne(b, b)` term.

One reproduction note in case anyone tries this `shared-inl.h:158` turns VQSort off entirely on
scalable SVE targets, `(HWY_TARGET & HWY_ALL_SVE) && HWY_HAVE_SCALABLE -> VQSORT_ENABLED 0`, and
`Sort` falls back to HeapSort which never calls `Min`. so an A/B without `-msve-vector-bits` builds
both arms byte identical and shows nothing at all. mine did, the first time.

This is not a correctness result. the disabled-workaround arm sorted all 240 arrays correctly but
the corpus has no NaNs in it, so it never touches the branch the workaround exists for. I havent
run highway's own sort_test/ops suite with the `#if` disabled and thats the thing that would
actually settle it.

For what its worth both intrinsics look fine on clang 24 in direct tests, `svminnm_f64_x(1.0, NaN)`
-> 1.0, `svminnm_f64_x(5.0, 2.0)` -> 2.0, `svmin_s64_x(-5, 3)` -> -5, `svmin_s64_x(7, -9)` -> -9.
thats two spot checks on one clang version at one vector length though, so its a hint and not a
result.

Does #2595 have an LLVM bug number, or a minimal repro that could be re-run against clang 24? if
the underlying miscompile is fixed then dropping the override is worth 26-40% of VQSort time on
SVE2 floats. if its still latent then it should probably be filed against LLVM, and either way
narrowing the workaround (ints only, or a version guard) would get most of the cost back.

Contributor guide

Open the contributing guide

Research direction

Start in hwy/ops/arm_sve-inl.h around line 2065 and review the Min workaround introduced by #2595, then run the highway sort_test/ops suite with the override enabled and disabled, including NaN cases. Check #2595 for an LLVM bug number or minimal reproducer and compare results on the stated clang SVE configuration. Done means the workaround’s necessity is established and any narrowing or removal is backed by correctness tests and performance measurements.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.