Changeset 27301 in webkit for trunk/JavaScriptCore/wtf/HashTable.h

Timestamp:

Oct 31, 2007, 1:22:12 AM (18 years ago)

Author:

mjs

Message:

Reviewed by ChangeLog.

• get rid of integer divide in PropertyMap and HashTable for 1% SunSpider speedup

Integer divide sucks. Fortunately, a bunch of shifts and XORs
biased towards the high bits is sufficient to provide a good
double hash. Besides the SunSpider win, I used the dump statistics
mode for both to verify that collisions did not increase and that
the longest collision chain is not any longer.

• kjs/property_map.cpp: (KJS::doubleHash): (KJS::PropertyMap::get): (KJS::PropertyMap::getLocation): (KJS::PropertyMap::put): (KJS::PropertyMap::insert): (KJS::PropertyMap::remove): (KJS::PropertyMap::checkConsistency):
• wtf/HashTable.h: (WTF::doubleHash): (WTF::::lookup): (WTF::::lookupForWriting): (WTF::::fullLookupForWriting): (WTF::::add):

File:

• trunk/JavaScriptCore/wtf/HashTable.h (modified) (5 diffs)

trunk/JavaScriptCore/wtf/HashTable.h

@@ -398 +398 @@
     }
 
+    static inline unsigned doubleHash(unsigned key)
+    {
+        key = ~key + (key >> 23);
+        key ^= (key << 12);
+        key ^= (key >> 7);
+        key ^= (key << 2);
+        key ^= (key >> 20);
+        return key;
+    }
+
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     template<typename T, typename HashTranslator>
@@ -443 +453 @@
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
@@ -500 +510 @@
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
@@ -557 +567 @@
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
@@ -622 +632 @@
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }