Skip to content

Commit 9858c70

Browse files
eendebakptclaude
andcommitted
ENH: use x86-simd-sort for descending sorts and partitions
The x86 SIMD paths were gated behind `!reverse` since numpygh-31345, because x86-simd-sort placed NaNs at the start of a descending result while NumPy keeps them at the end (see `npy::cmp<Tag, reverse>`). The vendored library gained a separate `nans_last` switch in numpy/x86-simd-sort#235, which came in with the submodule bump in numpygh-31947, so `descending` can now be forwarded directly: `nans_last` defaults to true and gives exactly NumPy's ordering. Removes the dispatch guards in quicksort.hpp/selection.hpp and the `assert(!reverse)` in the three dispatch translation units, and threads `reverse` through QSelect/ArgQSelect so partition and argpartition are covered as well. Measured on AVX2 over 1M elements, descending now runs at the speed of ascending: ~4-9x faster than before for `sort`/`partition` and ~2-3x for `argsort`/`argpartition`. Closes part of numpygh-31423. Co-Authored-By: Claude Opus 5 (1M context) <[email protected]>
1 parent 63c5826 commit 9858c70

8 files changed

Lines changed: 48 additions & 60 deletions

File tree

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
Descending sorts and partitions are now SIMD accelerated on x86
2+
---------------------------------------------------------------
3+
`numpy.sort`, `numpy.argsort`, `numpy.partition` and `numpy.argpartition`
4+
with ``descending=True`` no longer fall back to scalar code on x86, and now
5+
use the same SIMD kernels as the ascending versions for most integer and
6+
floating point dtypes. On AVX2 this is 2-9x faster than before.

‎doc/release/upcoming_changes/31511.new_feature.rst‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,5 +4,4 @@ Users can now pass the ``descending=True`` keyword argument to `numpy.partition`
44
`numpy.argpartition` to partition and argpartition arrays in descending order.
55
NaN values, if present, are partitioned to the end of the array in both ascending and
66
descending sorts. This feature is available for all built-in dtypes except
7-
``void`` and ``generic``. Note that SIMD optimizations for partitioning are currently
8-
not available for descending order, so performance may be slower.
7+
``void`` and ``generic``.

‎numpy/_core/src/npysort/quicksort.hpp‎

Lines changed: 6 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -81,21 +81,17 @@ inline bool quicksort_dispatch(T *start, npy_intp num)
8181
void (*dispfunc)(TF*, intptr_t, bool) = nullptr;
8282
if constexpr (sizeof(T) == sizeof(uint16_t)) {
8383
#if defined(NPY_CPU_AMD64) || defined(NPY_CPU_X86) // x86 32-bit and 64-bit
84-
if constexpr (!reverse) { // x86 SIMD sort is ascending-only
85-
#include "x86_simd_qsort_16bit.dispatch.h"
86-
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template QSort, <TF>);
87-
}
84+
#include "x86_simd_qsort_16bit.dispatch.h"
85+
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template QSort, <TF>);
8886
#else
8987
#include "highway_qsort_16bit.dispatch.h"
9088
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::highway::qsort_simd::template QSort, <TF>);
9189
#endif
9290
}
9391
else if constexpr (sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t)) {
9492
#if defined(NPY_CPU_AMD64) || defined(NPY_CPU_X86) // x86 32-bit and 64-bit
95-
if constexpr (!reverse) { // x86 SIMD sort is ascending-only
96-
#include "x86_simd_qsort.dispatch.h"
97-
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template QSort, <TF>);
98-
}
93+
#include "x86_simd_qsort.dispatch.h"
94+
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template QSort, <TF>);
9995
#else
10096
#include "highway_qsort.dispatch.h"
10197
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::highway::qsort_simd::template QSort, <TF>);
@@ -116,10 +112,9 @@ inline bool aquicksort_dispatch(T *start, npy_intp* arg, npy_intp num)
116112
{
117113
#if !defined(__CYGWIN__)
118114
if constexpr (
119-
((std::is_base_of_v<npy::floating_point_tag, Tag>
115+
(std::is_base_of_v<npy::floating_point_tag, Tag>
120116
&& !std::is_same_v<Tag, npy::longdouble_tag>) ||
121-
std::is_base_of_v<npy::integral_tag, Tag>)
122-
&& !reverse // x86 SIMD argsort is ascending-only
117+
std::is_base_of_v<npy::integral_tag, Tag>
123118
) {
124119
using TF = typename np::meta::FixedWidth<T>::Type;
125120
void (*dispfunc)(TF*, npy_intp*, npy_intp, bool) = nullptr;

‎numpy/_core/src/npysort/selection.hpp‎

Lines changed: 13 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@
2828
#include "x86_simd_qsort.hpp"
2929

3030
template<typename Tag, typename T>
31-
inline bool quickselect_dispatch(T* v, npy_intp num, npy_intp kth)
31+
inline bool quickselect_dispatch(T* v, npy_intp num, npy_intp kth, bool reverse)
3232
{
3333
#ifndef __CYGWIN__
3434
/*
@@ -43,7 +43,7 @@ inline bool quickselect_dispatch(T* v, npy_intp num, npy_intp kth)
4343
|| sizeof(T) == sizeof(uint32_t)
4444
|| sizeof(T) == sizeof(uint64_t))) {
4545
using TF = typename np::meta::FixedWidth<T>::Type;
46-
void (*dispfunc)(TF*, npy_intp, npy_intp) = nullptr;
46+
void (*dispfunc)(TF*, npy_intp, npy_intp, bool) = nullptr;
4747
if constexpr (sizeof(T) == sizeof(uint16_t)) {
4848
#include "x86_simd_qsort_16bit.dispatch.h"
4949
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template QSelect, <TF>);
@@ -53,17 +53,18 @@ inline bool quickselect_dispatch(T* v, npy_intp num, npy_intp kth)
5353
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template QSelect, <TF>);
5454
}
5555
if (dispfunc) {
56-
(*dispfunc)(reinterpret_cast<TF*>(v), num, kth);
56+
(*dispfunc)(reinterpret_cast<TF*>(v), num, kth, reverse);
5757
return true;
5858
}
5959
}
6060
#endif
61-
(void)v; (void)num; (void)kth; // to avoid unused arg warn
61+
(void)v; (void)num; (void)kth; (void)reverse; // to avoid unused arg warn
6262
return false;
6363
}
6464

6565
template<typename Tag, typename T>
66-
inline bool argquickselect_dispatch(T* v, npy_intp* arg, npy_intp num, npy_intp kth)
66+
inline bool argquickselect_dispatch(T* v, npy_intp* arg, npy_intp num, npy_intp kth,
67+
bool reverse)
6768
{
6869
#ifndef __CYGWIN__
6970
/*
@@ -75,15 +76,15 @@ inline bool argquickselect_dispatch(T* v, npy_intp* arg, npy_intp num, npy_intp
7576
(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t))) {
7677
using TF = typename np::meta::FixedWidth<T>::Type;
7778
#include "x86_simd_argsort.dispatch.h"
78-
void (*dispfunc)(TF*, npy_intp*, npy_intp, npy_intp) = nullptr;
79+
void (*dispfunc)(TF*, npy_intp*, npy_intp, npy_intp, bool) = nullptr;
7980
NPY_CPU_DISPATCH_CALL_XB(dispfunc = np::qsort_simd::template ArgQSelect, <TF>);
8081
if (dispfunc) {
81-
(*dispfunc)(reinterpret_cast<TF*>(v), arg, num, kth);
82+
(*dispfunc)(reinterpret_cast<TF*>(v), arg, num, kth, reverse);
8283
return true;
8384
}
8485
}
8586
#endif
86-
(void)v; (void)arg; (void)num; (void)kth; // to avoid unused arg warn
87+
(void)v; (void)arg; (void)num; (void)kth; (void)reverse; // to avoid unused arg warn
8788
return false;
8889
}
8990

@@ -458,10 +459,8 @@ introselect_noarg(void *v, npy_intp num, npy_intp kth, npy_intp *pivots,
458459
npy_intp *npiv, npy_intp nkth, void *)
459460
{
460461
using T = typename std::conditional<std::is_same_v<Tag, npy::half_tag>, np::Half, typename Tag::type>::type;
461-
if constexpr (!reverse) {
462-
if ((nkth == 1) && (quickselect_dispatch<Tag>((T *)v, num, kth))) {
463-
return 0;
464-
}
462+
if ((nkth == 1) && (quickselect_dispatch<Tag>((T *)v, num, kth, reverse))) {
463+
return 0;
465464
}
466465
return introselect_<Tag, false, reverse>((typename Tag::type *)v, nullptr, num, kth,
467466
pivots, npiv);
@@ -473,10 +472,8 @@ introselect_arg(void *v, npy_intp *tosort, npy_intp num, npy_intp kth,
473472
npy_intp *pivots, npy_intp *npiv, npy_intp nkth, void *)
474473
{
475474
using T = typename Tag::type;
476-
if constexpr (!reverse) {
477-
if ((nkth == 1) && (argquickselect_dispatch<Tag>((T *)v, tosort, num, kth))) {
478-
return 0;
479-
}
475+
if ((nkth == 1) && (argquickselect_dispatch<Tag>((T *)v, tosort, num, kth, reverse))) {
476+
return 0;
480477
}
481478
return introselect_<Tag, true, reverse>((typename Tag::type *)v, tosort, num, kth,
482479
pivots, npiv);

‎numpy/_core/src/npysort/x86_simd_argsort.dispatch.cpp‎

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,16 @@
11
#include "x86_simd_qsort.hpp"
22
#ifndef __CYGWIN__
33

4-
#include <cassert>
54
#include "x86-simd-sort/src/x86simdsort-static-incl.h"
65

76
#define DISPATCH_ARG_METHODS(TYPE) \
8-
template<> void NPY_CPU_DISPATCH_CURFX(ArgQSelect)(TYPE* arr, npy_intp* arg, npy_intp num, npy_intp kth) \
7+
template<> void NPY_CPU_DISPATCH_CURFX(ArgQSelect)(TYPE* arr, npy_intp* arg, npy_intp num, npy_intp kth, bool reverse) \
98
{ \
10-
x86simdsortStatic::argselect(arr, reinterpret_cast<size_t*>(arg), kth, num, true); \
9+
x86simdsortStatic::argselect(arr, reinterpret_cast<size_t*>(arg), kth, num, true, reverse); \
1110
} \
1211
template<> void NPY_CPU_DISPATCH_CURFX(ArgQSort)(TYPE* arr, npy_intp *arg, npy_intp size, bool reverse) \
1312
{ \
14-
assert(!reverse); (void)reverse; \
15-
x86simdsortStatic::argsort(arr, reinterpret_cast<size_t*>(arg), size, true); \
13+
x86simdsortStatic::argsort(arr, reinterpret_cast<size_t*>(arg), size, true, reverse); \
1614
} \
1715

1816
namespace np { namespace qsort_simd {

‎numpy/_core/src/npysort/x86_simd_qsort.dispatch.cpp‎

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,17 @@
11
#include "x86_simd_qsort.hpp"
22
#ifndef __CYGWIN__
33

4-
#include <cassert>
54
#include "x86-simd-sort/src/x86simdsort-static-incl.h"
65

6+
// hasnan is unknown up front, so always true; nans_last defaults to true.
77
#define DISPATCH_SORT_METHODS(TYPE) \
8-
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(TYPE *arr, npy_intp num, npy_intp kth) \
8+
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(TYPE *arr, npy_intp num, npy_intp kth, bool reverse) \
99
{ \
10-
x86simdsortStatic::qselect(arr, kth, num, true); \
10+
x86simdsortStatic::qselect(arr, kth, num, true, reverse); \
1111
} \
1212
template<> void NPY_CPU_DISPATCH_CURFX(QSort)(TYPE *arr, npy_intp num, bool reverse) \
1313
{ \
14-
assert(!reverse); (void)reverse; \
15-
x86simdsortStatic::qsort(arr, num, true); \
14+
x86simdsortStatic::qsort(arr, num, true, reverse); \
1615
} \
1716

1817
namespace np { namespace qsort_simd {

‎numpy/_core/src/npysort/x86_simd_qsort.hpp‎

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -5,20 +5,18 @@
55

66
namespace np { namespace qsort_simd {
77

8+
// ``reverse`` selects descending order; NaNs sort last either way.
89
#include "x86_simd_qsort.dispatch.h"
9-
// x86 SIMD sort is ascending-only; ``reverse`` must be false (asserted in
10-
// the implementation). The parameter exists purely so the dispatcher can
11-
// share one function-pointer signature with the Highway path.
1210
NPY_CPU_DISPATCH_DECLARE(template <typename T> void QSort, (T *arr, npy_intp size, bool reverse))
13-
NPY_CPU_DISPATCH_DECLARE(template <typename T> void QSelect, (T* arr, npy_intp num, npy_intp kth))
11+
NPY_CPU_DISPATCH_DECLARE(template <typename T> void QSelect, (T* arr, npy_intp num, npy_intp kth, bool reverse))
1412

1513
#include "x86_simd_argsort.dispatch.h"
1614
NPY_CPU_DISPATCH_DECLARE(template <typename T> void ArgQSort, (T *arr, npy_intp* arg, npy_intp size, bool reverse))
17-
NPY_CPU_DISPATCH_DECLARE(template <typename T> void ArgQSelect, (T *arr, npy_intp* arg, npy_intp kth, npy_intp size))
15+
NPY_CPU_DISPATCH_DECLARE(template <typename T> void ArgQSelect, (T *arr, npy_intp* arg, npy_intp kth, npy_intp size, bool reverse))
1816

1917
#include "x86_simd_qsort_16bit.dispatch.h"
2018
NPY_CPU_DISPATCH_DECLARE(template <typename T> void QSort, (T *arr, npy_intp size, bool reverse))
21-
NPY_CPU_DISPATCH_DECLARE(template <typename T> void QSelect, (T* arr, npy_intp num, npy_intp kth))
19+
NPY_CPU_DISPATCH_DECLARE(template <typename T> void QSelect, (T* arr, npy_intp num, npy_intp kth, bool reverse))
2220

2321
} } // np::qsort_simd
2422

‎numpy/_core/src/npysort/x86_simd_qsort_16bit.dispatch.cpp‎

Lines changed: 11 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
#include "x86_simd_qsort.hpp"
22
#ifndef __CYGWIN__
33

4-
#include <cassert>
54
#include "x86-simd-sort/src/x86simdsort-static-incl.h"
65
/*
76
* MSVC doesn't set the macro __AVX512VBMI2__ which is required for the 16-bit
@@ -16,46 +15,43 @@ namespace np { namespace qsort_simd {
1615
/*
1716
* QSelect dispatch functions:
1817
*/
19-
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(Half *arr, npy_intp num, npy_intp kth)
18+
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(Half *arr, npy_intp num, npy_intp kth, bool reverse)
2019
{
2120
#if defined(NPY_HAVE_AVX512_SPR)
22-
x86simdsortStatic::qselect(reinterpret_cast<_Float16*>(arr), kth, num, true);
21+
x86simdsortStatic::qselect(reinterpret_cast<_Float16*>(arr), kth, num, true, reverse);
2322
#else
24-
avx512_qselect_fp16(reinterpret_cast<uint16_t*>(arr), kth, num, true, false);
23+
avx512_qselect_fp16(reinterpret_cast<uint16_t*>(arr), kth, num, true, reverse);
2524
#endif
2625
}
2726

28-
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(uint16_t *arr, npy_intp num, npy_intp kth)
27+
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(uint16_t *arr, npy_intp num, npy_intp kth, bool reverse)
2928
{
30-
x86simdsortStatic::qselect(arr, kth, num);
29+
x86simdsortStatic::qselect(arr, kth, num, false, reverse);
3130
}
3231

33-
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(int16_t *arr, npy_intp num, npy_intp kth)
32+
template<> void NPY_CPU_DISPATCH_CURFX(QSelect)(int16_t *arr, npy_intp num, npy_intp kth, bool reverse)
3433
{
35-
x86simdsortStatic::qselect(arr, kth, num);
34+
x86simdsortStatic::qselect(arr, kth, num, false, reverse);
3635
}
3736

3837
/*
3938
* QSort dispatch functions:
4039
*/
4140
template<> void NPY_CPU_DISPATCH_CURFX(QSort)(Half *arr, npy_intp size, bool reverse)
4241
{
43-
assert(!reverse); (void)reverse;
4442
#if defined(NPY_HAVE_AVX512_SPR)
45-
x86simdsortStatic::qsort(reinterpret_cast<_Float16*>(arr), size, true);
43+
x86simdsortStatic::qsort(reinterpret_cast<_Float16*>(arr), size, true, reverse);
4644
#else
47-
avx512_qsort_fp16(reinterpret_cast<uint16_t*>(arr), size, true, false);
45+
avx512_qsort_fp16(reinterpret_cast<uint16_t*>(arr), size, true, reverse);
4846
#endif
4947
}
5048
template<> void NPY_CPU_DISPATCH_CURFX(QSort)(uint16_t *arr, npy_intp size, bool reverse)
5149
{
52-
assert(!reverse); (void)reverse;
53-
x86simdsortStatic::qsort(arr, size);
50+
x86simdsortStatic::qsort(arr, size, false, reverse);
5451
}
5552
template<> void NPY_CPU_DISPATCH_CURFX(QSort)(int16_t *arr, npy_intp size, bool reverse)
5653
{
57-
assert(!reverse); (void)reverse;
58-
x86simdsortStatic::qsort(arr, size);
54+
x86simdsortStatic::qsort(arr, size, false, reverse);
5955
}
6056

6157
}} // namespace np::qsort_simd

0 commit comments

Comments
 (0)