HashTable: bring per-table stats tracking back to life.

third_party/WebKit/Source/wtf/HashTable.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights
  * reserved.
  * Copyright (C) 2008 David Levin <levin@chromium.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
@@ skipping 24 matching lines @@
 #define DUMP_HASHTABLE_STATS 0
 #define DUMP_HASHTABLE_STATS_PER_TABLE 0
 
 #if DUMP_HASHTABLE_STATS
 #include "wtf/Atomics.h"
 #include "wtf/Threading.h"
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
 #include "wtf/DataLog.h"
+#include <type_traits>
 #endif
 
 #if DUMP_HASHTABLE_STATS
 #if DUMP_HASHTABLE_STATS_PER_TABLE
-#define UPDATE_PROBE_COUNTS()                         \
-  ++probeCount;                                       \
-  HashTableStats::recordCollisionAtCount(probeCount); \
-  ++perTableProbeCount;                               \
+
+#define UPDATE_PROBE_COUNTS()                                    \
+  ++probeCount;                                                  \
+  HashTableStats::instance().recordCollisionAtCount(probeCount); \
+  ++perTableProbeCount;                                          \
   m_stats->recordCollisionAtCount(perTableProbeCount)
-#define UPDATE_ACCESS_COUNTS()                   \
-  atomicIncrement(&HashTableStats::numAccesses); \
-  int probeCount = 0;                            \
-  ++m_stats->numAccesses;                        \
+#define UPDATE_ACCESS_COUNTS()                              \
+  atomicIncrement(&HashTableStats::instance().numAccesses); \
+  int probeCount = 0;                                       \
+  ++m_stats->numAccesses;                                   \
   int perTableProbeCount = 0
 #else
 #define UPDATE_PROBE_COUNTS() \
   ++probeCount;               \
-  HashTableStats::recordCollisionAtCount(probeCount)
-#define UPDATE_ACCESS_COUNTS()                   \
-  atomicIncrement(&HashTableStats::numAccesses); \
+  HashTableStats::instance().recordCollisionAtCount(probeCount)
+#define UPDATE_ACCESS_COUNTS()                              \
+  atomicIncrement(&HashTableStats::instance().numAccesses); \
   int probeCount = 0
 #endif
 #else
 #if DUMP_HASHTABLE_STATS_PER_TABLE
 #define UPDATE_PROBE_COUNTS() \
   ++perTableProbeCount;       \
   m_stats->recordCollisionAtCount(perTableProbeCount)
 #define UPDATE_ACCESS_COUNTS() \
   ++m_stats->numAccesses;      \
   int perTableProbeCount = 0
 #else
 #define UPDATE_PROBE_COUNTS() \
   do {                        \
   } while (0)
 #define UPDATE_ACCESS_COUNTS() \
   do {                         \
   } while (0)
 #endif
 #endif
 
 namespace WTF {
 
 #if DUMP_HASHTABLE_STATS
+struct WTF_EXPORT HashTableStats {
+  HashTableStats()
+      : numAccesses(0),
+        numRehashes(0),
+        numRemoves(0),
+        numReinserts(0),
+        maxCollisions(0),
+        numCollisions(0),
+        collisionGraph() {}
 
-struct WTF_EXPORT HashTableStats {
-  STATIC_ONLY(HashTableStats);
   // The following variables are all atomically incremented when modified.
-  static int numAccesses;
-  static int numRehashes;
-  static int numRemoves;
-  static int numReinserts;
+  int numAccesses;
+  int numRehashes;
+  int numRemoves;
+  int numReinserts;
 
   // The following variables are only modified in the recordCollisionAtCount
   // method within a mutex.
-  static int maxCollisions;
-  static int numCollisions;
-  static int collisionGraph[4096];
+  int maxCollisions;
+  int numCollisions;
+  int collisionGraph[4096];
 
-  static void recordCollisionAtCount(int count);
-  static void dumpStats();
+  void copy(const HashTableStats* other);
+  void recordCollisionAtCount(int count);
+  void dumpStats();
+
+  static HashTableStats& instance();
+
+  template <typename VisitorDispatcher>
+  void trace(VisitorDispatcher) {}
 };
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+template <typename Allocator, bool isGCType = Allocator::isGarbageCollected>
+class HashTableStatsPtr;
+
+template <typename Allocator>
+class HashTableStatsPtr<Allocator, false> final {
+  STATIC_ONLY(HashTableStatsPtr);
+
+ public:
+  static std::unique_ptr<HashTableStats> create() {
+    return wrapUnique(new HashTableStats);
+  }
+
+  static std::unique_ptr<HashTableStats> copy(
+      const std::unique_ptr<HashTableStats>& other) {
+    if (!other)
+      return nullptr;
+    return wrapUnique(new HashTableStats(*other));
+  }
+
+  static void swap(std::unique_ptr<HashTableStats>& stats,
+                   std::unique_ptr<HashTableStats>& other) {
+    stats.swap(other);
+  }
+};
+
+template <typename Allocator>
+class HashTableStatsPtr<Allocator, true> final {
+  STATIC_ONLY(HashTableStatsPtr);
+
+ public:
+  static HashTableStats* create() {
+    // Resort to manually allocating this POD on the vector
+    // backing heap, as blink::GarbageCollected<> isn't in scope
+    // in WTF.
+    void* storage = reinterpret_cast<void*>(
+        Allocator::template allocateVectorBacking<unsigned char>(
+            sizeof(HashTableStats)));
+    return new (storage) HashTableStats;
+  }
+
+  static HashTableStats* copy(const HashTableStats* other) {
+    if (!other)
+      return nullptr;
+    HashTableStats* obj = create();
+    obj->copy(other);
+    return obj;
+  }
+
+  static void swap(HashTableStats*& stats, HashTableStats*& other) {
+    std::swap(stats, other);
+  }
+};
+#endif
 #endif
 
 template <typename Key,
           typename Value,
           typename Extractor,
           typename HashFunctions,
           typename Traits,
           typename KeyTraits,
           typename Allocator>
 class HashTable;
@@ skipping 472 matching lines @@
       const_iterator;
   typedef Traits ValueTraits;
   typedef Key KeyType;
   typedef typename KeyTraits::PeekInType KeyPeekInType;
   typedef Value ValueType;
   typedef Extractor ExtractorType;
   typedef KeyTraits KeyTraitsType;
   typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
   typedef HashTableAddResult<HashTable, ValueType> AddResult;
 
-#if DUMP_HASHTABLE_STATS_PER_TABLE
-  struct Stats {
-    DISALLOW_NEW(Stats);
-    Stats()
-        : numAccesses(0),
-          numRehashes(0),
-          numRemoves(0),
-          numReinserts(0),
-          maxCollisions(0),
-          numCollisions(0),
-          collisionGraph() {}
-
-    int numAccesses;
-    int numRehashes;
-    int numRemoves;
-    int numReinserts;
-
-    int maxCollisions;
-    int numCollisions;
-    int collisionGraph[4096];
-
-    void recordCollisionAtCount(int count) {
-      if (count > maxCollisions)
-        maxCollisions = count;
-      numCollisions++;
-      collisionGraph[count]++;
-    }
-
-    void dumpStats() {
-      dataLogF("\nWTF::HashTable::Stats dump\n\n");
-      dataLogF("%d accesses\n", numAccesses);
-      dataLogF("%d total collisions, average %.2f probes per access\n",
-               numCollisions,
-               1.0 * (numAccesses + numCollisions) / numAccesses);
-      dataLogF("longest collision chain: %d\n", maxCollisions);
-      for (int i = 1; i <= maxCollisions; i++) {
-        dataLogF(
-            "  %d lookups with exactly %d collisions (%.2f%% , %.2f%% with "
-            "this many or more)\n",
-            collisionGraph[i], i,
-            100.0 * (collisionGraph[i] - collisionGraph[i + 1]) / numAccesses,
-            100.0 * collisionGraph[i] / numAccesses);
-      }
-      dataLogF("%d rehashes\n", numRehashes);
-      dataLogF("%d reinserts\n", numReinserts);
-    }
-  };
-#endif
-
   HashTable();
   void finalize() {
     ASSERT(!Allocator::isGarbageCollected);
     if (LIKELY(!m_table))
       return;
     ASSERT(!m_accessForbidden);
 #if ENABLE(ASSERT)
     m_accessForbidden = true;
 #endif
     deleteAllBucketsAndDeallocate(m_table, m_tableSize);
@@ skipping 195 matching lines @@
   unsigned m_queueFlag : 1;
   unsigned m_accessForbidden : 1;
   unsigned m_modifications;
 #else
   unsigned m_deletedCount : 31;
   unsigned m_queueFlag : 1;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
  public:
-  mutable std::unique_ptr<Stats> m_stats;
+  mutable
+      typename std::conditional<Allocator::isGarbageCollected,
+                                HashTableStats*,
+                                std::unique_ptr<HashTableStats>>::type m_stats;
 #endif
 
   template <WeakHandlingFlag x,
             typename T,
             typename U,
             typename V,
             typename W,
             typename X,
             typename Y,
             typename Z>
@@ skipping 21 matching lines @@
       m_keyCount(0),
       m_deletedCount(0),
       m_queueFlag(false)
 #if ENABLE(ASSERT)
       ,
       m_accessForbidden(false),
       m_modifications(0)
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
       ,
-      m_stats(wrapUnique(new Stats))
+      m_stats(nullptr)
 #endif
 {
   static_assert(Allocator::isGarbageCollected ||
                     (!IsPointerToGarbageCollectedType<Key>::value &&
                      !IsPointerToGarbageCollectedType<Value>::value),
                 "Cannot put raw pointers to garbage-collected classes into an "
                 "off-heap collection.");
 }
 
 inline unsigned doubleHash(unsigned key) {
@@ skipping 407 matching lines @@
           typename Allocator>
 Value*
 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
     reinsert(ValueType&& entry) {
   ASSERT(m_table);
   registerModification();
   ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
   ASSERT(
       !isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 #if DUMP_HASHTABLE_STATS
-  atomicIncrement(&HashTableStats::numReinserts);
+  atomicIncrement(&HashTableStats::instance().numReinserts);
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
   ++m_stats->numReinserts;
 #endif
   Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
   Mover<ValueType, Allocator,
         Traits::template NeedsToForbidGCOnMove<>::value>::move(std::move(entry),
                                                                *newEntry);
 
   return newEntry;
@@ skipping 74 matching lines @@
           typename Allocator>
 void HashTable<Key,
                Value,
                Extractor,
                HashFunctions,
                Traits,
                KeyTraits,
                Allocator>::remove(ValueType* pos) {
   registerModification();
 #if DUMP_HASHTABLE_STATS
-  atomicIncrement(&HashTableStats::numRemoves);
+  atomicIncrement(&HashTableStats::instance().numRemoves);
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
   ++m_stats->numRemoves;
 #endif
 
   ASSERT(!m_accessForbidden);
 #if ENABLE(ASSERT)
   m_accessForbidden = true;
 #endif
   deleteBucket(*pos);
@@ skipping 220 matching lines @@
           typename KeyTraits,
           typename Allocator>
 Value*
 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
     rehashTo(ValueType* newTable, unsigned newTableSize, Value* entry) {
   unsigned oldTableSize = m_tableSize;
   ValueType* oldTable = m_table;
 
 #if DUMP_HASHTABLE_STATS
   if (oldTableSize != 0)
-    atomicIncrement(&HashTableStats::numRehashes);
+    atomicIncrement(&HashTableStats::instance().numRehashes);
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
   if (oldTableSize != 0)
     ++m_stats->numRehashes;
 #endif
 
   m_table = newTable;
   m_tableSize = newTableSize;
 
   Value* newEntry = nullptr;
   for (unsigned i = 0; i != oldTableSize; ++i) {
     if (isEmptyOrDeletedBucket(oldTable[i])) {
       ASSERT(&oldTable[i] != entry);
       continue;
     }
     Value* reinsertedEntry = reinsert(std::move(oldTable[i]));
     if (&oldTable[i] == entry) {
       ASSERT(!newEntry);
       newEntry = reinsertedEntry;
     }
   }
 
   m_deletedCount = 0;
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+  if (!m_stats)
+    m_stats = HashTableStatsPtr<Allocator>::create();
+#endif
+
   return newEntry;
 }
 
 template <typename Key,
           typename Value,
           typename Extractor,
           typename HashFunctions,
           typename Traits,
           typename KeyTraits,
           typename Allocator>
 Value*
 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::
     rehash(unsigned newTableSize, Value* entry) {
   unsigned oldTableSize = m_tableSize;
   ValueType* oldTable = m_table;
 
 #if DUMP_HASHTABLE_STATS
   if (oldTableSize != 0)
-    atomicIncrement(&HashTableStats::numRehashes);
+    atomicIncrement(&HashTableStats::instance().numRehashes);
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
   if (oldTableSize != 0)
     ++m_stats->numRehashes;
 #endif
 
   // The Allocator::isGarbageCollected check is not needed.  The check is just
   // a static hint for a compiler to indicate that Base::expandBuffer returns
   // false if Allocator is a PartitionAllocator.
@@ skipping 64 matching lines @@
       m_keyCount(0),
       m_deletedCount(0),
       m_queueFlag(false)
 #if ENABLE(ASSERT)
       ,
       m_accessForbidden(false),
       m_modifications(0)
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
       ,
-      m_stats(wrapUnique(new Stats(*other.m_stats)))
+      m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats))
 #endif
 {
   // Copy the hash table the dumb way, by adding each element to the new
   // table.  It might be more efficient to copy the table slots, but it's not
   // clear that efficiency is needed.
   const_iterator end = other.end();
   for (const_iterator it = other.begin(); it != end; ++it)
     add(*it);
 }
 
@@ skipping 11 matching lines @@
       m_keyCount(0),
       m_deletedCount(0),
       m_queueFlag(false)
 #if ENABLE(ASSERT)
       ,
       m_accessForbidden(false),
       m_modifications(0)
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
       ,
-      m_stats(wrapUnique(new Stats(*other.m_stats)))
+      m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats))
 #endif
 {
   swap(other);
 }
 
 template <typename Key,
           typename Value,
           typename Extractor,
           typename HashFunctions,
           typename Traits,
@@ skipping 15 matching lines @@
   m_deletedCount = other.m_deletedCount;
   other.m_deletedCount = deleted;
   ASSERT(!m_queueFlag);
   ASSERT(!other.m_queueFlag);
 
 #if ENABLE(ASSERT)
   std::swap(m_modifications, other.m_modifications);
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
-  m_stats.swap(other.m_stats);
+  HashTableStatsPtr<Allocator>::swap(m_stats, other.m_stats);
 #endif
 }
 
 template <typename Key,
           typename Value,
           typename Extractor,
           typename HashFunctions,
           typename Traits,
           typename KeyTraits,
           typename Allocator>
@@ skipping 144 matching lines @@
           typename KeyTraits,
           typename Allocator>
 template <typename VisitorDispatcher>
 void HashTable<Key,
                Value,
                Extractor,
                HashFunctions,
                Traits,
                KeyTraits,
                Allocator>::trace(VisitorDispatcher visitor) {
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+  Allocator::markNoTracing(visitor, m_stats);
+#endif
+
   // If someone else already marked the backing and queued up the trace and/or
   // weak callback then we are done. This optimization does not happen for
   // ListHashSet since its iterator does not point at the backing.
   if (!m_table || Allocator::isHeapObjectAlive(m_table))
     return;
+
   // Normally, we mark the backing store without performing trace. This means
   // it is marked live, but the pointers inside it are not marked.  Instead we
   // will mark the pointers below. However, for backing stores that contain
   // weak pointers the handling is rather different.  We don't mark the
   // backing store here, so the marking GC will leave the backing unmarked. If
   // the backing is found in any other way than through its HashTable (ie from
   // an iterator) then the mark bit will be set and the pointers will be
   // marked strongly, avoiding problems with iterating over things that
   // disappear due to weak processing while we are iterating over them. We
   // register the backing store pointer for delayed marking which will take
@@ skipping 181 matching lines @@
   CollectionIterator end(toBeRemoved.end());
   for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
     collection.remove(*it);
 }
 
 }  // namespace WTF
 
 #include "wtf/HashIterators.h"
 
 #endif  // WTF_HashTable_h