New issue
Advanced search Search tips

Issue 662253 link

Starred by 3 users

Issue metadata

Status: Assigned
Owner:
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 3
Type: Bug

Blocked on:
issue 902789



Sign in to add a comment

WTF::PairHashImpl<T,U,true>::hash() truncates 64-bit ints before hashing

Reported by simon.ho...@arm.com, Nov 4 2016

Issue description

As 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.
 
Owner: cavalcantii@chromium.org
Status: Assigned (was: Unconfirmed)

Comment 2 by simon.ho...@arm.com, 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.

Comment 3 by simon.ho...@arm.com, 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.
Cc: scroggo@chromium.org yutak@chromium.org

Comment 5 by yutak@chromium.org, Nov 17 2016

Components: Blink>Internals>WTF
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.

Comment 6 by yutak@chromium.org, 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...
(This is not my area - why did I get cc'ed? Did you intend to cc someone else?)
Cc: -scroggo@chromium.org
Oops, my bad (removing from cc).
Blockedon: 902789

Sign in to add a comment