[Experimental, DO NOT LAND] bucket num 4

base/memory/address_hasher.cc

Index: base/memory/address_hasher.cc
diff --git a/base/memory/address_hasher.cc b/base/memory/address_hasher.cc
new file mode 100644
index 0000000000000000000000000000000000000000..69ea83be7f3114b399947ca82bada6d131f32998
--- /dev/null
+++ b/base/memory/address_hasher.cc
@@ -0,0 +1,23 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/memory/address_hasher.h"
+
+namespace base {
+
+size_t AddressHasher::operator()(const void* address) const {
+  // The multiplicative hashing scheme from [Knuth 1998]. The value of |a| has
+  // been chosen carefully based on measurements with real-word data (addresses
+  // recorded from a Chrome trace run). It is the first prime after 2^17. For
+  // |shift|, 15 yield good results for both 2^18 and 2^19 bucket sizes.
+  // Microbenchmarks show that this simple scheme outperforms fancy hashes like
+  // Murmur3 by 20 to 40 percent.
+  const uintptr_t key = reinterpret_cast<uintptr_t>(address);
+  const uintptr_t a = 131101;
+  const uintptr_t shift = 15;
+  const uintptr_t h = (key * a) >> shift;
+  return h;
+}
+
+}  // namespace base