Bug 1460674 - part 3 - make PLDHashTable iteration faster; r=njn
authorNathan Froyd <froydnj@mozilla.com>
Mon, 26 Nov 2018 16:24:50 -0500
changeset 507279 d94b469a0faa1b82ce5ca2a60b1d3825fed44d06
parent 507278 0c938490f21c626d84b00903fb6fcb4d94386ce5
child 507280 79b6eb03c0c9999c3bed469344aa9cdbaa122374
push id1905
push userffxbld-merge
push dateMon, 21 Jan 2019 12:33:13 +0000
treeherdermozilla-release@c2fca1944d8c [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 3 - make PLDHashTable iteration faster; r=njn The core loop of Iterator::Next() requires multiple branches, one to check for entry liveness and one to check for wraparound. We can rewrite this to use masking instead, as well as iterating only over the hashes, and reconstructing the entry pointer when we know we've reached a live entry. This change cuts the time taken on the collections benchmark by the iteration portion in half.
xpcom/ds/PLDHashTable.cpp
xpcom/ds/PLDHashTable.h
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -741,36 +741,33 @@ PLDHashTable::ShallowSizeOfExcludingThis
 size_t
 PLDHashTable::ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
 {
   return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
 }
 
 PLDHashTable::Iterator::Iterator(Iterator&& aOther)
   : mTable(aOther.mTable)
-  , mLimit(aOther.mLimit)
   , mCurrent(aOther.mCurrent)
   , mNexts(aOther.mNexts)
   , mNextsLimit(aOther.mNextsLimit)
   , mHaveRemoved(aOther.mHaveRemoved)
   , mEntrySize(aOther.mEntrySize)
 {
   // No need to change |mChecker| here.
   aOther.mTable = nullptr;
-  // We don't really have the concept of a null slot, so leave mLimit/mCurrent.
+  // We don't really have the concept of a null slot, so leave mCurrent.
   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,
-                                            mTable->Capacity()))
   , mCurrent(mTable->mEntryStore.SlotForIndex(0, mTable->mEntrySize,
                                               mTable->Capacity()))
   , mNexts(0)
   , mNextsLimit(mTable->EntryCount())
   , mHaveRemoved(false)
   , mEntrySize(aTable->mEntrySize)
 {
 #ifdef DEBUG
@@ -782,20 +779,18 @@ PLDHashTable::Iterator::Iterator(PLDHash
     // Start iterating at a random entry. It would be even more chaotic to
     // iterate in fully random order, but that's harder.
     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();
-    }
+  if (!Done() && IsOnNonLiveEntry()) {
+    MoveToNextLiveEntry();
   }
 }
 
 PLDHashTable::Iterator::~Iterator()
 {
   if (mTable) {
     if (mHaveRemoved) {
       mTable->ShrinkIfAppropriate();
@@ -808,42 +803,65 @@ PLDHashTable::Iterator::~Iterator()
 
 MOZ_ALWAYS_INLINE bool
 PLDHashTable::Iterator::IsOnNonLiveEntry() const
 {
   MOZ_ASSERT(!Done());
   return !mCurrent.IsLive();
 }
 
-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,
-                                                mTable->CapacityFromHashShift());
-  }
-}
-
 void
 PLDHashTable::Iterator::Next()
 {
   MOZ_ASSERT(!Done());
 
   mNexts++;
 
   // Advance to the next live entry, if there is one.
   if (!Done()) {
-    do {
-      MoveToNextEntry();
-    } while (IsOnNonLiveEntry());
+    MoveToNextLiveEntry();
   }
 }
 
+MOZ_ALWAYS_INLINE void
+PLDHashTable::Iterator::MoveToNextLiveEntry()
+{
+  // Chaos mode requires wraparound to cover all possible entries, so we can't
+  // simply move to the next live entry and stop when we hit the end of the
+  // entry store. But we don't want to introduce extra branches into our inner
+  // loop. So we are going to exploit the structure of the entry store in this
+  // method to implement an efficient inner loop.
+  //
+  // The idea is that since we are really only iterating through the stored
+  // hashes and because we know that there are a power-of-two number of
+  // hashes, we can use masking to implement the wraparound for us. This
+  // method does have the downside of needing to recalculate where the
+  // associated entry is once we've found it, but that seems OK.
+
+  // Our current slot and its associated hash.
+  Slot slot = mCurrent;
+  PLDHashNumber* p = slot.HashPtr();
+  const uint32_t capacity = mTable->CapacityFromHashShift();
+  const uint32_t mask = capacity - 1;
+  auto hashes = reinterpret_cast<PLDHashNumber*>(mTable->mEntryStore.Get());
+  uint32_t slotIndex = p - hashes;
+
+  do {
+    slotIndex = (slotIndex + 1) & mask;
+  } while (!Slot::IsLiveHash(hashes[slotIndex]));
+
+  // slotIndex now indicates where a live slot is. Rematerialize the entry
+  // and the slot.
+  auto entries = reinterpret_cast<char*>(&hashes[capacity]);
+  char* entryPtr = entries + slotIndex * mEntrySize;
+  auto entry = reinterpret_cast<PLDHashEntryHdr*>(entryPtr);
+
+  mCurrent = Slot(entry, &hashes[slotIndex]);
+}
+
 void
 PLDHashTable::Iterator::Remove()
 {
   mTable->RawRemove(mCurrent);
   mHaveRemoved = true;
 }
 
 #ifdef DEBUG
--- a/xpcom/ds/PLDHashTable.h
+++ b/xpcom/ds/PLDHashTable.h
@@ -242,31 +242,32 @@ private:
 
     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; }
+    bool IsLive() const { return IsLiveHash(KeyHash()); }
+    static bool IsLiveHash(uint32_t aHash) { return aHash >= 2; }
 
     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; }
 
+  private:
     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
@@ -608,26 +609,26 @@ public:
     // Remove the current entry. Must only be called once per entry, and Get()
     // must not be called on that entry afterwards.
     void Remove();
 
   protected:
     PLDHashTable* mTable;             // Main table pointer.
 
   private:
-    Slot mLimit;                      // One past the last entry.
     Slot mCurrent;                    // Pointer to the current entry.
     uint32_t mNexts;                  // Number of Next() calls.
     uint32_t mNextsLimit;             // Next() call limit.
 
     bool mHaveRemoved;                // Have any elements been removed?
     uint8_t mEntrySize;               // Size of entries.
 
     bool IsOnNonLiveEntry() const;
-    void MoveToNextEntry();
+
+    void MoveToNextLiveEntry();
 
     Iterator() = delete;
     Iterator(const Iterator&) = delete;
     Iterator& operator=(const Iterator&) = delete;
     Iterator& operator=(const Iterator&&) = delete;
   };
 
   Iterator Iter() { return Iterator(this); }