Changeset 3736 in webkit for trunk/JavaScriptCore/kjs/ustring.cpp

Timestamp:

Mar 3, 2003, 5:13:26 PM (22 years ago)

Author:

mjs

Message:

JavaScriptCore:

Reviewed by Trey.

• fixed 3158833 - ebay prefs page is so slow, it seems like a hang.

92% speed improvement on ebay prefs page.
1% speed improvement on js-ibench and js-performance plt suites.

There were a couple of problems with the identifier hash table that
I fixed:

• kjs/identifier.cpp: (void Identifier::remove): Adjust the shrink threshold to avoid constantly growing and shrinking.
• kjs/ustring.cpp: (UString::Rep::computeHash): Use a better hash function that avoids collisions for obvious data sets.

WebFoundation:

Reviewed by Trey.

Updated string hash function to match the new, improved one in
JavaScriptCore.

• Database.subproj/WebLRUFileList.m: (cStringHash):

WebCore:

Reviewed by Trey.

Updated string hash function to match the new, improved one in
JavaScriptCore.

• kwq/KWQCharsets.mm: (encodingNameHash):

File:

• trunk/JavaScriptCore/kjs/ustring.cpp (modified) (3 diffs)

trunk/JavaScriptCore/kjs/ustring.cpp

@@ -178 +178 @@
 }
 
+// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
+// or anything like that.
+const unsigned PHI = 0x9e3779b9U;
+
+// This hash algorithm comes from:
+// http://burtleburtle.net/bob/hash/hashfaq.html
+// http://burtleburtle.net/bob/hash/doobs.html
 unsigned UString::Rep::computeHash(const UChar *s, int length)
 {
@@ -183 +190 @@
     int suffixPosition = length < 16 ? 8 : length - 8;
 
-    unsigned h = length;
-    for (int i = 0; i < prefixLength; i++)
-        h = 127 * h + s[i].uc;
-    for (int i = suffixPosition; i < length; i++)
-        h = 127 * h + s[i].uc;
+    unsigned h = PHI;
+    h += length;
+    h += (h << 10); 
+    h ^= (h << 6); 
+
+    for (int i = 0; i < prefixLength; i++) {
+        h += s[i].uc; 
+        h += (h << 10); 
+        h ^= (h << 6); 
+    }
+    for (int i = suffixPosition; i < length; i++){
+        h += s[i].uc; 
+        h += (h << 10); 
+        h ^= (h << 6); 
+    }
+
+    h += (h << 3);
+    h ^= (h >> 11);
+    h += (h << 15);
+ 
     if (h == 0)
         h = 0x80000000;
+
     return h;
 }
 
+// This hash algorithm comes from:
+// http://burtleburtle.net/bob/hash/hashfaq.html
+// http://burtleburtle.net/bob/hash/doobs.html
 unsigned UString::Rep::computeHash(const char *s)
 {
@@ -199 +225 @@
     int suffixPosition = length < 16 ? 8 : length - 8;
 
-    unsigned h = length;
-    for (int i = 0; i < prefixLength; i++)
-        h = 127 * h + (unsigned char)s[i];
-    for (int i = suffixPosition; i < length; i++)
-        h = 127 * h + (unsigned char)s[i];
+    unsigned h = PHI;
+    h += length;
+    h += (h << 10); 
+    h ^= (h << 6); 
+
+    for (int i = 0; i < prefixLength; i++) {
+        h += (unsigned char)s[i];
+        h += (h << 10); 
+        h ^= (h << 6); 
+    }
+    for (int i = suffixPosition; i < length; i++) {
+        h += (unsigned char)s[i];
+        h += (h << 10); 
+        h ^= (h << 6); 
+    }
+
+    h += (h << 3);
+    h ^= (h >> 11);
+    h += (h << 15);
+
     if (h == 0)
         h = 0x80000000;
+
     return h;
 }