JuliaMath / JuliaMath/Interpolations.jl

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

Open
#656 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
575
Forks
117
PR merge metrics
No merged PRs in 30d

Description

`Gridded` finds a knot with a fixed binary search:

```julia
@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.

```julia
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.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start at the find_knot_index definition and trace how Gridded(Linear()) selects and invokes the knot search. Compare the existing bisection path with the issue's scan example, then determine how an opt-in search hook can preserve the current default; done means short-table users can select the alternative without a custom AbstractVector and existing behavior remains unchanged.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
65/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.