Skip to content

More hash optimization#50041

Merged
oscardssmith merged 3 commits intoJuliaLang:masterfrom
oscardssmith:more-hash-optimization
Jun 7, 2023
Merged

More hash optimization#50041
oscardssmith merged 3 commits intoJuliaLang:masterfrom
oscardssmith:more-hash-optimization

Conversation

@oscardssmith
Copy link
Copy Markdown
Member

@oscardssmith oscardssmith commented Jun 2, 2023

This is two separate optimizations.

The first is speeding up hash(::Union{Float16, Float32}) using the fact that they always are within the range of Int64 so you don't need to check that (or check whether they are within the UInt64 range.

The second is that AbstractFloats and Integers will never have a denominator that isn't 1, so we can change the rules of hashing to not hash the denominator if it is 1.

speed up hash of Float32/Float16 since they never are big numbers, an…
1ea1093 
…d hash of arbitrary real types by not hashing the denominatior when it is one
@sjkelly
Copy link
Copy Markdown
Contributor

sjkelly commented Jun 2, 2023

Do you have benchmarks?

@oscardssmith
Copy link
Copy Markdown
Member Author

oscardssmith commented Jun 2, 2023 •
edited
Loading 

#Before
julia> @btime hash(x, UInt(1)) setup=x=rand(Int128)
  16.148 ns (0 allocations: 0 bytes)

julia> @btime hash(x, UInt(1)) setup=x=big(rand(Int128))
  18.352 ns (0 allocations: 0 bytes)

#After
julia> @btime hash(x, UInt(1)) setup=x=rand(Int128)
  11.877 ns (0 allocations: 0 bytes)

julia> @btime hash(x, UInt(1)) setup=x=big(rand(Int128))
  18.248 ns (0 allocations: 0 bytes)

@oscardssmith
Copy link
Copy Markdown
Member Author

oscardssmith commented Jun 6, 2023

Now that we've successfully unbroken hashing on master, I think this is ready to go.

@oscardssmith oscardssmith requested a review from LilithHafner June 6, 2023 18:11
@oscardssmith oscardssmith merged commit 36c5953 into JuliaLang:master Jun 7, 2023
@oscardssmith oscardssmith deleted the more-hash-optimization branch June 7, 2023 13:26
@LilithHafner
Copy link
Copy Markdown
Member

LilithHafner commented Jun 7, 2023

For optimization 1, the OP is out of date, only Float16s are changed, not Float32s as well? I also don't see the speedup:

julia> @btime sum(hash, reinterpret(Float16, typemin(UInt16):typemax(UInt16)));
  224.000 μs (0 allocations: 0 bytes)

shell> git checkout more-hash-optimization -- base/float.jl base/gmp.jl base/rational.jl

julia> @btime sum(hash, reinterpret(Float16, typemin(UInt16):typemax(UInt16)));
  223.333 μs (0 allocations: 0 bytes)

@oscardssmith
Copy link
Copy Markdown
Member Author

oscardssmith commented Jun 7, 2023

Updated benchmarks. I agree that I'm not seeing much improvement for Float16. Not fully sure why.

@LilithHafner
Copy link
Copy Markdown
Member

LilithHafner commented Jun 8, 2023

If this doesn't provide measurable performance benefits, we should probably remove it:

julia/base/float.jl

Lines 658 to 669 in 0a2d6fc

function hash(x::Float16, h::UInt)
# see comments on trunc and hash(Real, UInt)
if isfinite(x) # all finite Float16 fit in Int64
xi = fptosi(Int64, x)
if isequal(xi, x)
return hash(xi, h)
end
elseif isnan(x)
return hx_NaN ⊻ h # NaN does not have a stable bit pattern
end
return hash_uint64(bitcast(UInt64, Float64(x))) - 3h
end

This was referenced Jul 21, 2023
Closed
Merged
@sostock sostock mentioned this pull request Jul 26, 2023
Merged
oscardssmith added a commit that referenced this pull request Jul 26, 2023
@oscardssmith
fix hashing regression. (#50655)
c777c71 
This fixes 2 bugs introduced by #49996 and #50041.
Closes #50628.
KristofferC pushed a commit that referenced this pull request Aug 10, 2023
@oscardssmith @KristofferC
fix hashing regression. (#50655)
3e133c9 
This fixes 2 bugs introduced by #49996 and #50041.
Closes #50628.

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

Reviewers

@LilithHafner LilithHafner Awaiting requested review from LilithHafner

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@oscardssmith @sjkelly @LilithHafner