Bug 1477626 - Move ScrambleHashCode() from js/src/Utility.h to mfbt/HashFunctions.h. r=Waldo
authorNicholas Nethercote <nnethercote@mozilla.com>
Thu, 26 Jul 2018 18:52:47 +1000
changeset 484415 2ce09953e25bfbcc4170ed989c028c469b6ea21d
parent 484414 9cf98793e243bd1fa1413d70cf957b9a4f4d54f4
child 484416 f953e6b321c522d50fe137601694805dea19a9cf
push id9719
push userffxbld-merge
push dateFri, 24 Aug 2018 17:49:46 +0000
treeherdermozilla-beta@719ec98fba77 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersWaldo
bugs1477626
milestone63.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 1477626 - Move ScrambleHashCode() from js/src/Utility.h to mfbt/HashFunctions.h. r=Waldo And use it in PLDHashTable.cpp. MozReview-Commit-ID: BqwEkE0p5AG
js/public/HashTable.h
js/public/Utility.h
js/src/ds/OrderedHashTable.h
mfbt/HashFunctions.h
xpcom/ds/PLDHashTable.cpp
xpcom/ds/PLDHashTable.h
--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -1277,17 +1277,17 @@ class HashTable : private AllocPolicy
 
     static bool isLiveHash(HashNumber hash)
     {
         return Entry::isLiveHash(hash);
     }
 
     static HashNumber prepareHash(const Lookup& l)
     {
-        HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(l));
+        HashNumber keyHash = mozilla::ScrambleHashCode(HashPolicy::hash(l));
 
         // Avoid reserved hash codes.
         if (!isLiveHash(keyHash))
             keyHash -= (sRemovedKey + 1);
         return keyHash & ~sCollisionBit;
     }
 
     enum FailureBehavior { DontReportFailure = false, ReportFailure = true };
--- a/js/public/Utility.h
+++ b/js/public/Utility.h
@@ -9,17 +9,16 @@
 
 #include "mozilla/Assertions.h"
 #include "mozilla/Atomics.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/Compiler.h"
 #include "mozilla/Move.h"
 #include "mozilla/TemplateLib.h"
 #include "mozilla/UniquePtr.h"
-#include "mozilla/WrappingOperations.h"
 
 #include <stdlib.h>
 #include <string.h>
 
 #ifdef JS_OOM_DO_BACKTRACES
 #include <execinfo.h>
 #include <stdio.h>
 #endif
@@ -659,61 +658,16 @@ struct FreePolicy
     }
 };
 
 typedef mozilla::UniquePtr<char[], JS::FreePolicy> UniqueChars;
 typedef mozilla::UniquePtr<char16_t[], JS::FreePolicy> UniqueTwoByteChars;
 
 } // namespace JS
 
-namespace js {
-
-namespace detail {
-
-/*
- * Given a raw hash code, h, return a number that can be used to select a hash
- * bucket.
- *
- * This function aims to produce as uniform an output distribution as possible,
- * especially in the most significant (leftmost) bits, even though the input
- * distribution may be highly nonrandom, given the constraints that this must
- * be deterministic and quick to compute.
- *
- * Since the leftmost bits of the result are best, the hash bucket index is
- * computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent
- * right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
- *
- * FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
- */
-inline uint32_t
-ScrambleHashCode(uint32_t h)
-{
-    /*
-     * Simply returning h would not cause any hash tables to produce wrong
-     * answers. But it can produce pathologically bad performance: The caller
-     * right-shifts the result, keeping only the highest bits. The high bits of
-     * hash codes are very often completely entropy-free. (So are the lowest
-     * bits.)
-     *
-     * So we use Fibonacci hashing, as described in Knuth, The Art of Computer
-     * Programming, 6.4. This mixes all the bits of the input hash code h.
-     *
-     * The value of goldenRatio is taken from the hex
-     * expansion of the golden ratio, which starts 1.9E3779B9....
-     * This value is especially good if values with consecutive hash codes
-     * are stored in a hash table; see Knuth for details.
-     */
-    static const uint32_t goldenRatio = 0x9E3779B9U;
-    return mozilla::WrappingMultiply(h, goldenRatio);
-}
-
-} /* namespace detail */
-
-} /* namespace js */
-
 /* sixgill annotation defines */
 #ifndef HAVE_STATIC_ANNOTATIONS
 # define HAVE_STATIC_ANNOTATIONS
 # ifdef XGILL_PLUGIN
 #  define STATIC_PRECONDITION(COND)         __attribute__((precondition(#COND)))
 #  define STATIC_PRECONDITION_ASSUME(COND)  __attribute__((precondition_assume(#COND)))
 #  define STATIC_POSTCONDITION(COND)        __attribute__((postcondition(#COND)))
 #  define STATIC_POSTCONDITION_ASSUME(COND) __attribute__((postcondition_assume(#COND)))
--- a/js/src/ds/OrderedHashTable.h
+++ b/js/src/ds/OrderedHashTable.h
@@ -613,17 +613,17 @@ class OrderedHashTable
     /*
      * The minimum permitted value of (liveCount / dataLength).
      * If that ratio drops below this value, we shrink the table.
      */
     static double minDataFill() { return 0.25; }
 
   public:
     HashNumber prepareHash(const Lookup& l) const {
-        return ScrambleHashCode(Ops::hash(l, hcs));
+        return mozilla::ScrambleHashCode(Ops::hash(l, hcs));
     }
 
   private:
     /* The size of hashTable, in elements. Always a power of two. */
     uint32_t hashBuckets() const {
         return 1 << (js::kHashNumberBits - hashShift);
     }
 
--- a/mfbt/HashFunctions.h
+++ b/mfbt/HashFunctions.h
@@ -61,16 +61,52 @@ namespace mozilla {
 using HashNumber = uint32_t;
 static const uint32_t kHashNumberBits = 32;
 
 /**
  * The golden ratio as a 32-bit fixed-point value.
  */
 static const HashNumber kGoldenRatioU32 = 0x9E3779B9U;
 
+/*
+ * Given a raw hash code, h, return a number that can be used to select a hash
+ * bucket.
+ *
+ * This function aims to produce as uniform an output distribution as possible,
+ * especially in the most significant (leftmost) bits, even though the input
+ * distribution may be highly nonrandom, given the constraints that this must
+ * be deterministic and quick to compute.
+ *
+ * Since the leftmost bits of the result are best, the hash bucket index is
+ * computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent
+ * right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
+ *
+ * FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
+ */
+constexpr HashNumber
+ScrambleHashCode(HashNumber h)
+{
+  /*
+   * Simply returning h would not cause any hash tables to produce wrong
+   * answers. But it can produce pathologically bad performance: The caller
+   * right-shifts the result, keeping only the highest bits. The high bits of
+   * hash codes are very often completely entropy-free. (So are the lowest
+   * bits.)
+   *
+   * So we use Fibonacci hashing, as described in Knuth, The Art of Computer
+   * Programming, 6.4. This mixes all the bits of the input hash code h.
+   *
+   * The value of goldenRatio is taken from the hex expansion of the golden
+   * ratio, which starts 1.9E3779B9.... This value is especially good if
+   * values with consecutive hash codes are stored in a hash table; see Knuth
+   * for details.
+   */
+  return mozilla::WrappingMultiply(h, kGoldenRatioU32);
+}
+
 namespace detail {
 
 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
 constexpr HashNumber
 RotateLeft5(HashNumber aValue)
 {
   return (aValue << 5) | (aValue >> 27);
 }
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -523,18 +523,17 @@ PLDHashTable::ChangeTable(int32_t aDelta
   return true;
 }
 
 MOZ_ALWAYS_INLINE PLDHashNumber
 PLDHashTable::ComputeKeyHash(const void* aKey) const
 {
   MOZ_ASSERT(mEntryStore.Get());
 
-  PLDHashNumber keyHash = mOps->hashKey(aKey);
-  keyHash *= kGoldenRatio;
+  PLDHashNumber keyHash = mozilla::ScrambleHashCode(mOps->hashKey(aKey));
 
   // Avoid 0 and 1 hash codes, they indicate free and removed entries.
   if (keyHash < 2) {
     keyHash -= 2;
   }
   keyHash &= ~kCollisionFlag;
 
   return keyHash;
--- a/xpcom/ds/PLDHashTable.h
+++ b/xpcom/ds/PLDHashTable.h
@@ -28,18 +28,18 @@ struct PLDHashTableOps;
 // either here. Instead, the API uses const void *key as a formal parameter.
 // The key need not be stored in the entry; it may be part of the value, but
 // need not be stored at all.
 //
 // Callback types are defined below and grouped into the PLDHashTableOps
 // structure, for single static initialization per hash table sub-type.
 //
 // Each hash table sub-type should make its entry type a subclass of
-// PLDHashEntryHdr. The mKeyHash member contains the result of multiplying the
-// hash code returned from the hashKey callback (see below) by kGoldenRatio,
+// PLDHashEntryHdr. The mKeyHash member contains the result of suitably
+// scrambling the hash code returned from the hashKey callback (see below),
 // then constraining the result to avoid the magic 0 and 1 values. The stored
 // mKeyHash value is table size invariant, and it is maintained automatically
 // -- users need never access it.
 struct PLDHashEntryHdr
 {
 private:
   friend class PLDHashTable;
 
@@ -498,20 +498,16 @@ public:
   // Use this if you need to initialize an Iterator in a const method. If you
   // use this case, you should not call Remove() on the iterator.
   Iterator ConstIter() const
   {
     return Iterator(const_cast<PLDHashTable*>(this));
   }
 
 private:
-  // Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
-  // expressed as a fixed-point 32-bit fraction.
-  static const uint32_t kGoldenRatio = 0x9E3779B9U;
-
   static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength);
 
   static const PLDHashNumber kCollisionFlag = 1;
 
   static bool EntryIsFree(const PLDHashEntryHdr* aEntry)
   {
     return aEntry->mKeyHash == 0;
   }