Changeset 39056 in webkit for trunk/JavaScriptCore/runtime

Timestamp:

Dec 5, 2008, 5:05:06 PM (16 years ago)

Author:

[email protected]

Message:

<rdar://problem/6331749> Provide a mechanism to disable perfect hashing in the DOM at build time

Reviewed by Darin Adler.

Initial patch by Yosen Lin. Adapted for ToT WebKit by David Kilzer.

Added back the code that generates a "compact" hash (instead of a
perfect hash) as a build-time option using the
ENABLE(PERFECT_HASH_SIZE) macro as defined in Lookup.h.

JavaScriptCore:

• create_hash_table: Rename variables to differentiate perfect hash values from compact hash values. Added back code to compute compact hash tables. Generate both hash table sizes and emit conditionalized code based on ENABLE(PERFECT_HASH_SIZE).
• runtime/Lookup.cpp: (JSC::HashTable::createTable): Added version of createTable() for use with compact hash tables. (JSC::HashTable::deleteTable): Updated to work with compact hash tables.
• runtime/Lookup.h: Defined ENABLE(PERFECT_HASH_SIZE) macro here. (JSC::HashEntry::initialize): Set m_next to zero when using compact hash tables. (JSC::HashEntry::setNext): Added for compact hash tables. (JSC::HashEntry::next): Added for compact hash tables. (JSC::HashTable::entry): Added version of entry() for use with compact hash tables.
• runtime/Structure.cpp: (JSC::Structure::getEnumerablePropertyNames): Updated to work with compact hash tables.

WebCore:

• bindings/scripts/CodeGeneratorJS.pm: (GenerateImplementation): Compute the number of elements that will be stored in each hash table and pass it to GenerateHashTable(). (GenerateHashTable): Added new second parameter representing the number of elements to store in the compact hash table. Added back code to compute compact hash tables. Generate both hash table sizes and emit conditionalized code based on ENABLE(PERFECT_HASH_SIZE).

Location:

trunk/JavaScriptCore/runtime

Files:

• Lookup.cpp (modified) (3 diffs)
• Lookup.h (modified) (6 diffs)
• Structure.cpp (modified) (1 diff)

trunk/JavaScriptCore/runtime/Lookup.cpp

@@ -27 +27 @@
 void HashTable::createTable(JSGlobalData* globalData) const
 {
+#if ENABLE(PERFECT_HASH_SIZE)
     ASSERT(!table);
     HashEntry* entries = new HashEntry[hashSizeMask + 1];
@@ -38 +39 @@
     }
     table = entries;
+#else
+    ASSERT(!table);
+    int linkIndex = compactHashSizeMask + 1;
+    HashEntry* entries = new HashEntry[compactSize];
+    for (int i = 0; i < compactSize; ++i)
+        entries[i].setKey(0);
+    for (int i = 0; values[i].key; ++i) {
+        UString::Rep* identifier = Identifier::add(globalData, values[i].key).releaseRef();
+        int hashIndex = identifier->computedHash() & compactHashSizeMask;
+        HashEntry* entry = &entries[hashIndex];
+
+        if (entry->key()) {
+            while (entry->next()) {
+                entry = entry->next();
+            }
+            ASSERT(linkIndex < compactSize);
+            entry->setNext(&entries[linkIndex++]);
+            entry = entry->next();
+        }
+
+        entry->initialize(identifier, values[i].attributes, values[i].value1, values[i].value2);
+    }
+    table = entries;
+#endif
 }
 
@@ -43 +68 @@
 {
     if (table) {
-        for (int i = 0; i != hashSizeMask + 1; ++i) {
+#if ENABLE(PERFECT_HASH_SIZE)
+        int max = hashSizeMask + 1;
+#else
+        int max = compactSize;
+#endif
+        for (int i = 0; i != max; ++i) {
             if (UString::Rep* key = table[i].key())
                 key->deref();

trunk/JavaScriptCore/runtime/Lookup.h

@@ -31 +31 @@
 #include <wtf/Assertions.h>
 
+// Set ENABLE_PERFECT_HASH_SIZE to 0 to save memory at the
+// cost of speed.  Test your platform as results may vary.
+#define ENABLE_PERFECT_HASH_SIZE 1
+
 namespace JSC {
 
@@ -54 +58 @@
             m_u.store.value1 = v1;
             m_u.store.value2 = v2;
+#if !ENABLE(PERFECT_HASH_SIZE)
+            m_next = 0;
+#endif
         }
 
@@ -68 +75 @@
 
         intptr_t lexerValue() const { ASSERT(!m_attributes); return m_u.lexer.value; }
+
+#if !ENABLE(PERFECT_HASH_SIZE)
+        void setNext(HashEntry *next) { m_next = next; }
+        HashEntry* next() const { return m_next; }
+#endif
 
     private:
@@ -91 +103 @@
             } lexer;
         } m_u;
+
+#if !ENABLE(PERFECT_HASH_SIZE)
+        HashEntry* m_next;
+#endif
     };
 
     struct HashTable {
+#if ENABLE(PERFECT_HASH_SIZE)
         int hashSizeMask; // Precomputed size for the hash table (minus 1).
+#else
+        int compactSize;
+        int compactHashSizeMask;
+#endif
         const HashTableValue* values; // Fixed values generated by script.
         mutable const HashEntry* table; // Table allocated at runtime.
@@ -128 +149 @@
         ALWAYS_INLINE const HashEntry* entry(const Identifier& identifier) const
         {
+#if ENABLE(PERFECT_HASH_SIZE)
             ASSERT(table);
             const HashEntry* entry = &table[identifier.ustring().rep()->computedHash() & hashSizeMask];
@@ -133 +155 @@
                 return 0;
             return entry;
+#else
+            ASSERT(table);
+
+            const HashEntry* entry = &table[identifier.ustring().rep()->computedHash() & compactHashSizeMask];
+
+            if (!entry->key())
+                return 0;
+
+            do {
+                if (entry->key() == identifier.ustring().rep())
+                    return entry;
+                entry = entry->next();
+            } while (entry);
+
+            return 0;
+#endif
         }
 

trunk/JavaScriptCore/runtime/Structure.cpp

@@ -308 +308 @@
         table->initializeIfNeeded(exec);
         ASSERT(table->table);
+#if ENABLE(PERFECT_HASH_SIZE)
         int hashSizeMask = table->hashSizeMask;
+#else
+        int hashSizeMask = table->compactSize - 1;
+#endif
         const HashEntry* entry = table->table;
         for (int i = 0; i <= hashSizeMask; ++i, ++entry) {