Changeset 11920 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Jan 6, 2006, 3:51:00 PM (19 years ago)
Author:
mjs
Message:

Reviewed by Darin.

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:
Location:
trunk/JavaScriptCore
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r11908 r11920  
     12006-01-06  Maciej Stachowiak  <[email protected]>
     2
     3        Reviewed by Darin.
     4
     5        - miscellaneous changes for 4% speedup on the JavaScript iBench
     6        http://bugzilla.opendarwin.org/show_bug.cgi?id=6396
     7       
     8        Changes mostly thanks to Maks Orlovich, tweaked a little by me.
     9
     10        * kjs/create_hash_table: Use the same hash as the one used buy Identifier.
     11        * kjs/function.cpp:
     12        (KJS::FunctionImp::processParameters): Use the new List::copyFrom
     13        (KJS::ActivationImp::ActivationImp): track variable while iterating
     14        * kjs/internal.cpp:
     15        (KJS::StringImp::toObject): create StringInstance directly
     16        * kjs/list.cpp:
     17        (KJS::List::copy): implement in terms of copyFrom
     18        (KJS::List::copyFrom): more efficient way to copy in another list
     19        * kjs/list.h:
     20        * kjs/lookup.cpp:
     21        (keysMatch): updated to work with identifier hash
     22        (findEntry): ditto
     23        (Lookup::findEntry): ditto
     24        (Lookup::find): ditto
     25        * kjs/lookup.h:
     26
    1272006-01-06  Maciej Stachowiak  <[email protected]>
    228

  • trunk/JavaScriptCore/kjs/create_hash_table

    r10818 r11920  
    2626@attrs = ();
    2727@params = ();
     28@hashes = ();
    2829
    2930my $inside = 0;
    … …  
    6465      @attrs = ();
    6566      @params = ();
     67      @hashes = ();
    6668      $inside = 0;
    6769    } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
    … …  
    7274      push(@keys, $key);
    7375      push(@values, $val);
     76      push(@hashes, hashValue($key));
    7477      printf STDERR "WARNING: Number of arguments missing for $key/$val\n"
    7578        if ( $att =~ m/Function/ && length($param) == 0);
    … …  
    132135}
    133136
     137# Paul Hsieh's SuperFastHash
     138# http://www.azillionmonkeys.com/qed/hash.html
     139# Ported from UString..
    134140sub hashValue($) {
    135141  @chars = split(/ */, $_[0]);
    136   my $val = 0;
    137   foreach $c (@chars) {
    138     $val += ord($c);
    139   }
    140   return $val;
     142
     143  # This hash is designed to work on 16-bit chunks at a time. But since the normal case
     144  # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
     145  # were 16-bit chunks, which should give matching results
     146
     147  my $EXP2_32 = 4294967296;
     148
     149  my $hash = 0x9e3779b9;
     150  my $l    = scalar @chars; #I wish this was in Ruby --- Maks
     151  my $rem  = $l & 1;
     152  $l = $l >> 1;
     153
     154  my $s = 0;
     155
     156  # Main loop
     157  for (; $l > 0; $l--) {
     158    $hash   += ord($chars[$s]);
     159    my $tmp = (ord($chars[$s+1]) << 11) ^ $hash;
     160    $hash   = (($hash << 16)% $EXP2_32) ^ $tmp;
     161    $s += 2;
     162    $hash += $hash >> 11;
     163  }
     164
     165  # Handle end case
     166  if ($rem !=0) {
     167    $hash += ord($chars[$s]);
     168    $hash ^= (($hash << 11)% $EXP2_32);
     169    $hash += $hash >> 17;
     170  }
     171
     172  # Force "avalanching" of final 127 bits
     173  $hash ^= ($hash << 3);
     174  $hash += ($hash >> 5);
     175  $hash = ($hash% $EXP2_32);
     176  $hash ^= (($hash << 2)% $EXP2_32);
     177  $hash += ($hash >> 15);
     178  $hash = $hash% $EXP2_32;
     179  $hash ^= (($hash << 10)% $EXP2_32);
     180 
     181  # this avoids ever returning a hash code of 0, since that is used to
     182  # signal "hash not computed yet", using a value that is likely to be
     183  # effectively the same as 0 when the low bits are masked
     184  $hash = 0x80000000  if ($hash == 0);
     185
     186  return $hash;
    141187}
    142188
    … …  
    173219        print "0 \}"
    174220      }
     221      print "/* " . $hashes[$entry] . " */ ";
    175222    } else {
    176223      print "   \{ 0, 0, 0, 0, 0 \}";

  • trunk/JavaScriptCore/kjs/function.cpp

    r11910 r11920  
    182182    ListIterator it = args.begin();
    183183    Parameter *p = param;
     184    JSValue  *v = *it;
    184185    while (p) {
    185186      if (it != args.end()) {
    … …  
    188189        printInfo(exec,"to", *it);
    189190#endif
    190         variable->put(exec, p->name, *it);
    191         it++;
     191        variable->put(exec, p->name, v);
     192        v = ++it;
    192193      } else
    193194        variable->put(exec, p->name, jsUndefined());
    … …  
    486487    : _function(function), _arguments(true), _argumentsObject(0)
    487488{
    488   _arguments = arguments.copy();
     489  _arguments.copyFrom(arguments);
    489490  // FIXME: Do we need to support enumerating the arguments property?
    490491}

  • trunk/JavaScriptCore/kjs/internal.cpp

    r11919 r11920  
    183183JSObject *StringImp::toObject(ExecState *exec) const
    184184{
    185   List args;
    186   args.append(const_cast<StringImp*>(this));
    187   return static_cast<JSObject *>(exec->lexicalInterpreter()->builtinString()->construct(exec, args));
     185    return new StringInstance(exec->lexicalInterpreter()->builtinStringPrototype(), val);
    188186}
    189187

  • trunk/JavaScriptCore/kjs/list.cpp

    r11527 r11920  
    289289{
    290290    List copy;
    291 
    292     ListImp *imp = static_cast<ListImp *>(_impBase);
     291    copy.copyFrom(*this);
     292    return copy;
     293}
     294
     295void List::copyFrom(const List& other)
     296{
     297    ListImp *imp = static_cast<ListImp *>(other._impBase);
    293298
    294299    int size = imp->size;
    … …  
    296301    int inlineSize = min(size, inlineValuesSize);
    297302    for (int i = 0; i != inlineSize; ++i)
    298         copy.append(imp->values[i]);
     303        append(imp->values[i]);
    299304
    300305    JSValue **overflow = imp->overflow;
    301306    int overflowSize = size - inlineSize;
    302307    for (int i = 0; i != overflowSize; ++i)
    303         copy.append(overflow[i]);
    304 
    305     return copy;
     308        append(overflow[i]);
    306309}
    307310

  • trunk/JavaScriptCore/kjs/list.h

    r11527 r11920  
    7373         */
    7474        List copy() const;
     75
     76        /**
     77         * Copy all elements from the second list here
     78         */
     79        void copyFrom(const List& other);
    7580
    7681        /**

  • trunk/JavaScriptCore/kjs/lookup.cpp

    r10701 r11920  
    3434static inline bool keysMatch(const UChar *c, unsigned len, const char *s)
    3535{
    36   for (unsigned i = 0; i != len; i++, c++, s++)
     36  const char* end = s + len;
     37  for (; s != end; c++, s++)
    3738    if (c->uc != (unsigned char)*s)
    3839      return false;
    … …  
    4041}
    4142
    42 const HashEntry* Lookup::findEntry( const struct HashTable *table,
    43                               const UChar *c, unsigned int len )
     43static inline const HashEntry* findEntry(const struct HashTable *table, unsigned int hash,
     44                                         const UChar *c, unsigned int len )
    4445{
    4546#ifndef NDEBUG
    … …  
    4950  }
    5051#endif
    51 
    52   int h = hash(c, len) % table->hashSize;
    53   const HashEntry *e = &table->entries[h];
     52  hash %= table->hashSize;
     53  const HashEntry *e = &table->entries[hash];
    5454
    5555  // empty bucket ?
    … …  
    6161    if (keysMatch(c, len, e->s))
    6262      return e;
     63
    6364    // try next bucket
    6465    e = e->next;
    6566  } while (e);
    66 
    6767  return 0;
    6868}
    6969
    70 const HashEntry* Lookup::findEntry( const struct HashTable *table,
    71                                 const Identifier &s )
     70const HashEntry* Lookup::findEntry(const struct HashTable *table,
     71                                   const Identifier &s )
    7272{
    73   return findEntry( table, s.data(), s.size() );
     73  const HashEntry* entry = ::findEntry(table, s.ustring().rep()->hash(), s.data(), s.size());
     74  return entry;
    7475}
    7576
    … …  
    7778                 const UChar *c, unsigned int len)
    7879{
    79   const HashEntry *entry = findEntry( table, c, len );
     80  const HashEntry *entry = ::findEntry(table, UString::Rep::computeHash(c, len), c, len);
    8081  if (entry)
    8182    return entry->value;
    … …  
    8586int Lookup::find(const struct HashTable *table, const Identifier &s)
    8687{
    87   return find(table, s.data(), s.size());
     88  //printf("looking for:%s\n", s.ascii());
     89  const HashEntry *entry = ::findEntry(table, s.ustring().rep()->hash(), s.data(), s.size());
     90  if (entry)
     91    return entry->value;
     92  return -1;
    8893}
    89 
    90 unsigned int Lookup::hash(const UChar *c, unsigned int len)
    91 {
    92   unsigned int val = 0;
    93   // ignoring higher byte
    94   for (unsigned int i = 0; i < len; i++, c++)
    95     val += c->low();
    96 
    97   return val;
    98 }
    99 
    100 unsigned int Lookup::hash(const Identifier &key)
    101 {
    102   return hash(key.data(), key.size());
    103 }
    104 
    105 unsigned int Lookup::hash(const char *s)
    106 {
    107   unsigned int val = 0;
    108   while (*s)
    109     val += *s++;
    110 
    111   return val;
    112 }

  • trunk/JavaScriptCore/kjs/lookup.h

    r11731 r11920  
    3939     */
    4040    const char *s;
     41
    4142    /**
    4243     * value is the result value (usually an enum value)
    … …  
    103104                    const UChar *c, unsigned int len);
    104105
     106
    105107    /**
    106108     * Find an entry in the table, and return the entry
    … …  
    110112    static const HashEntry* findEntry(const struct HashTable *table,
    111113                                      const Identifier &s);
    112     static const HashEntry* findEntry(const struct HashTable *table,
    113                                       const UChar *c, unsigned int len);
    114 
    115     /**
    116      * Calculate the hash value for a given key
    117      */
    118     static unsigned int hash(const Identifier &key);
    119     static unsigned int hash(const UChar *c, unsigned int len);
    120     static unsigned int hash(const char *s);
     114
    121115  };
    122116
Note: See TracChangeset for help on using the changeset viewer.