Ignore:
Timestamp:
Oct 21, 2007, 8:12:08 AM (18 years ago)
Author:
darin
Message:

Reviewed by Maciej.


Speeds up SunSpider by 10%.

  • kjs/array_object.cpp: (allocateStorage): Leave room for an additional pointer. (reallocateStorage): Ditto. (freeStorage): Ditto. (ArrayInstance::~ArrayInstance): Delete the overflow map if present. (ArrayInstance::getItem): Read values from the overflow map if present. Removed the check of length, since it slows down the common case. (ArrayInstance::getOwnPropertySlot): Ditto. Also removed the fallback to the property map. (ArrayInstance::put): Write values into the overflow map as needed. Also create overflow map when needed. (ArrayInstance::deleteProperty): Remove values from the overflow map as appropriate. (ArrayInstance::getPropertyNames): Add a name for each identifier in the property map. This is extremely inefficient. (ArrayInstance::setLength): Remove any values in the overflow map that are past the new length, as we formerly did with the property map. (ArrayInstance::mark): Mark any values in the overflow map. (compareByStringForQSort): Removed unneeded undefined case, since compactForSorting guarantees we will have no undefined values. (compareWithCompareFunctionForQSort): Ditto. (ArrayInstance::compactForSorting): Copy all the values out of the overflow map and destroy it.
  • kjs/property_map.h: Removed now-unused getSparseArrayPropertyNames.
  • kjs/property_map.cpp: Ditto.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kjs/array_object.cpp

    r26688 r26847  
    3636
    3737
    38 using namespace KJS;
     38namespace KJS {
     39
     40typedef HashMap<unsigned, JSValue*> OverflowMap;
     41
     42static inline OverflowMap* overflowMap(JSValue** storage)
     43{
     44    return storage ? reinterpret_cast<OverflowMap*>(storage[-2]) : 0;
     45}
    3946
    4047// ------------------------------ ArrayInstance -----------------------------
    … …  
    4956      return 0;
    5057
    51   // store capacity in extra space before the beginning of the storage array to save space
    52   JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 1, sizeof(JSValue *))) + 1;
     58  // store capacity and overflow map in extra space before the beginning of the storage array to save space
     59  JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 2, sizeof(JSValue *))) + 2;
    5360  storage[-1] = reinterpret_cast<JSValue*>(capacity);
    5461  return storage;
    … …  
    5865{
    5966  if (!storage) {
    60     storage =  allocateStorage(newCapacity);
     67    storage = allocateStorage(newCapacity);
    6168    return;
    6269  }
    6370
    64   // store capacity in extra space before the beginning of the storage array to save space
    65   storage = static_cast<JSValue**>(fastRealloc(storage - 1, (newCapacity + 1) * sizeof (JSValue*))) + 1;
     71  // store capacity and overflow map in extra space before the beginning of the storage array to save space
     72  storage = static_cast<JSValue**>(fastRealloc(storage - 2, (newCapacity + 2) * sizeof (JSValue*))) + 2;
    6673  storage[-1] = reinterpret_cast<JSValue*>(newCapacity);
    6774}
    … …  
    6976static inline void freeStorage(JSValue** storage)
    7077{
    71   if (storage)
    72     fastFree(storage - 1);
     78  fastFree(storage - 2);
    7379}
    7480
    … …  
    9096  ListIterator it = list.begin();
    9197  unsigned l = length;
    92   for (unsigned i = 0; i < l; ++i) {
     98  for (unsigned i = 0; i < l; ++i)
    9399    storage[i] = it++;
    94   }
    95   // When the array is created non-empty its cells are filled so it's really no worse than
     100  // When the array is created non-empty, its cells are filled so it's really no worse than
    96101  // a property map. Therefore don't report extra memory cost.
    97102}
    … …  
    99104ArrayInstance::~ArrayInstance()
    100105{
    101   freeStorage(storage);
     106  if (storage) {
     107    delete reinterpret_cast<OverflowMap*>(storage[-2]);
     108    freeStorage(storage);
     109  }
    102110}
    103111
    104112JSValue* ArrayInstance::getItem(unsigned i) const
    105113{
    106     if (i >= length)
     114    if (i < storageLength) {
     115        JSValue* value = storage[i];
     116        return value ? value : jsUndefined();
     117    }
     118
     119    const OverflowMap* overflow = overflowMap(storage);
     120    if (!overflow)
    107121        return jsUndefined();
    108    
    109     JSValue* val = (i < storageLength) ?
    110                             storage[i] :
    111                             getDirect(Identifier::from(i));
    112 
    113     return val ? val : jsUndefined();
     122
     123    JSValue* value = overflow->get(i);
     124    return value ? value : jsUndefined();
    114125}
    115126
    … …  
    128139  bool ok;
    129140  unsigned index = propertyName.toArrayIndex(&ok);
    130   if (ok) {
    131     if (index >= length)
    132       return false;
    133     if (index < storageLength) {
    134       JSValue *v = storage[index];
    135       if (!v)
    136         return false;     
    137       slot.setValueSlot(this, &storage[index]);
    138       return true;
    139     }
    140   }
    141 
    142   return JSObject::getOwnPropertySlot(exec, propertyName, slot);
     141  if (!ok)
     142    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
     143
     144  if (index < storageLength) {
     145    JSValue *v = storage[index];
     146    if (!v)
     147      return false;     
     148    slot.setValueSlot(this, &storage[index]);
     149    return true;
     150  }
     151  if (index > MAX_ARRAY_INDEX)
     152    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
     153  OverflowMap* overflow = overflowMap(storage);
     154  if (!overflow)
     155    return false;
     156  OverflowMap::iterator it = overflow->find(index);
     157  if (it == overflow->end())
     158    return false;
     159  slot.setValueSlot(this, &it->second);
     160  return true;
    143161}
    144162
    145163bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
    146164{
    147   if (index > MAX_ARRAY_INDEX)
    148     return getOwnPropertySlot(exec, Identifier::from(index), slot);
    149 
    150   if (index >= length)
    151     return false;
    152165  if (index < storageLength) {
    153166    JSValue *v = storage[index];
    … …  
    157170    return true;
    158171  }
    159 
    160   return JSObject::getOwnPropertySlot(exec, index, slot);
     172  if (index > MAX_ARRAY_INDEX)
     173    return getOwnPropertySlot(exec, Identifier::from(index), slot);
     174  OverflowMap* overflow = overflowMap(storage);
     175  if (!overflow)
     176    return false;
     177  OverflowMap::iterator it = overflow->find(index);
     178  if (it == overflow->end())
     179    return false;
     180  slot.setValueSlot(this, &it->second);
     181  return true;
    161182}
    162183
    … …  
    173194    return;
    174195  }
    175  
     196
    176197  bool ok;
    177198  unsigned index = propertyName.toArrayIndex(&ok);
    … …  
    180201    return;
    181202  }
    182  
     203
    183204  JSObject::put(exec, propertyName, value, attr);
    184205}
    … …  
    186207void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)
    187208{
    188   //0xFFFF FFFF is a bit weird --- it should be treated as a non-array index, even when
    189   //it's a string
     209  // 0xFFFFFFFF is a bit weird --- it should be treated as a non-array index, even when it's a string
    190210  if (index > MAX_ARRAY_INDEX) {
    191211    put(exec, Identifier::from(index), value, attr);
    … …  
    193213  }
    194214
    195   if (index < sparseArrayCutoff && index >= storageLength) {
     215  if (index < sparseArrayCutoff && index >= storageLength)
    196216    resizeStorage(index + 1);
    197   }
    198 
    199   if (index >= length) {
     217
     218  if (index >= length)
    200219    length = index + 1;
    201   }
    202220
    203221  if (index < storageLength) {
    … …  
    205223    return;
    206224  }
    207  
    208   ASSERT(index >= sparseArrayCutoff);
    209   JSObject::put(exec, Identifier::from(index), value, attr);
     225
     226  OverflowMap* overflow = overflowMap(storage);
     227  if (!overflow) {
     228    overflow = new OverflowMap;
     229    if (!storage)
     230      allocateStorage(1);
     231    storage[-2] = reinterpret_cast<JSValue*>(overflow);
     232  }
     233  overflow->add(index, value);
    210234}
    211235
    … …  
    214238  if (propertyName == exec->propertyNames().length)
    215239    return false;
    216  
     240
    217241  bool ok;
    218242  uint32_t index = propertyName.toArrayIndex(&ok);
    … …  
    224248      return true;
    225249    }
    226   }
    227  
     250    if (OverflowMap* overflow = overflowMap(storage)) {
     251      OverflowMap::iterator it = overflow->find(index);
     252      if (it == overflow->end())
     253        return false;
     254      overflow->remove(it);
     255      return true;
     256    }
     257    return false;
     258  }
     259
    228260  return JSObject::deleteProperty(exec, propertyName);
    229261}
    … …  
    240272    return true;
    241273  }
    242  
    243   return JSObject::deleteProperty(exec, Identifier::from(index));
     274  OverflowMap* overflow = overflowMap(storage);
     275  if (!overflow)
     276    return false;
     277  OverflowMap::iterator it = overflow->find(index);
     278  if (it == overflow->end())
     279    return false;
     280  overflow->remove(it);
     281  return true;
    244282}
    245283
    … …  
    253291    if (value && value != undefined)
    254292      propertyNames.add(Identifier::from(i));
     293  }
     294
     295  OverflowMap* overflow = overflowMap(storage);
     296  if (overflow) {
     297    OverflowMap::iterator end = overflow->end();
     298    for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
     299      JSValue* value = it->second;
     300      if (value && value != undefined)
     301        propertyNames.add(Identifier::from(it->first));
     302    }
    255303  }
    256304 
    … …  
    283331void ArrayInstance::setLength(unsigned newLength, ExecState *exec)
    284332{
    285   if (newLength <= storageLength) {
     333  if (newLength <= storageLength)
    286334    resizeStorage(newLength);
    287   }
    288335
    289336  if (newLength < length) {
    290     PropertyNameArray sparseProperties;
    291    
    292     _prop.getSparseArrayPropertyNames(sparseProperties);
    293    
    294     PropertyNameArrayIterator end = sparseProperties.end();
    295    
    296     for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {
    297       Identifier name = *it;
    298       bool ok;
    299       unsigned index = name.toArrayIndex(&ok);
    300       if (ok && index > newLength)
    301         deleteProperty(exec, name);
     337    if (OverflowMap* overflow = overflowMap(storage)) {
     338      OverflowMap copy = *overflow;
     339      OverflowMap::iterator end = copy.end();
     340      for (OverflowMap::iterator it = copy.begin(); it != end; ++it) {
     341        if (it->first >= newLength)
     342          overflow->remove(it->first);
     343      }
    302344    }
    303345  }
    … …  
    311353  unsigned l = storageLength;
    312354  for (unsigned i = 0; i < l; ++i) {
    313     JSValue *imp = storage[i];
     355    JSValue* imp = storage[i];
    314356    if (imp && !imp->marked())
    315357      imp->mark();
     358  }
     359  if (OverflowMap* overflow = overflowMap(storage)) {
     360    OverflowMap::iterator end = overflow->end();
     361    for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
     362      JSValue* value = it->second;
     363      if (value && !value->marked())
     364        value->mark();
     365    }
    316366  }
    317367}
    … …  
    324374    JSValue *va = *(JSValue **)a;
    325375    JSValue *vb = *(JSValue **)b;
    326     if (va->isUndefined()) {
    327         return vb->isUndefined() ? 0 : 1;
    328     }
    329     if (vb->isUndefined()) {
    330         return -1;
    331     }
     376    ASSERT(!va->isUndefined());
     377    ASSERT(!vb->isUndefined());
    332378    return compare(va->toString(exec), vb->toString(exec));
    333379}
    … …  
    385431    JSValue *va = *(JSValue **)a;
    386432    JSValue *vb = *(JSValue **)b;
    387     if (va->isUndefined()) {
    388         return vb->isUndefined() ? 0 : 1;
    389     }
    390     if (vb->isUndefined()) {
    391         return -1;
    392     }
     433    ASSERT(!va->isUndefined());
     434    ASSERT(!vb->isUndefined());
    393435
    394436    args->arguments.clear();
    … …  
    442484    }
    443485   
    444     PropertyNameArray sparseProperties;
    445     _prop.getSparseArrayPropertyNames(sparseProperties);
    446     unsigned newLength = o + sparseProperties.size();
    447    
    448     if (newLength > storageLength)
    449         resizeStorage(newLength);
    450    
    451     PropertyNameArrayIterator end = sparseProperties.end();
    452     for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {
    453         Identifier name = *it;
    454         storage[o] = getDirect(name);
    455         _prop.remove(name);
    456         o++;
     486    unsigned newLength = o;
     487
     488    if (OverflowMap* overflow = overflowMap(storage)) {
     489        OverflowMap::iterator end = overflow->end();
     490        for (OverflowMap::iterator it = overflow->begin(); it != end; ++it)
     491            newLength += it->second != undefined;
     492   
     493        if (newLength > storageLength)
     494            resizeStorage(newLength);
     495   
     496        for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
     497            JSValue* v = it->second;
     498            if (v != undefined) {
     499                storage[o] = v;
     500                o++;
     501            }
     502        }
     503        delete overflow;
     504        storage[-2] = 0;
    457505    }
    458506   
    … …  
    10471095  return construct(exec,args);
    10481096}
     1097
     1098}
Note: See TracChangeset for help on using the changeset viewer.