Setting a large numeric property on an object causes it to allocate a huge backing store

https://bugs.webkit.org/show_bug.cgi?id=118914

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

There are two distinct actions that we're trying to optimize for:

new Array(100000);

and:

a = [];
a[100000] = 42;

In the first case, the programmer has indicated that they expect this Array to be very big,
so they should get a contiguous array up until some threshold, above which we perform density
calculations to see if it is indeed dense enough to warrant being contiguous.

In the second case, the programmer hasn't indicated anything about the size of the Array, so
we should be more conservative and assume it should be sparse until we've proven otherwise.

Currently both of those cases are handled by MIN_SPARSE_ARRAY_INDEX. We should distinguish
between them for the purposes of not over-allocating large backing stores like we see on
http://www.peekanalytics.com/burgerjoints/

The way that we'll do this is to keep the MIN_SPARSE_ARRAY_INDEX for the first case, and
introduce a new heuristic for the second case. If we are putting to an index above a certain
threshold (say, 1000) and it is beyond the length of the array, then we will use a sparse
map instead. So for example, in the second case above the empty array has a blank indexing
type and a length of 0. We put-by-val to an index > 1000 and > a.length, so we'll use a sparse map.

This fix is ~800x speedup on the accompanying regression test :-o

* runtime/ArrayConventions.h:
(JSC::indexIsSufficientlyBeyondLengthForSparseMap):
* runtime/JSObject.cpp:
(JSC::JSObject::putByIndexBeyondVectorLengthWithoutAttributes):
(JSC::JSObject::putByIndexBeyondVectorLengthWithArrayStorage):
(JSC::JSObject::putByIndexBeyondVectorLength):
(JSC::JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153374 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Change-Id: I1c29992d6e09c9d523a8093e76e3848a9581ce45
Reviewed-by: Jocelyn Turcotte <jocelyn.turcotte@digia.com>

2 files changed, 16 insertions, 5 deletions

diff --git a/Source/JavaScriptCore/runtime/ArrayConventions.h b/Source/JavaScriptCore/runtime/ArrayConventions.h
index 3177c6c97..e5ef96336 100644
--- a/Source/JavaScriptCore/runtime/ArrayConventions.h
+++ b/Source/JavaScriptCore/runtime/ArrayConventions.h
@@ -71,6 +71,8 @@ namespace JSC {
 // is added.
 #define FIRST_VECTOR_GROW 4U
 
+#define MIN_BEYOND_LENGTH_SPARSE_INDEX 1000
+
 // 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.
 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
@@ -82,6 +84,11 @@ inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
     return length / minDensityMultiplier <= numValues;
 }
 
+inline bool indexIsSufficientlyBeyondLengthForSparseMap(unsigned i, unsigned length)
+{
+    return i >= MIN_BEYOND_LENGTH_SPARSE_INDEX && i > length;
+}
+
 inline IndexingHeader indexingHeaderForArray(unsigned length, unsigned vectorLength)
 {
     IndexingHeader result;
diff --git a/Source/JavaScriptCore/runtime/JSObject.cpp b/Source/JavaScriptCore/runtime/JSObject.cpp
index 48fc23186..47e424097 100644
--- a/Source/JavaScriptCore/runtime/JSObject.cpp
+++ b/Source/JavaScriptCore/runtime/JSObject.cpp
@@ -1872,7 +1872,8 @@ void JSObject::putByIndexBeyondVectorLengthWithoutAttributes(ExecState* exec, un
     
     if (i >= MAX_ARRAY_INDEX - 1
         || (i >= MIN_SPARSE_ARRAY_INDEX
-            && !isDenseEnoughForVector(i, countElements<indexingShape>(m_butterfly)))) {
+            && !isDenseEnoughForVector(i, countElements<indexingShape>(m_butterfly)))
+        || indexIsSufficientlyBeyondLengthForSparseMap(i, m_butterfly->vectorLength())) {
         ASSERT(i <= MAX_ARRAY_INDEX);
         ensureArrayStorageSlow(vm);
         SparseArrayValueMap* map = allocateSparseIndexMap(vm);
@@ -1920,7 +1921,7 @@ void JSObject::putByIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, uns
     
     // First, handle cases where we don't currently have a sparse map.
     if (LIKELY(!map)) {
-        // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
+        // If the array is not extensible, we should have entered dictionary mode, and created the sparse map.
         ASSERT(isExtensible());
     
         // Update m_length if necessary.
@@ -1928,7 +1929,9 @@ void JSObject::putByIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, uns
             storage->setLength(i + 1);
 
         // Check that it is sensible to still be using a vector, and then try to grow the vector.
-        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(vm, i + 1))) {
+        if (LIKELY(!indexIsSufficientlyBeyondLengthForSparseMap(i, storage->vectorLength())
+            && isDenseEnoughForVector(i, storage->m_numValuesInVector)
+            && increaseVectorLength(vm, i + 1))) {
             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
             storage = arrayStorage();
             storage->m_vector[i].set(vm, this, value);
@@ -1995,7 +1998,7 @@ void JSObject::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue
                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(vm));
             break;
         }
-        if (i >= MIN_SPARSE_ARRAY_INDEX) {
+        if (indexIsSufficientlyBeyondLengthForSparseMap(i, 0) || i >= MIN_SPARSE_ARRAY_INDEX) {
             putByIndexBeyondVectorLengthWithArrayStorage(
                 exec, i, value, shouldThrow, createArrayStorage(vm, 0, 0));
             break;
@@ -2075,7 +2078,8 @@ bool JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage(ExecState* exec,
         if (LIKELY(
                 !attributes
                 && (isDenseEnoughForVector(i, storage->m_numValuesInVector))
-                && increaseVectorLength(vm, i + 1))) {
+                && increaseVectorLength(vm, i + 1)
+                && !indexIsSufficientlyBeyondLengthForSparseMap(i, storage->vectorLength()))) {
             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
             storage = arrayStorage();
             storage->m_vector[i].set(vm, this, value);