Improve WTF::HashTable performance by changing probing method

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.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 467 matching lines @@
 #endif
 
 #if CHECK_HASHTABLE_ITERATORS
         void invalidateIterators();
 #else
         static void invalidateIterators() { }
 #endif
 
         static const int m_maxLoad = 2;
         static const int m_minLoad = 6;
+        static const int perturbShift = 5;
 
         ValueType* m_table;
         int m_tableSize;
         int m_tableSizeMask;
         int m_keyCount;
         int m_deletedCount;
 
 #if CHECK_HASHTABLE_ITERATORS
     public:
         // All access to m_iterators should be guarded with m_mutex.
@@ skipping 56 matching lines @@
 #if CHECK_HASHTABLE_ITERATORS
         , m_iterators(0)
         , m_mutex(adoptPtr(new Mutex))
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         , m_stats(adoptPtr(new Stats))
 #endif
     {
     }
 
-    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>
     template<typename HashTranslator, typename T>
     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
     {
     }
 
 #else
 
@@ skipping 12 matching lines @@
     }
 
 #endif
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     template<typename HashTranslator, typename T>
     inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
     {
         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;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
         int probeCount = 0;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numAccesses;
         int perTableProbeCount = 0;
 #endif
 
         while (1) {
-            ValueType* entry = table + i;
+            ValueType* entry = table + (i & sizeMask);
                 
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                 if (HashTranslator::equal(Extractor::extract(*entry), key))
                     return entry;
                 
                 if (isEmptyBucket(*entry))
                     return 0;
             } else {
                 if (isEmptyBucket(*entry))
                     return 0;
                 
                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
                     return entry;
             }
 #if DUMP_HASHTABLE_STATS
             ++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;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     template<typename HashTranslator, typename T>
     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
     {
         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);
         int probeCount = 0;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numAccesses;
         int perTableProbeCount = 0;
 #endif
 
         ValueType* deletedEntry = 0;
 
         while (1) {
-            ValueType* entry = table + i;
+            ValueType* entry = table + (i & sizeMask);
             
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                 if (isEmptyBucket(*entry))
                     return LookupType(deletedEntry ? deletedEntry : entry, false);
                 
                 if (HashTranslator::equal(Extractor::extract(*entry), key))
                     return LookupType(entry, true);
                 
                 if (isDeletedBucket(*entry))
@@ skipping 10 matching lines @@
 #if DUMP_HASHTABLE_STATS
             ++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;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     template<typename HashTranslator, typename T>
     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
     {
         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);
         int probeCount = 0;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numAccesses;
         int perTableProbeCount = 0;
 #endif
 
         ValueType* deletedEntry = 0;
 
         while (1) {
-            ValueType* entry = table + i;
+            ValueType* entry = table + (i & sizeMask);
             
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                 if (isEmptyBucket(*entry))
                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
                 
                 if (HashTranslator::equal(Extractor::extract(*entry), key))
                     return makeLookupResult(entry, true, h);
                 
                 if (isDeletedBucket(*entry))
@@ skipping 10 matching lines @@
 #if DUMP_HASHTABLE_STATS
             ++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;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
     }
 
     template<bool emptyValueIsZero> struct HashTableBucketInitializer;
 
     template<> struct HashTableBucketInitializer<false> {
         template<typename Traits, typename Value> static void initialize(Value& bucket)
         {
             new (NotNull, &bucket) Value(Traits::emptyValue());
         }
@@ skipping 23 matching lines @@
 
         invalidateIterators();
 
         if (!m_table)
             expand();
 
         internalCheckTableConsistency();
 
         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);
         int probeCount = 0;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numAccesses;
         int perTableProbeCount = 0;
 #endif
 
         ValueType* deletedEntry = 0;
         ValueType* entry;
         while (1) {
-            entry = table + i;
+            entry = table + (i & sizeMask);
             
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                 if (isEmptyBucket(*entry))
                     break;
                 
                 if (HashTranslator::equal(Extractor::extract(*entry), key))
                     return AddResult(makeKnownGoodIterator(entry), false);
                 
                 if (isDeletedBucket(*entry))
@@ skipping 10 matching lines @@
 #if DUMP_HASHTABLE_STATS
             ++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;
+            perturb >>= perturbShift;
+            i = i*5 + perturb + 1;
         }
 
         if (deletedEntry) {
             initializeBucket(*deletedEntry);
             entry = deletedEntry;
             --m_deletedCount; 
         }
 
         HashTranslator::translate(*entry, key, extra);
 
@@ skipping 524 matching lines @@
     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
 } // namespace WTF
 
 #include <wtf/HashIterators.h>
 
 #endif // WTF_HashTable_h