Bug 1382324 - Improve SpiderMonkey's pointer hashing function for pointers to neighboring memory locations; r=jandem
authorEhsan Akhgari <ehsan@mozilla.com>
Wed, 19 Jul 2017 14:34:16 -0400
changeset 418701 c0e5f705407b20acd628c572341e61366eda374e
parent 418700 da3b6b55ed0ba18e6efa6198c22af3ef8c90b5b3
child 418702 7e4f222d9501589ef8c53e58a5e90e9cc73763a6
push id7566
push usermtabara@mozilla.com
push dateWed, 02 Aug 2017 08:25:16 +0000
treeherdermozilla-beta@86913f512c3c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs1382324, 1379282
milestone56.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1382324 - Improve SpiderMonkey's pointer hashing function for pointers to neighboring memory locations; r=jandem This is very similar to the fix to bug 1379282 for the XPCOM hashtables.
js/public/HashTable.h
js/public/UbiNode.h
js/src/gc/Nursery.h
js/src/gc/StoreBuffer.h
js/src/gc/Zone.h
js/src/jit/LoopUnroller.cpp
js/src/jit/OptimizationTracking.cpp
js/src/vm/Caches.h
js/src/vm/SavedFrame.h
js/src/vm/TraceLogging.h
js/xpconnect/src/xpcprivate.h
--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -577,34 +577,26 @@ class HashSet
 // added Key value |k|, the user must ensure that |P::match(k,l)|. E.g.:
 //
 //   js::HashSet<Key, P>::AddPtr p = h.lookup(l);
 //   if (!p) {
 //     assert(P::match(k, l));  // must hold
 //     h.add(p, k);
 //   }
 
-// Pointer hashing policy that strips the lowest zeroBits when calculating the
-// hash to improve key distribution.
-template <typename Key, size_t zeroBits>
+// Pointer hashing policy that uses HashGeneric() to create good hashes for
+// pointers.  Note that we don't shift out the lowest k bits to generate a
+// good distribution for arena allocated pointers.
+template <typename Key>
 struct PointerHasher
 {
     typedef Key Lookup;
     static HashNumber hash(const Lookup& l) {
-        size_t word = reinterpret_cast<size_t>(l) >> zeroBits;
-        static_assert(sizeof(HashNumber) == 4,
-                      "subsequent code assumes a four-byte hash");
-#if JS_BITS_PER_WORD == 32
-        return HashNumber(word);
-#else
-        static_assert(sizeof(word) == 8,
-                      "unexpected word size, new hashing strategy required to "
-                      "properly incorporate all bits");
-        return HashNumber((word >> 32) ^ word);
-#endif
+        size_t word = reinterpret_cast<size_t>(l);
+        return mozilla::HashGeneric(word);
     }
     static bool match(const Key& k, const Lookup& l) {
         return k == l;
     }
     static void rekey(Key& k, const Key& newKey) {
         k = newKey;
     }
 };
@@ -628,26 +620,26 @@ struct DefaultHasher
     static void rekey(Key& k, const Key& newKey) {
         k = newKey;
     }
 };
 
 // Specialize hashing policy for pointer types. It assumes that the type is
 // at least word-aligned. For types with smaller size use PointerHasher.
 template <class T>
-struct DefaultHasher<T*> : PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>
+struct DefaultHasher<T*> : PointerHasher<T*>
 {};
 
 // Specialize hashing policy for mozilla::UniquePtr to proxy the UniquePtr's
 // raw pointer to PointerHasher.
 template <class T, class D>
 struct DefaultHasher<mozilla::UniquePtr<T, D>>
 {
     using Lookup = mozilla::UniquePtr<T, D>;
-    using PtrHasher = PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>;
+    using PtrHasher = PointerHasher<T*>;
 
     static HashNumber hash(const Lookup& l) {
         return PtrHasher::hash(l.get());
     }
     static bool match(const mozilla::UniquePtr<T, D>& k, const Lookup& l) {
         return PtrHasher::match(k.get(), l.get());
     }
     static void rekey(mozilla::UniquePtr<T, D>& k, mozilla::UniquePtr<T, D>&& newKey) {
--- a/js/public/UbiNode.h
+++ b/js/public/UbiNode.h
@@ -809,17 +809,17 @@ class Node {
         MOZ_ASSERT(JS::Value::isNumberRepresentable(id));
         return id;
     }
 
     // A hash policy for ubi::Nodes.
     // This simply uses the stock PointerHasher on the ubi::Node's pointer.
     // We specialize DefaultHasher below to make this the default.
     class HashPolicy {
-        typedef js::PointerHasher<void*, mozilla::tl::FloorLog2<sizeof(void*)>::value> PtrHash;
+        typedef js::PointerHasher<void*> PtrHash;
 
       public:
         typedef Node Lookup;
 
         static js::HashNumber hash(const Lookup& l) { return PtrHash::hash(l.base()->ptr); }
         static bool match(const Node& k, const Lookup& l) { return k == l; }
         static void rekey(Node& k, const Node& newKey) { k = newKey; }
     };
--- a/js/src/gc/Nursery.h
+++ b/js/src/gc/Nursery.h
@@ -359,31 +359,31 @@ class Nursery
         uint64_t tenuredBytes;
     } previousGC;
 
     /*
      * The set of externally malloced buffers potentially kept live by objects
      * stored in the nursery. Any external buffers that do not belong to a
      * tenured thing at the end of a minor GC must be freed.
      */
-    typedef HashSet<void*, PointerHasher<void*, 3>, SystemAllocPolicy> MallocedBuffersSet;
+    typedef HashSet<void*, PointerHasher<void*>, SystemAllocPolicy> MallocedBuffersSet;
     MallocedBuffersSet mallocedBuffers;
 
     /* A task structure used to free the malloced bufers on a background thread. */
     struct FreeMallocedBuffersTask;
     FreeMallocedBuffersTask* freeMallocedBuffersTask;
 
     /*
      * During a collection most hoisted slot and element buffers indicate their
      * new location with a forwarding pointer at the base. This does not work
      * for buffers whose length is less than pointer width, or when different
      * buffers might overlap each other. For these, an entry in the following
      * table is used.
      */
-    typedef HashMap<void*, void*, PointerHasher<void*, 1>, SystemAllocPolicy> ForwardedBufferMap;
+    typedef HashMap<void*, void*, PointerHasher<void*>, SystemAllocPolicy> ForwardedBufferMap;
     ForwardedBufferMap forwardedBuffers;
 
     /*
      * When we assign a unique id to cell in the nursery, that almost always
      * means that the cell will be in a hash table, and thus, held live,
      * automatically moving the uid from the nursery to its new home in
      * tenured. It is possible, if rare, for an object that acquired a uid to
      * be dead before the next collection, in which case we need to know to
--- a/js/src/gc/StoreBuffer.h
+++ b/js/src/gc/StoreBuffer.h
@@ -35,17 +35,17 @@ class ArenaCellSet;
  */
 class BufferableRef
 {
   public:
     virtual void trace(JSTracer* trc) = 0;
     bool maybeInRememberedSet(const Nursery&) const { return true; }
 };
 
-typedef HashSet<void*, PointerHasher<void*, 3>, SystemAllocPolicy> EdgeSet;
+typedef HashSet<void*, PointerHasher<void*>, SystemAllocPolicy> EdgeSet;
 
 /* The size of a single block of store buffer storage space. */
 static const size_t LifoAllocBlockSize = 1 << 13; /* 8KiB */
 
 /*
  * The StoreBuffer observes all writes that occur in the system and performs
  * efficient filtering of them to derive a remembered set for nursery GC.
  */
--- a/js/src/gc/Zone.h
+++ b/js/src/gc/Zone.h
@@ -74,17 +74,17 @@ struct ZoneComponentFinder : public Comp
 
 struct UniqueIdGCPolicy {
     static bool needsSweep(Cell** cell, uint64_t* value);
 };
 
 // Maps a Cell* to a unique, 64bit id.
 using UniqueIdMap = GCHashMap<Cell*,
                               uint64_t,
-                              PointerHasher<Cell*, 3>,
+                              PointerHasher<Cell*>,
                               SystemAllocPolicy,
                               UniqueIdGCPolicy>;
 
 extern uint64_t NextCellUniqueId(JSRuntime* rt);
 
 template <typename T>
 class ZoneCellIter;
 
--- a/js/src/jit/LoopUnroller.cpp
+++ b/js/src/jit/LoopUnroller.cpp
@@ -13,17 +13,17 @@ using namespace js::jit;
 
 using mozilla::ArrayLength;
 
 namespace {
 
 struct LoopUnroller
 {
     typedef HashMap<MDefinition*, MDefinition*,
-                    PointerHasher<MDefinition*, 2>, SystemAllocPolicy> DefinitionMap;
+                    PointerHasher<MDefinition*>, SystemAllocPolicy> DefinitionMap;
 
     explicit LoopUnroller(MIRGraph& graph)
       : graph(graph), alloc(graph.alloc()),
         header(nullptr), backedge(nullptr),
         unrolledHeader(nullptr), unrolledBackedge(nullptr),
         oldPreheader(nullptr), newPreheader(nullptr)
     {}
 
--- a/js/src/jit/OptimizationTracking.cpp
+++ b/js/src/jit/OptimizationTracking.cpp
@@ -209,17 +209,17 @@ CombineHash(HashNumber h, HashNumber n)
     h ^= (h >> 6);
     return h;
 }
 
 static inline HashNumber
 HashType(TypeSet::Type ty)
 {
     if (ty.isObjectUnchecked())
-        return PointerHasher<TypeSet::ObjectKey*, 3>::hash(ty.objectKey());
+        return PointerHasher<TypeSet::ObjectKey*>::hash(ty.objectKey());
     return HashNumber(ty.raw());
 }
 
 static HashNumber
 HashTypeList(const TempTypeList& types)
 {
     HashNumber h = 0;
     for (uint32_t i = 0; i < types.length(); i++)
--- a/js/src/vm/Caches.h
+++ b/js/src/vm/Caches.h
@@ -26,17 +26,17 @@ namespace js {
  * GetSrcNote cache to avoid O(n^2) growth in finding a source note for a
  * given pc in a script. We use the script->code pointer to tag the cache,
  * instead of the script address itself, so that source notes are always found
  * by offset from the bytecode with which they were generated.
  */
 struct GSNCache {
     typedef HashMap<jsbytecode*,
                     jssrcnote*,
-                    PointerHasher<jsbytecode*, 0>,
+                    PointerHasher<jsbytecode*>,
                     SystemAllocPolicy> Map;
 
     jsbytecode*     code;
     Map             map;
 
     GSNCache() : code(nullptr) { }
 
     void purge();
--- a/js/src/vm/SavedFrame.h
+++ b/js/src/vm/SavedFrame.h
@@ -183,17 +183,17 @@ class SavedFrame : public NativeObject {
         JSSLOT_COUNT
     };
 };
 
 struct SavedFrame::HashPolicy
 {
     typedef SavedFrame::Lookup              Lookup;
     typedef MovableCellHasher<SavedFrame*>  SavedFramePtrHasher;
-    typedef PointerHasher<JSPrincipals*, 3> JSPrincipalsPtrHasher;
+    typedef PointerHasher<JSPrincipals*> JSPrincipalsPtrHasher;
 
     static bool       hasHash(const Lookup& l);
     static bool       ensureHash(const Lookup& l);
     static HashNumber hash(const Lookup& lookup);
     static bool       match(SavedFrame* existing, const Lookup& lookup);
 
     typedef ReadBarriered<SavedFrame*> Key;
     static void rekey(Key& key, const Key& newKey);
--- a/js/src/vm/TraceLogging.h
+++ b/js/src/vm/TraceLogging.h
@@ -383,17 +383,17 @@ class TraceLoggerThreadState
     bool cooperatingThreadEnabled;
     bool helperThreadEnabled;
     bool graphSpewingEnabled;
     bool spewErrors;
     mozilla::LinkedList<TraceLoggerThread> threadLoggers;
 
     typedef HashMap<const void*,
                     TraceLoggerEventPayload*,
-                    PointerHasher<const void*, 3>,
+                    PointerHasher<const void*>,
                     SystemAllocPolicy> PointerHashMap;
     typedef HashMap<uint32_t,
                     TraceLoggerEventPayload*,
                     DefaultHasher<uint32_t>,
                     SystemAllocPolicy> TextIdHashMap;
     PointerHashMap pointerMap;
     TextIdHashMap textIdPayloads;
     uint32_t nextTextId;
--- a/js/xpconnect/src/xpcprivate.h
+++ b/js/xpconnect/src/xpcprivate.h
@@ -991,21 +991,21 @@ public:
     void
     AddSizeOfIncludingThis(ScopeSizeInfo* scopeSizeInfo);
 
     static bool
     IsDyingScope(XPCWrappedNativeScope* scope);
 
     typedef js::HashMap<JSAddonId*,
                         nsCOMPtr<nsIAddonInterposition>,
-                        js::PointerHasher<JSAddonId*, 3>,
+                        js::PointerHasher<JSAddonId*>,
                         js::SystemAllocPolicy> InterpositionMap;
 
     typedef js::HashSet<JSAddonId*,
-                        js::PointerHasher<JSAddonId*, 3>,
+                        js::PointerHasher<JSAddonId*>,
                         js::SystemAllocPolicy> AddonSet;
 
     // Gets the appropriate scope object for XBL in this scope. The context
     // must be same-compartment with the global upon entering, and the scope
     // object is wrapped into the compartment of the global.
     JSObject* EnsureContentXBLScope(JSContext* cx);
 
     JSObject* EnsureAddonScope(JSContext* cx, JSAddonId* addonId);