Changeset 2776 in webkit for trunk/JavaScriptCore/kjs


Ignore:
Timestamp:
Nov 20, 2002, 12:15:18 AM (23 years ago)
Author:
darin
Message:
  • atomic identifiers; gives another 6.5% in the iBench suite
  • kjs/identifier.h: Did the real thing.
  • kjs/identifier.cpp: Ditto.
  • kjs/property_map.h: _tableSizeHashMask -> _tableSizeMask
  • kjs/property_map.cpp: The above, plus take advantage of comparing by pointer instead of by comparing bytes.
Location:
trunk/JavaScriptCore/kjs
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kjs/identifier.cpp

    r2772 r2776  
    3838extern const Identifier valueOfPropertyName("valueOf");
    3939
    40 bool operator==(const Identifier &a, const char *b)
    41 {
    42     return a._ustring == b;
     40const int _minTableSize = 64;
     41
     42UString::Rep **Identifier::_table;
     43int Identifier::_tableSize;
     44int Identifier::_tableSizeMask;
     45int Identifier::_keyCount;
     46
     47bool Identifier::equal(UString::Rep *r, const char *s)
     48{
     49    int length = r->len;
     50    const UChar *d = r->dat;
     51    for (int i = 0; i != length; ++i)
     52        if (d[i].unicode() != (unsigned char)s[i])
     53            return false;
     54    return s[length] == 0;
     55}
     56
     57bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
     58{
     59    if (r->len != length)
     60        return false;
     61    const UChar *d = r->dat;
     62    for (int i = 0; i != length; ++i)
     63        if (d[i].unicode() != s[i].unicode())
     64            return false;
     65    return true;
     66}
     67
     68bool Identifier::equal(UString::Rep *r, UString::Rep *b)
     69{
     70    int length = r->len;
     71    if (length != b->len)
     72        return false;
     73    const UChar *d = r->dat;
     74    const UChar *s = b->dat;
     75    for (int i = 0; i != length; ++i)
     76        if (d[i].unicode() != s[i].unicode())
     77            return false;
     78    return true;
    4379}
    4480
    4581UString::Rep *Identifier::add(const char *c)
    4682{
    47   if (!c)
    48     return &UString::Rep::null;
    49   int length = strlen(c);
    50   if (length == 0)
    51     return &UString::Rep::empty;
    52 
    53   // Here's where we compute a hash and find it or put it in the hash table.
    54   UChar *d = new UChar[length];
    55   for (int i = 0; i < length; i++)
    56     d[i] = c[i];
    57 
    58   UString::Rep *r = new UString::Rep;
    59   r->dat = d;
    60   r->len = length;
    61   r->capacity = length;
    62   r->rc = 0;
    63   r->_hash = 0;
    64   return r;
     83    if (!c)
     84        return &UString::Rep::null;
     85    int length = strlen(c);
     86    if (length == 0)
     87        return &UString::Rep::empty;
     88   
     89    if (!_table)
     90        expand();
     91   
     92    unsigned hash = UString::Rep::computeHash(c);
     93   
     94    int i = hash & _tableSizeMask;
     95    while (UString::Rep *key = _table[i]) {
     96        if (equal(key, c))
     97            return key;
     98        i = (i + 1) & _tableSizeMask;
     99    }
     100   
     101    UChar *d = new UChar[length];
     102    for (int j = 0; j != length; j++)
     103        d[j] = c[j];
     104   
     105    UString::Rep *r = new UString::Rep;
     106    r->dat = d;
     107    r->len = length;
     108    r->capacity = UString::Rep::capacityForIdentifier;
     109    r->rc = 0;
     110    r->_hash = hash;
     111   
     112    _table[i] = r;
     113    ++_keyCount;
     114   
     115    if (_keyCount * 2 >= _tableSize)
     116        expand();
     117   
     118    return r;
    65119}
    66120
    67121UString::Rep *Identifier::add(const UChar *s, int length)
    68122{
    69   // Here's where we compute a hash and find it or put it in the hash table.
    70 
    71   UChar *d = new UChar[length];
    72   for (int i = 0; i < length; i++)
    73     d[i] = s[i];
    74 
    75   UString::Rep *r = new UString::Rep;
    76   r->dat = d;
    77   r->len = length;
    78   r->capacity = length;
    79   r->rc = 0;
    80   r->_hash = 0;
    81   return r;
    82 }
    83 
    84 UString::Rep *Identifier::add(const UString &s)
    85 {
    86   // Here's where we compute a hash and find it or put it in the hash table.
    87   // Don't forget to check for the case of a string that's already in the table by looking at capacity.
    88  
    89   return s.rep;
    90 }
    91 
    92 void Identifier::remove(UString::Rep *)
    93 {
    94   // Here's where we find the string already in the hash table, and remove it.
     123    if (length == 0)
     124        return &UString::Rep::empty;
     125   
     126    if (!_table)
     127        expand();
     128   
     129    unsigned hash = UString::Rep::computeHash(s, length);
     130   
     131    int i = hash & _tableSizeMask;
     132    while (UString::Rep *key = _table[i]) {
     133        if (equal(key, s, length))
     134            return key;
     135        i = (i + 1) & _tableSizeMask;
     136    }
     137   
     138    UChar *d = new UChar[length];
     139    for (int j = 0; j != length; j++)
     140        d[j] = s[j];
     141   
     142    UString::Rep *r = new UString::Rep;
     143    r->dat = d;
     144    r->len = length;
     145    r->capacity = UString::Rep::capacityForIdentifier;
     146    r->rc = 0;
     147    r->_hash = hash;
     148   
     149    _table[i] = r;
     150    ++_keyCount;
     151   
     152    if (_keyCount * 2 >= _tableSize)
     153        expand();
     154   
     155    return r;
     156}
     157
     158UString::Rep *Identifier::add(UString::Rep *r)
     159{
     160    if (r->capacity == UString::Rep::capacityForIdentifier)
     161        return r;
     162    if (r->len == 0)
     163        return &UString::Rep::empty;
     164   
     165    if (!_table)
     166        expand();
     167   
     168    unsigned hash = r->hash();
     169   
     170    int i = hash & _tableSizeMask;
     171    while (UString::Rep *key = _table[i]) {
     172        if (equal(key, r))
     173            return key;
     174        i = (i + 1) & _tableSizeMask;
     175    }
     176   
     177    r->capacity = UString::Rep::capacityForIdentifier;
     178   
     179    _table[i] = r;
     180    ++_keyCount;
     181   
     182    if (_keyCount * 2 >= _tableSize)
     183        expand();
     184   
     185    return r;
     186}
     187
     188inline void Identifier::insert(UString::Rep *key)
     189{
     190    unsigned hash = key->hash();
     191   
     192    int i = hash & _tableSizeMask;
     193    while (_table[i])
     194        i = (i + 1) & _tableSizeMask;
     195   
     196    _table[i] = key;
     197}
     198
     199void Identifier::remove(UString::Rep *r)
     200{
     201    unsigned hash = r->hash();
     202   
     203    UString::Rep *key;
     204   
     205    int i = hash & _tableSizeMask;
     206    while ((key = _table[i])) {
     207        if (equal(key, r))
     208            break;
     209        i = (i + 1) & _tableSizeMask;
     210    }
     211    if (!key)
     212        return;
     213   
     214    _table[i] = 0;
     215    --_keyCount;
     216   
     217    if (_keyCount * 3 < _tableSize && _tableSize > _minTableSize) {
     218        shrink();
     219        return;
     220    }
     221   
     222    // Reinsert all the items to the right in the same cluster.
     223    while (1) {
     224        i = (i + 1) & _tableSizeMask;
     225        key = _table[i];
     226        if (!key)
     227            break;
     228        _table[i] = 0;
     229        insert(key);
     230    }
     231}
     232
     233void Identifier::expand()
     234{
     235    rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
     236}
     237
     238void Identifier::shrink()
     239{
     240    rehash(_tableSize / 2);
     241}
     242
     243void Identifier::rehash(int newTableSize)
     244{
     245    int oldTableSize = _tableSize;
     246    UString::Rep **oldTable = _table;
     247
     248    _tableSize = newTableSize;
     249    _tableSizeMask = newTableSize - 1;
     250    _table = (UString::Rep **)calloc(newTableSize, sizeof(UString::Rep *));
     251
     252    for (int i = 0; i != oldTableSize; ++i)
     253        if (UString::Rep *key = oldTable[i])
     254            insert(key);
     255
     256    free(oldTable);
    95257}
    96258

  • trunk/JavaScriptCore/kjs/identifier.h

    r2772 r2776  
    3333        Identifier(const char *s) : _ustring(add(s)) { }
    3434        Identifier(const UChar *s, int length) : _ustring(add(s, length)) { }
    35         explicit Identifier(const UString &s) : _ustring(add(s)) { }
     35        explicit Identifier(const UString &s) : _ustring(add(s.rep)) { }
    3636       
    3737        const UString &ustring() const { return _ustring; }
    … …  
    6262
    6363    private:
     64        UString _ustring;
     65       
     66        static bool equal(UString::Rep *, const char *);
     67        static bool equal(UString::Rep *, const UChar *, int length);
     68        static bool equal(UString::Rep *, UString::Rep *);
     69
     70        static bool equal(const Identifier &a, const Identifier &b)
     71            { return a._ustring.rep == b._ustring.rep; }
     72        static bool equal(const Identifier &a, const char *b)
     73            { return equal(a._ustring.rep, b); }
     74       
    6475        static UString::Rep *add(const char *);
    6576        static UString::Rep *add(const UChar *, int length);
    66         static UString::Rep *add(const UString &);
     77        static UString::Rep *add(UString::Rep *);
    6778       
    68         UString _ustring;
     79        static void insert(UString::Rep *);
     80       
     81        static void rehash(int newTableSize);
     82        static void expand();
     83        static void shrink();
     84
     85        static UString::Rep **_table;
     86        static int _tableSize;
     87        static int _tableSizeMask;
     88        static int _keyCount;
    6989    };
    7090   
    7191    inline bool operator==(const Identifier &a, const Identifier &b)
    72     {
    73         return a._ustring == b._ustring;
    74     }
     92        { return Identifier::equal(a, b); }
    7593
    7694    inline bool operator!=(const Identifier &a, const Identifier &b)
    77     {
    78         return a._ustring != b._ustring;
    79     }
     95        { return !Identifier::equal(a, b); }
     96
     97    inline bool operator==(const Identifier &a, const char *b)
     98        { return Identifier::equal(a, b); }
    8099
    81100    extern const Identifier argumentsPropertyName;

  • trunk/JavaScriptCore/kjs/property_map.cpp

    r2769 r2776  
    3636PropertyMap::~PropertyMap()
    3737{
    38     //printf("key count is %d\n", _keyCount);
    3938    UString::Rep *key = _singleEntry.key;
    4039    if (key)
    … …  
    6766inline int PropertyMap::hash(const UString::Rep *s) const
    6867{
    69     return s->hash() & _tableSizeHashMask;
    70 }
    71 
    72 bool PropertyMap::keysMatch(const UString::Rep *a, const UString::Rep *b)
    73 {
    74     if (a == b)
    75         return true;
    76    
    77     int len = a->len;
    78     if (len != b->len)
    79         return false;
    80    
    81     for (int i = 0; i != len; ++i)
    82         if (a->dat[i].unicode() != b->dat[i].unicode())
    83             return false;
    84    
    85     return true;
     68    return s->hash() & _tableSizeMask;
    8669}
    8770
    … …  
    9073    if (!_table) {
    9174        UString::Rep *key = _singleEntry.key;
    92         if (key && keysMatch(name._ustring.rep, key)) {
     75        if (name._ustring.rep == key) {
    9376            attributes = _singleEntry.attributes;
    9477            return _singleEntry.value;
    … …  
    9982    int i = hash(name._ustring.rep);
    10083    while (UString::Rep *key = _table[i].key) {
    101         if (keysMatch(name._ustring.rep, key)) {
     84        if (name._ustring.rep == key) {
    10285            attributes = _table[i].attributes;
    10386            return _table[i].value;
    10487        }
    105         i = (i + 1) & _tableSizeHashMask;
     88        i = (i + 1) & _tableSizeMask;
    10689    }
    10790    return 0;
    … …  
    11295    if (!_table) {
    11396        UString::Rep *key = _singleEntry.key;
    114         if (key && keysMatch(name._ustring.rep, key))
     97        if (name._ustring.rep == key)
    11598            return _singleEntry.value;
    11699        return 0;
    … …  
    119102    int i = hash(name._ustring.rep);
    120103    while (UString::Rep *key = _table[i].key) {
    121         if (keysMatch(name._ustring.rep, key))
     104        if (name._ustring.rep == key)
    122105            return _table[i].value;
    123         i = (i + 1) & _tableSizeHashMask;
     106        i = (i + 1) & _tableSizeMask;
    124107    }
    125108    return 0;
    … …  
    131114        UString::Rep *key = _singleEntry.key;
    132115        if (key) {
    133             if (keysMatch(name._ustring.rep, key)) {
     116            if (name._ustring.rep == key) {
    134117                _singleEntry.value = value;
    135118                return;
    … …  
    150133    int i = hash(name._ustring.rep);
    151134    while (UString::Rep *key = _table[i].key) {
    152         if (keysMatch(name._ustring.rep, key)) {
     135        if (name._ustring.rep == key) {
    153136            // Put a new value in an existing hash table entry.
    154137            _table[i].value = value;
    … …  
    156139            return;
    157140        }
    158         i = (i + 1) & _tableSizeHashMask;
     141        i = (i + 1) & _tableSizeMask;
    159142    }
    160143   
    … …  
    171154    int i = hash(key);
    172155    while (_table[i].key)
    173         i = (i + 1) & _tableSizeHashMask;
     156        i = (i + 1) & _tableSizeMask;
    174157   
    175158    _table[i].key = key;
    … …  
    184167
    185168    _tableSize = oldTableSize ? oldTableSize * 2 : 16;
    186     _tableSizeHashMask = _tableSize - 1;
     169    _tableSizeMask = _tableSize - 1;
    187170    _table = (Entry *)calloc(_tableSize, sizeof(Entry));
    188171
    … …  
    208191    if (!_table) {
    209192        key = _singleEntry.key;
    210         if (key && keysMatch(name._ustring.rep, key)) {
     193        if (name._ustring.rep == key) {
    211194            key->deref();
    212195            _singleEntry.key = 0;
    … …  
    219202    int i = hash(name._ustring.rep);
    220203    while ((key = _table[i].key)) {
    221         if (keysMatch(name._ustring.rep, key))
     204        if (name._ustring.rep == key)
    222205            break;
    223         i = (i + 1) & _tableSizeHashMask;
     206        i = (i + 1) & _tableSizeMask;
    224207    }
    225208    if (!key)
    … …  
    233216    // Reinsert all the items to the right in the same cluster.
    234217    while (1) {
    235         i = (i + 1) & _tableSizeHashMask;
     218        i = (i + 1) & _tableSizeMask;
    236219        key = _table[i].key;
    237220        if (!key)

  • trunk/JavaScriptCore/kjs/property_map.h

    r2760 r2776  
    6464        typedef PropertyMapHashTableEntry Entry;
    6565       
    66         int _tableSizeHashMask;
     66        int _tableSizeMask;
    6767        int _tableSize;
    6868        Entry *_table;
Note: See TracChangeset for help on using the changeset viewer.