slow searchsorted due to keyword argument

[simonbyrne]

The keyword argument in searchsortedfirst/searchsortedlast causes a performance hit when used repeatedly, even when no keyword argument is used in calling:

julia> X = randn(10_000_000);

julia> f(X)=Int[searchsortedfirst(-5.0:5.0,x,Base.Order.Forward) for x in X]
f (generic function with 1 method)

julia> g(X)=Int[searchsortedfirst(-5.0:5.0,x) for x in X]
g (generic function with 1 method)

julia> @time f(X);
elapsed time: 1.461309065 seconds (80144356 bytes allocated)

julia> @time g(X);
elapsed time: 2.445579336 seconds (640000128 bytes allocated, 12.64% gc time)

cf: #8952

[simonster]

I think the performance hit actually comes not from the keyword arguments (which might cause a hit if a keyword argument is passed, but shouldn't if none are passed), but from absence of type information for the ordering returned by ord:

julia> @code_typed searchsortedfirst(-5.0:5.0,1.0)
1-element Array{Any,1}:
 :($(Expr(:lambda, Any[:v,:x], Any[Any[],Any[Any[:v,FloatRange{Float64},0],Any[:x,Float64,0]],Any[]], :(begin $(Expr(:line, 219, symbol("sort.jl"), symbol("")))
        return searchsortedfirst(v::FloatRange{Float64},x::Float64,ord(isless::F,identity::F,false,Forward::ForwardOrdering))::Int64
    end::Int64))))

[JeffBezanson]

Keyword arguments are no longer the problem here, but this has indeed gotten much slower.
v0.5: ~1.5 sec
v0.6: ~3.0 sec
v0.7: ~3.9 sec

[ViralBShah]

I now note with 0.7-alpha, that we are slightly better than 0.6. (2.8 sec on 0.7-alpha).

[JeffBezanson]

Almost all of the time here is in constructing the range, probably because ranges have gotten much more sophisticated. In the case of 2-argument :, a lot of time is wasted computing rat and twice-precision division for a step of 1. It might be worth special-casing that value in 3-argument colon.

I'll close this and open a new issue, since the part specific to searchsorted is fixed.