Changeset 153374 in webkit for trunk/Source/JavaScriptCore/runtime/JSObject.cpp

Timestamp:

Jul 26, 2013, 11:07:34 AM (12 years ago)

Author:

[email protected]

Message:

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):

LayoutTests:

Added new regression test for put-by-val-ing to a blank indexing type with a large index.
This fix is ~800x speedup on this regression test :-o

• fast/js/regress/put-by-val-large-index-blank-indexing-type.html: Added.
• fast/js/regress/script-tests/put-by-val-large-index-blank-indexing-type.js: Added.

File:

• trunk/Source/JavaScriptCore/runtime/JSObject.cpp (modified) (5 diffs)

trunk/Source/JavaScriptCore/runtime/JSObject.cpp

@@ -1854 +1854 @@
     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);
@@ -1902 +1903 @@
     // 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());
     
@@ -1910 +1911 @@
 
         // 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();
@@ -1977 +1980 @@
             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));
@@ -2057 +2060 @@
                 !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();