Skip to content

Fix length(::AbstractUnitRange) and speed up length(::AbstractUnitRange{<:Rational})#41479

Merged
KristofferC merged 11 commits intoJuliaLang:masterfrom
sostock:unitrangelength
Jul 28, 2021
Merged

Fix length(::AbstractUnitRange) and speed up length(::AbstractUnitRange{<:Rational})#41479
KristofferC merged 11 commits intoJuliaLang:masterfrom
sostock:unitrangelength

Conversation

@sostock
Copy link
Copy Markdown
Contributor

@sostock sostock commented Jul 6, 2021

The new length(::AbstractUnitRange) method from #40382 breaks HalfIntegers.jl (the Integer conversion circumvents the correct overflow behavior of HalfIntegers).

This PR fixes the length(::AbstractUnitRange) implementation. Since this change would slow down the AbstractUnitRange{<:Rational} case, I also added a specialized method for Rationals.

Current master:

julia> r = 49//17:338//17;

julia> @btime length($r);
  40.893 ns (0 allocations: 0 bytes)

This PR:

julia> r = 49//17:338//17;

julia> @btime length($r);
  0.020 ns (0 allocations: 0 bytes)

jw3126
jw3126 reviewed Jul 6, 2021
View reviewed changes
jw3126
jw3126 reviewed Jul 6, 2021
View reviewed changes
Copy link
Copy Markdown
Contributor

@jw3126 jw3126 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you maybe add a mwe test that mimics the failure in HalfIntegers.jl?

sostock and others added 2 commits July 6, 2021 16:22
@sostock @jw3126
Replace one by oneunit
206f154 
Co-authored-by: Jan Weidner <jw3126@gmail.com>
@sostock
Add test
c8e04d6
@sostock
Copy link
Copy Markdown
Contributor Author

sostock commented Jul 6, 2021

Can you maybe add a mwe test that mimics the failure in HalfIntegers.jl?

Done!

jw3126
jw3126 reviewed Jul 7, 2021
View reviewed changes
@sostock @jw3126
Add reference to PR
4a49d28 
Co-authored-by: Jan Weidner <jw3126@gmail.com>
@jw3126
Copy link
Copy Markdown
Contributor

jw3126 commented Jul 8, 2021

Can somebody rerun the failing CI?

@giordano
Copy link
Copy Markdown
Member

giordano commented Jul 10, 2021 •
edited
Loading

I suspect a similar fix is needed for Unitful.jl, for the length(r::OrdinalRange{T}) method: #40382 (comment).

Dividing

julia/base/range.jl

Line 668 in 56bb340

return Integer(start - start + zero(s))

by oneunit(s) might be sufficient

@sostock sostock mentioned this pull request Jul 15, 2021
Merged
@sostock
Copy link
Copy Markdown
Contributor Author

sostock commented Jul 15, 2021

I suspect a similar fix is needed for Unitful.jl, for the length(r::OrdinalRange{T}) method

I have now opened a PR for that as well: #41595

JeffBezanson
JeffBezanson reviewed Jul 19, 2021
View reviewed changes
vtjnash
vtjnash reviewed Jul 19, 2021
View reviewed changes
sostock
sostock commented Jul 22, 2021
View reviewed changes
base/rational.jl
# This method is only needed for performance. Since `first(r)` and `last(r)` have the same
# denominator (because their difference is an integer), `length(r)` can be calulated without
# calling `gcd`.
function length(r::AbstractUnitRange{T}) where T<:Rational
Copy link
Copy Markdown
Contributor Author

@sostock sostock Jul 22, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This method not only adds performance but changes behavior as well: Without this method, length(::AbstractUnitRange{<:Rational}) uses Rational arithmetic, which is checked. The specialized method uses integer arithmetic, so it can overflow.

I realize that we are okay with an overflowing length, but should this also apply to Rationals, which are using checked arithmetic by default? Or should the behavior be changed so that it matches Rational arithmetic?

I will add a specialized checked_length(::AbstractUnitRange{<:Rational}) method in any case.

Copy link
Copy Markdown
Member

@vtjnash vtjnash Jul 22, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think it is okay, since it should generally only overflow for extreme values that are unlikely

sostock
sostock commented Jul 24, 2021
View reviewed changes
base/rational.jl
@_inline_meta
f = first(r)
l = last(r)
return div(l.num - f.num + f.den, f.den)
Copy link
Copy Markdown
Contributor Author

@sostock sostock Jul 24, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
return div(l.num - f.num + f.den, f.den)
a = fld(l.num, l.den) - fld(f.num, f.den)
return a + oneunit(a)

This change would reduce the risk of overflow, but would be slightly less performant (two integer divisions instead of one). Is it worth it?

@KristofferC KristofferC merged commit 1c951f7 into JuliaLang:master Jul 28, 2021
@KristofferC KristofferC mentioned this pull request Aug 2, 2021
Merged
82 tasks
KristofferC pushed a commit that referenced this pull request Aug 2, 2021
@sostock @KristofferC
Fix length(::AbstractUnitRange) and speed up `length(::AbstractUnit…
6153a7e 
…Range{<:Rational})` (#41479)

* Fix length(::AbstractUnitRange), faster length(::AbstractUnitRange{<:Rational})

(cherry picked from commit 1c951f7)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@JeffBezanson JeffBezanson JeffBezanson left review comments

@vtjnash vtjnash vtjnash approved these changes

+1 more reviewer

@jw3126 jw3126 jw3126 left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

7 participants

@sostock @jw3126 @giordano @vtjnash @JeffBezanson @KristofferC @DilumAluthge