Random hashes with a more cache-friendly distribution

src/math.js

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 var rngstate;  // Initialized to a Uint32Array during genesis.
 
 (function(global, utils) {
 "use strict";
 
 %CheckIsBootstrapping();
@@ skipping 119 matching lines @@
 function MathRandom() {
   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;
   rngstate[1] = r1;
   var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
   // Division by 0x100000000 through multiplication by reciprocal.
   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;
   rngstate[1] = r1;
   var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
   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));
 }
 
 // ECMA 262 - 15.8.2.17
 function MathSqrtJS(x) {
   return %_MathSqrt(+x);
 }
 
@@ skipping 206 matching lines @@
 utils.Export(function(to) {
   to.MathAbs = MathAbs;
   to.MathExp = MathExp;
   to.MathFloor = MathFloorJS;
   to.IntRandom = MathRandomRaw;
   to.MathMax = MathMax;
   to.MathMin = MathMin;
 });
 
 })