Improve WTF::HashTable performance by changing probing method

Source/wtf/HashTable.h

Index: Source/wtf/HashTable.h
diff --git a/Source/wtf/HashTable.h b/Source/wtf/HashTable.h
index e99bc1e9cdccd0232083343cba1855cad9eb97f7..934073bfbbeddc26f29b4e4661f8a719e7239d51 100644
--- a/Source/wtf/HashTable.h
+++ b/Source/wtf/HashTable.h
@@ -485,6 +485,7 @@ namespace WTF {
 
         static const int m_maxLoad = 2;
         static const int m_minLoad = 6;
+        static const int perturbShift = 5;
 
         ValueType* m_table;
         int m_tableSize;
@@ -561,16 +562,6 @@ namespace WTF {
     {
     }
 
-    inline unsigned doubleHash(unsigned key)
-    {
-        key = ~key + (key >> 23);
-        key ^= (key << 12);
-        key ^= (key >> 7);
-        key ^= (key << 2);
-        key ^= (key >> 20);
-        return key;
-    }
-
 #if ASSERT_DISABLED
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
@@ -603,11 +594,10 @@ namespace WTF {
     {
         checkKey<HashTranslator>(key);
 
-        int k = 0;
-        int sizeMask = m_tableSizeMask;
         ValueType* table = m_table;
         unsigned h = HashTranslator::hash(key);
-        int i = h & sizeMask;
+        unsigned i = h;
+        unsigned perturb = h;
 
         if (!table)
             return 0;
@@ -623,7 +613,7 @@ namespace WTF {
 #endif
 
         while (1) {
-            ValueType* entry = table + i;
+            ValueType* entry = table + (i & m_tableSizeMask);
                 
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
@@ -649,9 +639,8 @@ namespace WTF {
             m_stats->recordCollisionAtCount(perTableProbeCount);
 #endif
 
-            if (k == 0)
-                k = 1 | doubleHash(h);
-            i = (i + k) & sizeMask;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
     }
 
@@ -662,11 +651,10 @@ namespace WTF {
         ASSERT(m_table);
         checkKey<HashTranslator>(key);
 
-        int k = 0;
         ValueType* table = m_table;
-        int sizeMask = m_tableSizeMask;

[abarth-chromium, 2013/06/25 05:03:38]

Is there a reason you remove the copy of m_tableSizeMask into a local variable?

         unsigned h = HashTranslator::hash(key);
-        int i = h & sizeMask;
+        unsigned i = h;
+        unsigned perturb = h;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
@@ -681,7 +669,7 @@ namespace WTF {
         ValueType* deletedEntry = 0;
 
         while (1) {
-            ValueType* entry = table + i;
+            ValueType* entry = table + (i & m_tableSizeMask);
             
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
@@ -712,9 +700,8 @@ namespace WTF {
             m_stats->recordCollisionAtCount(perTableProbeCount);
 #endif
 
-            if (k == 0)
-                k = 1 | doubleHash(h);
-            i = (i + k) & sizeMask;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
     }
 
@@ -725,11 +712,10 @@ namespace WTF {
         ASSERT(m_table);
         checkKey<HashTranslator>(key);
 
-        int k = 0;
         ValueType* table = m_table;
-        int sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
-        int i = h & sizeMask;
+        unsigned i = h;
+        unsigned perturb = h;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
@@ -744,7 +730,7 @@ namespace WTF {
         ValueType* deletedEntry = 0;
 
         while (1) {
-            ValueType* entry = table + i;
+            ValueType* entry = table + (i & m_tableSizeMask);
             
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
@@ -775,9 +761,8 @@ namespace WTF {
             m_stats->recordCollisionAtCount(perTableProbeCount);
 #endif
 
-            if (k == 0)
-                k = 1 | doubleHash(h);
-            i = (i + k) & sizeMask;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
     }
 
@@ -821,11 +806,10 @@ namespace WTF {
 
         ASSERT(m_table);
 
-        int k = 0;
         ValueType* table = m_table;
-        int sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
-        int i = h & sizeMask;
+        unsigned i = h;
+        unsigned perturb = h;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
@@ -840,7 +824,7 @@ namespace WTF {
         ValueType* deletedEntry = 0;
         ValueType* entry;
         while (1) {
-            entry = table + i;
+            entry = table + (i & m_tableSizeMask);
             
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
@@ -871,9 +855,8 @@ namespace WTF {
             m_stats->recordCollisionAtCount(perTableProbeCount);
 #endif
 
-            if (k == 0)
-                k = 1 | doubleHash(h);
-            i = (i + k) & sizeMask;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
 
         if (deletedEntry) {