Reviewed by Darin.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 6 Jan 2006 23:51:00 +0000 (23:51 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 6 Jan 2006 23:51:00 +0000 (23:51 +0000)
- miscellaneous changes for 4% speedup on the JavaScript iBench
http://bugzilla.opendarwin.org/show_bug.cgi?id=6396

        Changes mostly thanks to Maks Orlovich, tweaked a little by me.

        * kjs/create_hash_table: Use the same hash as the one used buy Identifier.
        * kjs/function.cpp:
        (KJS::FunctionImp::processParameters): Use the new List::copyFrom
        (KJS::ActivationImp::ActivationImp): track variable while iterating
        * kjs/internal.cpp:
        (KJS::StringImp::toObject): create StringInstance directly
        * kjs/list.cpp:
        (KJS::List::copy): implement in terms of copyFrom
        (KJS::List::copyFrom): more efficient way to copy in another list
        * kjs/list.h:
        * kjs/lookup.cpp:
        (keysMatch): updated to work with identifier hash
        (findEntry): ditto
        (Lookup::findEntry): ditto
        (Lookup::find): ditto
        * kjs/lookup.h:

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

JavaScriptCore/ChangeLog
JavaScriptCore/kjs/create_hash_table
JavaScriptCore/kjs/function.cpp
JavaScriptCore/kjs/internal.cpp
JavaScriptCore/kjs/list.cpp
JavaScriptCore/kjs/list.h
JavaScriptCore/kjs/lookup.cpp
JavaScriptCore/kjs/lookup.h

index f0236c3..705c4b5 100644 (file)
@@ -1,5 +1,31 @@
 2006-01-06  Maciej Stachowiak  <mjs@apple.com>
 
+       Reviewed by Darin.
+
+       - miscellaneous changes for 4% speedup on the JavaScript iBench
+       http://bugzilla.opendarwin.org/show_bug.cgi?id=6396
+       
+        Changes mostly thanks to Maks Orlovich, tweaked a little by me.
+
+        * kjs/create_hash_table: Use the same hash as the one used buy Identifier.
+        * kjs/function.cpp:
+        (KJS::FunctionImp::processParameters): Use the new List::copyFrom
+        (KJS::ActivationImp::ActivationImp): track variable while iterating
+        * kjs/internal.cpp:
+        (KJS::StringImp::toObject): create StringInstance directly
+        * kjs/list.cpp:
+        (KJS::List::copy): implement in terms of copyFrom
+        (KJS::List::copyFrom): more efficient way to copy in another list
+        * kjs/list.h:
+        * kjs/lookup.cpp:
+        (keysMatch): updated to work with identifier hash
+        (findEntry): ditto
+        (Lookup::findEntry): ditto
+        (Lookup::find): ditto
+        * kjs/lookup.h:
+
+2006-01-06  Maciej Stachowiak  <mjs@apple.com>
+
        - fix development build failure from the previous checkin
 
         * kjs/function.cpp:
index f3ceea3..2a0fd5b 100755 (executable)
@@ -25,6 +25,7 @@ open(IN, $file) or die "No such file $file";
 @values = ();
 @attrs = ();
 @params = ();
+@hashes = ();
 
 my $inside = 0;
 my $name;
@@ -63,6 +64,7 @@ while (<IN>) {
       @values = ();
       @attrs = ();
       @params = ();
+      @hashes = ();
       $inside = 0;
     } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
       my $key = $1;
@@ -71,6 +73,7 @@ while (<IN>) {
       my $param = $4;
       push(@keys, $key);
       push(@values, $val);
+      push(@hashes, hashValue($key));
       printf STDERR "WARNING: Number of arguments missing for $key/$val\n"
         if ( $att =~ m/Function/ && length($param) == 0);
       push(@attrs, length($att) > 0 ? $att : "0");
@@ -131,13 +134,56 @@ sub calcTable() {
 #  }
 }
 
+# Paul Hsieh's SuperFastHash
+# http://www.azillionmonkeys.com/qed/hash.html
+# Ported from UString..
 sub hashValue($) {
   @chars = split(/ */, $_[0]);
-  my $val = 0;
-  foreach $c (@chars) {
-    $val += ord($c);
+
+  # This hash is designed to work on 16-bit chunks at a time. But since the normal case
+  # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
+  # were 16-bit chunks, which should give matching results
+
+  my $EXP2_32 = 4294967296;
+
+  my $hash = 0x9e3779b9;
+  my $l    = scalar @chars; #I wish this was in Ruby --- Maks
+  my $rem  = $l & 1;
+  $l = $l >> 1;
+
+  my $s = 0;
+
+  # Main loop
+  for (; $l > 0; $l--) {
+    $hash   += ord($chars[$s]);
+    my $tmp = (ord($chars[$s+1]) << 11) ^ $hash;
+    $hash   = (($hash << 16)% $EXP2_32) ^ $tmp;
+    $s += 2;
+    $hash += $hash >> 11;
   }
-  return $val;
+
+  # Handle end case
+  if ($rem !=0) {
+    $hash += ord($chars[$s]);
+    $hash ^= (($hash << 11)% $EXP2_32);
+    $hash += $hash >> 17;
+  }
+
+  # Force "avalanching" of final 127 bits
+  $hash ^= ($hash << 3);
+  $hash += ($hash >> 5);
+  $hash = ($hash% $EXP2_32);
+  $hash ^= (($hash << 2)% $EXP2_32);
+  $hash += ($hash >> 15);
+  $hash = $hash% $EXP2_32;
+  $hash ^= (($hash << 10)% $EXP2_32);
+  
+  # this avoids ever returning a hash code of 0, since that is used to
+  # signal "hash not computed yet", using a value that is likely to be
+  # effectively the same as 0 when the low bits are masked
+  $hash = 0x80000000  if ($hash == 0);
+
+  return $hash;
 }
 
 sub output() {
@@ -172,6 +218,7 @@ sub output() {
       } else {
        print "0 \}"
       }
+      print "/* " . $hashes[$entry] . " */ ";
     } else {
       print "   \{ 0, 0, 0, 0, 0 \}";
     }
index 260983d..be68f68 100644 (file)
@@ -181,14 +181,15 @@ void FunctionImp::processParameters(ExecState *exec, const List &args)
   if (param) {
     ListIterator it = args.begin();
     Parameter *p = param;
+    JSValue  *v = *it;
     while (p) {
       if (it != args.end()) {
 #ifdef KJS_VERBOSE
        fprintf(stderr, "setting parameter %s ", p->name.ascii());
        printInfo(exec,"to", *it);
 #endif
-       variable->put(exec, p->name, *it);
-       it++;
+       variable->put(exec, p->name, v);
+       v = ++it;
       } else
        variable->put(exec, p->name, jsUndefined());
       p = p->next;
@@ -485,7 +486,7 @@ const ClassInfo ActivationImp::info = {"Activation", 0, 0, 0};
 ActivationImp::ActivationImp(FunctionImp *function, const List &arguments)
     : _function(function), _arguments(true), _argumentsObject(0)
 {
-  _arguments = arguments.copy();
+  _arguments.copyFrom(arguments);
   // FIXME: Do we need to support enumerating the arguments property?
 }
 
index 1eb58b2..2310b37 100644 (file)
@@ -182,9 +182,7 @@ UString StringImp::toString(ExecState *) const
 
 JSObject *StringImp::toObject(ExecState *exec) const
 {
-  List args;
-  args.append(const_cast<StringImp*>(this));
-  return static_cast<JSObject *>(exec->lexicalInterpreter()->builtinString()->construct(exec, args));
+    return new StringInstance(exec->lexicalInterpreter()->builtinStringPrototype(), val);
 }
 
 // ------------------------------ NumberImp ------------------------------------
index 7399944..743d390 100644 (file)
@@ -288,21 +288,24 @@ void List::append(JSValue *v)
 List List::copy() const
 {
     List copy;
+    copy.copyFrom(*this);
+    return copy;
+}
 
-    ListImp *imp = static_cast<ListImp *>(_impBase);
+void List::copyFrom(const List& other)
+{
+    ListImp *imp = static_cast<ListImp *>(other._impBase);
 
     int size = imp->size;
 
     int inlineSize = min(size, inlineValuesSize);
     for (int i = 0; i != inlineSize; ++i)
-        copy.append(imp->values[i]);
+        append(imp->values[i]);
 
     JSValue **overflow = imp->overflow;
     int overflowSize = size - inlineSize;
     for (int i = 0; i != overflowSize; ++i)
-        copy.append(overflow[i]);
-
-    return copy;
+        append(overflow[i]);
 }
 
 
index 08c3a57..bb94a13 100644 (file)
@@ -74,6 +74,11 @@ namespace KJS {
         List copy() const;
 
         /**
+         * Copy all elements from the second list here
+         */
+        void copyFrom(const List& other);
+
+        /**
          * Make a copy of the list, omitting the first element.
          */
         List copyTail() const;
index c0856a4..e60a464 100644 (file)
@@ -33,14 +33,15 @@ using namespace KJS;
 
 static inline bool keysMatch(const UChar *c, unsigned len, const char *s)
 {
-  for (unsigned i = 0; i != len; i++, c++, s++)
+  const char* end = s + len;
+  for (; s != end; c++, s++)
     if (c->uc != (unsigned char)*s)
       return false;
   return *s == 0;
 }
 
-const HashEntry* Lookup::findEntry( const struct HashTable *table,
-                              const UChar *c, unsigned int len )
+static inline const HashEntry* findEntry(const struct HashTable *table, unsigned int hash,
+                                         const UChar *c, unsigned int len )
 {
 #ifndef NDEBUG
   if (table->type != 2) {
@@ -48,9 +49,8 @@ const HashEntry* Lookup::findEntry( const struct HashTable *table,
     return 0;
   }
 #endif
-
-  int h = hash(c, len) % table->hashSize;
-  const HashEntry *e = &table->entries[h];
+  hash %= table->hashSize;
+  const HashEntry *e = &table->entries[hash];
 
   // empty bucket ?
   if (!e->s)
@@ -60,23 +60,24 @@ const HashEntry* Lookup::findEntry( const struct HashTable *table,
     // compare strings
     if (keysMatch(c, len, e->s))
       return e;
+
     // try next bucket
     e = e->next;
   } while (e);
-
   return 0;
 }
 
-const HashEntry* Lookup::findEntry( const struct HashTable *table,
-                                const Identifier &s )
+const HashEntry* Lookup::findEntry(const struct HashTable *table,
+                                   const Identifier &s )
 {
-  return findEntry( table, s.data(), s.size() );
+  const HashEntry* entry = ::findEntry(table, s.ustring().rep()->hash(), s.data(), s.size());
+  return entry;
 }
 
 int Lookup::find(const struct HashTable *table,
                 const UChar *c, unsigned int len)
 {
-  const HashEntry *entry = findEntry( table, c, len );
+  const HashEntry *entry = ::findEntry(table, UString::Rep::computeHash(c, len), c, len);
   if (entry)
     return entry->value;
   return -1;
@@ -84,29 +85,9 @@ int Lookup::find(const struct HashTable *table,
 
 int Lookup::find(const struct HashTable *table, const Identifier &s)
 {
-  return find(table, s.data(), s.size());
-}
-
-unsigned int Lookup::hash(const UChar *c, unsigned int len)
-{
-  unsigned int val = 0;
-  // ignoring higher byte
-  for (unsigned int i = 0; i < len; i++, c++)
-    val += c->low();
-
-  return val;
-}
-
-unsigned int Lookup::hash(const Identifier &key)
-{
-  return hash(key.data(), key.size());
-}
-
-unsigned int Lookup::hash(const char *s)
-{
-  unsigned int val = 0;
-  while (*s)
-    val += *s++;
-
-  return val;
+  //printf("looking for:%s\n", s.ascii());
+  const HashEntry *entry = ::findEntry(table, s.ustring().rep()->hash(), s.data(), s.size());
+  if (entry)
+    return entry->value;
+  return -1;
 }
index bc9e4f5..88fd7bc 100644 (file)
@@ -38,6 +38,7 @@ namespace KJS {
      * s is the key (e.g. a property name)
      */
     const char *s;
+
     /**
      * value is the result value (usually an enum value)
      */
@@ -102,6 +103,7 @@ namespace KJS {
     static int find(const struct HashTable *table,
                    const UChar *c, unsigned int len);
 
+
     /**
      * Find an entry in the table, and return the entry
      * This variant gives access to the other attributes of the entry,
@@ -109,15 +111,7 @@ namespace KJS {
      */
     static const HashEntry* findEntry(const struct HashTable *table,
                                       const Identifier &s);
-    static const HashEntry* findEntry(const struct HashTable *table,
-                                      const UChar *c, unsigned int len);
 
-    /**
-     * Calculate the hash value for a given key
-     */
-    static unsigned int hash(const Identifier &key);
-    static unsigned int hash(const UChar *c, unsigned int len);
-    static unsigned int hash(const char *s);
   };
 
   class ExecState;