Old interface for searchsorted* are not type stable anymore

[andyferris]

After finding unusual allocations in my code, I found some (undocumented!) changes to search using the new Ordering parameters. Which are really, really neat, but the backup option for the old interface at https://github.com/JuliaLang/julia/blob/master/base/sort.jl#L193 is not type stable:

for s in [:searchsortedfirst, :searchsortedlast, :searchsorted]
    @eval begin
        ...
        $s(v::AbstractVector, x;
           lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward) =
            $s(v,x,ord(lt,by,rev,order))
        ...
    end
end

The problem is the type returned by ord depends on the value of the boolean rev at https://github.com/JuliaLang/julia/blob/master/base/ordering.jl#L72. Using the new interface for this one method made my overall algorithm (spatial querying in 3D) twice as fast and allocate significantly less memory, so I think this is important.

I think we need to either (a) insert a deprecation warning so people know to switch their code, or (b) include the old methods, or (c) think of an alternative, type-stable workaround.

[andyferris]

I think we need to either (a) insert a deprecation warning so people know to switch their code,

Oh and I mean deprecating this right now for v0.5 final unless you wish to do (b) or (c) sometime in the future (and I can't see that (c) is feasible, but I may be wrong).

[simonster]

This looks like the same issue as #8991. Has something changed here?

[TotalVerb]

This can probably be fixed by allowing Val{true} and Val{false} for rev, and defaulting rev to Val{false}, and changing ord to accept ::Type{Val{b}} instead of Bool. Compatibility can be maintained by continuing to accept boolean arguments for rev, at cost of type instability, but no code breakage.

[kmsquire]

The Ordering functionality should probably be revisited now, since it was written before (and because) functions weren't types and therefore couldn't be inlined if passed in. Cc: @StefanKarpinski (who I'm sure is aware of this.)

[StefanKarpinski]

Yeah, this is on my todo list if someone else doesn't get to it first.

[andyferris]

This looks like the same issue as #8991. Has something changed here?

Oh, sorry, I didn't see that one (it's sometimes hard when there are 1610 open issues).

Yeah, this is on my todo list if someone else doesn't get to it first.

With the latter part in mind, what is the plan, @StefanKarpinski? Get rid of Ordering and have the keyword arguments accept type-stable functions and rev = Val{true}/Val{false}?

[JeffBezanson]

I added the definition

julia/base/sort.jl

Line 194 in 2ab4a0d

$s(v::AbstractVector, x) = $s(v, x, Forward)

so that calls that don't use the ordering arguments don't get penalized. Is that present in the version you're using?

[andyferris]

OK I think so but I had to use the by keyword (not rev). For my case I replaced that with By and everything was OK. Nonetheless that definition you linked should cover most cases.

Is it possible to cover all the signatures that don't have rev in them? I can't remember the rules for methods that differ only by keyword arguments.

Also, should we document this stuff (#18370) or is this all changing? It seems to have existed a while without documentation.

[tkelman]

We should at least document how it currently works for the sake of the release where it isn't going to change API. That added method also overwrites the default no-keyword method causing some annoying warnings during system image compilation, if any package were to try and do the same thing I don't think users would like it very much.

[simonster]

With keyword arguments you are basically screwed no matter what as far as performance goes, at least until #16580.

[timholy]

And the whole sorting API should change now that we have jb/functions. Order is a relic from times when functions-as-arguments were too slow.

[JeffBezanson]

If you don't explicitly pass rev this is now type stable (and might be even if you do pass rev, but I didn't check).