- Revision
- 153374
- Author
- [email protected]
- Date
- 2013-07-26 11:07:34 -0700 (Fri, 26 Jul 2013)
Log 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/_javascript_Core:
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.
Modified Paths
Added Paths
Diff
Modified: trunk/LayoutTests/ChangeLog (153373 => 153374)
--- trunk/LayoutTests/ChangeLog 2013-07-26 16:22:48 UTC (rev 153373)
+++ trunk/LayoutTests/ChangeLog 2013-07-26 18:07:34 UTC (rev 153374)
@@ -1,3 +1,16 @@
+2013-07-19 Mark Hahnenberg <[email protected]>
+
+ 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.
+
+ 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.
+
2013-07-25 Ryosuke Niwa <[email protected]>
Fix document leak when selection is created inside the document
Added: trunk/LayoutTests/fast/js/regress/put-by-val-large-index-blank-indexing-type-expected.txt (0 => 153374)
--- trunk/LayoutTests/fast/js/regress/put-by-val-large-index-blank-indexing-type-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/js/regress/put-by-val-large-index-blank-indexing-type-expected.txt 2013-07-26 18:07:34 UTC (rev 153374)
@@ -0,0 +1,10 @@
+JSRegress/put-by-val-large-index-blank-indexing-type
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/fast/js/regress/put-by-val-large-index-blank-indexing-type.html (0 => 153374)
--- trunk/LayoutTests/fast/js/regress/put-by-val-large-index-blank-indexing-type.html (rev 0)
+++ trunk/LayoutTests/fast/js/regress/put-by-val-large-index-blank-indexing-type.html 2013-07-26 18:07:34 UTC (rev 153374)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/fast/js/regress/script-tests/put-by-val-large-index-blank-indexing-type.js (0 => 153374)
--- trunk/LayoutTests/fast/js/regress/script-tests/put-by-val-large-index-blank-indexing-type.js (rev 0)
+++ trunk/LayoutTests/fast/js/regress/script-tests/put-by-val-large-index-blank-indexing-type.js 2013-07-26 18:07:34 UTC (rev 153374)
@@ -0,0 +1,16 @@
+var global = [];
+
+function foo(o, id) {
+ o[id] = 42;
+}
+
+var sum = 0;
+for (var i = 0; i < 20000; i++) {
+ var o = {};
+ foo(o, i);
+ sum += o[i];
+ global.push(o);
+}
+
+if (sum != 42 * 20000)
+ throw "Error!"
Modified: trunk/Source/_javascript_Core/ChangeLog (153373 => 153374)
--- trunk/Source/_javascript_Core/ChangeLog 2013-07-26 16:22:48 UTC (rev 153373)
+++ trunk/Source/_javascript_Core/ChangeLog 2013-07-26 18:07:34 UTC (rev 153374)
@@ -1,3 +1,46 @@
+2013-07-19 Mark Hahnenberg <[email protected]>
+
+ 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.
+
+ 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):
+
2013-07-26 Julien Brianceau <[email protected]>
REGRESSION(FTL): Fix lots of crashes in sh4 baseline JIT.
Modified: trunk/Source/_javascript_Core/runtime/ArrayConventions.h (153373 => 153374)
--- trunk/Source/_javascript_Core/runtime/ArrayConventions.h 2013-07-26 16:22:48 UTC (rev 153373)
+++ trunk/Source/_javascript_Core/runtime/ArrayConventions.h 2013-07-26 18:07:34 UTC (rev 153374)
@@ -71,6 +71,8 @@
// 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 @@
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;
Modified: trunk/Source/_javascript_Core/runtime/JSObject.cpp (153373 => 153374)
--- trunk/Source/_javascript_Core/runtime/JSObject.cpp 2013-07-26 16:22:48 UTC (rev 153373)
+++ trunk/Source/_javascript_Core/runtime/JSObject.cpp 2013-07-26 18:07:34 UTC (rev 153374)
@@ -1853,7 +1853,8 @@
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);
@@ -1901,7 +1902,7 @@
// 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.
@@ -1909,7 +1910,9 @@
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);
@@ -1976,7 +1979,7 @@
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;
@@ -2056,7 +2059,8 @@
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);
