Correct truncation behaviour in WTF::hashInts()

Correct truncation behaviour in WTF::hashInts()

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425
Committed: https://crrev.com/31223fba349e0ca9dc98655961767b4c6471744a
Cr-Commit-Position: refs/heads/master@{#433384}

[cavalcantii1, 2016-11-04 01:55:12]

The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run

[Simon Hosie, 2016-11-04 01:56:00]

The CQ bit was checked by simon.hosie@arm.com to run a CQ dry run

[commit-bot: I haz the power, 2016-11-04 01:56:07]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[cavalcantii1, 2016-11-04 02:00:25]

The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-04 02:00:56]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-04 05:39:55]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-04 05:39:56]

Dry run: This issue passed the CQ dry run.

[cavalcantii1, 2016-11-14 23:09:59]

The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-14 23:11:16]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Simon Hosie, 2016-11-14 23:12:23]

./wtf_unittests --gtest_filter='HashFunctionsTest.*'
Before fix:
[==========] Running 3 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 3 tests from HashFunctionsTest
[ RUN      ] HashFunctionsTest.IntHashCollisions
[       OK ] HashFunctionsTest.IntHashCollisions (2 ms)
[ RUN      ] HashFunctionsTest.Int64HashCollisions
[       OK ] HashFunctionsTest.Int64HashCollisions (4 ms)
[ RUN      ] HashFunctionsTest.IntIntHashCollisions
../../third_party/WebKit/Source/wtf/HashFunctionsTest.cpp:199: Failure
Expected: (result.first) <= (allowed), actual: 3720 vs 1
[  FAILED  ] HashFunctionsTest.IntIntHashCollisions (9 ms)
[----------] 3 tests from HashFunctionsTest (15 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 1 test case ran. (15 ms total)
[  PASSED  ] 2 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] HashFunctionsTest.IntIntHashCollisions

After:
[==========] Running 3 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 3 tests from HashFunctionsTest
[ RUN      ] HashFunctionsTest.IntHashCollisions
[       OK ] HashFunctionsTest.IntHashCollisions (2 ms)
[ RUN      ] HashFunctionsTest.Int64HashCollisions
[       OK ] HashFunctionsTest.Int64HashCollisions (3 ms)
[ RUN      ] HashFunctionsTest.IntIntHashCollisions
[       OK ] HashFunctionsTest.IntIntHashCollisions (10 ms)
[----------] 3 tests from HashFunctionsTest (15 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 1 test case ran. (15 ms total)
[  PASSED  ] 3 tests.

[Simon Hosie, 2016-11-15 00:01:02]

Description was changed from

==========
Correct truncation behaviour in WTF::hashInts().

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425
==========

to

==========
Correct truncation behaviour in WTF::hashInts()

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425
==========

[commit-bot: I haz the power, 2016-11-15 03:59:25]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-15 03:59:26]

Dry run: Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[Simon Hosie, 2016-11-15 19:02:25]

simon.hosie@arm.com changed reviewers:
+ danakj@chromium.org, yutak@chromium.org

[Yuta Kitamura, 2016-11-17 11:55:48]

This would probably cause a perf regression, and I think
the benefit of having better hashes is probably very small
in practical cases, so I don't think this is worth fixing,
unless we find an evidence denying my (either) assumption.

(However, it's a good idea to just add a comment about this
bug.)

[Simon Hosie, 2016-11-17 17:40:56]

On 2016/11/17 11:55:48, Yuta Kitamura wrote:
> This would probably cause a perf regression, and I think
> the benefit of having better hashes is probably very small
> in practical cases, so I don't think this is worth fixing,
> unless we find an evidence denying my (either) assumption.
> 
> (However, it's a good idea to just add a comment about this
> bug.)

Oh, sorry about the confusion, here; I filed two different bugs on two different
blocks of code (https://crbug.com/661425 and https://crbug.com/662253) because I
estimated that the latter would almost certainly require extra computation for
questionable benefit, while this one I think we can change without a performance
loss.

I'd better test that.

Here the idea is that the change in truncation enables algebraic simplification
of the whole algorithm.  64-bit architectures go from three multiplies down to
two.  Superficially it looks faster unless the CPU does enough data-dependant
optimisation to tip the balance the other way.

On 32-bit hardware I haven't looked as closely as I should have.  So I'll do
that now.  Seems like it should go from five down to four multiplies.

In 662253 I've experimented with some options but the results are unquestionably
slower, so I thought it better go in a different bug because it was likely to be
not appropriate.

[Simon Hosie, 2016-11-18 02:49:23]

On 2016/11/17 17:40:56, Simon Hosie wrote:
> I'd better test that.

Well that was an ordeal.  It turns out both Clang and GCC were making
counterproductive attempts at vectorising my simple test loop and that was
causing really uneven results.  It all cleared up when I made the loop
recursive.

Counting the number of clock() ticks (smaller is better) over multiple runs of
the following loop on various compilers:

    for (int j = 0; j < 1000000; ++j)
      x = hashInts_XXX(x, x ^ j);

-mtune=sandybridge:

./hashbench_clang_64:
old: 3246878
new: 2263578
./hashbench_gcc610_64:
old: 3588722
new: 2903137
./hashbench_clang_32:
old: 4976384
new: 4557503
./hashbench_gcc610_32:
old: 5022923
new: 4292507

-mtune=cortex-a57:

./hashbench_arm_clang_64:
old: 4788986
new: 5014435
./hashbench_arm_gcc490_64:
old: 5242084
new: 5241886
./hashbench_arm_gcc610_64:
old: 5241929
new: 5241840
./hashbench_arm_clang_32:
old: 6196593
new: 4774689
./hashbench_arm_gcc490_32:
old: 6194095
new: 5242111
./hashbench_arm_gcc610_32:
old: 6676624
new: 5249997

-mtune=cortex-a15:

./hashbench_a15_clang_32:
old: 9100811
new: 7373919
./hashbench_a15_gcc490_32:
old: 7938755
new: 6805359
./hashbench_a15_gcc610_32:
old: 8505152
new: 6804352

That glitch in arm_clang_64 is reflected in the quality of the code generated. 
I'll chase that up elsewhere, and I think it's OK to ignore it right now.

Apart from that all the tests run equal or faster with the change.

[Yuta Kitamura, 2016-11-18 09:41:37]

If the perf does not suffer, I'm okay with landing this.

The test, however, seems overly complex. This kind of tests
does not make a great sense as unit tests, so I'd drop
the tests and just land only the hash func change.

LGTM if the changes to HashFunctionsTest.cpp and BUILD.gn are
reverted.

[cavalcantii1, 2016-11-19 00:43:43]

Adding it to the CQ.

[cavalcantii1, 2016-11-19 00:43:48]

The CQ bit was checked by cavalcantii@chromium.org

[cavalcantii1, 2016-11-19 00:43:49]

The patchset sent to the CQ was uploaded after l-g-t-m from yutak@chromium.org
Link to the patchset: https://codereview.chromium.org/2469893005/#ps40001
(title: "remove test logic")

[commit-bot: I haz the power, 2016-11-19 00:44:39]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-19 02:28:18]

Description was changed from

==========
Correct truncation behaviour in WTF::hashInts()

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425
==========

to

==========
Correct truncation behaviour in WTF::hashInts()

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425
==========

[commit-bot: I haz the power, 2016-11-19 02:28:19]

Committed patchset #3 (id:40001)

[commit-bot: I haz the power, 2016-11-19 02:30:57]

Description was changed from

==========
Correct truncation behaviour in WTF::hashInts()

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425
==========

to

==========
Correct truncation behaviour in WTF::hashInts()

Multiplies were being truncated to 32-bit prematurely, thereby failing to
implement the advertised algorithm and allowing trivial hash collisions.

Also the final shift was calculated incorrectly, and the reference suggests
that longRandom should be odd.

And with the type promotion happening earlier it's possible to refactor the
arithmetic to perform two multiplies rather than three.

BUG=661425

Committed: https://crrev.com/31223fba349e0ca9dc98655961767b4c6471744a
Cr-Commit-Position: refs/heads/master@{#433384}
==========

[commit-bot: I haz the power, 2016-11-19 02:30:59]

Patchset 3 (id:??) landed as
https://crrev.com/31223fba349e0ca9dc98655961767b4c6471744a
Cr-Commit-Position: refs/heads/master@{#433384}