In the current implementation of hash code for objects (identity hash),
we do not bother to shift the hash when we retrieve it from the 
hash-length bitfield in a property array. (Even worse, we store shifted
value even if we do not have property array or inside dictionaries.)
That means that the hash-code for objects is always divisible by 1024.
Since our hash table uses a simple masking with (2^logsize - 1) to 
obtain the bucket, we get terrible hash collisions - essentially, our
hash table degenerates to a linked list for fewer than 1024 elements.

This CL always shifts the hash code so that the value in the lowest 
21 bits is uniformly distributed.

This results in big improvements on medium to large hash tables.
A program storing 1M elements into a WeakMap gets roughly
17x faster.  A program retrieving 1M elements from a Map 
improves even more dramatically (>100x).

const a = [];
for (let i = 0; i < 1e6; i++) a[i] = {};

const m = new Map();
console.time("Map.set");
for (let i = 0; i < 1e6; i++) {
  m.set(a[i], i);
}
console.timeEnd("Map.set");

console.time("Map.get");
let s = 0;
for (let i = 0; i < 1e6; i++) {
  s += m.get(a[i]);
}
console.timeEnd("Map.get");

const w = new WeakMap();
console.time("WeakMap.set");
for (let i = 0; i < 1e6; i++) {
  w.set(a[i], i);
}
console.timeEnd("WeakMap.set");

Before the fix:

Map.set: 157.575000
Map.get: 28333.182000
WeakMap.set: 6923.826000

After the fix:

Map.set: 178.382000
Map.get: 185.930000
WeakMap.set: 409.529000

Note that Map does not suffer from the hash collision on insertion because
it uses chaining (insertion into linked list is fast regardless of size!), and
we cleverly avoid lookup in the hash table on update if the key does not have 
identity hash yet. This is in contrast to the WeakMap, which uses 
open-addressing, and deals with collisions on insertion.

Bug: v8:6916
Change-Id: Ic5497bd4501e3b767b3f4acb7efb4784cbb3a2e4
Reviewed-on: https://chromium-review.googlesource.com/713616Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#48480}