Ignore:
Timestamp:
Oct 22, 2007, 6:35:17 AM (18 years ago)
Author:
darin
Message:

JavaScriptCore:

Reviewed by Maciej.

Makes the morph test in SunSpider 26% faster, and the overall
benchmark 3% faster.

This also fixes some small problems we had with the distinction
between nonexistent and undefined values in arrays.

  • kjs/array_instance.h: Tweaked formatting and naming.
  • kjs/array_instance.cpp: Copied from kjs/array_object.cpp. (KJS::storageSize): Added. Computes the size of the storage given a vector length. (KJS::increasedVectorLength): Added. Implements the rule for resizing the vector. (KJS::isDenseEnoughForVector): Added. (KJS::ArrayInstance::ArrayInstance): Initialize the new fields. (KJS::ArrayInstance::~ArrayInstance): Since m_storage is now never 0, delete it. (KJS::ArrayInstance::getItem): Updated for name changes. (KJS::ArrayInstance::lengthGetter): Ditto. (KJS::ArrayInstance::inlineGetOwnPropertySlot): Added. Allows both versions of getOwnPropertySlot to share more code. (KJS::ArrayInstance::getOwnPropertySlot): Just refactored, no code change. (KJS::ArrayInstance::put): Added logic for extending the vector as long as the array is dense enough. Also keep m_numValuesInVector up to date. (KJS::ArrayInstance::deleteProperty): Added code to keep m_numValuesInVector up to date. (KJS::ArrayInstance::getPropertyNames): Fixed bug where this would omit names for array indices with undefined values. (KJS::ArrayInstance::increaseVectorLength): Renamed from resizeStorage. Also simplified to only handle getting larger. (KJS::ArrayInstance::setLength): Added code to update m_numValuesInVector, to zero out the unused part of the vector and to delete the map if it's no longer needed. (KJS::ArrayInstance::mark): Tweaked formatting. (KJS::compareByStringForQSort): Ditto. (KJS::ArrayInstance::sort): Ditto. (KJS::CompareWithCompareFunctionArguments::CompareWithCompareFunctionArguments): Ditto. (KJS::compareWithCompareFunctionForQSort): Ditto. (KJS::ArrayInstance::compactForSorting): Fixed bug where this would turn undefined values into nonexistent values in some cases.
  • kjs/array_object.h: Removed MAX_ARRAY_INDEX.
  • kjs/array_object.cpp: Removed ArrayInstance. Moved to a separate file.

LayoutTests:

  • fast/js/kde/resources/Array.js: Added tests to cover missing value behavior (not the same as undefined values in arrays). This matches the ECMA JavaScript specification, but doesn't exactly match Firefox.
  • fast/js/kde/Array-expected.txt: Updated with results.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kjs/array_object.cpp

    r26862 r26881  
    11// -*- c-basic-offset: 2 -*-
    22/*
    3  *  This file is part of the KDE libraries
    43 *  Copyright (C) 1999-2000 Harri Porten ([email protected])
    54 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
    … …  
    2726#include "array_object.lut.h"
    2827
    29 #include "PropertyNameArray.h"
    3028#include "error_object.h"
    3129#include "lookup.h"
    … …  
    3533#include <wtf/HashSet.h>
    3634
    37 
    3835namespace KJS {
    39 
    40 typedef HashMap<unsigned, JSValue*> OverflowMap;
    41 
    42 static inline OverflowMap* overflowMap(JSValue** storage)
    43 {
    44     return storage ? reinterpret_cast<OverflowMap*>(storage[-2]) : 0;
    45 }
    46 
    47 // ------------------------------ ArrayInstance -----------------------------
    48 
    49 const unsigned sparseArrayCutoff = 10000;
    50 
    51 const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};
    52 
    53 static inline JSValue** allocateStorage(size_t capacity)
    54 {
    55   if (capacity == 0)
    56       return 0;
    57 
    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;
    60   storage[-1] = reinterpret_cast<JSValue*>(capacity);
    61   return storage;
    62 }
    63 
    64 static inline void reallocateStorage(JSValue**& storage, size_t newCapacity)
    65 {
    66   if (!storage) {
    67     storage = allocateStorage(newCapacity);
    68     return;
    69   }
    70 
    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;
    73   storage[-1] = reinterpret_cast<JSValue*>(newCapacity);
    74 }
    75 
    76 static inline void freeStorage(JSValue** storage)
    77 {
    78     if (storage)
    79         fastFree(storage - 2);
    80 }
    81 
    82 ArrayInstance::ArrayInstance(JSObject *proto, unsigned initialLength)
    83   : JSObject(proto)
    84   , length(initialLength)
    85   , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)
    86   , storage(allocateStorage(storageLength))
    87 {
    88   Collector::reportExtraMemoryCost(storageLength * sizeof(JSValue*));
    89 }
    90 
    91 ArrayInstance::ArrayInstance(JSObject *proto, const List &list)
    92   : JSObject(proto)
    93   , length(list.size())
    94   , storageLength(length)
    95   , storage(allocateStorage(storageLength))
    96 {
    97   ListIterator it = list.begin();
    98   unsigned l = length;
    99   for (unsigned i = 0; i < l; ++i)
    100     storage[i] = it++;
    101   // When the array is created non-empty, its cells are filled so it's really no worse than
    102   // a property map. Therefore don't report extra memory cost.
    103 }
    104 
    105 ArrayInstance::~ArrayInstance()
    106 {
    107   if (storage) {
    108     delete reinterpret_cast<OverflowMap*>(storage[-2]);
    109     freeStorage(storage);
    110   }
    111 }
    112 
    113 JSValue* ArrayInstance::getItem(unsigned i) const
    114 {
    115     if (i < storageLength) {
    116         JSValue* value = storage[i];
    117         return value ? value : jsUndefined();
    118     }
    119 
    120     const OverflowMap* overflow = overflowMap(storage);
    121     if (!overflow)
    122         return jsUndefined();
    123 
    124     JSValue* value = overflow->get(i);
    125     return value ? value : jsUndefined();
    126 }
    127 
    128 JSValue *ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
    129 {
    130   return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->length);
    131 }
    132 
    133 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
    134 {
    135   if (propertyName == exec->propertyNames().length) {
    136     slot.setCustom(this, lengthGetter);
    137     return true;
    138   }
    139 
    140   bool ok;
    141   unsigned index = propertyName.toArrayIndex(&ok);
    142   if (!ok)
    143     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
    144 
    145   if (index < storageLength) {
    146     JSValue *v = storage[index];
    147     if (!v)
    148       return false;     
    149     slot.setValueSlot(this, &storage[index]);
    150     return true;
    151   }
    152   if (index > MAX_ARRAY_INDEX)
    153     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
    154   OverflowMap* overflow = overflowMap(storage);
    155   if (!overflow)
    156     return false;
    157   OverflowMap::iterator it = overflow->find(index);
    158   if (it == overflow->end())
    159     return false;
    160   slot.setValueSlot(this, &it->second);
    161   return true;
    162 }
    163 
    164 bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
    165 {
    166   if (index < storageLength) {
    167     JSValue *v = storage[index];
    168     if (!v)
    169       return false;
    170     slot.setValueSlot(this, &storage[index]);
    171     return true;
    172   }
    173   if (index > MAX_ARRAY_INDEX)
    174     return getOwnPropertySlot(exec, Identifier::from(index), slot);
    175   OverflowMap* overflow = overflowMap(storage);
    176   if (!overflow)
    177     return false;
    178   OverflowMap::iterator it = overflow->find(index);
    179   if (it == overflow->end())
    180     return false;
    181   slot.setValueSlot(this, &it->second);
    182   return true;
    183 }
    184 
    185 // Special implementation of [[Put]] - see ECMA 15.4.5.1
    186 void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attr)
    187 {
    188   if (propertyName == exec->propertyNames().length) {
    189     unsigned int newLen = value->toUInt32(exec);
    190     if (value->toNumber(exec) != double(newLen)) {
    191       throwError(exec, RangeError, "Invalid array length.");
    192       return;
    193     }
    194     setLength(newLen);
    195     return;
    196   }
    197 
    198   bool ok;
    199   unsigned index = propertyName.toArrayIndex(&ok);
    200   if (ok) {
    201     put(exec, index, value, attr);
    202     return;
    203   }
    204 
    205   JSObject::put(exec, propertyName, value, attr);
    206 }
    207 
    208 void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)
    209 {
    210   // 0xFFFFFFFF is a bit weird --- it should be treated as a non-array index, even when it's a string
    211   if (index > MAX_ARRAY_INDEX) {
    212     put(exec, Identifier::from(index), value, attr);
    213     return;
    214   }
    215 
    216   if (index < sparseArrayCutoff && index >= storageLength)
    217     resizeStorage(index + 1);
    218 
    219   if (index >= length)
    220     length = index + 1;
    221 
    222   if (index < storageLength) {
    223     storage[index] = value;
    224     return;
    225   }
    226 
    227   OverflowMap* overflow = overflowMap(storage);
    228   if (!overflow) {
    229     overflow = new OverflowMap;
    230     if (!storage)
    231       storage = allocateStorage(1);
    232     storage[-2] = reinterpret_cast<JSValue*>(overflow);
    233   }
    234   overflow->add(index, value);
    235 }
    236 
    237 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier &propertyName)
    238 {
    239   if (propertyName == exec->propertyNames().length)
    240     return false;
    241 
    242   bool ok;
    243   uint32_t index = propertyName.toArrayIndex(&ok);
    244   if (ok) {
    245     if (index >= length)
    246       return true;
    247     if (index < storageLength) {
    248       storage[index] = 0;
    249       return true;
    250     }
    251     if (OverflowMap* overflow = overflowMap(storage)) {
    252       OverflowMap::iterator it = overflow->find(index);
    253       if (it == overflow->end())
    254         return false;
    255       overflow->remove(it);
    256       return true;
    257     }
    258     return false;
    259   }
    260 
    261   return JSObject::deleteProperty(exec, propertyName);
    262 }
    263 
    264 bool ArrayInstance::deleteProperty(ExecState *exec, unsigned index)
    265 {
    266   if (index > MAX_ARRAY_INDEX)
    267     return deleteProperty(exec, Identifier::from(index));
    268 
    269   if (index >= length)
    270     return true;
    271   if (index < storageLength) {
    272     storage[index] = 0;
    273     return true;
    274   }
    275   OverflowMap* overflow = overflowMap(storage);
    276   if (!overflow)
    277     return false;
    278   OverflowMap::iterator it = overflow->find(index);
    279   if (it == overflow->end())
    280     return false;
    281   overflow->remove(it);
    282   return true;
    283 }
    284 
    285 void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
    286 {
    287   // avoid fetching this every time through the loop
    288   JSValue* undefined = jsUndefined();
    289  
    290   for (unsigned i = 0; i < storageLength; ++i) {
    291     JSValue* value = storage[i];
    292     if (value && value != undefined)
    293       propertyNames.add(Identifier::from(i));
    294   }
    295 
    296   OverflowMap* overflow = overflowMap(storage);
    297   if (overflow) {
    298     OverflowMap::iterator end = overflow->end();
    299     for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    300       JSValue* value = it->second;
    301       if (value && value != undefined)
    302         propertyNames.add(Identifier::from(it->first));
    303     }
    304   }
    305  
    306   JSObject::getPropertyNames(exec, propertyNames);
    307 }
    308 
    309 void ArrayInstance::resizeStorage(unsigned newLength)
    310 {
    311     if (newLength < storageLength) {
    312       memset(storage + newLength, 0, sizeof(JSValue *) * (storageLength - newLength));
    313     }
    314     size_t cap = capacity();
    315     if (newLength > cap) {
    316       unsigned newCapacity;
    317       if (newLength > sparseArrayCutoff) {
    318         newCapacity = newLength;
    319       } else {
    320         newCapacity = (newLength * 3 + 1) / 2;
    321         if (newCapacity > sparseArrayCutoff) {
    322           newCapacity = sparseArrayCutoff;
    323         }
    324       }
    325      
    326       reallocateStorage(storage, newCapacity);
    327       memset(storage + cap, 0, sizeof(JSValue*) * (newCapacity - cap));
    328     }
    329     storageLength = newLength;
    330 }
    331 
    332 void ArrayInstance::setLength(unsigned newLength)
    333 {
    334   if (newLength <= storageLength)
    335     resizeStorage(newLength);
    336 
    337   if (newLength < length) {
    338     if (OverflowMap* overflow = overflowMap(storage)) {
    339       OverflowMap copy = *overflow;
    340       OverflowMap::iterator end = copy.end();
    341       for (OverflowMap::iterator it = copy.begin(); it != end; ++it) {
    342         if (it->first >= newLength)
    343           overflow->remove(it->first);
    344       }
    345     }
    346   }
    347  
    348   length = newLength;
    349 }
    350 
    351 void ArrayInstance::mark()
    352 {
    353   JSObject::mark();
    354   unsigned l = storageLength;
    355   for (unsigned i = 0; i < l; ++i) {
    356     JSValue* imp = storage[i];
    357     if (imp && !imp->marked())
    358       imp->mark();
    359   }
    360   if (OverflowMap* overflow = overflowMap(storage)) {
    361     OverflowMap::iterator end = overflow->end();
    362     for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    363       JSValue* value = it->second;
    364       if (value && !value->marked())
    365         value->mark();
    366     }
    367   }
    368 }
    369 
    370 static ExecState* execForCompareByStringForQSort = 0;
    371 
    372 static int compareByStringForQSort(const void *a, const void *b)
    373 {
    374     ExecState *exec = execForCompareByStringForQSort;
    375     JSValue *va = *(JSValue **)a;
    376     JSValue *vb = *(JSValue **)b;
    377     ASSERT(!va->isUndefined());
    378     ASSERT(!vb->isUndefined());
    379     return compare(va->toString(exec), vb->toString(exec));
    380 }
    381 
    382 void ArrayInstance::sort(ExecState* exec)
    383 {
    384     size_t lengthNotIncludingUndefined = compactForSorting();
    385      
    386     ExecState* oldExec = execForCompareByStringForQSort;
    387     execForCompareByStringForQSort = exec;
    388 #if HAVE(MERGESORT)
    389     // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
    390     // however, becuase it requires extra copies of the storage buffer, don't use it for very
    391     // large arrays
    392     // FIXME: for sorting by string value, the fastest thing would actually be to convert all the
    393     // values to string once up front, and then use a radix sort. That would be O(N) rather than
    394     // O(N log N).
    395     if (lengthNotIncludingUndefined < sparseArrayCutoff) {
    396         JSValue** storageCopy = allocateStorage(capacity());
    397         memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
    398         mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);
    399         freeStorage(storage);
    400         storage = storageCopy;
    401         execForCompareByStringForQSort = oldExec;
    402         return;
    403     }
    404 #endif
    405 
    406     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
    407     execForCompareByStringForQSort = oldExec;
    408 }
    409 
    410 struct CompareWithCompareFunctionArguments {
    411     CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
    412         : exec(e)
    413         , compareFunction(cf)
    414         , globalObject(e->dynamicInterpreter()->globalObject())
    415     {
    416         arguments.append(jsUndefined());
    417         arguments.append(jsUndefined());
    418     }
    419 
    420     ExecState *exec;
    421     JSObject *compareFunction;
    422     List arguments;
    423     JSObject *globalObject;
    424 };
    425 
    426 static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
    427 
    428 static int compareWithCompareFunctionForQSort(const void *a, const void *b)
    429 {
    430     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
    431 
    432     JSValue *va = *(JSValue **)a;
    433     JSValue *vb = *(JSValue **)b;
    434     ASSERT(!va->isUndefined());
    435     ASSERT(!vb->isUndefined());
    436 
    437     args->arguments.clear();
    438     args->arguments.append(va);
    439     args->arguments.append(vb);
    440     double compareResult = args->compareFunction->call
    441         (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
    442     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
    443 }
    444 
    445 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
    446 {
    447     size_t lengthNotIncludingUndefined = compactForSorting();
    448 
    449     CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
    450     CompareWithCompareFunctionArguments args(exec, compareFunction);
    451     compareWithCompareFunctionArguments = &args;
    452 #if HAVE(MERGESORT)
    453     // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
    454     // however, becuase it requires extra copies of the storage buffer, don't use it for very
    455     // large arrays
    456     // FIXME: a tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
    457     // better job of minimizing compares
    458     if (lengthNotIncludingUndefined < sparseArrayCutoff) {
    459         JSValue** storageCopy = allocateStorage(capacity());
    460         memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
    461         mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);
    462         freeStorage(storage);
    463         storage = storageCopy;
    464         compareWithCompareFunctionArguments = oldArgs;
    465         return;
    466     }
    467 #endif
    468     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
    469     compareWithCompareFunctionArguments = oldArgs;
    470 }
    471 
    472 unsigned ArrayInstance::compactForSorting()
    473 {
    474     JSValue *undefined = jsUndefined();
    475 
    476     unsigned o = 0;
    477    
    478     for (unsigned i = 0; i != storageLength; ++i) {
    479         JSValue *v = storage[i];
    480         if (v && v != undefined) {
    481             if (o != i)
    482                 storage[o] = v;
    483             o++;
    484         }
    485     }
    486    
    487     unsigned newLength = o;
    488 
    489     if (OverflowMap* overflow = overflowMap(storage)) {
    490         OverflowMap::iterator end = overflow->end();
    491         for (OverflowMap::iterator it = overflow->begin(); it != end; ++it)
    492             newLength += it->second != undefined;
    493    
    494         if (newLength > storageLength)
    495             resizeStorage(newLength);
    496    
    497         for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    498             JSValue* v = it->second;
    499             if (v != undefined) {
    500                 storage[o] = v;
    501                 o++;
    502             }
    503         }
    504         delete overflow;
    505         storage[-2] = 0;
    506     }
    507    
    508     if (newLength != storageLength)
    509         memset(storage + o, 0, sizeof(JSValue *) * (storageLength - o));
    510    
    511     return o;
    512 }
    51336
    51437// ------------------------------ ArrayPrototype ----------------------------
Note: See TracChangeset for help on using the changeset viewer.