Use a better hash function in IdentityMap.

Use a better hash function in IdentityMap.

Reduces time for ConstantArrayBuilderTest.AllocateAllEntries from 21000ms to 106ms in
debug mode.

BUG=v8:4280
LOG=N

Committed: https://crrev.com/c68f7194c2b27a9960bb2ab213cb0feb0a3d5341
Cr-Commit-Position: refs/heads/master@{#34038}

[rmcilroy, 2016-02-16 12:57:53]

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

[commit-bot: I haz the power, 2016-02-16 12:57:58]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1696363002/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1696363002/1

[rmcilroy, 2016-02-16 12:58:53]

rmcilroy@chromium.org changed reviewers:
+ titzer@chromium.org

[rmcilroy, 2016-02-16 12:58:53]

We use identity map for SMIs to, so the assumption that previous xoring approach
didn't work well for that. PTAL, thanks.

[titzer, 2016-02-16 13:02:27]

https://codereview.chromium.org/1696363002/diff/1/src/identity-map.cc
File src/identity-map.cc (left):

https://codereview.chromium.org/1696363002/diff/1/src/identity-map.cc#oldcode45
src/identity-map.cc:45: // Xor some of the upper bits, since the lower 2 or 3
are usually aligned.
What about the original comment? Objects will typically have the low-order two
bits set to "01" or "001" depending on the architecture. Does the hash utility
deal with this?

[commit-bot: I haz the power, 2016-02-16 13:17:31]

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

[commit-bot: I haz the power, 2016-02-16 13:17:32]

Dry run: This issue passed the CQ dry run.

[rmcilroy, 2016-02-16 14:00:55]

https://codereview.chromium.org/1696363002/diff/1/src/identity-map.cc
File src/identity-map.cc (left):

https://codereview.chromium.org/1696363002/diff/1/src/identity-map.cc#oldcode45
src/identity-map.cc:45: // Xor some of the upper bits, since the lower 2 or 3
are usually aligned.
On 2016/02/16 13:02:27, titzer wrote:
> What about the original comment? Objects will typically have the low-order two
> bits set to "01" or "001" depending on the architecture. Does the hash utility
> deal with this?

It uses 64-bit mix functions:
https://gist.github.com/badboy/6267743#64-bit-mix-functions
This does a bunch of shifting from upper to lower bits, so it should still be
good for aligned pointers.

[titzer, 2016-02-16 14:04:28]

On 2016/02/16 14:00:55, rmcilroy wrote:
> https://codereview.chromium.org/1696363002/diff/1/src/identity-map.cc
> File src/identity-map.cc (left):
> 
>
https://codereview.chromium.org/1696363002/diff/1/src/identity-map.cc#oldcode45
> src/identity-map.cc:45: // Xor some of the upper bits, since the lower 2 or 3
> are usually aligned.
> On 2016/02/16 13:02:27, titzer wrote:
> > What about the original comment? Objects will typically have the low-order
two
> > bits set to "01" or "001" depending on the architecture. Does the hash
utility
> > deal with this?
> 
> It uses 64-bit mix functions:
> https://gist.github.com/badboy/6267743#64-bit-mix-functions
> This does a bunch of shifting from upper to lower bits, so it should still be
> good for aligned pointers.

lgtm

[rmcilroy, 2016-02-16 14:07:20]

The CQ bit was checked by rmcilroy@chromium.org

[commit-bot: I haz the power, 2016-02-16 14:07:37]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1696363002/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1696363002/1

[commit-bot: I haz the power, 2016-02-16 14:08:49]

Committed patchset #1 (id:1)

[commit-bot: I haz the power, 2016-02-16 14:09:10]

Description was changed from

==========
Use a better hash function in IdentityMap.

Reduces time for ConstantArrayBuilderTest.AllocateAllEntries from 21000ms to
106ms in
debug mode.

BUG=v8:4280
LOG=N
==========

to

==========
Use a better hash function in IdentityMap.

Reduces time for ConstantArrayBuilderTest.AllocateAllEntries from 21000ms to
106ms in
debug mode.

BUG=v8:4280
LOG=N

Committed: https://crrev.com/c68f7194c2b27a9960bb2ab213cb0feb0a3d5341
Cr-Commit-Position: refs/heads/master@{#34038}
==========

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

Patchset 1 (id:??) landed as
https://crrev.com/c68f7194c2b27a9960bb2ab213cb0feb0a3d5341
Cr-Commit-Position: refs/heads/master@{#34038}