Changeset 39056 in webkit for trunk/JavaScriptCore


Ignore:
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
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r39055 r39056  
     12008-12-05  David Kilzer  <[email protected]>
     2
     3        <rdar://problem/6331749> Provide a mechanism to disable perfect hashing in the DOM at build time
     4
     5        Reviewed by Darin Adler.
     6
     7        Initial patch by Yosen Lin.  Adapted for ToT WebKit by David Kilzer.
     8
     9        Added back the code that generates a "compact" hash (instead of a
     10        perfect hash) as a build-time option using the
     11        ENABLE(PERFECT_HASH_SIZE) macro as defined in Lookup.h.
     12
     13        * create_hash_table: Rename variables to differentiate perfect hash
     14        values from compact hash values.  Added back code to compute compact
     15        hash tables.  Generate both hash table sizes and emit
     16        conditionalized code based on ENABLE(PERFECT_HASH_SIZE).
     17        * runtime/Lookup.cpp:
     18        (JSC::HashTable::createTable): Added version of createTable() for
     19        use with compact hash tables.
     20        (JSC::HashTable::deleteTable): Updated to work with compact hash
     21        tables.
     22        * runtime/Lookup.h: Defined ENABLE(PERFECT_HASH_SIZE) macro here.
     23        (JSC::HashEntry::initialize): Set m_next to zero when using compact
     24        hash tables.
     25        (JSC::HashEntry::setNext): Added for compact hash tables.
     26        (JSC::HashEntry::next): Added for compact hash tables.
     27        (JSC::HashTable::entry): Added version of entry() for use with
     28        compact hash tables.
     29        * runtime/Structure.cpp:
     30        (JSC::Structure::getEnumerablePropertyNames): Updated to work with
     31        compact hash tables.
     32
    1332008-12-05  Gavin Barraclough  <[email protected]>
    234

  • trunk/JavaScriptCore/create_hash_table

    r38155 r39056  
    4747my $inside = 0;
    4848my $name;
    49 my $size;
     49my $pefectHashSize;
     50my $compactSize;
     51my $compactHashSizeMask;
    5052my $banner = 0;
    51 sub calcSize();
     53sub calcPerfectHashSize();
     54sub calcCompactHashSize();
    5255sub output();
    5356sub jsc_ucfirst($);
    … …  
    6669        }
    6770    } elsif (/^\@end\s*$/ && $inside) {
    68         calcSize();
     71        calcPerfectHashSize();
     72        calcCompactHashSize();
    6973        output();
    7074
    … …  
    117121sub ceilingToPowerOf2
    118122{
    119     my ($size) = @_;
     123    my ($pefectHashSize) = @_;
    120124
    121125    my $powerOf2 = 1;
    122     while ($size > $powerOf2) {
     126    while ($pefectHashSize > $powerOf2) {
    123127        $powerOf2 <<= 1;
    124128    }
    … …  
    127131}
    128132
    129 sub calcSize()
     133sub calcPerfectHashSize()
    130134{
    131135tableSizeLoop:
    132     for ($size = ceilingToPowerOf2(scalar @keys); ; $size += $size) {
     136    for ($pefectHashSize = ceilingToPowerOf2(scalar @keys); ; $pefectHashSize += $pefectHashSize) {
    133137        my @table = ();
    134138        foreach my $key (@keys) {
    135             my $h = hashValue($key) % $size;
     139            my $h = hashValue($key) % $pefectHashSize;
    136140            next tableSizeLoop if $table[$h];
    137141            $table[$h] = 1;
    … …  
    144148    my ($value, $distance) = @_;
    145149    return (($value << $distance) & 0xFFFFFFFF);
     150}
     151
     152sub calcCompactHashSize()
     153{
     154    my @table = ();
     155    my @links = ();
     156    my $compactHashSize = ceilingToPowerOf2(2 * @keys);
     157    $compactHashSizeMask = $compactHashSize - 1;
     158    $compactSize = $compactHashSize;
     159    my $collisions = 0;
     160    my $maxdepth = 0;
     161    my $i = 0;
     162    foreach my $key (@keys) {
     163        my $depth = 0;
     164        my $h = hashValue($key) % $compactHashSize;
     165        while (defined($table[$h])) {
     166            if (defined($links[$h])) {
     167                $h = $links[$h];
     168                $depth++;
     169            } else {
     170                $collisions++;
     171                $links[$h] = $compactSize;
     172                $h = $compactSize;
     173                $compactSize++;
     174            }
     175        }
     176        $table[$h] = $i;
     177        $i++;
     178        $maxdepth = $depth if ( $depth > $maxdepth);
     179    }
    146180}
    147181
    … …  
    237271    print "   { 0, 0, 0, 0 }\n";
    238272    print "};\n\n";
    239     print "extern const struct HashTable $name = ";
    240     print "\{ ", $size - 1, ", $nameEntries, 0 \};\n\n";
     273    print "extern const struct HashTable $name =\n";
     274    print "#if ENABLE(PERFECT_HASH_SIZE)\n";
     275    print "    \{ ", $pefectHashSize - 1, ", $nameEntries, 0 \};\n";
     276    print "#else\n";
     277    print "    \{ $compactSize, $compactHashSizeMask, $nameEntries, 0 \};\n";
     278    print "#endif\n\n";
    241279    print "} // namespace\n";
    242280}

  • trunk/JavaScriptCore/runtime/Lookup.cpp

    r38137 r39056  
    2727void HashTable::createTable(JSGlobalData* globalData) const
    2828{
     29#if ENABLE(PERFECT_HASH_SIZE)
    2930    ASSERT(!table);
    3031    HashEntry* entries = new HashEntry[hashSizeMask + 1];
    … …  
    3839    }
    3940    table = entries;
     41#else
     42    ASSERT(!table);
     43    int linkIndex = compactHashSizeMask + 1;
     44    HashEntry* entries = new HashEntry[compactSize];
     45    for (int i = 0; i < compactSize; ++i)
     46        entries[i].setKey(0);
     47    for (int i = 0; values[i].key; ++i) {
     48        UString::Rep* identifier = Identifier::add(globalData, values[i].key).releaseRef();
     49        int hashIndex = identifier->computedHash() & compactHashSizeMask;
     50        HashEntry* entry = &entries[hashIndex];
     51
     52        if (entry->key()) {
     53            while (entry->next()) {
     54                entry = entry->next();
     55            }
     56            ASSERT(linkIndex < compactSize);
     57            entry->setNext(&entries[linkIndex++]);
     58            entry = entry->next();
     59        }
     60
     61        entry->initialize(identifier, values[i].attributes, values[i].value1, values[i].value2);
     62    }
     63    table = entries;
     64#endif
    4065}
    4166
    … …  
    4368{
    4469    if (table) {
    45         for (int i = 0; i != hashSizeMask + 1; ++i) {
     70#if ENABLE(PERFECT_HASH_SIZE)
     71        int max = hashSizeMask + 1;
     72#else
     73        int max = compactSize;
     74#endif
     75        for (int i = 0; i != max; ++i) {
    4676            if (UString::Rep* key = table[i].key())
    4777                key->deref();

  • trunk/JavaScriptCore/runtime/Lookup.h

    r38528 r39056  
    3131#include <wtf/Assertions.h>
    3232
     33// Set ENABLE_PERFECT_HASH_SIZE to 0 to save memory at the
     34// cost of speed.  Test your platform as results may vary.
     35#define ENABLE_PERFECT_HASH_SIZE 1
     36
    3337namespace JSC {
    3438
    … …  
    5458            m_u.store.value1 = v1;
    5559            m_u.store.value2 = v2;
     60#if !ENABLE(PERFECT_HASH_SIZE)
     61            m_next = 0;
     62#endif
    5663        }
    5764
    … …  
    6875
    6976        intptr_t lexerValue() const { ASSERT(!m_attributes); return m_u.lexer.value; }
     77
     78#if !ENABLE(PERFECT_HASH_SIZE)
     79        void setNext(HashEntry *next) { m_next = next; }
     80        HashEntry* next() const { return m_next; }
     81#endif
    7082
    7183    private:
    … …  
    91103            } lexer;
    92104        } m_u;
     105
     106#if !ENABLE(PERFECT_HASH_SIZE)
     107        HashEntry* m_next;
     108#endif
    93109    };
    94110
    95111    struct HashTable {
     112#if ENABLE(PERFECT_HASH_SIZE)
    96113        int hashSizeMask; // Precomputed size for the hash table (minus 1).
     114#else
     115        int compactSize;
     116        int compactHashSizeMask;
     117#endif
    97118        const HashTableValue* values; // Fixed values generated by script.
    98119        mutable const HashEntry* table; // Table allocated at runtime.
    … …  
    128149        ALWAYS_INLINE const HashEntry* entry(const Identifier& identifier) const
    129150        {
     151#if ENABLE(PERFECT_HASH_SIZE)
    130152            ASSERT(table);
    131153            const HashEntry* entry = &table[identifier.ustring().rep()->computedHash() & hashSizeMask];
    … …  
    133155                return 0;
    134156            return entry;
     157#else
     158            ASSERT(table);
     159
     160            const HashEntry* entry = &table[identifier.ustring().rep()->computedHash() & compactHashSizeMask];
     161
     162            if (!entry->key())
     163                return 0;
     164
     165            do {
     166                if (entry->key() == identifier.ustring().rep())
     167                    return entry;
     168                entry = entry->next();
     169            } while (entry);
     170
     171            return 0;
     172#endif
    135173        }
    136174

  • trunk/JavaScriptCore/runtime/Structure.cpp

    r38440 r39056  
    308308        table->initializeIfNeeded(exec);
    309309        ASSERT(table->table);
     310#if ENABLE(PERFECT_HASH_SIZE)
    310311        int hashSizeMask = table->hashSizeMask;
     312#else
     313        int hashSizeMask = table->compactSize - 1;
     314#endif
    311315        const HashEntry* entry = table->table;
    312316        for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
Note: See TracChangeset for help on using the changeset viewer.