numpy / numpy/x86-simd-sort

argsort: the `is_sorted` early exit calls its comparator through a function pointer when `descending` is a runtime value

Open
#240 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C++
Stars
1k
Forks
74
PR merge metrics
No merged PRs in 30d

Description

AI disclosure: found and drafted with the help of Claude Code

The early exit added in #197 selects the comparator with a runtime conditional (xss-common-argsort.h#L630-L632):

auto comp = descending ? Comparator<vectype, true>::STDSortComparator
                       : Comparator<vectype, false>::STDSortComparator;
if (std::is_sorted(arr, arr + arrsize, comp)) { return; }

comp is a function pointer. If descending is a compile-time constant at the call site (static header API, everything inlined) the compiler can see through it and inline the comparison into the is_sorted loop. If descending is a runtime value it cannot, and the scan makes an indirect call per element. For input that is already sorted the scan is the whole cost of the call, so this is directly visible.

I ran into this in numpy/numpy#32690, which started forwarding NumPy's runtime descending flag to x86simdsortStatic::argsort instead of relying on the default false. That slowed down ascending argsort of sorted input. np.argsort, n = 1M, gcc 14.2, AVX2 (i7-13650HX), minimum over alternating runs of the two builds:

input descending constant descending runtime
int32, already sorted 0.97 ms 1.34 ms +38%
float64, already sorted 1.45 ms 1.85 ms +27%
int32, reversed (no early exit, control) 19.3 ms 19.5 ms +1%

A fix inside the library could be to select the scan instead of the comparator, so each is_sorted instantiation has a comparator known at compile time, e.g. (untested):

bool sorted = descending
        ? std::is_sorted(arr, arr + arrsize, [](const T &a, const T &b) {
              return Comparator<vectype, true>::STDSortComparator(a, b); })
        : std::is_sorted(arr, arr + arrsize, [](const T &a, const T &b) {
              return Comparator<vectype, false>::STDSortComparator(a, b); });
if (sorted) { return; }

or to make descending a template parameter of xss_argsort and branch in avx2_argsort / avx512_argsort, the way xss_qsort already does it.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start at xss-common-argsort.h lines 630-632 and trace xss_argsort through avx2_argsort and avx512_argsort; compare the compile-time branching used by xss_qsort. Reproduce the sorted and reversed benchmarks described in the issue, then verify that runtime descending avoids an indirect comparator call without changing argsort results or the early-exit behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
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.