Changeset 64320 in webkit for trunk/JavaScriptCore/runtime/JSArray.cpp

Timestamp:

Jul 29, 2010, 4:29:17 PM (15 years ago)

Author:

[email protected]

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 <​[email protected]> 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):

File:

• trunk/JavaScriptCore/runtime/JSArray.cpp (modified) (55 diffs)

trunk/JavaScriptCore/runtime/JSArray.cpp

@@ -79 +79 @@
 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
 
+// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
+// for an array that was created with a sepcified length (e.g. a = new Array(123))
+#define BASE_VECTOR_LEN 4U
+    
+// The upper bound to the size we'll grow a zero length array when the first element
+// is added.
+#define FIRST_VECTOR_GROW 4U
+
 // Our policy for when to use a vector and when to use a sparse map.
 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
@@ -86 +94 @@
 
 const ClassInfo JSArray::info = {"Array", 0, 0, 0};
+
+// We keep track of the size of the last array after it was grown.  We use this
+// as a simple heuristic for as the value to grow the next array from size 0.
+// This value is capped by the constant FIRST_VECTOR_GROW defined above.
+static unsigned lastArraySize = 0;
 
 static inline size_t storageSize(unsigned vectorLength)
@@ -101 +114 @@
 }
 
-static inline unsigned increasedVectorLength(unsigned newLength)
-{
-    ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
-
-    // Mathematically equivalent to:
-    //   increasedLength = (newLength * 3 + 1) / 2;
-    // or:
-    //   increasedLength = (unsigned)ceil(newLength * 1.5));
-    // This form is not prone to internal overflow.
-    unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
-    ASSERT(increasedLength >= newLength);
-
-    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
-}
-
 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
 {
@@ -134 +132 @@
     unsigned initialCapacity = 0;
 
-    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
+    ArrayStorage* storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
+    m_indexBias = 0;
+    setArrayStorage(storage);
     m_vectorLength = initialCapacity;
 
@@ -147 +147 @@
         initialCapacity = initialLength;
     else
-        initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
-
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
+        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
+    
+    ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
+    storage->m_length = initialLength;
+    m_indexBias = 0;
     m_vectorLength = initialCapacity;
-    m_storage->m_sparseValueMap = 0;
-    m_storage->subclassData = 0;
-    m_storage->reportedMapCapacity = 0;
+    setArrayStorage(storage);    
+    storage->m_sparseValueMap = 0;
+    storage->subclassData = 0;
+    storage->reportedMapCapacity = 0;
 
     if (creationMode == CreateCompact) {
 #if CHECK_ARRAY_CONSISTENCY
-        m_storage->m_inCompactInitialization = !!initialCapacity;
+        storage->m_inCompactInitialization = !!initialCapacity;
 #endif
-        m_storage->m_length = 0;
-        m_storage->m_numValuesInVector = initialCapacity;
+        storage->m_length = 0;
+        storage->m_numValuesInVector = initialCapacity;
     } else {
 #if CHECK_ARRAY_CONSISTENCY
-        m_storage->m_inCompactInitialization = false;
+        storage->m_inCompactInitialization = false;
 #endif
-        m_storage->m_length = initialLength;
-        m_storage->m_numValuesInVector = 0;
-        JSValue* vector = m_storage->m_vector;
+        storage->m_length = initialLength;
+        storage->m_numValuesInVector = 0;
+        JSValue* vector = m_vector;
         for (size_t i = 0; i < initialCapacity; ++i)
             vector[i] = JSValue();
@@ -173 +176 @@
 
     checkConsistency();
-
+    
     Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
 }
@@ -182 +185 @@
     unsigned initialCapacity = list.size();
 
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
-    m_storage->m_length = initialCapacity;
+    ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
+    m_indexBias = 0;
+    storage->m_length = initialCapacity;
     m_vectorLength = initialCapacity;
-    m_storage->m_numValuesInVector = initialCapacity;
-    m_storage->m_sparseValueMap = 0;
-    m_storage->subclassData = 0;
-    m_storage->reportedMapCapacity = 0;
+    storage->m_numValuesInVector = initialCapacity;
+    storage->m_sparseValueMap = 0;
+    storage->subclassData = 0;
+    storage->reportedMapCapacity = 0;
 #if CHECK_ARRAY_CONSISTENCY
-    m_storage->m_inCompactInitialization = false;
+    storage->m_inCompactInitialization = false;
 #endif
+    setArrayStorage(storage);
 
     size_t i = 0;
+    JSValue* vector = m_vector;
     ArgList::const_iterator end = list.end();
     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
-        m_storage->m_vector[i] = *it;
+        vector[i] = *it;
 
     checkConsistency();
@@ -208 +214 @@
     checkConsistency(DestructorConsistencyCheck);
 
-    delete m_storage->m_sparseValueMap;
-    fastFree(m_storage);
+    ArrayStorage* storage = arrayStorage();
+    delete storage->m_sparseValueMap;
+    char* realStorage = reinterpret_cast<char*>(storage) - (m_indexBias * sizeof(JSValue));
+    fastFree(realStorage);
 }
 
 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 {
-    ArrayStorage* storage = m_storage;
-
+    ArrayStorage* storage = arrayStorage();
+    
     if (i >= storage->m_length) {
         if (i > MAX_ARRAY_INDEX)
@@ -223 +231 @@
 
     if (i < m_vectorLength) {
-        JSValue& valueSlot = storage->m_vector[i];
+        JSValue& valueSlot = m_vector[i];
         if (valueSlot) {
             slot.setValueSlot(&valueSlot);
@@ -262 +270 @@
         return true;
     }
+
+    ArrayStorage* storage = arrayStorage();
     
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex) {
-        if (i >= m_storage->m_length)
+        if (i >= storage->m_length)
             return false;
         if (i < m_vectorLength) {
-            JSValue& value = m_storage->m_vector[i];
+            JSValue& value = m_vector[i];
             if (value) {
                 descriptor.setDescriptor(value, 0);
                 return true;
             }
-        } else if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
+        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
             if (i >= MIN_SPARSE_ARRAY_INDEX) {
                 SparseArrayValueMap::iterator it = map->find(i);
@@ -314 +324 @@
     checkConsistency();
 
-    unsigned length = m_storage->m_length;
+    ArrayStorage* storage = arrayStorage();
+
+    unsigned length = storage->m_length;
     if (i >= length && i <= MAX_ARRAY_INDEX) {
         length = i + 1;
-        m_storage->m_length = length;
+        storage->m_length = length;
     }
 
     if (i < m_vectorLength) {
-        JSValue& valueSlot = m_storage->m_vector[i];
+        JSValue& valueSlot = m_vector[i];
         if (valueSlot) {
             valueSlot = value;
@@ -328 +340 @@
         }
         valueSlot = value;
-        ++m_storage->m_numValuesInVector;
+        ++storage->m_numValuesInVector;
         checkConsistency();
         return;
@@ -338 +350 @@
 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
 {
-    ArrayStorage* storage = m_storage;
+    ArrayStorage* storage = arrayStorage();
+    
     SparseArrayValueMap* map = storage->m_sparseValueMap;
 
@@ -375 +388 @@
     if (!map || map->isEmpty()) {
         if (increaseVectorLength(i + 1)) {
-            storage = m_storage;
-            storage->m_vector[i] = value;
-            ++storage->m_numValuesInVector;
+            m_vector[i] = value;
+            ++arrayStorage()->m_numValuesInVector;
             checkConsistency();
         } else
@@ -386 +398 @@
     // Decide how many values it would be best to move from the map.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
-    unsigned newVectorLength = increasedVectorLength(i + 1);
+    unsigned newVectorLength = getNewVectorLength(i + 1);
     for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
         newNumValuesInVector += map->contains(j);
@@ -395 +407 @@
         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
         while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
-            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
+            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
                 proposedNewNumValuesInVector += map->contains(j);
@@ -405 +417 @@
     }
 
-    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {
+    int baseBias = m_indexBias * sizeof(JSValue);
+    char* baseStorage = reinterpret_cast<char*>(storage - baseBias);
+    
+    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
         throwOutOfMemoryError(exec);
         return;
     }
 
+    storage = reinterpret_cast<ArrayStorage*>(baseStorage + baseBias);
+    setArrayStorage(storage);
+    
     unsigned vectorLength = m_vectorLength;
 
     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
         for (unsigned j = vectorLength; j < newVectorLength; ++j)
-            storage->m_vector[j] = JSValue();
+            m_vector[j] = JSValue();
         if (i > MIN_SPARSE_ARRAY_INDEX)
             map->remove(i);
     } else {
         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
-            storage->m_vector[j] = JSValue();
+            m_vector[j] = JSValue();
         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
-            storage->m_vector[j] = map->take(j);
-    }
-
-    storage->m_vector[i] = value;
+            m_vector[j] = map->take(j);
+    }
+
+    ASSERT(i < newVectorLength);
 
     m_vectorLength = newVectorLength;
     storage->m_numValuesInVector = newNumValuesInVector;
 
-    m_storage = storage;
+    m_vector[i] = value;
 
     checkConsistency();
@@ -453 +471 @@
     checkConsistency();
 
-    ArrayStorage* storage = m_storage;
-
+    ArrayStorage* storage = arrayStorage();
+    
     if (i < m_vectorLength) {
-        JSValue& valueSlot = storage->m_vector[i];
+        JSValue& valueSlot = m_vector[i];
         if (!valueSlot) {
             checkConsistency();
@@ -492 +510 @@
     // which almost certainly means a different structure for PropertyNameArray.
 
-    ArrayStorage* storage = m_storage;
-
+    ArrayStorage* storage = arrayStorage();
+    
     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
-        if (storage->m_vector[i])
+        if (m_vector[i])
             propertyNames.add(Identifier::from(exec, i));
     }
@@ -512 +530 @@
 }
 
+ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
+{
+    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
+
+    unsigned increasedLength;
+    unsigned length = arrayStorage()->m_length;
+
+    if (desiredLength < length)
+        increasedLength = length;
+    else if (!m_vectorLength)
+        increasedLength = max(desiredLength, lastArraySize);
+    else {
+        // Mathematically equivalent to:
+        //   increasedLength = (newLength * 3 + 1) / 2;
+        // or:
+        //   increasedLength = (unsigned)ceil(newLength * 1.5));
+        // This form is not prone to internal overflow.
+        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
+    }
+
+    ASSERT(increasedLength >= desiredLength);
+
+    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
+
+    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
+}
+
 bool JSArray::increaseVectorLength(unsigned newLength)
 {
@@ -517 +562 @@
     // to the vector. Callers have to account for that, because they can do it more efficiently.
 
-    ArrayStorage* storage = m_storage;
+    ArrayStorage* storage = arrayStorage();
 
     unsigned vectorLength = m_vectorLength;
     ASSERT(newLength > vectorLength);
     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
-    unsigned newVectorLength = increasedVectorLength(newLength);
-
-    if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))
+    unsigned newVectorLength = getNewVectorLength(newLength);
+    int baseBias = m_indexBias * sizeof(JSValue);
+    char* baseStorage = reinterpret_cast<char*>(storage) - baseBias;
+
+    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage))
         return false;
+    
+    storage = reinterpret_cast<ArrayStorage*>(baseStorage + baseBias);
+    setArrayStorage(storage);
+
+    JSValue* vector = m_vector;
+    for (unsigned i = vectorLength; i < newVectorLength; ++i)
+        vector[i] = JSValue();
 
     m_vectorLength = newVectorLength;
-
-    for (unsigned i = vectorLength; i < newVectorLength; ++i)
-        storage->m_vector[i] = JSValue();
-
-    m_storage = storage;
-
+    
     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
 
     return true;
 }
+
+bool JSArray::increaseVectorPrefixLength(unsigned newLength)
+{
+    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
+    // to the vector. Callers have to account for that, because they can do it more efficiently.
+    
+    ArrayStorage* storage = arrayStorage();
+    ArrayStorage* newStorage;
+    
+    unsigned vectorLength = m_vectorLength;
+    ASSERT(newLength > vectorLength);
+    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
+    unsigned newVectorLength = getNewVectorLength(newLength);
+    char* baseStorage = reinterpret_cast<char*>(storage) - (m_indexBias * sizeof(JSValue));
+    
+    char* newBaseStorage = reinterpret_cast<char*>(fastMalloc(storageSize(newVectorLength + m_indexBias)));
+    if (!newBaseStorage)
+        return false;
+    
+    m_indexBias += newVectorLength - newLength;
+    int newStorageOffset = m_indexBias * sizeof(JSValue);
+    
+    newStorage = reinterpret_cast<ArrayStorage*>(newBaseStorage + newStorageOffset);
+    
+    memcpy(newStorage, storage, storageSize(0));
+    memcpy(&newStorage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], storage->m_length * sizeof(JSValue));
+    
+    m_vectorLength = newLength;
+    
+    fastFree(baseStorage);
+
+    setArrayStorage(newStorage);
+    
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+    
+    return true;
+}
+    
 
 void JSArray::setLength(unsigned newLength)
@@ -548 +635 @@
 #endif
 
-    ArrayStorage* storage = m_storage;
-
-    unsigned length = m_storage->m_length;
+    ArrayStorage* storage = arrayStorage();
+    
+    unsigned length = storage->m_length;
 
     if (newLength < length) {
         unsigned usedVectorLength = min(length, m_vectorLength);
         for (unsigned i = newLength; i < usedVectorLength; ++i) {
-            JSValue& valueSlot = storage->m_vector[i];
+            JSValue& valueSlot = m_vector[i];
             bool hadValue = valueSlot;
             valueSlot = JSValue();
@@ -575 +662 @@
     }
 
-    m_storage->m_length = newLength;
+    storage->m_length = newLength;
 
     checkConsistency();
@@ -584 +671 @@
     checkConsistency();
 
-    unsigned length = m_storage->m_length;
+    ArrayStorage* storage = arrayStorage();
+    
+    unsigned length = storage->m_length;
     if (!length)
         return jsUndefined();
@@ -593 +682 @@
 
     if (length < m_vectorLength) {
-        JSValue& valueSlot = m_storage->m_vector[length];
+        JSValue& valueSlot = m_vector[length];
         if (valueSlot) {
-            --m_storage->m_numValuesInVector;
+            --storage->m_numValuesInVector;
             result = valueSlot;
             valueSlot = JSValue();
@@ -602 +691 @@
     } else {
         result = jsUndefined();
-        if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
+        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
             SparseArrayValueMap::iterator it = map->find(length);
             if (it != map->end()) {
@@ -609 +698 @@
                 if (map->isEmpty()) {
                     delete map;
-                    m_storage->m_sparseValueMap = 0;
+                    storage->m_sparseValueMap = 0;
                 }
             }
@@ -615 +704 @@
     }
 
-    m_storage->m_length = length;
+    storage->m_length = length;
 
     checkConsistency();
@@ -625 +714 @@
 {
     checkConsistency();
-
-    if (m_storage->m_length < m_vectorLength) {
-        m_storage->m_vector[m_storage->m_length] = value;
-        ++m_storage->m_numValuesInVector;
-        ++m_storage->m_length;
+    
+    ArrayStorage* storage = arrayStorage();
+
+    if (storage->m_length < m_vectorLength) {
+        m_vector[storage->m_length] = value;
+        ++storage->m_numValuesInVector;
+        ++storage->m_length;
         checkConsistency();
         return;
     }
 
-    if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
-        SparseArrayValueMap* map = m_storage->m_sparseValueMap;
+    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
+        SparseArrayValueMap* map = storage->m_sparseValueMap;
         if (!map || map->isEmpty()) {
-            if (increaseVectorLength(m_storage->m_length + 1)) {
-                m_storage->m_vector[m_storage->m_length] = value;
-                ++m_storage->m_numValuesInVector;
-                ++m_storage->m_length;
+            if (increaseVectorLength(storage->m_length + 1)) {
+                storage = arrayStorage();
+                m_vector[storage->m_length] = value;
+                ++storage->m_numValuesInVector;
+                ++storage->m_length;
                 checkConsistency();
                 return;
@@ -650 +742 @@
     }
 
-    putSlowCase(exec, m_storage->m_length++, value);
+    putSlowCase(exec, storage->m_length++, value);
+}
+
+void JSArray::shiftCount(ExecState* exec, int count)
+{
+    ASSERT(count > 0);
+    
+    ArrayStorage* storage = arrayStorage();
+    
+    unsigned oldLength = storage->m_length;
+    
+    if (!oldLength)
+        return;
+    
+    if (oldLength != storage->m_numValuesInVector) {
+        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
+        // which means we need to go through each entry looking for the the "empty"
+        // slots and then fill them with possible properties.  See ECMA spec.
+        // 15.4.4.9 steps 11 through 13.
+        for (unsigned i = count; i < oldLength; ++i) {
+            if ((i >= m_vectorLength) || (!m_vector[i])) {
+                PropertySlot slot(this);
+                JSValue p = prototype();
+                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
+                    put(exec, i, slot.getValue(exec, i));
+            }
+        }
+
+        storage = arrayStorage(); // The put() above could have grown the vector and realloc'ed storage.
+
+        // Need to decrement numValuesInvector based on number of real entries
+        for (unsigned i = 0; i < (unsigned)count; ++i)
+            if ((i < m_vectorLength) && (m_vector[i]))
+                --storage->m_numValuesInVector;
+    } else
+        storage->m_numValuesInVector -= count;
+    
+    storage->m_length -= count;
+    
+    if (m_vectorLength) {
+        count = min(m_vectorLength, (unsigned)count);
+        
+        m_vectorLength -= count;
+        
+        if (m_vectorLength) {
+            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
+            memmove(newBaseStorage, storage, storageSize(0));
+            storage = reinterpret_cast<ArrayStorage*>(newBaseStorage);
+
+            m_indexBias += count;
+            setArrayStorage(storage);
+        }
+    }
+}
+    
+void JSArray::unshiftCount(ExecState* exec, int count)
+{
+    ArrayStorage* storage = arrayStorage();
+
+    ASSERT(m_indexBias >= 0);
+    ASSERT(count >= 0);
+    
+    unsigned length = storage->m_length;
+    
+    if (length != storage->m_numValuesInVector) {
+        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
+        // which means we need to go through each entry looking for the the "empty"
+        // slots and then fill them with possible properties.  See ECMA spec.
+        // 15.4.4.13 steps 8 through 10.
+        for (unsigned i = 0; i < length; ++i) {
+            if ((i >= m_vectorLength) || (!m_vector[i])) {
+                PropertySlot slot(this);
+                JSValue p = prototype();
+                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
+                    put(exec, i, slot.getValue(exec, i));
+            }
+        }
+    }
+    
+    storage = arrayStorage(); // The put() above could have grown the vector and realloc'ed storage.
+    
+    if (m_indexBias >= count) {
+        m_indexBias -= count;
+        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
+        memmove(newBaseStorage, storage, storageSize(0));
+        storage = reinterpret_cast<ArrayStorage*>(newBaseStorage);
+        setArrayStorage(storage);
+        m_vectorLength += count;
+    } else if ((!m_indexBias) && (!increaseVectorPrefixLength(m_vectorLength + count))) {
+        throwOutOfMemoryError(exec);
+        return;
+    }
 }
 
@@ -676 +859 @@
 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
+    ArrayStorage* storage = arrayStorage();
+
     unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (m_storage->m_sparseValueMap) {
+    if (storage->m_sparseValueMap) {
         throwOutOfMemoryError(exec);
         return;
@@ -686 +871 @@
         
     bool allValuesAreNumbers = true;
-    size_t size = m_storage->m_numValuesInVector;
+    size_t size = storage->m_numValuesInVector;
     for (size_t i = 0; i < size; ++i) {
-        if (!m_storage->m_vector[i].isNumber()) {
+        if (!m_vector[i].isNumber()) {
             allValuesAreNumbers = false;
             break;
@@ -700 +885 @@
     // also don't require mergesort's stability, since there's no user visible
     // side-effect from swapping the order of equal primitive values.
-    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
+    qsort(m_vector, size, sizeof(JSValue), compareNumbersForQSort);
 
     checkConsistency(SortConsistencyCheck);
@@ -707 +892 @@
 void JSArray::sort(ExecState* exec)
 {
+    ArrayStorage* storage = arrayStorage();
+
     unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (m_storage->m_sparseValueMap) {
+    if (storage->m_sparseValueMap) {
         throwOutOfMemoryError(exec);
         return;
@@ -728 +915 @@
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
-        JSValue value = m_storage->m_vector[i];
+        JSValue value = m_vector[i];
         ASSERT(!value.isUndefined());
         values[i].first = value;
@@ -760 +947 @@
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-        m_storage->m_vector[i] = values[i].first;
+        m_vector[i] = values[i].first;
 
     checkConsistency(SortConsistencyCheck);
@@ -847 +1034 @@
     checkConsistency();
 
+    ArrayStorage* storage = arrayStorage();
+
     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
 
     // The maximum tree depth is compiled in - but the caller is clearly up to no good
     // if a larger array is passed.
-    ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
-    if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
-        return;
-
-    if (!m_storage->m_length)
-        return;
-
-    unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
+    ASSERT(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+    if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
+        return;
+
+    if (!storage->m_length)
+        return;
+
+    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
 
     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
@@ -866 +1055 @@
     tree.abstractor().m_compareCallData = &callData;
     tree.abstractor().m_globalThisValue = exec->globalThisValue();
-    tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
+    tree.abstractor().m_nodes.resize(usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0));
 
     if (callType == CallTypeJS)
@@ -884 +1073 @@
     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
     for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = m_storage->m_vector[numDefined];
+        JSValue v = m_vector[numDefined];
         if (!v || v.isUndefined())
             break;
@@ -891 +1080 @@
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = m_storage->m_vector[i];
+        JSValue v = m_vector[i];
         if (v) {
             if (v.isUndefined())
@@ -905 +1094 @@
     unsigned newUsedVectorLength = numDefined + numUndefined;
 
-    if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
+    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         newUsedVectorLength += map->size();
         if (newUsedVectorLength > m_vectorLength) {
@@ -914 +1103 @@
             }
         }
+        
+        storage = arrayStorage();
 
         SparseArrayValueMap::iterator end = map->end();
@@ -923 +1114 @@
 
         delete map;
-        m_storage->m_sparseValueMap = 0;
+        storage->m_sparseValueMap = 0;
     }
 
@@ -935 +1126 @@
     iter.start_iter_least(tree);
     for (unsigned i = 0; i < numDefined; ++i) {
-        m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
+        m_vector[i] = tree.abstractor().m_nodes[*iter].value;
         ++iter;
     }
@@ -941 +1132 @@
     // Put undefined values back in.
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        m_storage->m_vector[i] = jsUndefined();
+        m_vector[i] = jsUndefined();
 
     // Ensure that unused values in the vector are zeroed out.
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        m_storage->m_vector[i] = JSValue();
-
-    m_storage->m_numValuesInVector = newUsedVectorLength;
+        m_vector[i] = JSValue();
+
+    storage->m_numValuesInVector = newUsedVectorLength;
 
     checkConsistency(SortConsistencyCheck);
@@ -954 +1145 @@
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {
-    JSValue* vector = m_storage->m_vector;
-    unsigned vectorEnd = min(m_storage->m_length, m_vectorLength);
+    ArrayStorage* storage = arrayStorage();
+
+    JSValue* vector = storage->m_vector;
+    unsigned vectorEnd = min(storage->m_length, m_vectorLength);
     unsigned i = 0;
     for (; i < vectorEnd; ++i) {
@@ -964 +1157 @@
     }
 
-    for (; i < m_storage->m_length; ++i)
+    for (; i < storage->m_length; ++i)
         args.append(get(exec, i));
 }
@@ -970 +1163 @@
 void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
 {
-    ASSERT(m_storage->m_length >= maxSize);
+    ASSERT(arrayStorage()->m_length >= maxSize);
     UNUSED_PARAM(maxSize);
-    JSValue* vector = m_storage->m_vector;
+    JSValue* vector = m_vector;
     unsigned vectorEnd = min(maxSize, m_vectorLength);
     unsigned i = 0;
@@ -990 +1183 @@
     checkConsistency();
 
-    ArrayStorage* storage = m_storage;
-
-    unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
+    ArrayStorage* storage = arrayStorage();
+
+    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
 
     unsigned numDefined = 0;
@@ -998 +1191 @@
 
     for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = storage->m_vector[numDefined];
+        JSValue v = m_vector[numDefined];
         if (!v || v.isUndefined())
             break;
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = storage->m_vector[i];
+        JSValue v = m_vector[i];
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
             else
-                storage->m_vector[numDefined++] = v;
+                m_vector[numDefined++] = v;
         }
     }
@@ -1021 +1214 @@
             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
                 return 0;
-            storage = m_storage;
+
+            storage = arrayStorage();
         }
 
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
-            storage->m_vector[numDefined++] = it->second;
+            m_vector[numDefined++] = it->second;
 
         delete map;
@@ -1033 +1227 @@
 
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        storage->m_vector[i] = jsUndefined();
+        m_vector[i] = jsUndefined();
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        storage->m_vector[i] = JSValue();
+        m_vector[i] = JSValue();
 
     storage->m_numValuesInVector = newUsedVectorLength;
@@ -1046 +1240 @@
 void* JSArray::subclassData() const
 {
-    return m_storage->subclassData;
+    return arrayStorage()->subclassData;
 }
 
 void JSArray::setSubclassData(void* d)
 {
-    m_storage->subclassData = d;
+    arrayStorage()->subclassData = d;
 }
 
@@ -1058 +1252 @@
 void JSArray::checkConsistency(ConsistencyCheckType type)
 {
-    ASSERT(m_storage);
+    ArrayStorage* storage = arrayStorage();
+
+    ASSERT(storage);
     if (type == SortConsistencyCheck)
-        ASSERT(!m_storage->m_sparseValueMap);
+        ASSERT(!storage->m_sparseValueMap);
 
     unsigned numValuesInVector = 0;
     for (unsigned i = 0; i < m_vectorLength; ++i) {
-        if (JSValue value = m_storage->m_vector[i]) {
-            ASSERT(i < m_storage->m_length);
+        if (JSValue value = m_vector[i]) {
+            ASSERT(i < storage->m_length);
             if (type != DestructorConsistencyCheck)
                 value.isUndefined(); // Likely to crash if the object was deallocated.
@@ -1071 +1267 @@
         } else {
             if (type == SortConsistencyCheck)
-                ASSERT(i >= m_storage->m_numValuesInVector);
-        }
-    }
-    ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
-    ASSERT(numValuesInVector <= m_storage->m_length);
-
-    if (m_storage->m_sparseValueMap) {
-        SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
-        for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
+                ASSERT(i >= storage->m_numValuesInVector);
+        }
+    }
+    ASSERT(numValuesInVector == storage->m_numValuesInVector);
+    ASSERT(numValuesInVector <= storage->m_length);
+
+    if (storage->m_sparseValueMap) {
+        SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end();
+        for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) {
             unsigned index = it->first;
-            ASSERT(index < m_storage->m_length);
+            ASSERT(index < storage->m_length);
             ASSERT(index >= m_vectorLength);
             ASSERT(index <= MAX_ARRAY_INDEX);