Whoa, that is one of the ugliest diffs I've ever seen. The actual code just adds new functions and deletes the content of old ones. I suggest looking at the files direct.

Note that I use some static arrays inside the functions which are only written to when they are initialized. The initialization may not be thread safe, although they should be in C++11. They can be purely local without much cost. I used tables so that minimal changes would be needed if we add function slots one way or another. They contain variables that are not available until link time, but then, so do the standard dtypes. I'm not clear if function names can be considered constant at compile time, If so, I could simply pull them out of the functions and initialize them in the usual way.

I think it can be done, but I not sure.

OK, const myfunc foo[] = {func1, func2}; works.

Cleaned things up a bit. @seberg You wanted to remove the legacy PyArray_Sort and PyArray_ArgSort from the public API. This is a chance to avoid exposing the new functions in API. I suppose we can always add them later if someone wants them.

I think I'd still suggest that the new C-API does not have sort kind at all, and that the old functions just translate. Alternatively, for now, make the new functions private and have the public SortEx not have the kind argument, i.e., both old and new call into the private ones.

I think I'd still suggest that the new C-API does not have sort kind at all

Internally, I've been using the fourth flag bit to mark using "kind" as a table index. We could translate the kind values into flag bits:

kind == 0 -> 0 (default)
kind == 1 -> 8 (new bit, heapsort)
kind == 2 -> 1 (stable)

or maybe

kind == 0 -> 8 (default)
kind == 1 -> 9 (new bit, heapsort)
kind == 2 -> 10 (stable)

i.e., if the fourth bit is set, use the lower bits to hold the flag value. I chose the fourth bit to reserve eight values of the keywords, but we could pretty reserve more space. I expect we will have a minimum of 32 bits to work with, flags is an int type. So we can get rid of kind in the C-API. Getting rid of it in the public method API will take deprecation. For that matter, we might could use a different bit to mark argsorts, but maybe that is going too far.

Maybe we should just make the flags variable uint32.

The way I see things at the moment.

Decided:

• Methods sort and argsort keep their current APIs for back compatibility (done)
• Remove the which argument from the new C-API functions, use only the flags. (done)
• Make the flags argument explicitly uint32. (todo)

To be Decided:

• Remap kind losing heapsort ,
• Make public the new C-API,
• Deprecate kind ,

I would also argue for reserving the lower 8 bits of of the flags for sort selection, and the remaining bits for hints.
That is just to avoid future complications in implementations. That can be handled through documentation.

Agreed on the "decided". For those to be decided, I'd say "remap, make public, and deprecate" - though the deprecation could be done in a follow-up PR.

I went ahead and made the modifications. It isn't possible to set the enum type until C23, so to be safe I just left it an enum, which will change size if needed, but the size will be platform specific. I think that is safe.

We can postpone adding documentation and keywords at the Python Level until we actually add the new functionality.

We can postpone adding documentation and keywords at the Python Level until we actually add the new functionality.

indeed, though whatever we expose at the C level should be correct (even if it means erroring on NPY_SORT_DESCENDING)

All the keywords are there if you want to test them:

In [1]: np.ones(10).sort(descending=1)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[1], line 1
----> 1 np.ones(10).sort(descending=1)

TypeError: no current sort function meets the requirements

They just won't be documented. I suppose we could print out the flag values to make it clearer.

Do we want that? E.g., @seberg suggested to not have nanfirst yet.

Yes, there is no reason in Python to add a kwarg early, it is just confusing to have it. On C the story may be a bit different (although, not much because NPY_TARGET_VERSION allows us to decide whether or not to expose a new flag! We could skip adding the flags even there -- although I don't care about that!).

I am curious now if we can't avoid the new function and just change the definition of which in PyArray_Sort()? (Eventually deprecated if e.g. "heapsort" is passed. Would leave some bits unused in the new sort flags, but that seems OK.)
Not sure how one would best write it, though. Maybe a union of both enums (and make sure the enums don't collide in flags)? Or just document it as "legacy flag maps to stable/unstable".

I am curious now if we can't avoid the new function

Yes, we could. But you didn't want to extend SORTKIND :) And to be fair, that would have been a kludge.

I rather like the new functions and the flags interface, I think things worked out well. The only real difference is heapsort not being public, and I've thought it unneeded since introsort went in. From the beginning it was the slowest sort, taking about 2x longer than quicksort, and quicksort has gotten faster.

The flag interface is nicely extensible in the future, we have been abusing SORTKIND for many years as new sorting functions have come along: introsort, radix sort, timsort, SIMD quicksort, etc. We don't want to make users choose among those options, let the experts do it.

All we have do to get rid of nanfirst is comment out a line

//           "$nanfirst", &PyArray_OptionalBoolConverter, &nanfirst,

The parser then raises an error:

In [1]: np.ones(10).sort(nanfirst=1)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[1], line 1
----> 1 np.ones(10).sort(nanfirst=1)

TypeError: sort() got an unexpected keyword argument 'nanfirst'

Note that all user dtypes need is a compare function, they just put NULLs in the current sorting slots. We only need the current sorting slots for type specific builtin sorts. To add descending sorts, the quick and dirty solution is to add generic sorting routines and add them to the new tables which are introduced here along with the new interfaces. We only need an extended dtype if we want them to be builtin. We can start with the generic sorts and use them for timing comparison, which will tell us if it is worth going to type specific sorts.

I need to see how runtime dispatching works, I haven't figured that out yet.

the quick and dirty solution is to add generic sorting routines and add them to the new tables which are introduced here along with the new interfaces. We only need an extended dtype if we want them to be builtin.

Yeah, but I happen to care a lot about this, that if we add descending we do it in a way that can be exposed to user DTypes, because we can't focus on the API decisions.
(But this is the other PR and I think most decisions are actually already getting close -- but API is hard and it's necessary to have multiple eyes on it. The biggest API complexity is maybe not missing the chance of fixing more of the API at the same time.)

I don't see that we can expect generic sorts to have decent performance for descending, if that was the case, we wouldn't use Raghuveers or highway sorts (which we should plug in for descending as well if possible).

But you didn't want to extend SORTKIND

Maybe, I may have changed my opinion. But there were two different things here: One is keeping the actual algorithm choice (we are doing the opposite now, always removing that choice) and the other is absorbing the new sort option flags into a single larger enum.

Now that we decided to narrow the algorithm choice to stable/unstable. I think avoiding PyArray_SortEx() is probably nice (I am not 100% yet, because I am not sure if that ends up with some monster of an enum). Just having PyArray_SortEx is not that pretty and a bit confusing as well (which one should I use?).

I need to see how runtime dispatching works, I haven't figured that out yet.

Isn't that what the other PR tried to solve -- and while it should morph with recent discussion, mostly did solve?

that ends up with some monster of an enum)

The current values are orthogonal, so three enum entries gives 8 choices. I don't expect the enum to grow much, what will grow are the switch statements.

EDIT: I expect the other PR, if implemented with either a table or function, to get passed a flag, which is just a number. If implemented with a table the number is an index into the table. In short, I expect the switch statements to go away, essentially moved down to the new interface.

For instance, descending && stable becomes an option. What would grow exponentially is SORTKIND. I think the flag option is preferable and doesn't impact the other PR, except it becomes simpler IMHO.

is make sure that the C-side raises an error when the new flags are used

You get a TypeError: "no current sort function meets the requirements"

What do you want done before this goes in?

I'm OK with it as is, but think given the discussion it might be best not to advertise NANFIRST in any way -- easiest would be just to remove it for now. I do think it is fine to leave descending in, even if it is not yet supported, since the array API requires that eventually we implement it. But that the way that one is added also already sets an obvious template for adding further options later.

But again, I don't feel strongly, so maybe @seberg can pipe in too.

p.s. Overall, a bit of a tortuous path, but I think a very nice result!

only need to define that a descending sort also should return the NaNs last.

If there is no nanfirst keyword, we should say that all alternatives sort NaNs to the end.
If there is a nanfirst keyword, we should say that all alternatives sort NaNs to the end unless nanfirst=1.

Not sure where that should go, maybe in the extending dtypes documentation.

I have removed all references to nanfirst.
I left the descending converter alone, as it seems a converter is wanted and the current converter looks exactly right

PyArray_BoolConverter(PyObject *object, npy_bool *val)
{
    int bool_val = PyObject_IsTrue(object);
    if (bool_val == -1) {
        return NPY_FAIL;
    }
    *val = (npy_bool)bool_val;
    return NPY_SUCCEED;
}

I think OptionalBoolConverter is for the case that one can pass in None as well.)

Why do you need None in parsing a keyword only argument $stable? The parser isn't called if the argument isn't present. If we use builtin formats and parse it as 'i':

    case 'i': {/* signed int */
        int *p = va_arg(*p_va, int *);
        long ival;
        if (float_argument_error(arg))
            RETURN_ERR_OCCURRED;
        ival = PyLong_AsLong(arg);
        if (ival == -1 && PyErr_Occurred())
            RETURN_ERR_OCCURRED;
        else if (ival > INT_MAX) {
            PyErr_SetString(PyExc_OverflowError,
                            "signed integer is greater than maximum");
            RETURN_ERR_OCCURRED;
        }
        else if (ival < INT_MIN) {
            PyErr_SetString(PyExc_OverflowError,
                            "signed integer is less than minimum");
            RETURN_ERR_OCCURRED;
        }
        else
            *p = ival;
        break;
    }

which is not simpler than calling the __bool__ dunder, which doesn't need to do all those other checks. We could make a new converter that checked for an integer type first, (PyLong_Check), if you want to avoid accepting all types that define __bool__. Can't do better than that, Python doesn't have a real bool type.

I think just use PyArray_BoolConverter

I think just use PyArray_BoolConverter

Ah, it's already written, is it. Which raises the opposite question, why isn't it used for stable? Lets try that.

Well, that answers that question, the original was in fact correct, PyArray_OptionalBoolConverter does need to be used for both 'stable' and 'descending'.

@mhvk it was suggested by @seberg that I not use PyArray_OptionalBoolConverter for the new options,
by which I assume he meant PyArray_BoolConverter instead, which I had forgotten existed.

the original was in fact correct, PyArray_OptionalBoolConverter does need to be used for both 'stable' and 'descending'.

I am not following. You don't really need it for stable but it is has some sense because of the -1 default when it's not passed.
What it gives you is that kind="stable", stable=None is allowed, i.e. stable=None behaves identical to it not being passed.

But for descending= you don't need it, it's signature is not stable=None/np._NoValue, but descending=False. It has a well defined default and descending=None has the same meaning as desecnding=False and that will always be true.
There will never be later code checking for descending == -1 in the C-code here.

But for descending= you don't need it

I tested that and it didn't work. It compiles, and runs without errors, but not correctly. Which is to say, sortkind is not correctly constructed. The function signature is defined in the parser call, and both "|stable" and "|descending" are keyword only, so it makes sense that they need the same function. Note that using the alternate function to parse stable gives hundreds of test errors.

I think the vectorcall logic goes this way. All the possible variables must be processed. If it is determined that there is no corresponding value in the args list, the question is "what to do"? This is determined on our end, and I think we have decided to return None in that case, so the Optional parsing function is needed to ignore that case and do nothing.
The straight boolean parser will only work correctly for strictly positional arguments, where the wanted value is always in the args list or an error is raised if the args list is too short.

Note that the two functions also have different return types, the straight converter returns to npy_bool (unsigned char), while the optional converter returns to int. That could cause problems on big endian architectures if the return variables don't have the correct type.

@ngoldbaum I think you implemented the fastcall processing, can you confirm my understanding?

That could cause problems on big endian architectures if the return variables don't have the correct type.

I implemented fastcall, but it has nothing to do with things here, it behaves exactly the same as the builtin parser.
Maybe you forgot to change the variable to npy_bool descending = NPY_FALSE;?

This is determined on our end, and I think we have decided to return None in that case

When the argument is optional, you always have to set the default. I would still avoid OptionalBoolConverter because it converts None to False rather than "keep default unchanged".

Summary: As long as we allow kind or keywords, but not both, we need to use the optional parser so that we can tell when a keyword is used.

The problem with not using the non-optional converter is that we assume that it doesn't affect the current value of the variable (which is what online documentation suggests), which is incorrect. It sets the variable to either 0 ot 1. Setting the variable -1 before the call serves no purpose. So the non-optional version can only be used when 0 is the default value. The code can be fixed to work with the non-optional parser, but will not work as long as we want to enforce use kind, or use keywords, but not both.

I don't think we need to keep the one or the other choice now that heapsort is gone, but as long as we do, we need to use the optional parser. If we allow both kind and keywords, then we can do;

int stable = -1;  -> npy_bool stable = 0; 

and give the keyword priority over kind in the sortkind construction.

Summary: As long as we allow kind or keywords, but not both, we need to use the optional parser so that we can tell when a keyword is used.

I suppose I think there is no reason to reject sort(kind="mergesort", descending=False). But fine, if you want kind="mergesort", descending=None to work but kind="mergesort", descending=False to fail, then yes we need the Optional version.
(If I went back in time, I might actually start arguing the same direction for stable= also -- to not use the Optional one.)

EDIt: anyway, I don't care much, just do the version you prefer.

Summary: I'll stick with the current implementation.

Using a split is an easy rule to remember, as opposed to having different behaviors for different keywords. I'll go for that.

Thanks all. And especial thanks to @mhvk for his close reading and suggestions.

Looking forward to the next steps!