Bug 1400193 (part 2) - Shrink PLDHashTable. r=froydnj.
authorNicholas Nethercote <nnethercote@mozilla.com>
Fri, 15 Sep 2017 20:04:29 +1000
changeset 382380 4dce29de45e3c5ecf8476bd77195c11a4ebe64ad
parent 382379 bd2852c72caef1f1ac622ff8862d8dc72fc072bd
child 382381 2fac6141f39e2ef741884165f56a675561924f39
push id32555
push userarchaeopteryx@coole-files.de
push dateFri, 22 Sep 2017 09:43:20 +0000
treeherdermozilla-central@82b2ae0b03ca [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1400193
milestone58.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 1400193 (part 2) - Shrink PLDHashTable. r=froydnj. This patch reduces sizeof(PLDHashTable) as follows. - 64-bit: from 40 bytes to 32 - 32-bit: from 28 bytes to 20 It does this by doing the following. - It moves mGeneration from EntryStore to PLDHashTable, to avoid unnecessary padding on 64-bit. This requires tweaking EntryStore::Set() as explained in a comment. - It also shrinks mGeneration from uint32_t to uint16_t, saving 2 bytes of data. - It shrinks mEntrySize from uint32_t to uint8_t, to cut 3 bytes of data. - It shrinks mHashShift from int16_t to uint8_t, trimming another byte of data, and moves it, saving another 2 bytes of padding. And it reorders the fields so the word-sized ones are at the start, which makes it easier to imagine the memory layout. The patch also adds a test, and fixes some misordered function arguments in existing tests.
xpcom/ds/PLDHashTable.cpp
xpcom/ds/PLDHashTable.h
xpcom/tests/gtest/TestPLDHash.cpp
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -194,25 +194,32 @@ PLDHashTable::HashShift(uint32_t aEntryS
 
   // Compute the hashShift value.
   return kHashBits - log2;
 }
 
 PLDHashTable::PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
                            uint32_t aLength)
   : mOps(aOps)
+  , mEntryStore()
+  , mGeneration(0)
   , mHashShift(HashShift(aEntrySize, aLength))
   , mEntrySize(aEntrySize)
   , mEntryCount(0)
   , mRemovedCount(0)
-  , mEntryStore()
 #ifdef DEBUG
   , mChecker()
 #endif
 {
+  // An entry size greater than 0xff is unlikely, but let's check anyway. If
+  // you hit this, your hashtable would waste lots of space for unused entries
+  // and you should change your hash table's entries to pointers.
+  if (aEntrySize != uint32_t(mEntrySize)) {
+    MOZ_CRASH("Entry size is too large");
+  }
 }
 
 PLDHashTable&
 PLDHashTable::operator=(PLDHashTable&& aOther)
 {
   if (this == &aOther) {
     return *this;
   }
@@ -227,27 +234,27 @@ PLDHashTable::operator=(PLDHashTable&& a
   // makes sense to assign in cases where they match.
   MOZ_RELEASE_ASSERT(mOps == aOther.mOps);
   MOZ_RELEASE_ASSERT(mEntrySize == aOther.mEntrySize);
 
   // Move non-const pieces over.
   mHashShift = Move(aOther.mHashShift);
   mEntryCount = Move(aOther.mEntryCount);
   mRemovedCount = Move(aOther.mRemovedCount);
-  mEntryStore.Set(aOther.mEntryStore);
+  mEntryStore.Set(aOther.mEntryStore.Get(), &mGeneration);
 #ifdef DEBUG
   mChecker = Move(aOther.mChecker);
 #endif
 
   // Clear up |aOther| so its destruction will be a no-op.
   {
 #ifdef DEBUG
     AutoDestructorOp op(mChecker);
 #endif
-    aOther.mEntryStore.Set(nullptr);
+    aOther.mEntryStore.Set(nullptr, &aOther.mGeneration);
   }
 
   return *this;
 }
 
 PLDHashNumber
 PLDHashTable::Hash1(PLDHashNumber aHash0)
 {
@@ -478,17 +485,17 @@ PLDHashTable::ChangeTable(int32_t aDelta
   mHashShift = kHashBits - newLog2;
   mRemovedCount = 0;
 
   // Assign the new entry store to table.
   memset(newEntryStore, 0, nbytes);
   char* oldEntryStore;
   char* oldEntryAddr;
   oldEntryAddr = oldEntryStore = mEntryStore.Get();
-  mEntryStore.Set(newEntryStore);
+  mEntryStore.Set(newEntryStore, &mGeneration);
   PLDHashMoveEntry moveEntry = mOps->moveEntry;
 
   // Copy only live entries, leaving removed ones behind.
   uint32_t oldCapacity = 1u << oldLog2;
   for (uint32_t i = 0; i < oldCapacity; ++i) {
     PLDHashEntryHdr* oldEntry = (PLDHashEntryHdr*)oldEntryAddr;
     if (EntryIsLive(oldEntry)) {
       oldEntry->mKeyHash &= ~kCollisionFlag;
@@ -543,17 +550,17 @@ PLDHashTable::Add(const void* aKey, cons
 #endif
 
   // Allocate the entry storage if it hasn't already been allocated.
   if (!mEntryStore.Get()) {
     uint32_t nbytes;
     // We already checked this in the constructor, so it must still be true.
     MOZ_RELEASE_ASSERT(SizeOfEntryStore(CapacityFromHashShift(), mEntrySize,
                                         &nbytes));
-    mEntryStore.Set((char*)malloc(nbytes));
+    mEntryStore.Set((char*)malloc(nbytes), &mGeneration);
     if (!mEntryStore.Get()) {
       return nullptr;
     }
     memset(mEntryStore.Get(), 0, nbytes);
   }
 
   // If alpha is >= .75, grow or compress the table. If aKey is already in the
   // table, we may grow once more than necessary, but only if we are on the
--- a/xpcom/ds/PLDHashTable.h
+++ b/xpcom/ds/PLDHashTable.h
@@ -204,50 +204,55 @@ private:
 // 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:
   // This class maintains the invariant that every time the entry store is
   // changed, the generation is updated.
+  //
+  // 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;
-    uint32_t mGeneration;
 
   public:
-    EntryStore() : mEntryStore(nullptr), mGeneration(0) {}
+    EntryStore() : mEntryStore(nullptr) {}
 
     ~EntryStore()
     {
       free(mEntryStore);
       mEntryStore = nullptr;
-      mGeneration++;    // a little paranoid, but why not be extra safe?
     }
 
     char* Get() { return mEntryStore; }
     const char* Get() const { return mEntryStore; }
 
-    void Set(char* aEntryStore)
+    void Set(char* aEntryStore, uint16_t* aGeneration)
     {
       mEntryStore = aEntryStore;
-      mGeneration++;
+      *aGeneration += 1;
     }
-
-    uint32_t Generation() const { return mGeneration; }
   };
 
+  // These fields are packed carefully. On 32-bit platforms,
+  // sizeof(PLDHashTable) is 20. On 64-bit platforms, sizeof(PLDHashTable) is
+  // 32; 28 bytes of data followed by 4 bytes of padding for alignment.
   const PLDHashTableOps* const mOps;  // Virtual operations; see below.
-  int16_t             mHashShift;     // Multiplicative hash shift.
-  const uint32_t      mEntrySize;     // Number of bytes in an entry.
+  EntryStore          mEntryStore;    // (Lazy) entry storage and generation.
+  uint16_t            mGeneration;    // The storage generation.
+  uint8_t             mHashShift;     // Multiplicative hash shift.
+  const uint8_t       mEntrySize;     // Number of bytes in an entry.
   uint32_t            mEntryCount;    // Number of entries in table.
   uint32_t            mRemovedCount;  // Removed entry sentinels in table.
-  EntryStore          mEntryStore;    // (Lazy) entry storage and generation.
 
 #ifdef DEBUG
   mutable Checker mChecker;
 #endif
 
 public:
   // Table capacity limit; do not exceed. The max capacity used to be 1<<23 but
   // that occasionally that wasn't enough. Making it much bigger than 1<<26
@@ -273,23 +278,26 @@ public:
   // initial capacity won't be relevant until the first element is added; prior
   // to that the capacity will be zero.
   //
   // This will crash if |aEntrySize| and/or |aLength| are too large.
   PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
                uint32_t aLength = kDefaultInitialLength);
 
   PLDHashTable(PLDHashTable&& aOther)
-      // These two fields are |const|. Initialize them here because the
-      // move assignment operator cannot modify them.
+      // We initialize mOps and mEntrySize here because they are |const|, and
+      // the move assignment operator cannot modify them.
+      // We initialize mEntryStore because it is required for a safe call to
+      // the destructor, which the move assignment operator does.
+      // We initialize mGeneration because it is modified by the move
+      // assignment operator.
     : mOps(aOther.mOps)
+    , mEntryStore()
+    , mGeneration(0)
     , mEntrySize(aOther.mEntrySize)
-      // Initialize this field because it is required for a safe call to the
-      // destructor, which the move assignment operator does.
-    , mEntryStore()
 #ifdef DEBUG
     , mChecker()
 #endif
   {
     *this = mozilla::Move(aOther);
   }
 
   PLDHashTable& operator=(PLDHashTable&& aOther);
@@ -304,17 +312,17 @@ public:
   // entry storage will not have yet been allocated.
   uint32_t Capacity() const
   {
     return mEntryStore.Get() ? CapacityFromHashShift() : 0;
   }
 
   uint32_t EntrySize()  const { return mEntrySize; }
   uint32_t EntryCount() const { return mEntryCount; }
-  uint32_t Generation() const { return mEntryStore.Generation(); }
+  uint32_t Generation() const { return mGeneration; }
 
   // To search for a |key| in |table|, call:
   //
   //   entry = table.Search(key);
   //
   // If |entry| is non-null, |key| was found. If |entry| is null, key was not
   // found.
   PLDHashEntryHdr* Search(const void* aKey);
--- a/xpcom/tests/gtest/TestPLDHash.cpp
+++ b/xpcom/tests/gtest/TestPLDHash.cpp
@@ -100,38 +100,51 @@ InitCapacityOk_InitialLengthTooBig()
 }
 
 void
 InitCapacityOk_InitialEntryStoreTooBig()
 {
   // Try the smallest disallowed power-of-two entry store size, which is 2^32
   // bytes (which overflows to 0). (Note that the 2^23 *length* gets converted
   // to a 2^24 *capacity*.)
-  PLDHashTable t(PLDHashTable::StubOps(), (uint32_t)1 << 23, (uint32_t)1 << 8);
+  PLDHashTable t(PLDHashTable::StubOps(), (uint32_t)1 << 8, (uint32_t)1 << 23);
+}
+
+void
+InitCapacityOk_EntrySizeTooBig()
+{
+  // Try the smallest disallowed entry size, which is 256 bytes.
+  PLDHashTable t(PLDHashTable::StubOps(), 256);
 }
 
 TEST(PLDHashTableTest, InitCapacityOk)
 {
   // Try the largest allowed capacity.  With kMaxCapacity==1<<26, this
   // would allocate (if we added an element) 0.5GB of entry store on 32-bit
   // platforms and 1GB on 64-bit platforms.
   PLDHashTable t1(PLDHashTable::StubOps(), sizeof(PLDHashEntryStub),
                   PLDHashTable::kMaxInitialLength);
 
   // Try the largest allowed power-of-two entry store size, which is 2^31 bytes
   // (Note that the 2^23 *length* gets converted to a 2^24 *capacity*.)
-  PLDHashTable t2(PLDHashTable::StubOps(), (uint32_t)1 << 23, (uint32_t)1 << 7);
+  PLDHashTable t2(PLDHashTable::StubOps(), (uint32_t)1 << 7, (uint32_t)1 << 23);
 
   // Try a too-large capacity (which aborts).
   TestCrashyOperation(InitCapacityOk_InitialLengthTooBig);
 
   // Try a large capacity combined with a large entry size that when multiplied
   // overflow (causing abort).
   TestCrashyOperation(InitCapacityOk_InitialEntryStoreTooBig);
 
+  // Try the largest allowed entry size.
+  PLDHashTable t3(PLDHashTable::StubOps(), 255);
+
+  // Try an overly large entry size.
+  TestCrashyOperation(InitCapacityOk_EntrySizeTooBig);
+
   // Ideally we'd also try a large-but-ok capacity that almost but doesn't
   // quite overflow, but that would result in allocating slightly less than 4
   // GiB of entry storage. That would be very likely to fail on 32-bit
   // platforms, so such a test wouldn't be reliable.
 }
 
 TEST(PLDHashTableTest, LazyStorage)
 {