Changeset 64320 in webkit


Ignore:
Timestamp:
Jul 29, 2010 4:29:17 PM (14 years ago)
Author:
barraclough@apple.com
Message:

Changed the handling for removing and adding elements at the front
of an array. The code now keeps a bias that indicates the amount of
JSValue sized holes are prior to the ArrayStorage block. This means
that shift operations are now memmove's of the header part of
the ArrayStorage and unshift operations are similar, but may require a
realloc first to create the space. Similar operations are performed
for special cases of splice and slice.
Also optimized the new Array(size) case so that we don't allocate and
initialize array elements until the JS code starts using elements.
The array growth code is slightly more aggressive for initial growth
based on size growth of any previous array.

Patch by Michael Saboff <​msaboff@apple.com> on 2010-07-29
Reviewed by Gavin Barraclough.

  • Configurations/JavaScriptCore.xcconfig:
  • jit/JITPropertyAccess.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::privateCompilePatchGetArrayLength):

  • jit/JITPropertyAccess32_64.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::privateCompilePatchGetArrayLength):

  • runtime/ArrayPrototype.cpp:

(JSC::arrayProtoFuncShift):
(JSC::arrayProtoFuncSplice):
(JSC::arrayProtoFuncUnShift):

  • runtime/JSArray.cpp:

(JSC::JSArray::JSArray):
(JSC::JSArray::~JSArray):
(JSC::JSArray::getOwnPropertySlot):
(JSC::JSArray::getOwnPropertyDescriptor):
(JSC::JSArray::put):
(JSC::JSArray::putSlowCase):
(JSC::JSArray::deleteProperty):
(JSC::JSArray::getOwnPropertyNames):
(JSC::JSArray::getNewVectorLength):
(JSC::JSArray::increaseVectorLength):
(JSC::JSArray::increaseVectorPrefixLength):
(JSC::JSArray::setLength):
(JSC::JSArray::pop):
(JSC::JSArray::push):
(JSC::JSArray::shiftCount):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sort):
(JSC::JSArray::fillArgList):
(JSC::JSArray::copyToRegisters):
(JSC::JSArray::compactForSorting):
(JSC::JSArray::subclassData):
(JSC::JSArray::setSubclassData):
(JSC::JSArray::checkConsistency):

  • runtime/JSArray.h:

(JSC::JSArray::length):
(JSC::JSArray::canGetIndex):
(JSC::JSArray::getIndex):
(JSC::JSArray::setIndex):
(JSC::JSArray::uncheckedSetIndex):
(JSC::JSArray::arrayStorage):
(JSC::JSArray::setArrayStorage):
(JSC::JSArray::markChildrenDirect):

Location:
trunk/JavaScriptCore
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r64319 r64320  
     12010-07-29  Michael Saboff  <msaboff@apple.com>
     2
     3        Reviewed by Gavin Barraclough.
     4
     5        Changed the handling for removing and adding elements at the front
     6        of an array.  The code now keeps a bias that indicates the amount of
     7        JSValue sized holes are prior to the ArrayStorage block.  This means
     8        that shift operations are now memmove's of the header part of
     9        the ArrayStorage and unshift operations are similar, but may require a
     10        realloc first to create the space.  Similar operations are performed
     11        for special cases of splice and slice.
     12        Also optimized the new Array(size) case so that we don't allocate and
     13        initialize array elements until the JS code starts using elements.
     14        The array growth code is slightly more aggressive for initial growth
     15        based on size growth of any previous array.
     16
     17        * Configurations/JavaScriptCore.xcconfig:
     18        * jit/JITPropertyAccess.cpp:
     19        (JSC::JIT::emit_op_get_by_val):
     20        (JSC::JIT::emit_op_put_by_val):
     21        (JSC::JIT::privateCompilePatchGetArrayLength):
     22        * jit/JITPropertyAccess32_64.cpp:
     23        (JSC::JIT::emit_op_get_by_val):
     24        (JSC::JIT::emit_op_put_by_val):
     25        (JSC::JIT::privateCompilePatchGetArrayLength):
     26        * runtime/ArrayPrototype.cpp:
     27        (JSC::arrayProtoFuncShift):
     28        (JSC::arrayProtoFuncSplice):
     29        (JSC::arrayProtoFuncUnShift):
     30        * runtime/JSArray.cpp:
     31        (JSC::JSArray::JSArray):
     32        (JSC::JSArray::~JSArray):
     33        (JSC::JSArray::getOwnPropertySlot):
     34        (JSC::JSArray::getOwnPropertyDescriptor):
     35        (JSC::JSArray::put):
     36        (JSC::JSArray::putSlowCase):
     37        (JSC::JSArray::deleteProperty):
     38        (JSC::JSArray::getOwnPropertyNames):
     39        (JSC::JSArray::getNewVectorLength):
     40        (JSC::JSArray::increaseVectorLength):
     41        (JSC::JSArray::increaseVectorPrefixLength):
     42        (JSC::JSArray::setLength):
     43        (JSC::JSArray::pop):
     44        (JSC::JSArray::push):
     45        (JSC::JSArray::shiftCount):
     46        (JSC::JSArray::unshiftCount):
     47        (JSC::JSArray::sortNumeric):
     48        (JSC::JSArray::sort):
     49        (JSC::JSArray::fillArgList):
     50        (JSC::JSArray::copyToRegisters):
     51        (JSC::JSArray::compactForSorting):
     52        (JSC::JSArray::subclassData):
     53        (JSC::JSArray::setSubclassData):
     54        (JSC::JSArray::checkConsistency):
     55        * runtime/JSArray.h:
     56        (JSC::JSArray::length):
     57        (JSC::JSArray::canGetIndex):
     58        (JSC::JSArray::getIndex):
     59        (JSC::JSArray::setIndex):
     60        (JSC::JSArray::uncheckedSetIndex):
     61        (JSC::JSArray::arrayStorage):
     62        (JSC::JSArray::setArrayStorage):
     63        (JSC::JSArray::markChildrenDirect):
     64
    1652010-07-29  Michael Saboff  <msaboff@apple.com>
    266

  • trunk/JavaScriptCore/jit/JITPropertyAccess.cpp

    r64184 r64320  
    104104    addSlowCase(branchPtr(NotEqual, Address(regT0), ImmPtr(m_globalData->jsArrayVPtr)));
    105105
    106     loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_storage)), regT2);
     106    loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_vector)), regT2);
    107107    addSlowCase(branch32(AboveOrEqual, regT1, Address(regT0, OBJECT_OFFSETOF(JSArray, m_vectorLength))));
    108108
    109     loadPtr(BaseIndex(regT2, regT1, ScalePtr, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])), regT0);
     109    loadPtr(BaseIndex(regT2, regT1, ScalePtr), regT0);
    110110    addSlowCase(branchTestPtr(Zero, regT0));
    111111
    … …  
    215215    addSlowCase(branch32(AboveOrEqual, regT1, Address(regT0, OBJECT_OFFSETOF(JSArray, m_vectorLength))));
    216216
    217     loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_storage)), regT2);
    218 
    219     Jump empty = branchTestPtr(Zero, BaseIndex(regT2, regT1, ScalePtr, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])));
     217    loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_vector)), regT2);
     218    Jump empty = branchTestPtr(Zero, BaseIndex(regT2, regT1, ScalePtr));
    220219
    221220    Label storeResult(this);
    222221    emitGetVirtualRegister(value, regT0);
    223     storePtr(regT0, BaseIndex(regT2, regT1, ScalePtr, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])));
     222    storePtr(regT0, BaseIndex(regT2, regT1, ScalePtr));
    224223    Jump end = jump();
    225224   
    226225    empty.link(this);
    227     add32(Imm32(1), Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector)));
    228     branch32(Below, regT1, Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length))).linkTo(storeResult, this);
     226    add32(Imm32(1), Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector)-OBJECT_OFFSETOF(ArrayStorage, m_vector)));
     227    branch32(Below, regT1, Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length)-OBJECT_OFFSETOF(ArrayStorage, m_vector))).linkTo(storeResult, this);
    229228
    230229    move(regT1, regT0);
    231230    add32(Imm32(1), regT0);
    232     store32(regT0, Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length)));
     231    store32(regT0, Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length)-OBJECT_OFFSETOF(ArrayStorage, m_vector)));
    233232    jump().linkTo(storeResult, this);
    234233
    … …  
    727726
    728727    // Checks out okay! - get the length from the storage
    729     loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_storage)), regT2);
    730     load32(Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length)), regT2);
    731 
     728    loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_vector)), regT3);
     729    load32(Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_length)-OBJECT_OFFSETOF(ArrayStorage, m_vector)), regT2);
    732730    Jump failureCases2 = branch32(Above, regT2, Imm32(JSImmediate::maxImmediateInt));
    733731

  • trunk/JavaScriptCore/jit/JITPropertyAccess32_64.cpp

    r64184 r64320  
    312312    addSlowCase(branchPtr(NotEqual, Address(regT0), ImmPtr(m_globalData->jsArrayVPtr)));
    313313   
    314     loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_storage)), regT3);
     314    loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_vector)), regT3);
    315315    addSlowCase(branch32(AboveOrEqual, regT2, Address(regT0, OBJECT_OFFSETOF(JSArray, m_vectorLength))));
    316316   
    317     load32(BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0]) + OBJECT_OFFSETOF(JSValue, u.asBits.tag)), regT1); // tag
    318     load32(BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0]) + OBJECT_OFFSETOF(JSValue, u.asBits.payload)), regT0); // payload
     317    load32(BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.tag)), regT1); // tag
     318    load32(BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.payload)), regT0); // payload
    319319    addSlowCase(branch32(Equal, regT1, Imm32(JSValue::EmptyValueTag)));
    320320   
    … …  
    365365    addSlowCase(branch32(AboveOrEqual, regT2, Address(regT0, OBJECT_OFFSETOF(JSArray, m_vectorLength))));
    366366   
    367     loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_storage)), regT3);
    368    
    369     Jump empty = branch32(Equal, BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0]) + OBJECT_OFFSETOF(JSValue, u.asBits.tag)), Imm32(JSValue::EmptyValueTag));
     367    loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_vector)), regT3);
     368   
     369    Jump empty = branch32(Equal, BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.tag)), Imm32(JSValue::EmptyValueTag));
    370370   
    371371    Label storeResult(this);
    372372    emitLoad(value, regT1, regT0);
    373     store32(regT0, BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0]) + OBJECT_OFFSETOF(JSValue, u.asBits.payload))); // payload
    374     store32(regT1, BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0]) + OBJECT_OFFSETOF(JSValue, u.asBits.tag))); // tag
     373    store32(regT0, BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.payload))); // payload
     374    store32(regT1, BaseIndex(regT3, regT2, TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.tag))); // tag
    375375    Jump end = jump();
    376376   
    377377    empty.link(this);
    378     add32(Imm32(1), Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector)));
    379     branch32(Below, regT2, Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_length))).linkTo(storeResult, this);
     378    add32(Imm32(1), Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector)-OBJECT_OFFSETOF(ArrayStorage, m_vector)));
     379    branch32(Below, regT2, Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_length)-OBJECT_OFFSETOF(ArrayStorage, m_vector))).linkTo(storeResult, this);
    380380   
    381381    add32(Imm32(1), regT2, regT0);
    382     store32(regT0, Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_length)));
     382    store32(regT0, Address(regT3, OBJECT_OFFSETOF(ArrayStorage, m_length)-OBJECT_OFFSETOF(ArrayStorage, m_vector)));
    383383    jump().linkTo(storeResult, this);
    384384   
    … …  
    732732   
    733733    // Checks out okay! - get the length from the storage
    734     loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_storage)), regT2);
    735     load32(Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length)), regT2);
     734    loadPtr(Address(regT0, OBJECT_OFFSETOF(JSArray, m_vector)), regT2);
     735    load32(Address(regT2, OBJECT_OFFSETOF(ArrayStorage, m_length)-OBJECT_OFFSETOF(ArrayStorage, m_vector)), regT2);
    736736   
    737737    Jump failureCases2 = branch32(Above, regT2, Imm32(INT_MAX));

  • trunk/JavaScriptCore/runtime/ArrayPrototype.cpp

    r64184 r64320  
    425425    } else {
    426426        result = thisObj->get(exec, 0);
    427         for (unsigned k = 1; k < length; k++) {
    428             if (JSValue obj = getProperty(exec, thisObj, k))
    429                 thisObj->put(exec, k - 1, obj);
    430             else
    431                 thisObj->deleteProperty(exec, k - 1);
    432         }
    433         thisObj->deleteProperty(exec, length - 1);
     427        if (isJSArray(&exec->globalData(), thisObj))
     428            ((JSArray *)thisObj)->shiftCount(exec, 1);
     429        else {
     430            for (unsigned k = 1; k < length; k++) {
     431                if (JSValue obj = getProperty(exec, thisObj, k))
     432                    thisObj->put(exec, k - 1, obj);
     433                else
     434                    thisObj->deleteProperty(exec, k - 1);
     435            }
     436            thisObj->deleteProperty(exec, length - 1);
     437        }
    434438        putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length - 1));
    435439    }
    … …  
    579583    if (additionalArgs != deleteCount) {
    580584        if (additionalArgs < deleteCount) {
    581             for (unsigned k = begin; k < length - deleteCount; ++k) {
    582                 if (JSValue v = getProperty(exec, thisObj, k + deleteCount))
    583                     thisObj->put(exec, k + additionalArgs, v);
    584                 else
    585                     thisObj->deleteProperty(exec, k + additionalArgs);
     585            if ((!begin) && (isJSArray(&exec->globalData(), thisObj)))
     586                ((JSArray *)thisObj)->shiftCount(exec, deleteCount - additionalArgs);
     587            else {
     588                for (unsigned k = begin; k < length - deleteCount; ++k) {
     589                    if (JSValue v = getProperty(exec, thisObj, k + deleteCount))
     590                        thisObj->put(exec, k + additionalArgs, v);
     591                    else
     592                        thisObj->deleteProperty(exec, k + additionalArgs);
     593                }
     594                for (unsigned k = length; k > length - deleteCount + additionalArgs; --k)
     595                    thisObj->deleteProperty(exec, k - 1);
    586596            }
    587             for (unsigned k = length; k > length - deleteCount + additionalArgs; --k)
    588                 thisObj->deleteProperty(exec, k - 1);
    589597        } else {
    590             for (unsigned k = length - deleteCount; k > begin; --k) {
    591                 if (JSValue obj = getProperty(exec, thisObj, k + deleteCount - 1))
    592                     thisObj->put(exec, k + additionalArgs - 1, obj);
    593                 else
    594                     thisObj->deleteProperty(exec, k + additionalArgs - 1);
     598            if ((!begin) && (isJSArray(&exec->globalData(), thisObj)))
     599                ((JSArray *)thisObj)->unshiftCount(exec, additionalArgs - deleteCount);
     600            else {
     601                for (unsigned k = length - deleteCount; k > begin; --k) {
     602                    if (JSValue obj = getProperty(exec, thisObj, k + deleteCount - 1))
     603                        thisObj->put(exec, k + additionalArgs - 1, obj);
     604                    else
     605                        thisObj->deleteProperty(exec, k + additionalArgs - 1);
     606                }
    595607            }
    596608        }
    … …  
    611623    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    612624    unsigned nrArgs = exec->argumentCount();
    613     if (nrArgs) {
    614         for (unsigned k = length; k > 0; --k) {
    615             if (JSValue v = getProperty(exec, thisObj, k - 1))
    616                 thisObj->put(exec, k + nrArgs - 1, v);
    617             else
    618                 thisObj->deleteProperty(exec, k + nrArgs - 1);
     625    if ((nrArgs) && (length)) {
     626        if (isJSArray(&exec->globalData(), thisObj))
     627            ((JSArray *)thisObj)->unshiftCount(exec, nrArgs);
     628        else {
     629            for (unsigned k = length; k > 0; --k) {
     630                if (JSValue v = getProperty(exec, thisObj, k - 1))
     631                    thisObj->put(exec, k + nrArgs - 1, v);
     632                else
     633                    thisObj->deleteProperty(exec, k + nrArgs - 1);
     634            }
    619635        }
    620636    }

  • trunk/JavaScriptCore/runtime/JSArray.cpp

    r64184 r64320  
    7979#define MAX_ARRAY_INDEX 0xFFFFFFFEU
    8080
     81// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
     82// for an array that was created with a sepcified length (e.g. a = new Array(123))
     83#define BASE_VECTOR_LEN 4U
     84   
     85// The upper bound to the size we'll grow a zero length array when the first element
     86// is added.
     87#define FIRST_VECTOR_GROW 4U
     88
    8189// Our policy for when to use a vector and when to use a sparse map.
    8290// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
    … …  
    8694
    8795const ClassInfo JSArray::info = {"Array", 0, 0, 0};
     96
     97// We keep track of the size of the last array after it was grown.  We use this
     98// as a simple heuristic for as the value to grow the next array from size 0.
     99// This value is capped by the constant FIRST_VECTOR_GROW defined above.
     100static unsigned lastArraySize = 0;
    88101
    89102static inline size_t storageSize(unsigned vectorLength)
    … …  
    101114}
    102115
    103 static inline unsigned increasedVectorLength(unsigned newLength)
    104 {
    105     ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
    106 
    107     // Mathematically equivalent to:
    108     //   increasedLength = (newLength * 3 + 1) / 2;
    109     // or:
    110     //   increasedLength = (unsigned)ceil(newLength * 1.5));
    111     // This form is not prone to internal overflow.
    112     unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
    113     ASSERT(increasedLength >= newLength);
    114 
    115     return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
    116 }
    117 
    118116static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
    119117{
    … …  
    134132    unsigned initialCapacity = 0;
    135133
    136     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
     134    ArrayStorage* storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
     135    m_indexBias = 0;
     136    setArrayStorage(storage);
    137137    m_vectorLength = initialCapacity;
    138138
    … …  
    147147        initialCapacity = initialLength;
    148148    else
    149         initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
    150 
    151     m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
     149        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
     150   
     151    ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
     152    storage->m_length = initialLength;
     153    m_indexBias = 0;
    152154    m_vectorLength = initialCapacity;
    153     m_storage->m_sparseValueMap = 0;
    154     m_storage->subclassData = 0;
    155     m_storage->reportedMapCapacity = 0;
     155    setArrayStorage(storage);   
     156    storage->m_sparseValueMap = 0;
     157    storage->subclassData = 0;
     158    storage->reportedMapCapacity = 0;
    156159
    157160    if (creationMode == CreateCompact) {
    158161#if CHECK_ARRAY_CONSISTENCY
    159         m_storage->m_inCompactInitialization = !!initialCapacity;
     162        storage->m_inCompactInitialization = !!initialCapacity;
    160163#endif
    161         m_storage->m_length = 0;
    162         m_storage->m_numValuesInVector = initialCapacity;
     164        storage->m_length = 0;
     165        storage->m_numValuesInVector = initialCapacity;
    163166    } else {
    164167#if CHECK_ARRAY_CONSISTENCY
    165         m_storage->m_inCompactInitialization = false;
     168        storage->m_inCompactInitialization = false;
    166169#endif
    167         m_storage->m_length = initialLength;
    168         m_storage->m_numValuesInVector = 0;
    169         JSValue* vector = m_storage->m_vector;
     170        storage->m_length = initialLength;
     171        storage->m_numValuesInVector = 0;
     172        JSValue* vector = m_vector;
    170173        for (size_t i = 0; i < initialCapacity; ++i)
    171174            vector[i] = JSValue();
    … …  
    173176
    174177    checkConsistency();
    175 
     178   
    176179    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
    177180}
    … …  
    182185    unsigned initialCapacity = list.size();
    183186
    184     m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    185     m_storage->m_length = initialCapacity;
     187    ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
     188    m_indexBias = 0;
     189    storage->m_length = initialCapacity;
    186190    m_vectorLength = initialCapacity;
    187     m_storage->m_numValuesInVector = initialCapacity;
    188     m_storage->m_sparseValueMap = 0;
    189     m_storage->subclassData = 0;
    190     m_storage->reportedMapCapacity = 0;
     191    storage->m_numValuesInVector = initialCapacity;
     192    storage->m_sparseValueMap = 0;
     193    storage->subclassData = 0;
     194    storage->reportedMapCapacity = 0;
    191195#if CHECK_ARRAY_CONSISTENCY
    192     m_storage->m_inCompactInitialization = false;
     196    storage->m_inCompactInitialization = false;
    193197#endif
     198    setArrayStorage(storage);
    194199
    195200    size_t i = 0;
     201    JSValue* vector = m_vector;
    196202    ArgList::const_iterator end = list.end();
    197203    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
    198         m_storage->m_vector[i] = *it;
     204        vector[i] = *it;
    199205
    200206    checkConsistency();
    … …  
    208214    checkConsistency(DestructorConsistencyCheck);
    209215
    210     delete m_storage->m_sparseValueMap;
    211     fastFree(m_storage);
     216    ArrayStorage* storage = arrayStorage();
     217    delete storage->m_sparseValueMap;
     218    char* realStorage = reinterpret_cast<char*>(storage) - (m_indexBias * sizeof(JSValue));
     219    fastFree(realStorage);
    212220}
    213221
    214222bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
    215223{
    216     ArrayStorage* storage = m_storage;
    217 
     224    ArrayStorage* storage = arrayStorage();
     225   
    218226    if (i >= storage->m_length) {
    219227        if (i > MAX_ARRAY_INDEX)
    … …  
    223231
    224232    if (i < m_vectorLength) {
    225         JSValue& valueSlot = storage->m_vector[i];
     233        JSValue& valueSlot = m_vector[i];
    226234        if (valueSlot) {
    227235            slot.setValueSlot(&valueSlot);
    … …  
    262270        return true;
    263271    }
     272
     273    ArrayStorage* storage = arrayStorage();
    264274   
    265275    bool isArrayIndex;
    266276    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
    267277    if (isArrayIndex) {
    268         if (i >= m_storage->m_length)
     278        if (i >= storage->m_length)
    269279            return false;
    270280        if (i < m_vectorLength) {
    271             JSValue& value = m_storage->m_vector[i];
     281            JSValue& value = m_vector[i];
    272282            if (value) {
    273283                descriptor.setDescriptor(value, 0);
    274284                return true;
    275285            }
    276         } else if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
     286        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
    277287            if (i >= MIN_SPARSE_ARRAY_INDEX) {
    278288                SparseArrayValueMap::iterator it = map->find(i);
    … …  
    314324    checkConsistency();
    315325
    316     unsigned length = m_storage->m_length;
     326    ArrayStorage* storage = arrayStorage();
     327
     328    unsigned length = storage->m_length;
    317329    if (i >= length && i <= MAX_ARRAY_INDEX) {
    318330        length = i + 1;
    319         m_storage->m_length = length;
     331        storage->m_length = length;
    320332    }
    321333
    322334    if (i < m_vectorLength) {
    323         JSValue& valueSlot = m_storage->m_vector[i];
     335        JSValue& valueSlot = m_vector[i];
    324336        if (valueSlot) {
    325337            valueSlot = value;
    … …  
    328340        }
    329341        valueSlot = value;
    330         ++m_storage->m_numValuesInVector;
     342        ++storage->m_numValuesInVector;
    331343        checkConsistency();
    332344        return;
    … …  
    338350NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
    339351{
    340     ArrayStorage* storage = m_storage;
     352    ArrayStorage* storage = arrayStorage();
     353   
    341354    SparseArrayValueMap* map = storage->m_sparseValueMap;
    342355
    … …  
    375388    if (!map || map->isEmpty()) {
    376389        if (increaseVectorLength(i + 1)) {
    377             storage = m_storage;
    378             storage->m_vector[i] = value;
    379             ++storage->m_numValuesInVector;
     390            m_vector[i] = value;
     391            ++arrayStorage()->m_numValuesInVector;
    380392            checkConsistency();
    381393        } else
    … …  
    386398    // Decide how many values it would be best to move from the map.
    387399    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
    388     unsigned newVectorLength = increasedVectorLength(i + 1);
     400    unsigned newVectorLength = getNewVectorLength(i + 1);
    389401    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
    390402        newNumValuesInVector += map->contains(j);
    … …  
    395407        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
    396408        while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
    397             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
     409            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
    398410            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
    399411                proposedNewNumValuesInVector += map->contains(j);
    … …  
    405417    }
    406418
    407     if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {
     419    int baseBias = m_indexBias * sizeof(JSValue);
     420    char* baseStorage = reinterpret_cast<char*>(storage - baseBias);
     421   
     422    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
    408423        throwOutOfMemoryError(exec);
    409424        return;
    410425    }
    411426
     427    storage = reinterpret_cast<ArrayStorage*>(baseStorage + baseBias);
     428    setArrayStorage(storage);
     429   
    412430    unsigned vectorLength = m_vectorLength;
    413431
    414432    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
    415433        for (unsigned j = vectorLength; j < newVectorLength; ++j)
    416             storage->m_vector[j] = JSValue();
     434            m_vector[j] = JSValue();
    417435        if (i > MIN_SPARSE_ARRAY_INDEX)
    418436            map->remove(i);
    419437    } else {
    420438        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
    421             storage->m_vector[j] = JSValue();
     439            m_vector[j] = JSValue();
    422440        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
    423             storage->m_vector[j] = map->take(j);
    424     }
    425 
    426     storage->m_vector[i] = value;
     441            m_vector[j] = map->take(j);
     442    }
     443
     444    ASSERT(i < newVectorLength);
    427445
    428446    m_vectorLength = newVectorLength;
    429447    storage->m_numValuesInVector = newNumValuesInVector;
    430448
    431     m_storage = storage;
     449    m_vector[i] = value;
    432450
    433451    checkConsistency();
    … …  
    453471    checkConsistency();
    454472
    455     ArrayStorage* storage = m_storage;
    456 
     473    ArrayStorage* storage = arrayStorage();
     474   
    457475    if (i < m_vectorLength) {
    458         JSValue& valueSlot = storage->m_vector[i];
     476        JSValue& valueSlot = m_vector[i];
    459477        if (!valueSlot) {
    460478            checkConsistency();
    … …  
    492510    // which almost certainly means a different structure for PropertyNameArray.
    493511
    494     ArrayStorage* storage = m_storage;
    495 
     512    ArrayStorage* storage = arrayStorage();
     513   
    496514    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
    497515    for (unsigned i = 0; i < usedVectorLength; ++i) {
    498         if (storage->m_vector[i])
     516        if (m_vector[i])
    499517            propertyNames.add(Identifier::from(exec, i));
    500518    }
    … …  
    512530}
    513531
     532ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
     533{
     534    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
     535
     536    unsigned increasedLength;
     537    unsigned length = arrayStorage()->m_length;
     538
     539    if (desiredLength < length)
     540        increasedLength = length;
     541    else if (!m_vectorLength)
     542        increasedLength = max(desiredLength, lastArraySize);
     543    else {
     544        // Mathematically equivalent to:
     545        //   increasedLength = (newLength * 3 + 1) / 2;
     546        // or:
     547        //   increasedLength = (unsigned)ceil(newLength * 1.5));
     548        // This form is not prone to internal overflow.
     549        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
     550    }
     551
     552    ASSERT(increasedLength >= desiredLength);
     553
     554    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
     555
     556    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
     557}
     558
    514559bool JSArray::increaseVectorLength(unsigned newLength)
    515560{
    … …  
    517562    // to the vector. Callers have to account for that, because they can do it more efficiently.
    518563
    519     ArrayStorage* storage = m_storage;
     564    ArrayStorage* storage = arrayStorage();
    520565
    521566    unsigned vectorLength = m_vectorLength;
    522567    ASSERT(newLength > vectorLength);
    523568    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    524     unsigned newVectorLength = increasedVectorLength(newLength);
    525 
    526     if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))
     569    unsigned newVectorLength = getNewVectorLength(newLength);
     570    int baseBias = m_indexBias * sizeof(JSValue);
     571    char* baseStorage = reinterpret_cast<char*>(storage) - baseBias;
     572
     573    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage))
    527574        return false;
     575   
     576    storage = reinterpret_cast<ArrayStorage*>(baseStorage + baseBias);
     577    setArrayStorage(storage);
     578
     579    JSValue* vector = m_vector;
     580    for (unsigned i = vectorLength; i < newVectorLength; ++i)
     581        vector[i] = JSValue();
    528582
    529583    m_vectorLength = newVectorLength;
    530 
    531     for (unsigned i = vectorLength; i < newVectorLength; ++i)
    532         storage->m_vector[i] = JSValue();
    533 
    534     m_storage = storage;
    535 
     584   
    536585    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
    537586
    538587    return true;
    539588}
     589
     590bool JSArray::increaseVectorPrefixLength(unsigned newLength)
     591{
     592    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
     593    // to the vector. Callers have to account for that, because they can do it more efficiently.
     594   
     595    ArrayStorage* storage = arrayStorage();
     596    ArrayStorage* newStorage;
     597   
     598    unsigned vectorLength = m_vectorLength;
     599    ASSERT(newLength > vectorLength);
     600    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
     601    unsigned newVectorLength = getNewVectorLength(newLength);
     602    char* baseStorage = reinterpret_cast<char*>(storage) - (m_indexBias * sizeof(JSValue));
     603   
     604    char* newBaseStorage = reinterpret_cast<char*>(fastMalloc(storageSize(newVectorLength + m_indexBias)));
     605    if (!newBaseStorage)
     606        return false;
     607   
     608    m_indexBias += newVectorLength - newLength;
     609    int newStorageOffset = m_indexBias * sizeof(JSValue);
     610   
     611    newStorage = reinterpret_cast<ArrayStorage*>(newBaseStorage + newStorageOffset);
     612   
     613    memcpy(newStorage, storage, storageSize(0));
     614    memcpy(&newStorage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], storage->m_length * sizeof(JSValue));
     615   
     616    m_vectorLength = newLength;
     617   
     618    fastFree(baseStorage);
     619
     620    setArrayStorage(newStorage);
     621   
     622    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
     623   
     624    return true;
     625}
     626   
    540627
    541628void JSArray::setLength(unsigned newLength)
    … …  
    548635#endif
    549636
    550     ArrayStorage* storage = m_storage;
    551 
    552     unsigned length = m_storage->m_length;
     637    ArrayStorage* storage = arrayStorage();
     638   
     639    unsigned length = storage->m_length;
    553640
    554641    if (newLength < length) {
    555642        unsigned usedVectorLength = min(length, m_vectorLength);
    556643        for (unsigned i = newLength; i < usedVectorLength; ++i) {
    557             JSValue& valueSlot = storage->m_vector[i];
     644            JSValue& valueSlot = m_vector[i];
    558645            bool hadValue = valueSlot;
    559646            valueSlot = JSValue();
    … …  
    575662    }
    576663
    577     m_storage->m_length = newLength;
     664    storage->m_length = newLength;
    578665
    579666    checkConsistency();
    … …  
    584671    checkConsistency();
    585672
    586     unsigned length = m_storage->m_length;
     673    ArrayStorage* storage = arrayStorage();
     674   
     675    unsigned length = storage->m_length;
    587676    if (!length)
    588677        return jsUndefined();
    … …  
    593682
    594683    if (length < m_vectorLength) {
    595         JSValue& valueSlot = m_storage->m_vector[length];
     684        JSValue& valueSlot = m_vector[length];
    596685        if (valueSlot) {
    597             --m_storage->m_numValuesInVector;
     686            --storage->m_numValuesInVector;
    598687            result = valueSlot;
    599688            valueSlot = JSValue();
    … …  
    602691    } else {
    603692        result = jsUndefined();
    604         if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
     693        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
    605694            SparseArrayValueMap::iterator it = map->find(length);
    606695            if (it != map->end()) {
    … …  
    609698                if (map->isEmpty()) {
    610699                    delete map;
    611                     m_storage->m_sparseValueMap = 0;
     700                    storage->m_sparseValueMap = 0;
    612701                }
    613702            }
    … …  
    615704    }
    616705
    617     m_storage->m_length = length;
     706    storage->m_length = length;
    618707
    619708    checkConsistency();
    … …  
    625714{
    626715    checkConsistency();
    627 
    628     if (m_storage->m_length < m_vectorLength) {
    629         m_storage->m_vector[m_storage->m_length] = value;
    630         ++m_storage->m_numValuesInVector;
    631         ++m_storage->m_length;
     716   
     717    ArrayStorage* storage = arrayStorage();
     718
     719    if (storage->m_length < m_vectorLength) {
     720        m_vector[storage->m_length] = value;
     721        ++storage->m_numValuesInVector;
     722        ++storage->m_length;
    632723        checkConsistency();
    633724        return;
    634725    }
    635726
    636     if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
    637         SparseArrayValueMap* map = m_storage->m_sparseValueMap;
     727    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
     728        SparseArrayValueMap* map = storage->m_sparseValueMap;
    638729        if (!map || map->isEmpty()) {
    639             if (increaseVectorLength(m_storage->m_length + 1)) {
    640                 m_storage->m_vector[m_storage->m_length] = value;
    641                 ++m_storage->m_numValuesInVector;
    642                 ++m_storage->m_length;
     730            if (increaseVectorLength(storage->m_length + 1)) {
     731                storage = arrayStorage();
     732                m_vector[storage->m_length] = value;
     733                ++storage->m_numValuesInVector;
     734                ++storage->m_length;
    643735                checkConsistency();
    644736                return;
    … …  
    650742    }
    651743
    652     putSlowCase(exec, m_storage->m_length++, value);
     744    putSlowCase(exec, storage->m_length++, value);
     745}
     746
     747void JSArray::shiftCount(ExecState* exec, int count)
     748{
     749    ASSERT(count > 0);
     750   
     751    ArrayStorage* storage = arrayStorage();
     752   
     753    unsigned oldLength = storage->m_length;
     754   
     755    if (!oldLength)
     756        return;
     757   
     758    if (oldLength != storage->m_numValuesInVector) {
     759        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
     760        // which means we need to go through each entry looking for the the "empty"
     761        // slots and then fill them with possible properties.  See ECMA spec.
     762        // 15.4.4.9 steps 11 through 13.
     763        for (unsigned i = count; i < oldLength; ++i) {
     764            if ((i >= m_vectorLength) || (!m_vector[i])) {
     765                PropertySlot slot(this);
     766                JSValue p = prototype();
     767                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
     768                    put(exec, i, slot.getValue(exec, i));
     769            }
     770        }
     771
     772        storage = arrayStorage(); // The put() above could have grown the vector and realloc'ed storage.
     773
     774        // Need to decrement numValuesInvector based on number of real entries
     775        for (unsigned i = 0; i < (unsigned)count; ++i)
     776            if ((i < m_vectorLength) && (m_vector[i]))
     777                --storage->m_numValuesInVector;
     778    } else
     779        storage->m_numValuesInVector -= count;
     780   
     781    storage->m_length -= count;
     782   
     783    if (m_vectorLength) {
     784        count = min(m_vectorLength, (unsigned)count);
     785       
     786        m_vectorLength -= count;
     787       
     788        if (m_vectorLength) {
     789            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
     790            memmove(newBaseStorage, storage, storageSize(0));
     791            storage = reinterpret_cast<ArrayStorage*>(newBaseStorage);
     792
     793            m_indexBias += count;
     794            setArrayStorage(storage);
     795        }
     796    }
     797}
     798   
     799void JSArray::unshiftCount(ExecState* exec, int count)
     800{
     801    ArrayStorage* storage = arrayStorage();
     802
     803    ASSERT(m_indexBias >= 0);
     804    ASSERT(count >= 0);
     805   
     806    unsigned length = storage->m_length;
     807   
     808    if (length != storage->m_numValuesInVector) {
     809        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
     810        // which means we need to go through each entry looking for the the "empty"
     811        // slots and then fill them with possible properties.  See ECMA spec.
     812        // 15.4.4.13 steps 8 through 10.
     813        for (unsigned i = 0; i < length; ++i) {
     814            if ((i >= m_vectorLength) || (!m_vector[i])) {
     815                PropertySlot slot(this);
     816                JSValue p = prototype();
     817                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
     818                    put(exec, i, slot.getValue(exec, i));
     819            }
     820        }
     821    }
     822   
     823    storage = arrayStorage(); // The put() above could have grown the vector and realloc'ed storage.
     824   
     825    if (m_indexBias >= count) {
     826        m_indexBias -= count;
     827        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
     828        memmove(newBaseStorage, storage, storageSize(0));
     829        storage = reinterpret_cast<ArrayStorage*>(newBaseStorage);
     830        setArrayStorage(storage);
     831        m_vectorLength += count;
     832    } else if ((!m_indexBias) && (!increaseVectorPrefixLength(m_vectorLength + count))) {
     833        throwOutOfMemoryError(exec);
     834        return;
     835    }
    653836}
    654837
    … …  
    676859void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
    677860{
     861    ArrayStorage* storage = arrayStorage();
     862
    678863    unsigned lengthNotIncludingUndefined = compactForSorting();
    679     if (m_storage->m_sparseValueMap) {
     864    if (storage->m_sparseValueMap) {
    680865        throwOutOfMemoryError(exec);
    681866        return;
    … …  
    686871       
    687872    bool allValuesAreNumbers = true;
    688     size_t size = m_storage->m_numValuesInVector;
     873    size_t size = storage->m_numValuesInVector;
    689874    for (size_t i = 0; i < size; ++i) {
    690         if (!m_storage->m_vector[i].isNumber()) {
     875        if (!m_vector[i].isNumber()) {
    691876            allValuesAreNumbers = false;
    692877            break;
    … …  
    700885    // also don't require mergesort's stability, since there's no user visible
    701886    // side-effect from swapping the order of equal primitive values.
    702     qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
     887    qsort(m_vector, size, sizeof(JSValue), compareNumbersForQSort);
    703888
    704889    checkConsistency(SortConsistencyCheck);
    … …  
    707892void JSArray::sort(ExecState* exec)
    708893{
     894    ArrayStorage* storage = arrayStorage();
     895
    709896    unsigned lengthNotIncludingUndefined = compactForSorting();
    710     if (m_storage->m_sparseValueMap) {
     897    if (storage->m_sparseValueMap) {
    711898        throwOutOfMemoryError(exec);
    712899        return;
    … …  
    728915
    729916    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
    730         JSValue value = m_storage->m_vector[i];
     917        JSValue value = m_vector[i];
    731918        ASSERT(!value.isUndefined());
    732919        values[i].first = value;
    … …  
    760947
    761948    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
    762         m_storage->m_vector[i] = values[i].first;
     949        m_vector[i] = values[i].first;
    763950
    764951    checkConsistency(SortConsistencyCheck);
    … …  
    8471034    checkConsistency();
    8481035
     1036    ArrayStorage* storage = arrayStorage();
     1037
    8491038    // FIXME: This ignores exceptions raised in the compare function or in toNumber.
    8501039
    8511040    // The maximum tree depth is compiled in - but the caller is clearly up to no good
    8521041    // if a larger array is passed.
    853     ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
    854     if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
    855         return;
    856 
    857     if (!m_storage->m_length)
    858         return;
    859 
    860     unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
     1042    ASSERT(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
     1043    if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
     1044        return;
     1045
     1046    if (!storage->m_length)
     1047        return;
     1048
     1049    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
    8611050
    8621051    AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
    … …  
    8661055    tree.abstractor().m_compareCallData = &callData;
    8671056    tree.abstractor().m_globalThisValue = exec->globalThisValue();
    868     tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
     1057    tree.abstractor().m_nodes.resize(usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0));
    8691058
    8701059    if (callType == CallTypeJS)
    … …  
    8841073    // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
    8851074    for (; numDefined < usedVectorLength; ++numDefined) {
    886         JSValue v = m_storage->m_vector[numDefined];
     1075        JSValue v = m_vector[numDefined];
    8871076        if (!v || v.isUndefined())
    8881077            break;
    … …  
    8911080    }
    8921081    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
    893         JSValue v = m_storage->m_vector[i];
     1082        JSValue v = m_vector[i];
    8941083        if (v) {
    8951084            if (v.isUndefined())
    … …  
    9051094    unsigned newUsedVectorLength = numDefined + numUndefined;
    9061095
    907     if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
     1096    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
    9081097        newUsedVectorLength += map->size();
    9091098        if (newUsedVectorLength > m_vectorLength) {
    … …  
    9141103            }
    9151104        }
     1105       
     1106        storage = arrayStorage();
    9161107
    9171108        SparseArrayValueMap::iterator end = map->end();
    … …  
    9231114
    9241115        delete map;
    925         m_storage->m_sparseValueMap = 0;
     1116        storage->m_sparseValueMap = 0;
    9261117    }
    9271118
    … …  
    9351126    iter.start_iter_least(tree);
    9361127    for (unsigned i = 0; i < numDefined; ++i) {
    937         m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
     1128        m_vector[i] = tree.abstractor().m_nodes[*iter].value;
    9381129        ++iter;
    9391130    }
    … …  
    9411132    // Put undefined values back in.
    9421133    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
    943         m_storage->m_vector[i] = jsUndefined();
     1134        m_vector[i] = jsUndefined();
    9441135
    9451136    // Ensure that unused values in the vector are zeroed out.
    9461137    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
    947         m_storage->m_vector[i] = JSValue();
    948 
    949     m_storage->m_numValuesInVector = newUsedVectorLength;
     1138        m_vector[i] = JSValue();
     1139
     1140    storage->m_numValuesInVector = newUsedVectorLength;
    9501141
    9511142    checkConsistency(SortConsistencyCheck);
    … …  
    9541145void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
    9551146{
    956     JSValue* vector = m_storage->m_vector;
    957     unsigned vectorEnd = min(m_storage->m_length, m_vectorLength);
     1147    ArrayStorage* storage = arrayStorage();
     1148
     1149    JSValue* vector = storage->m_vector;
     1150    unsigned vectorEnd = min(storage->m_length, m_vectorLength);
    9581151    unsigned i = 0;
    9591152    for (; i < vectorEnd; ++i) {
    … …  
    9641157    }
    9651158
    966     for (; i < m_storage->m_length; ++i)
     1159    for (; i < storage->m_length; ++i)
    9671160        args.append(get(exec, i));
    9681161}
    … …  
    9701163void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
    9711164{
    972     ASSERT(m_storage->m_length >= maxSize);
     1165    ASSERT(arrayStorage()->m_length >= maxSize);
    9731166    UNUSED_PARAM(maxSize);
    974     JSValue* vector = m_storage->m_vector;
     1167    JSValue* vector = m_vector;
    9751168    unsigned vectorEnd = min(maxSize, m_vectorLength);
    9761169    unsigned i = 0;
    … …  
    9901183    checkConsistency();
    9911184
    992     ArrayStorage* storage = m_storage;
    993 
    994     unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
     1185    ArrayStorage* storage = arrayStorage();
     1186
     1187    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
    9951188
    9961189    unsigned numDefined = 0;
    … …  
    9981191
    9991192    for (; numDefined < usedVectorLength; ++numDefined) {
    1000         JSValue v = storage->m_vector[numDefined];
     1193        JSValue v = m_vector[numDefined];
    10011194        if (!v || v.isUndefined())
    10021195            break;
    10031196    }
    10041197    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
    1005         JSValue v = storage->m_vector[i];
     1198        JSValue v = m_vector[i];
    10061199        if (v) {
    10071200            if (v.isUndefined())
    10081201                ++numUndefined;
    10091202            else
    1010                 storage->m_vector[numDefined++] = v;
     1203                m_vector[numDefined++] = v;
    10111204        }
    10121205    }
    … …  
    10211214            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
    10221215                return 0;
    1023             storage = m_storage;
     1216
     1217            storage = arrayStorage();
    10241218        }
    10251219
    10261220        SparseArrayValueMap::iterator end = map->end();
    10271221        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
    1028             storage->m_vector[numDefined++] = it->second;
     1222            m_vector[numDefined++] = it->second;
    10291223
    10301224        delete map;
    … …  
    10331227
    10341228    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
    1035         storage->m_vector[i] = jsUndefined();
     1229        m_vector[i] = jsUndefined();
    10361230    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
    1037         storage->m_vector[i] = JSValue();
     1231        m_vector[i] = JSValue();
    10381232
    10391233    storage->m_numValuesInVector = newUsedVectorLength;
    … …  
    10461240void* JSArray::subclassData() const
    10471241{
    1048     return m_storage->subclassData;
     1242    return arrayStorage()->subclassData;
    10491243}
    10501244
    10511245void JSArray::setSubclassData(void* d)
    10521246{
    1053     m_storage->subclassData = d;
     1247    arrayStorage()->subclassData = d;
    10541248}
    10551249
    … …  
    10581252void JSArray::checkConsistency(ConsistencyCheckType type)
    10591253{
    1060     ASSERT(m_storage);
     1254    ArrayStorage* storage = arrayStorage();
     1255
     1256    ASSERT(storage);
    10611257    if (type == SortConsistencyCheck)
    1062         ASSERT(!m_storage->m_sparseValueMap);
     1258        ASSERT(!storage->m_sparseValueMap);
    10631259
    10641260    unsigned numValuesInVector = 0;
    10651261    for (unsigned i = 0; i < m_vectorLength; ++i) {
    1066         if (JSValue value = m_storage->m_vector[i]) {
    1067             ASSERT(i < m_storage->m_length);
     1262        if (JSValue value = m_vector[i]) {
     1263            ASSERT(i < storage->m_length);
    10681264            if (type != DestructorConsistencyCheck)
    10691265                value.isUndefined(); // Likely to crash if the object was deallocated.
    … …  
    10711267        } else {
    10721268            if (type == SortConsistencyCheck)
    1073                 ASSERT(i >= m_storage->m_numValuesInVector);
    1074         }
    1075     }
    1076     ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
    1077     ASSERT(numValuesInVector <= m_storage->m_length);
    1078 
    1079     if (m_storage->m_sparseValueMap) {
    1080         SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
    1081         for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
     1269                ASSERT(i >= storage->m_numValuesInVector);
     1270        }
     1271    }
     1272    ASSERT(numValuesInVector == storage->m_numValuesInVector);
     1273    ASSERT(numValuesInVector <= storage->m_length);
     1274
     1275    if (storage->m_sparseValueMap) {
     1276        SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end();
     1277        for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) {
    10821278            unsigned index = it->first;
    1083             ASSERT(index < m_storage->m_length);
     1279            ASSERT(index < storage->m_length);
    10841280            ASSERT(index >= m_vectorLength);
    10851281            ASSERT(index <= MAX_ARRAY_INDEX);

  • trunk/JavaScriptCore/runtime/JSArray.h

    r64184 r64320  
    3030    typedef HashMap<unsigned, JSValue> SparseArrayValueMap;
    3131
     32    // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
     33    // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and
     34    // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that
     35    // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
     36    //     getStorage() - m_indexBias * sizeof(JSValue)
    3237    struct ArrayStorage {
    33         unsigned m_length;
     38        unsigned m_length; // The "length" property on the array
    3439        unsigned m_numValuesInVector;
    3540        SparseArrayValueMap* m_sparseValueMap;
    … …  
    6873
    6974        static JS_EXPORTDATA const ClassInfo info;
    70 
    71         unsigned length() const { return m_storage->m_length; }
     75       
     76        unsigned length() const { return arrayStorage()->m_length; }
    7277        void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray.
    7378
    … …  
    7984        JSValue pop();
    8085
    81         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
     86        void shiftCount(ExecState*, int count);
     87        void unshiftCount(ExecState*, int count);
     88
     89        bool canGetIndex(unsigned i) { return i < m_vectorLength && m_vector[i]; }
    8290        JSValue getIndex(unsigned i)
    8391        {
    8492            ASSERT(canGetIndex(i));
    85             return m_storage->m_vector[i];
     93            return m_vector[i];
    8694        }
    8795
    … …  
    9098        {
    9199            ASSERT(canSetIndex(i));
    92             JSValue& x = m_storage->m_vector[i];
     100           
     101            JSValue& x = m_vector[i];
    93102            if (!x) {
    94                 ++m_storage->m_numValuesInVector;
    95                 if (i >= m_storage->m_length)
    96                     m_storage->m_length = i + 1;
     103                ArrayStorage *storage = arrayStorage();
     104                ++storage->m_numValuesInVector;
     105                if (i >= storage->m_length)
     106                    storage->m_length = i + 1;
    97107            }
    98108            x = v;
    99109        }
    100 
     110       
    101111        void uncheckedSetIndex(unsigned i, JSValue v)
    102112        {
    103113            ASSERT(canSetIndex(i));
     114            ArrayStorage *storage = arrayStorage();
    104115#if CHECK_ARRAY_CONSISTENCY
    105             ASSERT(m_storage->m_inCompactInitialization);
     116            ASSERT(storage->m_inCompactInitialization);
    106117#endif
    107             m_storage->m_vector[i] = v;
     118            storage->m_vector[i] = v;
    108119        }
    109120
    … …  
    128139        void* subclassData() const;
    129140        void setSubclassData(void*);
     141       
     142        inline ArrayStorage *arrayStorage() const
     143        {
     144            return reinterpret_cast<ArrayStorage*>(reinterpret_cast<char*>(m_vector) - (sizeof(ArrayStorage) - sizeof(JSValue)));
     145        }
     146
     147        inline void setArrayStorage(ArrayStorage *storage)
     148        {
     149            m_vector = &storage->m_vector[0];
     150        }
    130151
    131152    private:
    … …  
    135156        void putSlowCase(ExecState*, unsigned propertyName, JSValue);
    136157
     158        unsigned getNewVectorLength(unsigned desiredLength);
    137159        bool increaseVectorLength(unsigned newLength);
     160        bool increaseVectorPrefixLength(unsigned newLength);
    138161       
    139162        unsigned compactForSorting();
    … …  
    142165        void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
    143166
    144         unsigned m_vectorLength;
    145         ArrayStorage* m_storage;
     167        unsigned m_vectorLength; // The valid length of m_vector
     168        int m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
     169        JSValue* m_vector; // Copy of ArrayStorage.m_vector.  Used for quick vector access and to materialize ArrayStorage ptr.
    146170    };
    147171
    … …  
    169193        JSObject::markChildrenDirect(markStack);
    170194       
    171         ArrayStorage* storage = m_storage;
     195        ArrayStorage* storage = arrayStorage();
    172196
    173197        unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength);
Note: See TracChangeset for help on using the changeset viewer.