Changeset 4188 in webkit for trunk/JavaScriptCore/kjs


Ignore:
Timestamp:
Apr 25, 2003, 2:51:12 PM (22 years ago)
Author:
darin
Message:

Reviewed by Maciej.

  • move from linear probing to double hashing, gives an 0.7% speedup in iBench JavaScript
  • kjs/property_map.h: Remove the hash function.
  • kjs/property_map.cpp: Added statistics for rehashes and removes. Moved from linear probing to double hashing, using the hash modulo (table size minus one) plus one for the probing distance.
  • kjs/ustring.h: Use unsigned instead of int for hash function result.
Location:
trunk/JavaScriptCore/kjs
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kjs/property_map.cpp

    r3373 r4188  
    4242static int numProbes;
    4343static int numCollisions;
     44static int numRehashes;
     45static int numRemoves;
    4446
    4547struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
    … …  
    5254    printf("%d probes\n", numProbes);
    5355    printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
     56    printf("%d rehashes\n", numRehashes);
     57    printf("%d removes\n", numRemoves);
    5458}
    5559
    … …  
    98102        UString::Rep *key = _table->entries[i].key;
    99103        if (key)
    100           key->deref();
     104            key->deref();
    101105    }
    102106    free(_table);
    … …  
    126130}
    127131
    128 inline int PropertyMap::hash(const UString::Rep *s) const
    129 {
    130     return s->hash() & _table->sizeMask;
    131 }
    132 
    133132ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const
    134133{
     134    assert(!name.isNull());
     135   
    135136    UString::Rep *rep = name._ustring.rep;
    136137   
    … …  
    146147    }
    147148   
    148     int i = hash(rep);
     149    unsigned h = rep->hash();
     150    int i = h & _table->sizeMask;
     151    int k = 0;
    149152#if DUMP_STATISTICS
    150153    ++numProbes;
    … …  
    156159            return _table->entries[i].value;
    157160        }
    158         i = (i + 1) & _table->sizeMask;
     161        if (k == 0)
     162            k = 1 | (h % _table->sizeMask);
     163        i = (i + k) & _table->sizeMask;
     164#if DUMP_STATISTICS
     165        ++numRehashes;
     166#endif
    159167    }
    160168    return 0;
    … …  
    163171ValueImp *PropertyMap::get(const Identifier &name) const
    164172{
     173    assert(!name.isNull());
     174   
    165175    UString::Rep *rep = name._ustring.rep;
    166176
    … …  
    174184    }
    175185   
    176     int i = hash(rep);
     186    unsigned h = rep->hash();
     187    int i = h & _table->sizeMask;
     188    int k = 0;
    177189#if DUMP_STATISTICS
    178190    ++numProbes;
    … …  
    182194        if (rep == key)
    183195            return _table->entries[i].value;
    184         i = (i + 1) & _table->sizeMask;
     196        if (k == 0)
     197            k = 1 | (h % _table->sizeMask);
     198        i = (i + k) & _table->sizeMask;
     199#if DUMP_STATISTICS
     200        ++numRehashes;
     201#endif
    185202    }
    186203    return 0;
    … …  
    191208{
    192209    if (attributes == 0)
    193         printf ("None ");
    194     if (attributes & ReadOnly)
    195         printf ("ReadOnly ");
    196     if (attributes & DontEnum)
    197         printf ("DontEnum ");
    198     if (attributes & DontDelete)
    199         printf ("DontDelete ");
    200     if (attributes & Internal)
    201         printf ("Internal ");
    202     if (attributes & Function)
    203         printf ("Function ");
     210        printf("None");
     211    else {
     212        if (attributes & ReadOnly)
     213            printf("ReadOnly ");
     214        if (attributes & DontEnum)
     215            printf("DontEnum ");
     216        if (attributes & DontDelete)
     217            printf("DontDelete ");
     218        if (attributes & Internal)
     219            printf("Internal ");
     220        if (attributes & Function)
     221            printf("Function ");
     222    }
    204223}
    205224#endif
    … …  
    207226void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
    208227{
     228    assert(!name.isNull());
     229    assert(value != 0);
     230   
    209231    checkConsistency();
    210232
    … …  
    212234   
    213235#if DEBUG_PROPERTIES
    214     printf ("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
     236    printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
    215237    printAttributes(attributes);
    216     printf (")\n");
     238    printf(")\n");
    217239#endif
    218240   
    … …  
    239261        expand();
    240262   
    241     int i = hash(rep);
     263    unsigned h = rep->hash();
     264    int i = h & _table->sizeMask;
     265    int k = 0;
    242266#if DUMP_STATISTICS
    243267    ++numProbes;
    … …  
    251275            return;
    252276        }
    253         i = (i + 1) & _table->sizeMask;
     277        // If we find the deleted-element sentinel, insert on top of it.
     278        if (key == &UString::Rep::null) {
     279            key->deref();
     280            break;
     281        }
     282        if (k == 0)
     283            k = 1 | (h % _table->sizeMask);
     284        i = (i + k) & _table->sizeMask;
     285#if DUMP_STATISTICS
     286        ++numRehashes;
     287#endif
    254288    }
    255289   
    … …  
    264298}
    265299
    266 inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
     300void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
    267301{
    268302    assert(_table);
    269303
    270     int i = hash(key);
     304    unsigned h = key->hash();
     305    int i = h & _table->sizeMask;
     306    int k = 0;
    271307#if DUMP_STATISTICS
    272308    ++numProbes;
    273309    numCollisions += _table->entries[i].key && _table->entries[i].key != key;
    274310#endif
    275     while (_table->entries[i].key)
    276         i = (i + 1) & _table->sizeMask;
     311    while (_table->entries[i].key) {
     312        assert(_table->entries[i].key != &UString::Rep::null);
     313        if (k == 0)
     314            k = 1 | (h % _table->sizeMask);
     315        i = (i + k) & _table->sizeMask;
     316#if DUMP_STATISTICS
     317        ++numRehashes;
     318#endif
     319    }
    277320   
    278321    _table->entries[i].key = key;
    … …  
    303346    for (int i = 0; i != oldTableSize; ++i) {
    304347        UString::Rep *key = oldTable->entries[i].key;
    305         if (key)
    306             insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
     348        if (key) {
     349            // Don't copy deleted-element sentinels.
     350            if (key == &UString::Rep::null)
     351                key->deref();
     352            else
     353                insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
     354        }
    307355    }
    308356
    … …  
    314362void PropertyMap::remove(const Identifier &name)
    315363{
     364    assert(!name.isNull());
     365   
    316366    checkConsistency();
    317367
    … …  
    333383
    334384    // Find the thing to remove.
    335     int i = hash(rep);
     385    unsigned h = rep->hash();
     386    int i = h & _table->sizeMask;
     387    int k = 0;
    336388#if DUMP_STATISTICS
    337389    ++numProbes;
     390    ++numRemoves;
    338391    numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
    339392#endif
    … …  
    341394        if (rep == key)
    342395            break;
    343         i = (i + 1) & _table->sizeMask;
     396        if (k == 0)
     397            k = 1 | (h % _table->sizeMask);
     398        i = (i + k) & _table->sizeMask;
     399#if DUMP_STATISTICS
     400        ++numRehashes;
     401#endif
    344402    }
    345403    if (!key)
    346404        return;
    347405   
    348     // Remove the one key.
     406    // Replace this one element with the deleted sentinel,
     407    // &UString::Rep::null; also set value to 0 and attributes to DontEnum
     408    // to help callers that iterate all keys not have to check for the sentinel.
    349409    key->deref();
    350     _table->entries[i].key = 0;
     410    key = &UString::Rep::null;
     411    key->ref();
     412    _table->entries[i].key = key;
     413    _table->entries[i].value = 0;
     414    _table->entries[i].attributes = DontEnum;
    351415    assert(_table->keyCount >= 1);
    352416    --_table->keyCount;
    353417   
    354     // Reinsert all the items to the right in the same cluster.
    355     while (1) {
    356         i = (i + 1) & _table->sizeMask;
    357         key = _table->entries[i].key;
    358         if (!key)
    359             break;
    360         _table->entries[i].key = 0;
    361         insert(key, _table->entries[i].value, _table->entries[i].attributes);
    362     }
    363 
    364418    checkConsistency();
    365419}
    … …  
    379433
    380434    for (int i = 0; i != _table->size; ++i) {
    381         if (_table->entries[i].key) {
     435        UString::Rep *key = _table->entries[i].key;
     436        if (key) {
    382437            ValueImp *v = _table->entries[i].value;
    383             if (!v->marked())
     438            // Check v against 0 to handle deleted elements
     439            // without comparing key to UString::Rep::null.
     440            if (v && !v->marked())
    384441                v->mark();
    385442        }
    … …  
    423480    for (int i = 0; i != _table->size; ++i) {
    424481        UString::Rep *key = _table->entries[i].key;
    425         if (key) {
     482        if (key && key != &UString::Rep::null)
     483        {
    426484            UString k(key);
    427485            bool fitsInUInt32;
    … …  
    500558        if (!rep)
    501559            continue;
    502         int i = hash(rep);
     560        unsigned h = rep->hash();
     561        int i = h & _table->sizeMask;
    503562        while (UString::Rep *key = _table->entries[i].key) {
    504563            if (rep == key)

  • trunk/JavaScriptCore/kjs/property_map.h

    r3373 r4188  
    7878
    7979    private:
    80         int hash(const UString::Rep *) const;
    8180        static bool keysMatch(const UString::Rep *, const UString::Rep *);
    8281        void expand();

  • trunk/JavaScriptCore/kjs/ustring.h

    r3373 r4188  
    214214      int size() const { return len; }
    215215     
    216       int hash() const { if (_hash == 0) _hash = computeHash(dat, len); return _hash; }
     216      unsigned hash() const { if (_hash == 0) _hash = computeHash(dat, len); return _hash; }
    217217      static unsigned computeHash(const UChar *, int length);
    218218      static unsigned computeHash(const char *);
    … …  
    225225      int capacity;
    226226      int rc;
    227       mutable int _hash;
     227      mutable unsigned _hash;
    228228     
    229229      enum { capacityForIdentifier = 0x10000000 };
Note: See TracChangeset for help on using the changeset viewer.