Add per-HashTable stats
authorweinig@apple.com <weinig@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 25 Jul 2012 01:07:21 +0000 (01:07 +0000)
committerweinig@apple.com <weinig@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 25 Jul 2012 01:07:21 +0000 (01:07 +0000)
https://bugs.webkit.org/show_bug.cgi?id=92185

Reviewed by Anders Carlsson.

Add per-HashTable stats, so we can look at the effectiveness of an individual HashTable.

* wtf/HashTable.h:
(WTF::HashTable::Stats::Stats):
Add a HashTable::Stats to hold the stats.

(WTF::HashTable::Stats::recordCollisionAtCount):
(WTF::HashTable::Stats::dumpStats):
Add versions of recordCollisionAtCount and dumpStats for per-HashTable version.

(WTF::HashTable):
Keep the stats, if enabled, in an OwnPtr, to not blow JSCell max size restrictions.

(WTF::lookup):
(WTF::lookupForWriting):
(WTF::fullLookupForWriting):
(WTF::add):
(WTF::reinsert):
(WTF::remove):
(WTF::rehash):
Keep track of the stats as the table is used.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@123559 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/HashTable.h

index 82b27c9..a2039eb 100644 (file)
@@ -1,3 +1,32 @@
+2012-07-24  Sam Weinig  <sam@webkit.org>
+
+        Add per-HashTable stats
+        https://bugs.webkit.org/show_bug.cgi?id=92185
+
+        Reviewed by Anders Carlsson.
+
+        Add per-HashTable stats, so we can look at the effectiveness of an individual HashTable.
+
+        * wtf/HashTable.h:
+        (WTF::HashTable::Stats::Stats):
+        Add a HashTable::Stats to hold the stats.
+
+        (WTF::HashTable::Stats::recordCollisionAtCount):
+        (WTF::HashTable::Stats::dumpStats):
+        Add versions of recordCollisionAtCount and dumpStats for per-HashTable version.
+
+        (WTF::HashTable):
+        Keep the stats, if enabled, in an OwnPtr, to not blow JSCell max size restrictions.
+
+        (WTF::lookup):
+        (WTF::lookupForWriting):
+        (WTF::fullLookupForWriting):
+        (WTF::add):
+        (WTF::reinsert):
+        (WTF::remove):
+        (WTF::rehash):
+        Keep track of the stats as the table is used.
+
 2012-07-24  Patrick Gansterer  <paroga@webkit.org>
 
         Store the full year in GregorianDateTime
index ccf62dc..8beab3d 100644 (file)
@@ -24,6 +24,7 @@
 
 #include <wtf/Alignment.h>
 #include <wtf/Assertions.h>
+#include <wtf/DataLog.h>
 #include <wtf/FastMalloc.h>
 #include <wtf/HashTraits.h>
 #include <wtf/StdLibExtras.h>
@@ -39,6 +40,7 @@
 namespace WTF {
 
 #define DUMP_HASHTABLE_STATS 0
+#define DUMP_HASHTABLE_STATS_PER_TABLE 0
 
 // Enables internal WTF consistency checks that are invoked automatically. Non-WTF callers can call checkTableConsistency() even if internal checks are disabled.
 #define CHECK_HASHTABLE_CONSISTENCY 0
@@ -54,8 +56,6 @@ namespace WTF {
 #if DUMP_HASHTABLE_STATS
 
     struct HashTableStats {
-        // All of the variables are accessed in ~HashTableStats when the static struct is destroyed.
-
         // The following variables are all atomically incremented when modified.
         WTF_EXPORTDATA static int numAccesses;
         WTF_EXPORTDATA static int numRehashes;
@@ -319,6 +319,51 @@ namespace WTF {
         typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
         typedef HashTableAddResult<iterator> AddResult;
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        struct 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()
+            {
+                dataLog("\nWTF::HashTable::Stats dump\n\n");
+                dataLog("%d accesses\n", numAccesses);
+                dataLog("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
+                dataLog("longest collision chain: %d\n", maxCollisions);
+                for (int i = 1; i <= maxCollisions; i++) {
+                    dataLog("  %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);
+                }
+                dataLog("%d rehashes\n", numRehashes);
+                dataLog("%d reinserts\n", numReinserts);
+            }
+        };
+#endif
+
         HashTable();
         ~HashTable() 
         {
@@ -453,6 +498,11 @@ namespace WTF {
         // Use OwnPtr so HashTable can still be memmove'd or memcpy'ed.
         mutable OwnPtr<Mutex> m_mutex;
 #endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+    public:
+        mutable OwnPtr<Stats> m_stats;
+#endif
     };
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
@@ -466,6 +516,9 @@ namespace WTF {
         , m_iterators(0)
         , m_mutex(adoptPtr(new Mutex))
 #endif
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        , m_stats(adoptPtr(new Stats))
+#endif
     {
     }
 
@@ -525,6 +578,11 @@ namespace WTF {
         int probeCount = 0;
 #endif
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        ++m_stats->numAccesses;
+        int perTableProbeCount = 0;
+#endif
+
         while (1) {
             ValueType* entry = table + i;
                 
@@ -546,6 +604,12 @@ namespace WTF {
             ++probeCount;
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+            ++perTableProbeCount;
+            m_stats->recordCollisionAtCount(perTableProbeCount);
+#endif
+
             if (k == 0)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
@@ -570,6 +634,11 @@ namespace WTF {
         int probeCount = 0;
 #endif
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        ++m_stats->numAccesses;
+        int perTableProbeCount = 0;
+#endif
+
         ValueType* deletedEntry = 0;
 
         while (1) {
@@ -598,6 +667,12 @@ namespace WTF {
             ++probeCount;
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+            ++perTableProbeCount;
+            m_stats->recordCollisionAtCount(perTableProbeCount);
+#endif
+
             if (k == 0)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
@@ -622,6 +697,11 @@ namespace WTF {
         int probeCount = 0;
 #endif
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        ++m_stats->numAccesses;
+        int perTableProbeCount = 0;
+#endif
+
         ValueType* deletedEntry = 0;
 
         while (1) {
@@ -650,6 +730,12 @@ namespace WTF {
             ++probeCount;
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+            ++perTableProbeCount;
+            m_stats->recordCollisionAtCount(perTableProbeCount);
+#endif
+
             if (k == 0)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
@@ -707,6 +793,11 @@ namespace WTF {
         int probeCount = 0;
 #endif
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        ++m_stats->numAccesses;
+        int perTableProbeCount = 0;
+#endif
+
         ValueType* deletedEntry = 0;
         ValueType* entry;
         while (1) {
@@ -735,6 +826,12 @@ namespace WTF {
             ++probeCount;
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+            ++perTableProbeCount;
+            m_stats->recordCollisionAtCount(perTableProbeCount);
+#endif
+
             if (k == 0)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
@@ -820,6 +917,9 @@ namespace WTF {
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numReinserts);
 #endif
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        ++m_stats->numReinserts;
+#endif
 
         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
     }
@@ -883,6 +983,9 @@ namespace WTF {
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numRemoves);
 #endif
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        ++m_stats->numRemoves;
+#endif
 
         deleteBucket(*pos);
         ++m_deletedCount;
@@ -979,6 +1082,11 @@ namespace WTF {
             atomicIncrement(&HashTableStats::numRehashes);
 #endif
 
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        if (oldTableSize != 0)
+            ++m_stats->numRehashes;
+#endif
+
         m_tableSize = newTableSize;
         m_tableSizeMask = newTableSize - 1;
         m_table = allocateTable(newTableSize);
@@ -1019,6 +1127,9 @@ namespace WTF {
         , m_iterators(0)
         , m_mutex(adoptPtr(new Mutex))
 #endif
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        , m_stats(adoptPtr(new Stats(*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.
@@ -1052,6 +1163,10 @@ namespace WTF {
         int tmp_deletedCount = m_deletedCount;
         m_deletedCount = other.m_deletedCount;
         other.m_deletedCount = tmp_deletedCount;
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+        m_stats.swap(other.m_stats);
+#endif
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>