[builtins] Cap and grow Array.p.join's internal buffer.
This allows very large arrays being joined to incrementally,
on-demand allocate the internal buffer. Previously, join
would allocate the buffer upfront and all at once. Large,
sparse arrays will use less memory.
Bug: chromium:897404
Change-Id: Id914b14a7c55a62834f63ad602bdb45363249075
Reviewed-on: https://chromium-review.googlesource.com/c/1303538
Commit-Queue: Peter Wong <peter.wm.wong@gmail.com>
Reviewed-by: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#57075}
diff --git a/src/builtins/array-join.tq b/src/builtins/array-join.tq
index d5f6531..5bc20d3 100644
--- a/src/builtins/array-join.tq
+++ b/src/builtins/array-join.tq
@@ -109,6 +109,27 @@
}
}
+ // Stores an element to a fixed array and return the fixed array. If the fixed
+ // array is not large enough, create and return a new, larger fixed array that
+ // contains all previously elements and the new element.
+ macro StoreAndGrowFixedArray<T: type>(
+ fixedArray: FixedArray, index: intptr, element: T): FixedArray {
+ const length: intptr = fixedArray.length_intptr;
+ assert(index <= length);
+ if (index < length) {
+ fixedArray[index] = element;
+ return fixedArray;
+ } else
+ deferred {
+ const newLength: intptr = CalculateNewElementsCapacity(length);
+ assert(index < newLength);
+ const newfixedArray: FixedArray =
+ ExtractFixedArray(fixedArray, 0, length, newLength, kFixedArrays);
+ newfixedArray[index] = element;
+ return newfixedArray;
+ }
+ }
+
// Contains the information necessary to create a single, separator delimited,
// flattened one or two byte string.
// The buffer is maintained and updated by BufferInit(), BufferAdd(),
@@ -143,8 +164,8 @@
}
macro BufferInit(len: uintptr, sep: String): Buffer {
- const cappedBufferSize: intptr = len > kFixedArrayMaxLength ?
- FromConstexpr<intptr>(kFixedArrayMaxLength) :
+ const cappedBufferSize: intptr = len > kMaxNewSpaceFixedArrayElements ?
+ kMaxNewSpaceFixedArrayElements :
Signed(len);
assert(cappedBufferSize > 0);
const fixedArray: FixedArray = AllocateZeroedFixedArray(cappedBufferSize);
@@ -164,11 +185,11 @@
const totalStringLength: intptr =
AddStringLength(buffer.totalStringLength, str.length);
let index: intptr = buffer.index;
- assert(index < buffer.fixedArray.length_intptr);
- buffer.fixedArray[index++] = str;
+ const fixedArray: FixedArray =
+ StoreAndGrowFixedArray<String>(buffer.fixedArray, index++, str);
const isOneByte: bool =
HasOnlyOneByteChars(str.instanceType) & buffer.isOneByte;
- return Buffer{buffer.fixedArray, index, totalStringLength, isOneByte};
+ return Buffer{fixedArray, index, totalStringLength, isOneByte};
}
macro BufferAddSeparators(implicit context: Context)(
@@ -187,16 +208,12 @@
const totalStringLength: intptr =
AddStringLength(buffer.totalStringLength, sepsLen);
let index: intptr = buffer.index;
+ let fixedArray: FixedArray = buffer.fixedArray;
if (write) deferred {
- assert(index < buffer.fixedArray.length_intptr);
- buffer.fixedArray[index++] = Convert<Smi>(nofSeparatorsInt);
+ fixedArray = StoreAndGrowFixedArray<Smi>(
+ buffer.fixedArray, index++, Convert<Smi>(nofSeparatorsInt));
}
- return Buffer{
- buffer.fixedArray,
- index,
- totalStringLength,
- buffer.isOneByte
- };
+ return Buffer{fixedArray, index, totalStringLength, buffer.isOneByte};
}
macro BufferJoin(implicit context: Context)(
@@ -381,10 +398,8 @@
}
// If no open slots were found, grow the stack and add receiver to the end.
- const newCapacity: intptr = CalculateNewElementsCapacity(capacity);
const newStack: FixedArray =
- ExtractFixedArray(stack, 0, capacity, newCapacity, kFixedArrays);
- newStack[capacity] = receiver;
+ StoreAndGrowFixedArray<JSReceiver>(stack, capacity, receiver);
SetJoinStack(newStack);
return True;
}
@@ -460,8 +475,8 @@
const len: Number = GetLengthProperty(o);
// 3. If separator is undefined, let sep be the single-element String ",".
// 4. Else, let sep be ? ToString(separator).
- let sep: String = sepObj == Undefined ? FromConstexpr<String>(',') :
- ToString_Inline(context, sepObj);
+ let sep: String =
+ sepObj == Undefined ? ',' : ToString_Inline(context, sepObj);
try {
// Fast paths for zero elements
if (len == 0) goto IfReturnEmpty;
diff --git a/test/mjsunit/regress/regress-crbug-897404.js b/test/mjsunit/regress/regress-crbug-897404.js
new file mode 100644
index 0000000..7e8b48d
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-897404.js
@@ -0,0 +1,16 @@
+// Copyright 2018 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+function TestError() {}
+
+const a = new Array(2**32 - 1);
+
+// Force early exit to avoid an unreasonably long test.
+a[0] = {
+ toString() { throw new TestError(); }
+};
+
+// Verify join throws test error and does not fail due to asserts (Negative
+// length fixed array allocation).
+assertThrows(() => a.join(), TestError);