Skip to content

Faster integer hashing (fixes #37800 UB)#38031

Merged
vtjnash merged 2 commits intomasterfrom
jn/hash-faster
Oct 30, 2020
Merged

Faster integer hashing (fixes #37800 UB)#38031
vtjnash merged 2 commits intomasterfrom
jn/hash-faster

Conversation

@vtjnash
Copy link
Copy Markdown
Member

@vtjnash vtjnash commented Oct 14, 2020

In LLVM (inherited from C), fptosi has undefined behavior if the result
does not fit the integer size after rounding down. But by using the same
strategy as generic hashing of Real values, we actually can end up with
a situation that is not much slower for the CPU to deal with and avoids
the UB.

Refs #6624 (3696968)
Fixes #37800

Benchmarks:

julia> Random.seed!(1); a = rand(Int64, 10^8); b = copy(reinterpret(Float64, a)); c = rand(Float64, length(a)); d = copy(reinterpret(UInt64, a));
julia> @time sum(hash, a); @time sum(hash, b); @time sum(hash, c); @time sum(hash, d);

master:
  0.174493 seconds (1 allocation: 16 bytes)
  0.316409 seconds (1 allocation: 16 bytes)
  0.317264 seconds (1 allocation: 16 bytes)
  0.145938 seconds (1 allocation: 16 bytes)

PR:
  0.119815 seconds (1 allocation: 16 bytes)
  0.687834 seconds (1 allocation: 16 bytes)
  0.468544 seconds (1 allocation: 16 bytes)
  0.210141 seconds (1 allocation: 16 bytes)

Aside: note that integers-as-floating-point aren't affected as much:

julia> e = map(Float64, a);
master:  0.313309 seconds (1 allocation: 16 bytes)
PR:   0.338984 seconds (1 allocation: 16 bytes)

@StefanKarpinski I picked these factors mostly at random. So if you have better ideas for the specific hashing function itself, I'll update to that. This is showing the general idea and testing performance of it.

@jmkuhn
Copy link
Copy Markdown
Contributor

jmkuhn commented Oct 14, 2020

With this PR you have

julia> hash(0.0) == hash(-0.0)
true

@vtjnash
Copy link
Copy Markdown
Member Author

vtjnash commented Oct 15, 2020

Ah, you're right. Good catch. I completely botched that and forgot to use isequal with hashing instead of ==.

@vtjnash vtjnash added the triage This should be discussed on a triage call label Oct 19, 2020
StefanKarpinski
StefanKarpinski reviewed Oct 22, 2020
View reviewed changes
@vtjnash
Copy link
Copy Markdown
Member Author

vtjnash commented Oct 22, 2020

triage concluded to simplify this (disable the breaking tests), and otherwise to proceed

@vtjnash vtjnash removed the triage This should be discussed on a triage call label Oct 22, 2020
@vtjnash
faster hashing by avoiding UB
24dde5d 
In LLVM (inherited from C), fptosi has undefined behavior if the result
does not fit the integer size after rounding down. But by using the same
strategy as generic hashing of Real values, we actually can end up with
a sitatuion that is faster for the CPU to deal with and avoids the UB.

Refs #6624 (3696968)
Fixes #37800
@vtjnash
move hashing2 functions to their relevant files [NFC]
a38c088
@Keno
Copy link
Copy Markdown
Member

Keno commented Oct 29, 2020

What is holding this up? IIRC Triage ok'ed this, so can we just merge it?

@vtjnash vtjnash merged commit 9f8b22e into master Oct 30, 2020
@vtjnash vtjnash deleted the jn/hash-faster branch October 30, 2020 18:05
@jmkuhn jmkuhn mentioned this pull request Oct 30, 2020
Closed
@thofma thofma mentioned this pull request Oct 31, 2020
Merged
@vtjnash vtjnash mentioned this pull request Sep 29, 2022
Closed
@LilithHafner LilithHafner mentioned this pull request Jun 6, 2023
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@StefanKarpinski StefanKarpinski Awaiting requested review from StefanKarpinski

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Floating point hash bug

4 participants

@vtjnash @jmkuhn @Keno @StefanKarpinski