Bug 1460674 - part 2 - reorganize PLDHashTable's internal storage; r=njn
authorNathan Froyd <froydnj@mozilla.com>
Mon, 26 Nov 2018 16:24:50 -0500
changeset 504498 0c938490f21c626d84b00903fb6fcb4d94386ce5
parent 504497 90e48634e1c329829854028465d311e2156196e3
child 504499 d94b469a0faa1b82ce5ca2a60b1d3825fed44d06
push id10290
push userffxbld-merge
push dateMon, 03 Dec 2018 16:23:23 +0000
treeherdermozilla-beta@700bed2445e6 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnjn
bugs1460674
milestone65.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 1460674 - part 2 - reorganize PLDHashTable's internal storage; r=njn As discussed in the previous commit message, PLDHashTable's storage wastes space for common entry types. This commit reorganizes the storage to store all the hashes packed together, followed by all the entries, which eliminates said waste.
xpcom/ds/PLDHashTable.cpp
xpcom/ds/PLDHashTable.h
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -122,18 +122,19 @@ static const PLDHashTableOps gStubOps = 
 PLDHashTable::StubOps()
 {
   return &gStubOps;
 }
 
 static bool
 SizeOfEntryStore(uint32_t aCapacity, uint32_t aEntrySize, uint32_t* aNbytes)
 {
-  uint64_t nbytes64 = uint64_t(aCapacity) * uint64_t(aEntrySize);
-  *aNbytes = aCapacity * aEntrySize;
+  uint32_t slotSize = aEntrySize + sizeof(PLDHashNumber);
+  uint64_t nbytes64 = uint64_t(aCapacity) * uint64_t(slotSize);
+  *aNbytes = aCapacity * slotSize;
   return uint64_t(*aNbytes) == nbytes64;   // returns false on overflow
 }
 
 // Compute max and min load numbers (entry counts). We have a secondary max
 // that allows us to overload a table reasonably if it cannot be grown further
 // (i.e. if ChangeTable() fails). The table slows down drastically if the
 // secondary max is too close to 1, but 0.96875 gives only a slight slowdown
 // while allowing 1.3x more elements.
@@ -301,34 +302,21 @@ PLDHashTable::Hash2(PLDHashNumber aHash0
 
 // Match an entry's mKeyHash against an unstored one computed from a key.
 /* static */ bool
 PLDHashTable::MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aKeyHash)
 {
   return (aSlot.KeyHash() & ~kCollisionFlag) == aKeyHash;
 }
 
-/* static */ bool
-PLDHashTable::MatchEntryKeyhash(const PLDHashEntryHdr* aEntry,
-                                const PLDHashNumber aKeyHash)
-{
-  return (aEntry->mKeyHash & ~kCollisionFlag) == aKeyHash;
-}
-
 // Compute the address of the indexed entry in table.
 auto
 PLDHashTable::SlotForIndex(uint32_t aIndex) const -> Slot
 {
-  return mEntryStore.SlotForIndex(aIndex, mEntrySize);
-}
-
-PLDHashEntryHdr*
-PLDHashTable::AddressEntry(uint32_t aIndex) const
-{
-  return SlotForIndex(aIndex).ToEntry();
+  return mEntryStore.SlotForIndex(aIndex, mEntrySize, CapacityFromHashShift());
 }
 
 PLDHashTable::~PLDHashTable()
 {
 #ifdef DEBUG
   AutoDestructorOp op(mChecker);
 #endif
 
@@ -612,17 +600,17 @@ PLDHashTable::Add(const void* aKey, cons
 
   // Look for entry after possibly growing, so we don't have to add it,
   // then skip it while growing the table and re-add it after.
   PLDHashNumber keyHash = ComputeKeyHash(aKey);
   Slot slot = SearchTable<ForAdd>(aKey, keyHash,
                                   [&](Slot& found) -> Slot { return found; },
                                   [&]() -> Slot {
                                     MOZ_CRASH("Nope");
-                                    return Slot(nullptr);
+                                    return Slot(nullptr, nullptr);
                                   });
   if (!slot.IsLive()) {
     // Initialize the slot, indicating that it's no longer free.
     if (slot.IsRemoved()) {
       mRemovedCount--;
       keyHash |= kCollisionFlag;
     }
     if (mOps->initEntry) {
@@ -687,17 +675,17 @@ PLDHashTable::RemoveEntry(PLDHashEntryHd
 
   RawRemove(aEntry);
   ShrinkIfAppropriate();
 }
 
 void
 PLDHashTable::RawRemove(PLDHashEntryHdr* aEntry)
 {
-  Slot slot(aEntry);
+  Slot slot(mEntryStore.SlotForPLDHashEntry(aEntry, Capacity(), mEntrySize));
   RawRemove(slot);
 }
 
 void
 PLDHashTable::RawRemove(Slot& aSlot)
 {
   // Unfortunately, we can only do weak checking here. That's because
   // RawRemove() can be called legitimately while an Enumerate() call is
@@ -771,33 +759,36 @@ PLDHashTable::Iterator::Iterator(Iterato
   aOther.mNexts = 0;
   aOther.mNextsLimit = 0;
   aOther.mHaveRemoved = false;
   aOther.mEntrySize = 0;
 }
 
 PLDHashTable::Iterator::Iterator(PLDHashTable* aTable)
   : mTable(aTable)
-  , mLimit(mTable->mEntryStore.SlotForIndex(mTable->Capacity(), mTable->mEntrySize))
-  , mCurrent(mTable->mEntryStore.SlotForIndex(0, mTable->mEntrySize))
+  , mLimit(mTable->mEntryStore.SlotForIndex(mTable->Capacity(), mTable->mEntrySize,
+                                            mTable->Capacity()))
+  , mCurrent(mTable->mEntryStore.SlotForIndex(0, mTable->mEntrySize,
+                                              mTable->Capacity()))
   , mNexts(0)
   , mNextsLimit(mTable->EntryCount())
   , mHaveRemoved(false)
   , mEntrySize(aTable->mEntrySize)
 {
 #ifdef DEBUG
   mTable->mChecker.StartReadOp();
 #endif
 
   if (ChaosMode::isActive(ChaosFeature::HashTableIteration) &&
       mTable->Capacity() > 0) {
     // Start iterating at a random entry. It would be even more chaotic to
     // iterate in fully random order, but that's harder.
-    uint32_t i = ChaosMode::randomUint32LessThan(mTable->Capacity());
-    mCurrent = mTable->mEntryStore.SlotForIndex(i, mTable->mEntrySize);
+    uint32_t capacity = mTable->CapacityFromHashShift();
+    uint32_t i = ChaosMode::randomUint32LessThan(capacity);
+    mCurrent = mTable->mEntryStore.SlotForIndex(i, mTable->mEntrySize, capacity);
   }
 
   // Advance to the first live entry, if there is one.
   if (!Done()) {
     while (IsOnNonLiveEntry()) {
       MoveToNextEntry();
     }
   }
@@ -823,17 +814,18 @@ PLDHashTable::Iterator::IsOnNonLiveEntry
 }
 
 MOZ_ALWAYS_INLINE void
 PLDHashTable::Iterator::MoveToNextEntry()
 {
   mCurrent.Next(mEntrySize);
   if (mCurrent == mLimit) {
     // We wrapped around.  Possible due to chaos mode.
-    mCurrent = mTable->mEntryStore.SlotForIndex(0, mEntrySize);
+    mCurrent = mTable->mEntryStore.SlotForIndex(0, mEntrySize,
+                                                mTable->CapacityFromHashShift());
   }
 }
 
 void
 PLDHashTable::Iterator::Next()
 {
   MOZ_ASSERT(!Done());
 
--- a/xpcom/ds/PLDHashTable.h
+++ b/xpcom/ds/PLDHashTable.h
@@ -32,33 +32,30 @@ 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 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.
+// PLDHashEntryHdr. PLDHashEntryHdr is merely a common superclass to present a
+// uniform interface to PLDHashTable clients. The zero-sized base class
+// optimization, employed by all of our supported C++ compilers, will ensure
+// that this abstraction does not make objects needlessly larger.
 struct PLDHashEntryHdr
 {
   PLDHashEntryHdr() = default;
   PLDHashEntryHdr(const PLDHashEntryHdr&) = delete;
   PLDHashEntryHdr& operator=(const PLDHashEntryHdr&) = delete;
   PLDHashEntryHdr(PLDHashEntryHdr&&) = default;
   PLDHashEntryHdr& operator=(PLDHashEntryHdr&&) = default;
 
 private:
   friend class PLDHashTable;
-
-  PLDHashNumber mKeyHash;
 };
 
 #ifdef DEBUG
 
 // This class does three kinds of checking:
 //
 // - that calls to one of |mOps| or to an enumerator do not cause re-entry into
 //   the table in an unsafe way;
@@ -218,102 +215,168 @@ private:
 // case you should keep using double hashing but switch to using pointer
 // elements). Also, with double hashing, you can't safely hold an entry pointer
 // and use it after an add or remove operation, unless you sample Generation()
 // before adding or removing, and compare the sample after, dereferencing the
 // entry pointer only if Generation() has not changed.
 class PLDHashTable
 {
 private:
-  // A slot represents a cached hash value and its associated entry stored
-  // in the hash table.  While they currently belong to the same object,
-  // PLDHashEntryHdr, they do not necessarily need to be contiguous in memory,
-  // and this abstraction helps enforce the separation between the two.
+  // A slot represents a cached hash value and its associated entry stored in
+  // the hash table. The hash value and the entry are not stored contiguously.
   struct Slot
   {
-    Slot(PLDHashEntryHdr* aEntry)
+    Slot(PLDHashEntryHdr* aEntry, PLDHashNumber* aKeyHash)
       : mEntry(aEntry)
+      , mKeyHash(aKeyHash)
     {}
 
     Slot(const Slot&) = default;
-    Slot(Slot&& aOther)
-      : mEntry(aOther.mEntry)
-    {}
+    Slot(Slot&& aOther) = default;
 
     Slot& operator=(Slot&& aOther) {
       this->~Slot();
       new (this) Slot(std::move(aOther));
       return *this;
     }
 
-    bool operator==(const Slot& aOther)
-    {
-      return mEntry == aOther.mEntry;
-    }
+    bool operator==(const Slot& aOther) { return mEntry == aOther.mEntry; }
 
-    PLDHashNumber KeyHash() const { return mEntry->mKeyHash; }
-    void SetKeyHash(PLDHashNumber aHash) { mEntry->mKeyHash = aHash; }
+    PLDHashNumber KeyHash() const { return *HashPtr(); }
+    void SetKeyHash(PLDHashNumber aHash) { *HashPtr() = aHash; }
 
     PLDHashEntryHdr* ToEntry() const { return mEntry; }
 
     bool IsFree() const { return KeyHash() == 0; }
     bool IsRemoved() const { return KeyHash() == 1; }
     bool IsLive() const { return KeyHash() >= 2; }
 
-    void MarkFree() { mEntry->mKeyHash = 0; }
-    void MarkRemoved() { mEntry->mKeyHash = 1; }
-    void MarkColliding() { mEntry->mKeyHash |= kCollisionFlag; }
+    void MarkFree() { *HashPtr() = 0; }
+    void MarkRemoved() { *HashPtr() = 1; }
+    void MarkColliding() { *HashPtr() |= kCollisionFlag; }
 
     void Next(uint32_t aEntrySize) {
       char* p = reinterpret_cast<char*>(mEntry);
       p += aEntrySize;
       mEntry = reinterpret_cast<PLDHashEntryHdr*>(p);
+      mKeyHash++;
     }
   private:
+    PLDHashNumber* HashPtr() const { return mKeyHash; }
+
     PLDHashEntryHdr* mEntry;
+    PLDHashNumber* mKeyHash;
   };
 
   // This class maintains the invariant that every time the entry store is
   // changed, the generation is updated.
   //
+  // The data layout separates the cached hashes of entries and the entries
+  // themselves to save space. We could store the entries thusly:
+  //
+  // +--------+--------+---------+
+  // | entry0 | entry1 | ...     |
+  // +--------+--------+---------+
+  //
+  // where the entries themselves contain the cached hash stored as their
+  // first member. PLDHashTable did this for a long time, with entries looking
+  // like:
+  //
+  // class PLDHashEntryHdr
+  // {
+  //   PLDHashNumber mKeyHash;
+  // };
+  //
+  // class MyEntry : public PLDHashEntryHdr
+  // {
+  //   ...
+  // };
+  //
+  // The problem with this setup is that, depending on the layout of
+  // `MyEntry`, there may be platform ABI-mandated padding between `mKeyHash`
+  // and the first member of `MyEntry`. This ABI-mandated padding is wasted
+  // space, and was surprisingly common, e.g. when MyEntry contained a single
+  // pointer on 64-bit platforms.
+  //
+  // As previously alluded to, the current setup stores things thusly:
+  //
+  // +-------+-------+-------+-------+--------+--------+---------+
+  // | hash0 | hash1 | ..... | hashN | entry0 | entry1 | ...     |
+  // +-------+-------+-------+-------+--------+--------+---------+
+  //
+  // which contains no wasted space between the hashes themselves, and no
+  // wasted space between the entries themselves. malloc is guaranteed to
+  // return blocks of memory with at least word alignment on all of our major
+  // platforms. PLDHashTable mandates that the size of the hash table is
+  // always a power of two, so the alignment of the memory containing the
+  // first entry is always at least the alignment of the entire entry store.
+  // That means the alignment of `entry0` should be its natural alignment.
+  // Entries may have problems if they contain over-aligned members such as
+  // SIMD vector types, but this has not been a problem in practice.
+  //
   // Note: It would be natural to store the generation within this class, but
   // we can't do that without bloating sizeof(PLDHashTable) on 64-bit machines.
   // So instead we store it outside this class, and Set() takes a pointer to it
   // and ensures it is updated as necessary.
   class EntryStore
   {
   private:
     char* mEntryStore;
 
-    PLDHashEntryHdr* EntryAt(uint32_t aIndex, uint32_t aEntrySize) const {
-      return reinterpret_cast<PLDHashEntryHdr*>(Get() + aIndex * aEntrySize);
+    static char* Entries(char* aStore, uint32_t aCapacity)
+    {
+      return aStore + aCapacity * sizeof(PLDHashNumber);
     }
+
+    char* Entries(uint32_t aCapacity) const
+    {
+      return Entries(Get(), aCapacity);
+    }
+
   public:
     EntryStore() : mEntryStore(nullptr) {}
 
     ~EntryStore()
     {
       free(mEntryStore);
       mEntryStore = nullptr;
     }
 
     char* Get() const { return mEntryStore; }
-    Slot SlotForIndex(uint32_t aIndex, uint32_t aEntrySize) const {
-      return Slot(EntryAt(aIndex, aEntrySize));
+
+    Slot SlotForIndex(uint32_t aIndex, uint32_t aEntrySize,
+                      uint32_t aCapacity) const
+    {
+      char* entries = Entries(aCapacity);
+      auto entry = reinterpret_cast<PLDHashEntryHdr*>(entries + aIndex * aEntrySize);
+      auto hashes = reinterpret_cast<PLDHashNumber*>(Get());
+      return Slot(entry, &hashes[aIndex]);
+    }
+
+    Slot SlotForPLDHashEntry(PLDHashEntryHdr* aEntry,
+                             uint32_t aCapacity, uint32_t aEntrySize)
+    {
+      char* entries = Entries(aCapacity);
+      char* entry = reinterpret_cast<char*>(aEntry);
+      uint32_t entryOffset = entry - entries;
+      uint32_t slotIndex = entryOffset / aEntrySize;
+      return SlotForIndex(slotIndex, aEntrySize, aCapacity);
     }
 
     template<typename F>
     void ForEachSlot(uint32_t aCapacity, uint32_t aEntrySize, F&& aFunc) {
       ForEachSlot(Get(), aCapacity, aEntrySize, std::move(aFunc));
     }
 
     template<typename F>
     static void ForEachSlot(char* aStore, uint32_t aCapacity, uint32_t aEntrySize,
                             F&& aFunc) {
-      Slot slot(reinterpret_cast<PLDHashEntryHdr*>(aStore));
+      char* entries = Entries(aStore, aCapacity);
+      Slot slot(reinterpret_cast<PLDHashEntryHdr*>(entries),
+                reinterpret_cast<PLDHashNumber*>(aStore));
       for (size_t i = 0; i < aCapacity; ++i) {
         aFunc(slot);
         slot.Next(aEntrySize);
       }
     }
 
     void Set(char* aEntryStore, uint16_t* aGeneration)
     {
@@ -412,21 +475,19 @@ public:
 
   // To add an entry identified by |key| to table, call:
   //
   //   entry = table.Add(key, mozilla::fallible);
   //
   // If |entry| is null upon return, then the table is severely overloaded and
   // memory can't be allocated for entry storage.
   //
-  // Otherwise, |aEntry->mKeyHash| has been set so that
-  // PLDHashTable::EntryIsFree(entry) is false, and it is up to the caller to
-  // initialize the key and value parts of the entry sub-type, if they have not
-  // been set already (i.e. if entry was not already in the table, and if the
-  // optional initEntry hook was not used).
+  // Otherwise, if the initEntry hook was provided, |entry| will be
+  // initialized.  If the initEntry hook was not provided, the caller
+  // should initialize |entry| as appropriate.
   PLDHashEntryHdr* Add(const void* aKey, const mozilla::fallible_t&);
 
   // This is like the other Add() function, but infallible, and so never
   // returns null.
   PLDHashEntryHdr* Add(const void* aKey);
 
   // To remove an entry identified by |key| from table, call:
   //
@@ -578,47 +639,22 @@ public:
     return Iterator(const_cast<PLDHashTable*>(this));
   }
 
 private:
   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;
-  }
-  static bool EntryIsRemoved(const PLDHashEntryHdr* aEntry)
-  {
-    return aEntry->mKeyHash == 1;
-  }
-  static bool EntryIsLive(const PLDHashEntryHdr* aEntry)
-  {
-    return aEntry->mKeyHash >= 2;
-  }
-
-  static void MarkEntryFree(PLDHashEntryHdr* aEntry)
-  {
-    aEntry->mKeyHash = 0;
-  }
-  static void MarkEntryRemoved(PLDHashEntryHdr* aEntry)
-  {
-    aEntry->mKeyHash = 1;
-  }
-
   PLDHashNumber Hash1(PLDHashNumber aHash0) const;
   void Hash2(PLDHashNumber aHash,
              uint32_t& aHash2Out, uint32_t& aSizeMaskOut) const;
 
   static bool MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aHash);
-  static bool MatchEntryKeyhash(const PLDHashEntryHdr* aEntry,
-                                const PLDHashNumber aHash);
   Slot SlotForIndex(uint32_t aIndex) const;
-  PLDHashEntryHdr* AddressEntry(uint32_t aIndex) const;
 
   // We store mHashShift rather than sizeLog2 to optimize the collision-free
   // case in SearchTable.
   uint32_t CapacityFromHashShift() const
   {
     return ((uint32_t)1 << (kPLDHashNumberBits - mHashShift));
   }
 
@@ -661,40 +697,37 @@ typedef void (*PLDHashMoveEntry)(PLDHash
                                  const PLDHashEntryHdr* aFrom,
                                  PLDHashEntryHdr* aTo);
 
 // Clear the entry and drop any strong references it holds. This callback is
 // invoked by Remove(), but only if the given key is found in the table.
 typedef void (*PLDHashClearEntry)(PLDHashTable* aTable,
                                   PLDHashEntryHdr* aEntry);
 
-// Initialize a new entry, apart from mKeyHash. This function is called when
-// Add() finds no existing entry for the given key, and must add a new one. At
-// that point, |aEntry->mKeyHash| is not set yet, to avoid claiming the last
-// free entry in a severely overloaded table.
+// Initialize a new entry. This function is called when
+// Add() finds no existing entry for the given key, and must add a new one.
 typedef void (*PLDHashInitEntry)(PLDHashEntryHdr* aEntry, const void* aKey);
 
 // Finally, the "vtable" structure for PLDHashTable. The first four hooks
 // must be provided by implementations; they're called unconditionally by the
 // generic PLDHashTable.cpp code. Hooks after these may be null.
 //
 // Summary of allocation-related hook usage with C++ placement new emphasis:
 //  initEntry           Call placement new using default key-based ctor.
 //  moveEntry           Call placement new using copy ctor, run dtor on old
 //                      entry storage.
 //  clearEntry          Run dtor on entry.
 //
 // Note the reason why initEntry is optional: the default hooks (stubs) clear
-// entry storage:  On successful Add(tbl, key), the returned entry pointer
-// addresses an entry struct whose mKeyHash member has been set non-zero, but
-// all other entry members are still clear (null). Add() callers can test such
-// members to see whether the entry was newly created by the Add() call that
-// just succeeded. If placement new or similar initialization is required,
-// define an |initEntry| hook. Of course, the |clearEntry| hook must zero or
-// null appropriately.
+// entry storage. On a successful Add(tbl, key), the returned entry pointer
+// addresses an entry struct whose entry members are still clear (null). Add()
+// callers can test such members to see whether the entry was newly created by
+// the Add() call that just succeeded. If placement new or similar
+// initialization is required, define an |initEntry| hook. Of course, the
+// |clearEntry| hook must zero or null appropriately.
 //
 // XXX assumes 0 is null for pointer types.
 struct PLDHashTableOps
 {
   // Mandatory hooks. All implementations must provide these.
   PLDHashHashKey      hashKey;
   PLDHashMatchEntry   matchEntry;
   PLDHashMoveEntry    moveEntry;