[webkit-changes] cvs commit: JavaScriptCore/kjs create_hash_table
function.cpp internal.cpp list.cpp list.h lookup.cpp lookup.h
Maciej
mjs at opensource.apple.com
Fri Jan 6 15:51:02 PST 2006
mjs 06/01/06 15:51:01
Modified: . ChangeLog
kjs create_hash_table function.cpp internal.cpp
list.cpp list.h lookup.cpp lookup.h
Log:
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:
Revision Changes Path
1.949 +26 -0 JavaScriptCore/ChangeLog
Index: ChangeLog
===================================================================
RCS file: /cvs/root/JavaScriptCore/ChangeLog,v
retrieving revision 1.948
retrieving revision 1.949
diff -u -r1.948 -r1.949
--- ChangeLog 6 Jan 2006 10:44:45 -0000 1.948
+++ ChangeLog 6 Jan 2006 23:50:57 -0000 1.949
@@ -1,5 +1,31 @@
2006-01-06 Maciej Stachowiak <mjs at 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 at apple.com>
+
- fix development build failure from the previous checkin
* kjs/function.cpp:
1.7 +52 -5 JavaScriptCore/kjs/create_hash_table
Index: create_hash_table
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/create_hash_table,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- create_hash_table 11 Oct 2005 20:43:49 -0000 1.6
+++ create_hash_table 6 Jan 2006 23:50:59 -0000 1.7
@@ -25,6 +25,7 @@
@values = ();
@attrs = ();
@params = ();
+ at hashes = ();
my $inside = 0;
my $name;
@@ -63,6 +64,7 @@
@values = ();
@attrs = ();
@params = ();
+ @hashes = ();
$inside = 0;
} elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
my $key = $1;
@@ -71,6 +73,7 @@
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 @@
# }
}
+# 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);
- }
- return $val;
+
+ # 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;
+ }
+
+ # 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 @@
} else {
print "0 \}"
}
+ print "/* " . $hashes[$entry] . " */ ";
} else {
print " \{ 0, 0, 0, 0, 0 \}";
}
1.68 +4 -3 JavaScriptCore/kjs/function.cpp
Index: function.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/function.cpp,v
retrieving revision 1.67
retrieving revision 1.68
diff -u -r1.67 -r1.68
--- function.cpp 6 Jan 2006 11:03:11 -0000 1.67
+++ function.cpp 6 Jan 2006 23:50:59 -0000 1.68
@@ -181,14 +181,15 @@
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 @@
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?
}
1.88 +1 -3 JavaScriptCore/kjs/internal.cpp
Index: internal.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/internal.cpp,v
retrieving revision 1.87
retrieving revision 1.88
diff -u -r1.87 -r1.88
--- internal.cpp 6 Jan 2006 22:49:05 -0000 1.87
+++ internal.cpp 6 Jan 2006 23:51:00 -0000 1.88
@@ -182,9 +182,7 @@
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 ------------------------------------
1.19 +8 -5 JavaScriptCore/kjs/list.cpp
Index: list.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/list.cpp,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -r1.18 -r1.19
--- list.cpp 11 Dec 2005 02:05:44 -0000 1.18
+++ list.cpp 6 Jan 2006 23:51:00 -0000 1.19
@@ -288,21 +288,24 @@
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]);
}
1.12 +5 -0 JavaScriptCore/kjs/list.h
Index: list.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/list.h,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- list.h 11 Dec 2005 02:05:44 -0000 1.11
+++ list.h 6 Jan 2006 23:51:00 -0000 1.12
@@ -74,6 +74,11 @@
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;
1.13 +17 -36 JavaScriptCore/kjs/lookup.cpp
Index: lookup.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/lookup.cpp,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -r1.12 -r1.13
--- lookup.cpp 3 Oct 2005 21:11:49 -0000 1.12
+++ lookup.cpp 6 Jan 2006 23:51:00 -0000 1.13
@@ -33,14 +33,15 @@
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 @@
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 @@
// 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, 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;
}
1.23 +2 -8 JavaScriptCore/kjs/lookup.h
Index: lookup.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/lookup.h,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -r1.22 -r1.23
--- lookup.h 22 Dec 2005 21:07:37 -0000 1.22
+++ lookup.h 6 Jan 2006 23:51:00 -0000 1.23
@@ -38,6 +38,7 @@
* 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 @@
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 @@
*/
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;
More information about the webkit-changes
mailing list