Random hashes with a more cache-friendly distribution

src/math.js

Index: src/math.js
diff --git a/src/math.js b/src/math.js
index fc3bf2fcdabf1b4fd5b0083d4b9a219454e388b7..1bd6a734757ff0f2d1c31ed60e31cbee4635652f 100644
--- a/src/math.js
+++ b/src/math.js
@@ -137,7 +137,15 @@ function MathRandom() {
   return (x < 0 ? (x + 0x100000000) : x) * 2.3283064365386962890625e-10;
 }
 
-function MathRandomRaw() {
+var level_0_left = 0;
+var level_0 = 0;
+var level_1_left = 0;
+var level_1 = 0;
+var level_2_left = 0;
+var level_2 = 0;
+
+
+function RandomHelper() {
   var r0 = (MathImul(18030, rngstate[0] & 0xFFFF) + (rngstate[0] >>> 16)) | 0;
   rngstate[0] = r0;
   var r1 = (MathImul(36969, rngstate[1] & 0xFFFF) + (rngstate[1] >>> 16)) | 0;
@@ -146,6 +154,36 @@ function MathRandomRaw() {
   return x & 0x3fffffff;
 }
 
+function MathRandomRaw() {
+  if (level_0_left != 0) {
+    // We have to clash 4 times before it gets annoying.
+    level_0 += 4;

[Erik Corry Chromium.org, 2015/05/26 21:56:56]

This should perhaps be co-prime with powers of 2.  5 seems to work well too, for
example.

+    level_0_left--;
+    return level_0;
+  }
+  if (level_1_left != 0) {
+    level_0_left = 8;
+    level_0 = (RandomHelper() & 0x1ff) + level_1;
+    level_1_left--;
+    return level_0;
+  }
+  if (level_2_left == 0) {
+    // Reduced 1 bit so the '+' doesn't overflow Smi.
+    level_2 = (RandomHelper() & 0x1fffffff);
+    level_2_left = 8;
+  }
+  // Level 0 and 1 give 128 entries, and the mask is 512, so we have
+  // to clash 4 times before it gets annoying at this level too. The
+  // mask of 512 is chosen to stay in one page on a 4k-page 8-byte-pointer
+  // system.
+  level_1_left = 16;
+  level_1 = (RandomHelper() & 0x3ffff) + level_2;
+  level_0_left = 8;
+  level_0 = (RandomHelper() & 0x1ff) + level_1;
+  level_2_left--;
+  return level_0;
+}
+
 // ECMA 262 - 15.8.2.15
 function MathRound(x) {
   return %RoundNumber(TO_NUMBER_INLINE(x));