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):

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

diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index 197dea76a22a8d80ec36d7d80bac526794345167..e8be2f9ca411d744d003c3f5d9879cb00f459427 100644 (file)
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -1,3 +1,30 @@
+2007-10-31  Maciej Stachowiak  <mjs@apple.com>
+
+        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):
+
 2007-10-30  Adam Roben  <aroben@apple.com>
 
         Build fix

diff --git a/JavaScriptCore/kjs/property_map.cpp b/JavaScriptCore/kjs/property_map.cpp
index aa55d33b3dc54073a243852b061622bb44dd25a0..de993fcae07874e1e15c5a8a2be8a2183dcb67b6 100644 (file)
--- a/JavaScriptCore/kjs/property_map.cpp
+++ b/JavaScriptCore/kjs/property_map.cpp
@@ -25,6 +25,7 @@
 #include "object.h"
 #include "protect.h"
 #include "PropertyNameArray.h"
+#include "HashTable.h"
 #include <algorithm>
 #include <wtf/Assertions.h>
 #include <wtf/FastMalloc.h>
@@ -34,7 +35,7 @@ using std::max;
 
 #define DEBUG_PROPERTIES 0
 #define DO_CONSISTENCY_CHECK 0
-#define DUMP_STATISTICS 0
+#define DUMP_PROPERTYMAP_STATS 0
 #define USE_SINGLE_ENTRY 1
 
 // 2/28/2006 ggaren: command-line JS iBench says that USE_SINGLE_ENTRY is a
@@ -50,7 +51,7 @@ namespace KJS {
 // but it's not going to blow out the stack to allocate this number of pointers.
 const int smallMapThreshold = 1024;
 
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
 
 static int numProbes;
 static int numCollisions;
@@ -180,7 +181,7 @@ JSValue *PropertyMap::get(const Identifier &name, unsigned &attributes) const
     Entry *entries = m_u.table->entries;
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
 #endif
@@ -196,9 +197,9 @@ JSValue *PropertyMap::get(const Identifier &name, unsigned &attributes) const
         }
         
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }
@@ -224,7 +225,7 @@ JSValue *PropertyMap::get(const Identifier &name) const
     Entry *entries = m_u.table->entries;
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
 #endif
@@ -238,9 +239,9 @@ JSValue *PropertyMap::get(const Identifier &name) const
             return entries[i].value;
         
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }
@@ -266,7 +267,7 @@ JSValue **PropertyMap::getLocation(const Identifier &name)
     Entry *entries = m_u.table->entries;
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
 #endif
@@ -280,9 +281,9 @@ JSValue **PropertyMap::getLocation(const Identifier &name)
             return &entries[i].value;
         
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }
@@ -352,7 +353,7 @@ void PropertyMap::put(const Identifier &name, JSValue *value, int attributes, bo
     int k = 0;
     bool foundDeletedElement = false;
     int deletedElementIndex = 0;    /* initialize to make the compiler happy */
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
 #endif
@@ -371,9 +372,9 @@ void PropertyMap::put(const Identifier &name, JSValue *value, int attributes, bo
             deletedElementIndex = i;
         }
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }
@@ -404,16 +405,16 @@ void PropertyMap::insert(UString::Rep *key, JSValue *value, int attributes, int
     Entry *entries = m_u.table->entries;
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != key;
 #endif
     while (entries[i].key) {
         ASSERT(entries[i].key != deletedSentinel());
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }
@@ -531,7 +532,7 @@ void PropertyMap::remove(const Identifier &name)
     Entry *entries = m_u.table->entries;
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     ++numRemoves;
     numCollisions += entries[i].key && entries[i].key != rep;
@@ -540,9 +541,9 @@ void PropertyMap::remove(const Identifier &name)
         if (rep == key)
             break;
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }
@@ -750,7 +751,7 @@ void PropertyMap::checkConsistency()
             if (rep == key)
                 break;
             if (k == 0)
-                k = 1 | (h % m_u.table->sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & m_u.table->sizeMask;
         }
         ASSERT(i == j);

diff --git a/JavaScriptCore/wtf/HashTable.h b/JavaScriptCore/wtf/HashTable.h
index 32a79d76fcf523c33b9aabc4edddc110eefe8c8b..ebc41c4d3e7c4d6a875fb084b5f3a2e0dad526dc 100644 (file)
--- a/JavaScriptCore/wtf/HashTable.h
+++ b/JavaScriptCore/wtf/HashTable.h
@@ -397,6 +397,16 @@ namespace WTF {
     {
     }
 
+    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>
     inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
@@ -442,7 +452,7 @@ namespace WTF {
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
@@ -499,7 +509,7 @@ namespace WTF {
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
@@ -556,7 +566,7 @@ namespace WTF {
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
@@ -621,7 +631,7 @@ namespace WTF {
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
             if (k == 0)
-                k = 1 | (h % sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }