Gridded: allow choosing the knot search (a scan beats bisection on short tables)

[1-Bart-1]

Gridded finds a knot with a fixed binary search:

@inline find_knot_index(knotv, x) = searchsortedfirst(knotv, x, Base.Order.ForwardOrdering()) - 1

On short tables that search is the dominant cost of a lookup. Measured on Vector{Float64} knots, Gridded(Linear()) + Flat(), Julia 1.12, Interpolations 0.16.3:

knots	searchsortedfirst alone	full lookup
9	5.06 ns	8.41 ns

The search alone costs more than an equivalent hand-written lookup that scans and clamps (3.71 ns total), because at this length a forward scan over contiguous memory is branch-predictable where bisection's branches are not. The crossover is around 20–30 knots; above it bisection wins by a lot (at 361 knots a scan is 71 ns vs 13 ns), so this is not a request to change the default — only to make it selectable.

There is a workaround today, since find_knot_index dispatches on the knot vector: define an AbstractVector wrapper with its own searchsortedfirst method.

struct ScanKnots <: AbstractVector{Float64}
    data::Vector{Float64}
end
Base.size(k::ScanKnots) = size(k.data)
Base.@propagate_inbounds Base.getindex(k::ScanKnots, i::Int) = k.data[i]
Base.IndexStyle(::Type{ScanKnots}) = IndexLinear()
@inline function Base.searchsortedfirst(k::ScanKnots, x, ::Base.Order.ForwardOrdering)
    @inbounds for i in eachindex(k.data)
        k.data[i] >= x && return i
    end
    return length(k.data) + 1
end

That takes the n=9 lookup from 7.78 ns to 5.84 ns and is not piracy, but every package that wants it reinvents the same wrapper, and it only works if you happen to know that the search dispatches on the knot type.

Would you take something like Gridded(Linear(); search = ...) — or any documented hook for the knot search — so short-table users can opt in without a custom AbstractVector? Happy to open a PR if there's a shape you'd prefer.

[mkitti]

Go ahead and submit the pull request. I'm trying to decide if the keyword argument makes sense. Alternatives:

1. Add another Gridded-like type
2. Add a type parameter to Gridded