ENH,REF: New-style generic sorting ArrayMethod loops by MaanasArora · Pull Request #30328 · numpy/numpy

MaanasArora · 2025-11-29T02:16:25Z

Implements PyArrayMethod_StridedLoop wrappers for quicksort and mergesort to align with #29737. These can be used to implement a new sort_compare slot and move to the new API for builtin dtypes in the future. StringDType now wraps these new loops for its sorting implementation.

This uses @mhvk's suggestion of using context->method->static_data as the location for the (sort) compare function. I think this should be fine since the static data is a private slot and can be evolved if needed, but open to discussion!

ping @seberg @mhvk - thanks!

mhvk

@MaanasArora - This looks nice! But I think we should have just two loops, say, npy_sort_loop and npy_argsort_loop, which do the switch for stable/unstable implementations inside themelves. I.e., have these be loops where the context decides everything, including future extensions such as whether to sort ascending/descending, or where to sort NaN.

The nice aspect would then be that in the stringdtype wrappers, you really only need to worry about wrapping, not implementation details like what kind of sort is requested (and no changes will be needed if more sort kinds are implemented).

I guess one small question is whether their name should be more descriptive. Maybe npy_sort_by_comparisons_loop? Or a lamer npy_default_sort_loop?

p.s. Separately, possibly this enables again removing implementations from the header files that you added in the last PR? In follow-up, it might be nice to have the new-style loops be the "real" ones, and old-style implementations just be wrappers (as long as we still need them).

MaanasArora · 2025-11-30T20:30:09Z

Thanks for reviewing @mhvk! That's a really nice idea, I've made just two loops, thanks - though was unsure where to put them so had to write a new c file npy_sort.c (npysort_common.c was possible, since that's just a header, but seemed more complicated to include it), hopefully that is ok. I just called it npy_default_(arg)sort_loop, sounded more in line with its function I guess!

Replaced its use in StringDType as well - agreed that it is quite nice to have a default loop so that the same logic doesn't have to be replicated everywhere!

I tried to remove the implementations from the header, but it seems a bit tricky because of how the files are structured (we use the implementations in npy_sort.c)... maybe we could move things around, but unclear if that is going to be too disruptive. One way to do it would be to define arraymethod loops also for quicksort, mergesort, etc., and use them in these loops, don't think there's a use case for that though!

mhvk

Nice that that works so well!

One in-line comment still, about trying to remove the exposure of npy_quicksort_impl, etc., in npy_sort.h.src that you added in #30266 -- I think they shouldn't be needed any more...

mhvk · 2025-11-30T21:20:45Z

+
+#ifdef __cplusplus
+}
+#endif


Missing end of line.

Fixed, sorry, thanks!

mhvk · 2025-11-30T21:27:29Z

+NPY_NO_EXPORT int npy_default_argsort_loop(PyArrayMethod_Context *context,
+        char *const *data, const npy_intp *dimensions, const npy_intp *strides,
+        NpyAuxData *transferdata);



I'm still a bit confused: in #30266, you added the GENERIC SORT IMPLEMENTATIONS below. WIth the new scheme introduced here, do these still need to be exposed in this header file? If we need them for defining the default (arg)sort loops in a new npy_sort.c file, can we remove them if instead we define the default sort loops in the same file as these generic implementations are defined?

p.s. I realize this may all be a bit pedantic, but I didn't quite like exposing "old" implementations in #30266 and am hoping we can remove them again here! This all in the hope of making it easier to completely remove the old implementations in the (near) future.

Not pedantic at all, great point! I wished to remove as well. Unfortunately the sort implementations are defined in the files quicksort.cpp and mergesort.cpp - not sure which one the defaults would go in, I guess neither, so we end up with this... I suppose one workaround could be to expose these in a different header file - would that be OK?

Edit: that could be npysort_common.h, I did want to use the new file npysort_common.c, though this seems closer to NumPy core than npysort. I feel like some header is needed simply because these loop implementations are defined in the algorithm-specific files.

Ah, yes, I see your problem now. Since this header also has the old npy_mergesort (without _impl), probably just best/easiest to stick with what you have here!

Sounds good, thanks!

mhvk · 2025-11-30T21:30:47Z

-    int ret = sort_loop(
-            data[0], dimensions[0], context,
-            context->descriptors[0]->elsize, &_sort_compare);
+    int ret = npy_default_sort_loop(context, data, dimensions, strides, transferdata);


Ah, yes, this is what I hoped would be possible! Now StringDType really has to do nothing more than acquire and release the allocator. Nice!

mhvk

Thanks for explaining why what I hoped would be possible is not...

I think with that, this is great, so I'll approve. Maybe nice still for @seberg to have a look, so I won't merge yet.

mhvk · 2025-11-30T22:14:51Z

+NPY_NO_EXPORT int npy_default_argsort_loop(PyArrayMethod_Context *context,
+        char *const *data, const npy_intp *dimensions, const npy_intp *strides,
+        NpyAuxData *transferdata);



Ah, yes, I see your problem now. Since this header also has the old npy_mergesort (without _impl), probably just best/easiest to stick with what you have here!

seberg · 2025-12-01T09:49:16Z

This seems all fine to me. Ideally we find this is useful for other implementations as well (and maybe updating the implementation if we find that useful; although we need to keep supporting legacy dtypes for a while -- not forever since adding a sort for an existing legacy user dtype is very possible. A scheme I actually think we may want to extend -- i.e. make dtypes more "mutable" even if it is not ideal, just to make transitioning dtypes to the new API one a step-by-step process).

MaanasArora · 2025-12-01T12:26:05Z

Thanks! It could be a useful implementation for object maybe, but the primary use case is probably sort_compare - unless we should also actually expose this loop or similar publicly (not sure)? Most dtypes within NumPy use (SIMD) specific loops, so wrapping them could be wrinkly, and could likely end up being independent to this unfortunately.

Scaffolding by wrapping the existing machinery makes a lot of sense! Could definitely make later steps e.g. deprecations smoother at least.

seberg · 2025-12-01T12:33:21Z

Hmmm, making it public to simplify some implementations may make sense. Although, in that case I am tempted to pass the cmp function in explicitly and not look it up inside the helper and then, I guess drop transferdata (clearly this loop doesn't need it).

MaanasArora · 2025-12-01T12:40:30Z

Hmm, maybe, but then we don't have the ArrayMethod signature, so some implementations might actually get a bit more complicated? I can already think of compare at least, for which we would have to add another wrapper (instead of just using this directly) if the signature changes! If we do want to expose, maybe adjusting another loop on top of this would make more sense than changing the signature... but perhaps just too much to think about for now.

mhvk · 2025-12-01T14:14:39Z

One way to think of this might go to a more general way of registering a ufunc, where there is a default loop that just calls to a C function for every element. Here, that would be compare, for vectorize it is a python function, for object loops we effectively do that already. Passing in such functions via context seems appropriate. But probably best to implement this further as needed...

mhvk · 2025-12-10T00:55:43Z

@seberg - the conversation here started to go towards follow-up territory. Shall we put this one in? I don't think it precludes any time of follow up!

seberg · 2025-12-10T08:34:19Z

Yeah, let's move forward here, thanks Maanas and Marten.

ENH,REF: New arraymethod-style default sorting loops

d7d1bfc

github-actions Bot added the 01 - Enhancement label Nov 29, 2025

MaanasArora changed the title ~~ENH,REF: New-style default sorting ArrayMethod loops~~ ENH,REF: New-style generic sorting ArrayMethod loops Nov 29, 2025

mhvk reviewed Nov 30, 2025

View reviewed changes

ENH: Implement single default sorting loops in npy_sort.c

5580fc7

mhvk reviewed Nov 30, 2025

View reviewed changes

STYLE: Add missing newline

b9ebb96

mhvk approved these changes Nov 30, 2025

View reviewed changes

seberg merged commit a64d310 into numpy:main Dec 10, 2025
74 checks passed

MaanasArora mentioned this pull request Dec 11, 2025

ENH: Add sort_compare dtype slot to register new-style sorts #30415

Open

Noxaster mentioned this pull request Dec 15, 2025

[shayo] Reviewing exercise submission Simulation-Software-Engineering/reviewing-exercise#16

Closed

Conversation

MaanasArora commented Nov 29, 2025

Uh oh!

mhvk left a comment

Choose a reason for hiding this comment

Uh oh!

MaanasArora commented Nov 30, 2025

Uh oh!

mhvk left a comment

Choose a reason for hiding this comment

Uh oh!

mhvk Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

MaanasArora Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

mhvk Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

MaanasArora Nov 30, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mhvk Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

MaanasArora Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

mhvk Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

mhvk left a comment

Choose a reason for hiding this comment

Uh oh!

mhvk Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

seberg commented Dec 1, 2025

Uh oh!

MaanasArora commented Dec 1, 2025

Uh oh!

seberg commented Dec 1, 2025

Uh oh!

MaanasArora commented Dec 1, 2025

Uh oh!

mhvk commented Dec 1, 2025

Uh oh!

mhvk commented Dec 10, 2025

Uh oh!

seberg commented Dec 10, 2025

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

MaanasArora Nov 30, 2025 •

edited

Loading