WTF::PairHashImpl<T,U,true>::hash() truncates 64-bit ints before hashing
Reported by
simon.ho...@arm.com,
Nov 4 2016
|
|||||
Issue descriptionAs far as I can tell, in the pairs-of-integral-types specialisation on PairHashImpl, the individual hashes of first and second are deferred and only the pairwise hashInts() is used. This eliminates redundant hashing provided the operands fit within `unsigned`, but no allowance is made for when one operand is _larger_ than unsigned so we get simple truncation. I believe this should emit a compiler warning, so hopefully it isn't happening in real code.
,
Nov 14 2016
While working on unit tests for 661425 I included a test for this. There is no compiler warning but the test does fail.
,
Nov 15 2016
https://codereview.chromium.org/2469893005/ contains template code for a unit test that would cover this. Just need to add this test: TEST(HashFunctionsTest, Int64IntHashCollisions) { auto result = countCollisions<std::pair<uint64_t, unsigned>, 2>(3); auto expect = expectedCollisions(result.second); auto allowed = static_cast<size_t>(ceil(3.0 * expect)); EXPECT_LE(result.first, allowed); } and that test will currently fail. Fixing this could conceivably introduce a performance regression and might not improve real-world collision performance, so it's not clear that anything needs to be done.
,
Nov 16 2016
,
Nov 17 2016
Yeah, this sounds like a bug. I think fixing this (in a correct manner) won't cause a perf regression, because it is guarded by a template.
,
Nov 17 2016
Sorry, I've realized I misunderstood the problem after I looked at the CL. I'm not sure if we should fix this, unless we have some evidence showing that we have too many collisions caused by this glitch in some real world scenarios. In our HashTable implementation, we chop off the hash value down to a few bits (depending on the table size), so the quality of hash values does not really matter in most cases. According to my prior research (on string hashes rather than int hashes), I found the calculation speed was much more important than the hash quality. So, assuming the same applies for int hashes, I guess we can leave it as it is...
,
Nov 17 2016
(This is not my area - why did I get cc'ed? Did you intend to cc someone else?)
,
Nov 17 2016
Oops, my bad (removing from cc).
,
Nov 10
|
|||||
►
Sign in to add a comment |
|||||
Comment 1 by cavalcantii@chromium.org
, Nov 4 2016Status: Assigned (was: Unconfirmed)