use old searchsorted() implementation until julia 1.11

[aplavin]

Looks like the recently merged https://github.com/JuliaMath/IntervalSets.jl/pull/111 has a significant overhead on Julia 1.10(rc), 1.9, and earlier. It's only in 1.11 with https://github.com/JuliaLang/julia/pull/50365 where the overhead disappears. Here, I revert to the old searchsorted_interval implementation for older Julias.

Not just ranges – probably any type that is not an Array (?):

needle = 1..10

haystack = 1:10^5
@btime searchsorted_interval($haystack, $needle)
# IntervalSets 0.7.7 or this PR:
  2.541 ns (0 allocations: 0 bytes)
# IntervalSets 0.7.8:
  83.808 ns (2 allocations: 64 bytes)

using FlexiMaps
haystack = mapview(x -> x, collect(1:10^5))
@btime searchsorted_interval($haystack, $needle)
# IntervalSets 0.7.7 or this PR:
   50.997 ns (0 allocations: 0 bytes)
# IntervalSets 0.7.8:
  123.564 ns (2 allocations: 32 bytes)

For a package that's supposed to be used in all kinds of code, including performance-sensitive, these are highly noticeable.

[hyrodium]

Reverting the function may break the zero-step range test (https://github.com/JuliaMath/IntervalSets.jl/issues/100), right?

I think adding the following description to the documentation would be reasonable.

---

There was a performance degression in IntervalSets.jl v0.7.8 due to the Base implementation (https://github.com/JuliaLang/julia/pull/50365).

• For users who really care about the performance
  • and would like to use the latest version of this package:
    • Use upcoming Julia v1.11.
  • and are using Julia earlier than v1.11:
    • Install this package with ]add IntervalSets#v0.7.7
    • Or, add IntervalSets = "=0.7.7" to compat table in your Project.toml.
• For users who don't care about the performance:
  • Install the latest version of IntervalSets.jl on your Julia environment as usual.

See https://github.com/JuliaMath/IntervalSets.jl/pull/111 for more discussion.

[dlfivefifty]

I agree with @hyrodium: trying to keep performance high on every supported version of Julia is going to add a lot of burden to both the code writer and maintainers.

Is there evidence that this code is impacting other packages out in the wild? If not I think if its fine if its slow until Julia v1.11.

[aplavin]

trying to keep performance high on every supported version of Julia is going to add a lot of burden to both the code writer and maintainers

On every Julia version – yeah probably it's too much to ask for. But as it is now, the regression happens on all released Julia versions, and it will be the case for another ~year to come (even 1.10 isn't released yet, so who knows when 1.11 will be).

For users who don't care about the performance: ...

Pretty sure lots of Julia users do :)

Is there evidence that this code is impacting other packages out in the wild?

I actually found this regression by running FlexiJoins.jl tests, and noticed they fail because of way more allocations. Had to restrict IntervalSets compat (https://github.com/JuliaRegistries/General/pull/95080) to avoid this performance drop.

Well I guess if the decision is to keep this regression in IntervalSets, I'll just keep using 0.7.7 for another year or two (until 1.10- becomes irrelevant). In my view, regressions (and fixing them whenever possible) have higher priorities than potential new features.

[dlfivefifty]

Ah ok thanks for the explanation! Yes I agree if its impacting your code we should def fix it

[aplavin]

Fixing zero-step ranges seems trivial, should be ready to go now.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 79.48718% with 8 lines in your changes missing coverage. Please review.

Project coverage is 96.06%. Comparing base (9f3b49a) to head (8401b59). Report is 17 commits behind head on master.

Files with missing lines	Patch %	Lines
src/findall.jl	79.48%	8 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #168      +/-   ##
==========================================
- Coverage   99.10%   96.06%   -3.05%     
==========================================
  Files           4        4              
  Lines         224      254      +30     
==========================================
+ Hits          222      244      +22     
- Misses          2       10       +8     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[hyrodium]

I'm not sure that reopening the issue with Unitful.jl is considered as breaking. https://github.com/JuliaMath/IntervalSets.jl/pull/111#issuecomment-1767598579

[aplavin]

I'm generally indifferent to which decision is made regarding this PR (eg, release "breaking" version, or "non-breaking" one). I find it highly improbable that anyone already relies on features from #111, so would slightly prefer a "non-breaking" update even if technically breaking, just to reduce the burden across the ecosystem. So, leaving it to IntervalSets devs.

And even if this PR ends up simply closed I myself will be fine with that: will just use IntervalSets 0.7.7 until Julia 1.9 and 1.10 becomes irrelevant for me, then switch to Julia 1.11 and update IntervalSets. It's unlikely that IntervalSets gets many new important features in the next year, it's quite a stable package. Still, more generally I find this scenario unfortunate, especially given that 1.10 is likely to become the LTS version.