Proposal to update to sortperm signature

proposal
sort
sortperm

#1

I have written a faster sortperm for Radixsort (defined in SortingAlgorithms.jl).

However I encountered a number of difficulties in extending the sortperm from Base, the main reason is that the signature for sortperm is sortperm(v; alg::Algorithm, ...), so I if I define sort(v; alg::RadiSortAlg) then it will override the Base.sort when I do sort(v).

So I think it’s better to have an additional sortperm signature that looks like sortperm(v, alg::Algorithm; ...). This way I can define sortperm(v, alg::RadixSortAlg).

This is the main impetus behind my PR to Base’s sortperm signatures.


#2

The main issue here is keyword args don’t dispatch. But the true fix is… make keyword arguments able to dispatch. Step 1 was implementing NamedTuples. Step 2 is making keyword args use NamedTuples so that way they are concretely typed (that will give them speed). Step 3 is to allow it to dispatch off of the type signatures. I’d much rather see it just happen the right way than fudge APIs for the time being.


#3

I think that is not on the books for 1.0 though, at least the performance part: https://github.com/JuliaLang/julia/issues/9551. Which presumably also means the dispatch (edit: also dispatch would be breaking, I think, thus 2.0).


#4

Step 1 is complete of course. I’m not worried about the performance part: it’s quick not hard to implement yourself with a macro and NamedTuples.jl (see Keys.jl) so it should not be difficult to do in Base. As for dispatching, I am not sure how that stuff is implemented in Base so I don’t know exactly how difficult it would be, but this doesn’t seem like it’s so far away.

Would it be breaking? It didn’t have a meaning before other than a type-assertion. But if things failed the type-assertion, then I believe it would just get a method error which is the same that dispatch would do. It would then just allow you to define a different dispatch, which is right now just overwriting the method so I don’t believe that actually has a use right now. I would go even further than that: I think that most people who put an assertion on keyword args might not know that it’s not actually dispatching (I didn’t know for a long time), so in some sense it’s a bugfix.


#5

Yes, you’re right, it shouldn’t be breaking in-itself. But updating an API to make use of it might well be (as updating any API really is potentially breaking).


#6

If the APIs are asserting on an abstract type like this is doing, then people can extend it without breaking the API just by dispatching on a concrete subtype. So this could be extended by adding keyword argument dispatch and then adding a new Algorithm type dispatch without breaking the existing API.


#7

Well, well: