Skip to content

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

Closed

Description

@eendebakpt

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.

Activity

  1. r-devulap commented on Nov 5, 2026

    @r-devulap
    Member

    HI @eendebakpt if you have a patch, please submit and will be happy to review it. Apologies for getting to this so late.

  2. Dhruvdesai793 commented on Nov 13, 2026

    @Dhruvdesai793
    Contributor

    @r-devulap I have submited this patch based on the issue author's suggested fix.
    PR

  3. r-devulap commented on Nov 14, 2026

    @r-devulap
    Member

    Fixed with #246

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions