Skip to content

Faster searchsorted methods for range and array inputs#38527

Closed
IanButterworth wants to merge 2 commits intoJuliaLang:masterfrom
IanButterworth:ib/faster_searchsorted
Closed

Faster searchsorted methods for range and array inputs#38527
IanButterworth wants to merge 2 commits intoJuliaLang:masterfrom
IanButterworth:ib/faster_searchsorted

Conversation

@IanButterworth
Copy link
Copy Markdown
Member

@IanButterworth IanButterworth commented Nov 22, 2020 •
edited
Loading

For searching through an AbstractRange, the fastest one can use searchsortedfirst to evaluate multiple values currently is:

function foo(r, x)
   i = similar(x, keytype(r))
   @inbounds for ci in CartesianIndices(x)
       i[ci] = searchsortedfirst(r,x[ci])
   end
   return i
end
r = 0x00:0x02:0xff;
x = rand(UInt8, 1000, 1000);
@btime foo($r, $x)
  6.159 ms (2 allocations: 7.63 MiB)
1000×1000 Matrix{Int64}: ...

This PR provides the following, which only checks for one-based indexing and the length of r once, given they are expensive. It can also be preallocated:

@btime searchsortedfirst($r, $x)
  3.193 ms (2 allocations: 7.63 MiB)
1000×1000 Matrix{Int64}: ...

i = similar(x, keytype(r));
@btime searchsortedfirst!($i, $r, $x) 
  2.830 ms (0 allocations: 0 bytes)
1000×1000 Matrix{Int64}: ...

I didn't extend the methods for searching through AbstractVectors, as I didn't see a performance limitation with using those looped through values

@mcabbott
Copy link
Copy Markdown
Contributor

mcabbott commented Nov 22, 2020

Is it necessary to require one-based indexing at all? Perhaps + one(keytype(a)) can just be + firstindex(a), or does this go wrong somewhere?

@dkarrasch dkarrasch added collections Data structures holding multiple items, e.g. sets performance Must go faster labels Nov 22, 2020
@IanButterworth
Copy link
Copy Markdown
Member Author

IanButterworth commented Nov 22, 2020

Maybe! Would zero become firstindex(a) - 1?

I didn't feel confident enough to try to handle non one based indexed ranges. I assume that it would require adding test cases for stuff out in the ecosystem that I'm unaware of

@mcabbott
Copy link
Copy Markdown
Contributor

mcabbott commented Nov 22, 2020

The only example I know if is the axes of OffsetArrays, which behave like this:

julia> OffsetArray('a':'z', -10)
'a':1:'z' with indices -9:16

julia> axes(ans, 1)
OffsetArrays.IdOffsetRange(-9:16)

julia> axes(ans, 1)
OffsetArrays.IdOffsetRange(-9:16)

The general idea here is similar to JuliaMath/IntervalSets.jl#63, in which it wasn't so hard to allow offsets. But that can depend on the package for tests. I think there is a (simplified?) implementation of this loaded for tests, e.g. https://github.com/JuliaLang/julia/blob/master/test/offsetarray.jl

@KristofferC
Copy link
Copy Markdown
Member

KristofferC commented Nov 30, 2020

Is the addition of the new API (the bang versions of searchsortedxxx) necessarily coupled with the rest of this PR?

@IanButterworth
Copy link
Copy Markdown
Member Author

IanButterworth commented Dec 1, 2020

Not necessary, but logical I think. I think it would be odd to add the array-based methods without allowing preallocation.

Do you think the PR needs to be split?

vtjnash added a commit that referenced this pull request Apr 5, 2021
@vtjnash
ensure require_one_based_indexing can constant-fold for ranges
a89de9f 
Refs performance issue noted in #38527
@vtjnash vtjnash mentioned this pull request Apr 5, 2021
Merged
vtjnash
vtjnash reviewed Apr 5, 2021
View reviewed changes
@IanButterworth IanButterworth force-pushed the ib/faster_searchsorted branch from a1e4c1f to ccc981c Compare April 5, 2021 17:56
@vtjnash vtjnash mentioned this pull request Apr 6, 2021
Merged
@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Apr 6, 2021

While looking into this, I sought to understand the code, and realized there was a broken case resulting as the code had been slowly diverging over the years. I think this can be replaced by #40364 and #40358, and achieves the same performance objective without needing these new methods

@IanButterworth
Copy link
Copy Markdown
Member Author

IanButterworth commented Apr 6, 2021

Nice. Thanks!

vtjnash added a commit that referenced this pull request Apr 6, 2021
@vtjnash
ensure require_one_based_indexing can constant-fold for ranges (#40358)
bda6b94 
Refs performance issue noted in #38527
@IanButterworth
Copy link
Copy Markdown
Member Author

IanButterworth commented Apr 8, 2021

Closing given superseded by #40364 and #40358

@IanButterworth IanButterworth deleted the ib/faster_searchsorted branch April 8, 2021 01:09
ElOceanografo pushed a commit to ElOceanografo/julia that referenced this pull request May 4, 2021
@vtjnash @ElOceanografo
ensure require_one_based_indexing can constant-fold for ranges (Julia…
71ec23d 
…Lang#40358)

Refs performance issue noted in JuliaLang#38527
antoine-levitt pushed a commit to antoine-levitt/julia that referenced this pull request May 9, 2021
@vtjnash @antoine-levitt
ensure require_one_based_indexing can constant-fold for ranges (Julia…
e47a95e 
…Lang#40358)

Refs performance issue noted in JuliaLang#38527
johanmon pushed a commit to johanmon/julia that referenced this pull request Jul 5, 2021
@vtjnash @johanmon
ensure require_one_based_indexing can constant-fold for ranges (Julia…
dca61f1 
…Lang#40358)

Refs performance issue noted in JuliaLang#38527
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@vtjnash vtjnash vtjnash left review comments

Assignees

No one assigned

Labels

collections Data structures holding multiple items, e.g. sets performance Must go faster

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@IanButterworth @mcabbott @KristofferC @vtjnash @dkarrasch