Changeset 27301 in webkit for trunk/JavaScriptCore/kjs/property_map.cpp

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/kjs/property_map.cpp (modified) (16 diffs)

trunk/JavaScriptCore/kjs/property_map.cpp

@@ -26 +26 @@
 #include "protect.h"
 #include "PropertyNameArray.h"
+#include "HashTable.h"
 #include <algorithm>
 #include <wtf/Assertions.h>
@@ -35 +36 @@
 #define DEBUG_PROPERTIES 0
 #define DO_CONSISTENCY_CHECK 0
-#define DUMP_STATISTICS 0
+#define DUMP_PROPERTYMAP_STATS 0
 #define USE_SINGLE_ENTRY 1
 
@@ -51 +52 @@
 const int smallMapThreshold = 1024;
 
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
 
 static int numProbes;
@@ -181 +182 @@
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
@@ -197 +198 @@
         
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
@@ -225 +226 @@
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
@@ -239 +240 @@
         
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
@@ -267 +268 @@
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != rep;
@@ -281 +282 @@
         
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
@@ -353 +354 @@
     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;
@@ -372 +373 @@
         }
         if (k == 0)
-            k = 1 | (h % sizeMask);
+            k = 1 | doubleHash(h);
         i = (i + k) & sizeMask;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
@@ -405 +406 @@
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     numCollisions += entries[i].key && entries[i].key != key;
@@ -412 +413 @@
         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
@@ -532 +533 @@
     int i = h & sizeMask;
     int k = 0;
-#if DUMP_STATISTICS
+#if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     ++numRemoves;
@@ -541 +542 @@
             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
@@ -751 +752 @@
                 break;
             if (k == 0)
-                k = 1 | (h % m_u.table->sizeMask);
+                k = 1 | doubleHash(h);
             i = (i + k) & m_u.table->sizeMask;
         }