Modified: trunk/Source/WTF/wtf/HashTable.h (123558 => 123559)
--- trunk/Source/WTF/wtf/HashTable.h 2012-07-25 00:48:31 UTC (rev 123558)
+++ trunk/Source/WTF/wtf/HashTable.h 2012-07-25 01:07:21 UTC (rev 123559)
@@ -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 @@
#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 @@
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 @@
// 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 @@
, 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 @@
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 @@
++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 @@
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 @@
++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 @@
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 @@
++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 @@
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 @@
++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 @@
#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 @@
#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 @@
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 @@
, 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 @@
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>
