Bug 1038601 - Shrink js::HashTable. r=luke.
authorNicholas Nethercote <nnethercote@mozilla.com>
Wed, 16 Jul 2014 16:51:09 -0700
changeset 216448 8cf3f3b925a362186c6cdf408a46aa539d895db2
parent 216447 63c52b7ddc282ca2b334eb51c8ec32702c60d5d1
child 216449 4cbe04a905ef870e2bc8b9fd76c0dfbe6d227cbd
push id515
push userraliiev@mozilla.com
push dateMon, 06 Oct 2014 12:51:51 +0000
treeherdermozilla-release@267c7a481bef [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs1038601
milestone33.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 1038601 - Shrink js::HashTable. r=luke. This patch reduces sizeof(js::HashTable): - On 64-bit: from 32 bytes to 24 bytes. - On 32-bit: from 24 bytes to 16 bytes. The latter is particularly nice because jemalloc rounds up allocation requests of 24 bytes to 32, but it can allocate 16 bytes without slop, so we're saving 16 bytes per heap-allocated HashTable. This is done by: - Shrinking |removedCount| and |hashShift|. - Reordering the fields. - Not defining |mutationCount| and |mEntered| in non-DEBUG builds rather than using DebugOnly<> -- in non-DEBUG builds, DebugOnly<> fields take up 1 byte each. This change saves over 55 KiB when starting Firefox and loading Gmail. The patch also uses uint32_t more consistently for the generation.
js/public/HashTable.h
js/src/jsapi.h
--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -202,17 +202,17 @@ class HashMap
         return impl.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
     }
 
     // If |generation()| is the same before and after a HashMap operation,
     // pointers into the table remain valid.
-    unsigned generation() const                       { return impl.generation(); }
+    uint32_t generation() const                       { return impl.generation(); }
 
     /************************************************** Shorthand operations */
 
     bool has(const Lookup &l) const {
         return impl.lookup(l) != nullptr;
     }
 
     // Overwrite existing value with v. Return false on oom.
@@ -430,17 +430,17 @@ class HashSet
         return impl.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
         return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
     }
 
     // If |generation()| is the same before and after a HashSet operation,
     // pointers into the table remain valid.
-    unsigned generation() const                       { return impl.generation(); }
+    uint32_t generation() const                       { return impl.generation(); }
 
     /************************************************** Shorthand operations */
 
     bool has(const Lookup &l) const {
         return impl.lookup(l) != nullptr;
     }
 
     // Add |u| if it is not present already. Return false on oom.
@@ -737,16 +737,18 @@ class HashTableEntry
         new(mem.addr()) T(mozilla::Forward<U>(u));
         MOZ_ASSERT(isLive());
     }
 };
 
 template <class T, class HashPolicy, class AllocPolicy>
 class HashTable : private AllocPolicy
 {
+    friend class mozilla::ReentrancyGuard;
+
     typedef typename mozilla::RemoveConst<T>::Type NonConstT;
     typedef typename HashPolicy::KeyType Key;
     typedef typename HashPolicy::Lookup Lookup;
 
   public:
     typedef HashTableEntry<T> Entry;
 
     // A nullable pointer to a hash table element. A Ptr |p| can be tested
@@ -812,20 +814,26 @@ class HashTable : private AllocPolicy
         }
     };
 
     // A Ptr that can be used to add a key after a failed lookup.
     class AddPtr : public Ptr
     {
         friend class HashTable;
         HashNumber keyHash;
-        mozilla::DebugOnly<uint64_t> mutationCount;
+#ifdef DEBUG
+        uint64_t mutationCount;
+#endif
 
         AddPtr(Entry &entry, const HashTable &tableArg, HashNumber hn)
-          : Ptr(entry, tableArg), keyHash(hn), mutationCount(tableArg.mutationCount)
+          : Ptr(entry, tableArg)
+          , keyHash(hn)
+#ifdef DEBUG
+          , mutationCount(tableArg.mutationCount)
+#endif
         {}
 
       public:
         // Leaves AddPtr uninitialized.
         AddPtr() {}
     };
 
     // A collection of hash table entries. The collection is enumerated by
@@ -979,28 +987,28 @@ class HashTable : private AllocPolicy
     }
 
   private:
     // HashTable is not copyable or assignable
     HashTable(const HashTable &) MOZ_DELETE;
     void operator=(const HashTable &) MOZ_DELETE;
 
   private:
-    uint32_t    hashShift;      // multiplicative hash shift
-    uint32_t    entryCount;     // number of entries in table
-    uint32_t    gen;            // entry storage generation number
-    uint32_t    removedCount;   // removed entry sentinels in table
-    Entry       *table;         // entry storage
+    static const size_t CAP_BITS = 24;
 
-    void setTableSizeLog2(unsigned sizeLog2)
-    {
-        hashShift = sHashBits - sizeLog2;
-    }
+  public:
+    Entry       *table;                 // entry storage
+    uint32_t    gen;                    // entry storage generation number
+    uint32_t    entryCount;             // number of entries in table
+    uint32_t    removedCount:CAP_BITS;  // removed entry sentinels in table
+    uint32_t    hashShift:8;            // multiplicative hash shift
 
 #ifdef JS_DEBUG
+    mozilla::DebugOnly<uint64_t>     mutationCount;
+    mutable mozilla::DebugOnly<bool> mEntered;
     mutable struct Stats
     {
         uint32_t        searches;       // total number of table searches
         uint32_t        steps;          // hash chain links traversed
         uint32_t        hits;           // searches that found key
         uint32_t        misses;         // searches that didn't find key
         uint32_t        addOverRemoved; // adds that recycled a removed entry
         uint32_t        removes;        // calls to remove
@@ -1010,38 +1018,39 @@ class HashTable : private AllocPolicy
         uint32_t        compresses;     // table compressions
         uint32_t        rehashes;       // tombstone decontaminations
     } stats;
 #   define METER(x) x
 #else
 #   define METER(x)
 #endif
 
-    friend class mozilla::ReentrancyGuard;
-    mutable mozilla::DebugOnly<bool> mEntered;
-    mozilla::DebugOnly<uint64_t>     mutationCount;
-
     // The default initial capacity is 32 (enough to hold 16 elements), but it
     // can be as low as 4.
     static const unsigned sMinCapacityLog2 = 2;
     static const unsigned sMinCapacity  = 1 << sMinCapacityLog2;
-    static const unsigned sMaxInit      = JS_BIT(23);
-    static const unsigned sMaxCapacity  = JS_BIT(24);
+    static const unsigned sMaxInit      = JS_BIT(CAP_BITS - 1);
+    static const unsigned sMaxCapacity  = JS_BIT(CAP_BITS);
     static const unsigned sHashBits     = mozilla::tl::BitSize<HashNumber>::value;
 
     // Hash-table alpha is conceptually a fraction, but to avoid floating-point
     // math we implement it as a ratio of integers.
     static const uint8_t sAlphaDenominator = 4;
     static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
     static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4
 
     static const HashNumber sFreeKey = Entry::sFreeKey;
     static const HashNumber sRemovedKey = Entry::sRemovedKey;
     static const HashNumber sCollisionBit = Entry::sCollisionBit;
 
+    void setTableSizeLog2(unsigned sizeLog2)
+    {
+        hashShift = sHashBits - sizeLog2;
+    }
+
     static bool isLiveHash(HashNumber hash)
     {
         return Entry::isLiveHash(hash);
     }
 
     static HashNumber prepareHash(const Lookup& l)
     {
         HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(l));
@@ -1065,24 +1074,26 @@ class HashTable : private AllocPolicy
     {
         for (Entry *e = oldTable, *end = e + capacity; e < end; ++e)
             e->destroyIfLive();
         alloc.free_(oldTable);
     }
 
   public:
     explicit HashTable(AllocPolicy ap)
-      : AllocPolicy(ap),
-        hashShift(sHashBits),
-        entryCount(0),
-        gen(0),
-        removedCount(0),
-        table(nullptr),
-        mEntered(false),
-        mutationCount(0)
+      : AllocPolicy(ap)
+      , table(nullptr)
+      , gen(0)
+      , entryCount(0)
+      , removedCount(0)
+      , hashShift(sHashBits)
+#ifdef DEBUG
+      , mutationCount(0)
+      , mEntered(false)
+#endif
     {}
 
     MOZ_WARN_UNUSED_RESULT bool init(uint32_t length)
     {
         MOZ_ASSERT(!initialized());
 
         // Reject all lengths whose initial computed capacity would exceed
         // sMaxCapacity.  Round that maximum length down to the nearest power
@@ -1359,17 +1370,19 @@ class HashTable : private AllocPolicy
         if (e.hasCollision()) {
             e.removeLive();
             removedCount++;
         } else {
             METER(stats.removeFrees++);
             e.clearLive();
         }
         entryCount--;
+#ifdef DEBUG
         mutationCount++;
+#endif
     }
 
     void checkUnderloaded()
     {
         if (underloaded()) {
             METER(stats.shrinks++);
             (void) changeTableSize(-1);
         }
@@ -1442,32 +1455,36 @@ class HashTable : private AllocPolicy
             memset(table, 0, sizeof(*table) * capacity());
         } else {
             uint32_t tableCapacity = capacity();
             for (Entry *e = table, *end = table + tableCapacity; e < end; ++e)
                 e->clear();
         }
         removedCount = 0;
         entryCount = 0;
+#ifdef DEBUG
         mutationCount++;
+#endif
     }
 
     void finish()
     {
         MOZ_ASSERT(!mEntered);
 
         if (!table)
             return;
 
         destroyTable(*this, table, capacity());
         table = nullptr;
         gen++;
         entryCount = 0;
         removedCount = 0;
+#ifdef DEBUG
         mutationCount++;
+#endif
     }
 
     Range all() const
     {
         MOZ_ASSERT(table);
         return Range(*this, table, table + capacity());
     }
 
@@ -1547,18 +1564,18 @@ class HashTable : private AllocPolicy
             if (status == RehashFailed)
                 return false;
             if (status == Rehashed)
                 p.entry_ = &findFreeEntry(p.keyHash);
         }
 
         p.entry_->setLive(p.keyHash, mozilla::Forward<U>(u));
         entryCount++;
+#ifdef DEBUG
         mutationCount++;
-#ifdef DEBUG
         p.generation = generation();
         p.mutationCount = mutationCount;
 #endif
         return true;
     }
 
     // Note: |l| may be a reference to a piece of |u|, so this function
     // must take care not to use |l| after moving |u|.
@@ -1573,17 +1590,19 @@ class HashTable : private AllocPolicy
         if (entry->isRemoved()) {
             METER(stats.addOverRemoved++);
             removedCount--;
             keyHash |= sCollisionBit;
         }
 
         entry->setLive(keyHash, mozilla::Forward<U>(u));
         entryCount++;
+#ifdef DEBUG
         mutationCount++;
+#endif
     }
 
     // Note: |l| may be a reference to a piece of |u|, so this function
     // must take care not to use |l| after moving |u|.
     template <class U>
     bool putNew(const Lookup &l, U &&u)
     {
         if (checkOverloaded() == RehashFailed)
--- a/js/src/jsapi.h
+++ b/js/src/jsapi.h
@@ -285,17 +285,17 @@ class AutoHashMapRooter : protected Auto
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
         return map.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
         return map.sizeOfIncludingThis(mallocSizeOf);
     }
 
-    unsigned generation() const {
+    uint32_t generation() const {
         return map.generation();
     }
 
     /************************************************** Shorthand operations */
 
     bool has(const Lookup &l) const {
         return map.has(l);
     }
@@ -400,17 +400,17 @@ class AutoHashSetRooter : protected Auto
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
         return set.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
         return set.sizeOfIncludingThis(mallocSizeOf);
     }
 
-    unsigned generation() const {
+    uint32_t generation() const {
         return set.generation();
     }
 
     /************************************************** Shorthand operations */
 
     bool has(const Lookup &l) const {
         return set.has(l);
     }