Skip to content

Commit 696b2ce

Browse files
ripsawridgeCommit Bot
ripsawridge
authored and
Commit Bot
committed
[Builtins] Array.prototype.splice performance improvements
a) The current size of the backing store for the array under splice wasn't considered. Additionally, allocate the array with the normal growing strategy. b) Use primitives memcpy and memmove when appropriate. These calls are wrapped in new CSA functions MoveElements and CopyElements, which use the C functions when a write barrier isn't needed (otherwise they just copy elements in a loop). Bug: chromium:880780 Change-Id: I39a917c71036f52250c68f2cced77a1c24f97b67 Reviewed-on: https://chromium-review.googlesource.com/c/1243104 Commit-Queue: Michael Stanton <[email protected]> Reviewed-by: Tobias Tebbi <[email protected]> Cr-Commit-Position: refs/heads/master@{#56534}
1 parent d4f749c commit 696b2ce

4 files changed

Lines changed: 290 additions & 41 deletions

File tree

‎src/builtins/array-splice.tq‎

Lines changed: 62 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,12 @@ module array {
99
// zero-length input FixedArray is handled here.
1010
macro Extract<FixedArrayType: type>(
1111
elements: FixedArrayBase, first: Smi, count: Smi,
12-
capacity: Smi): FixedArrayType {
13-
return UnsafeCast<FixedArrayType>(
12+
capacity: Smi): FixedArrayType;
13+
14+
Extract<FixedArray>(
15+
elements: FixedArrayBase, first: Smi, count: Smi,
16+
capacity: Smi): FixedArray {
17+
return UnsafeCast<FixedArray>(
1418
ExtractFixedArray(elements, first, count, capacity));
1519
}
1620

@@ -24,63 +28,80 @@ module array {
2428
ExtractFixedArray(elements, first, count, capacity));
2529
}
2630

31+
macro DoMoveElements<FixedArrayType: type>(
32+
elements: FixedArrayType, dstIndex: Smi, srcIndex: Smi,
33+
count: Smi): void {
34+
TorqueMoveElements(
35+
elements, Convert<intptr>(dstIndex), Convert<intptr>(srcIndex),
36+
Convert<intptr>(count));
37+
}
38+
39+
macro StoreHoles<FixedArrayType: type>(
40+
elements: FixedArrayType, holeStartIndex: Smi, holeEndIndex: Smi): void {
41+
for (let i: Smi = holeStartIndex; i < holeEndIndex; i++) {
42+
StoreArrayHole(elements, i);
43+
}
44+
}
45+
46+
macro DoCopyElements<FixedArrayType: type>(
47+
dstElements: FixedArrayType, dstIndex: Smi, srcElements: FixedArrayType,
48+
srcIndex: Smi, count: Smi): void {
49+
TorqueCopyElements(
50+
dstElements, Convert<intptr>(dstIndex), srcElements,
51+
Convert<intptr>(srcIndex), Convert<intptr>(count));
52+
}
53+
2754
macro FastSplice<FixedArrayType: type, ElementType: type>(
2855
args: constexpr Arguments, a: JSArray, length: Smi, newLength: Smi,
2956
lengthDelta: Smi, actualStart: Smi, insertCount: Smi,
3057
actualDeleteCount: Smi): void
3158
labels Bailout {
32-
const elements: FixedArrayBase = a.elements;
33-
const elementsMap: Map = elements.map;
34-
35-
// If the spliced array is larger then the
36-
// source array, then allocate a new FixedArrayType to hold the result.
37-
let newElements: FixedArrayBase = elements;
38-
if (elementsMap == kCOWMap || lengthDelta > 0) {
39-
newElements =
40-
Extract<FixedArrayType>(elements, 0, actualStart, newLength);
41-
if (elementsMap == kCOWMap) {
42-
newElements.map = elementsMap;
59+
// Make sure elements are writable.
60+
EnsureWriteableFastElements(a);
61+
62+
if (insertCount != actualDeleteCount) {
63+
const elements: FixedArrayBase = a.elements;
64+
const dstIndex: Smi = actualStart + insertCount;
65+
const srcIndex: Smi = actualStart + actualDeleteCount;
66+
const count: Smi = length - actualDeleteCount - actualStart;
67+
if (insertCount < actualDeleteCount) {
68+
// Shrink.
69+
DoMoveElements<FixedArrayType>(
70+
UnsafeCast<FixedArrayType>(elements), dstIndex, srcIndex, count);
71+
StoreHoles<FixedArrayType>(
72+
UnsafeCast<FixedArrayType>(elements), newLength, length);
73+
} else if (insertCount > actualDeleteCount) {
74+
// If the backing store is big enough, then moving elements is enough.
75+
if (newLength <= elements.length) {
76+
DoMoveElements<FixedArrayType>(
77+
UnsafeCast<FixedArrayType>(elements), dstIndex, srcIndex, count);
78+
} else {
79+
// Grow.
80+
let capacity: Smi = CalculateNewElementsCapacity(newLength);
81+
const newElements: FixedArrayType =
82+
Extract<FixedArrayType>(elements, 0, actualStart, capacity);
83+
a.elements = newElements;
84+
if (elements.length > 0) {
85+
DoCopyElements<FixedArrayType>(
86+
newElements, dstIndex, UnsafeCast<FixedArrayType>(elements),
87+
srcIndex, count);
88+
}
89+
}
4390
}
44-
a.elements = newElements;
4591
}
4692

47-
// Copy over inserted elements.
93+
// Copy arguments.
4894
let k: Smi = actualStart;
4995
if (insertCount > 0) {
5096
const typedNewElements: FixedArrayType =
51-
UnsafeCast<FixedArrayType>(newElements);
97+
UnsafeCast<FixedArrayType>(a.elements);
5298
for (let e: Object of args [2: ]) {
5399
// The argument elements were already validated to be an appropriate
54100
// {ElementType} to store in {FixedArrayType}.
55101
typedNewElements[k++] = UnsafeCast<ElementType>(e);
56102
}
57103
}
58104

59-
// Copy over elements after deleted elements.
60-
let count: Smi = length - actualStart - actualDeleteCount;
61-
while (count > 0) {
62-
const typedElements: FixedArrayType =
63-
UnsafeCast<FixedArrayType>(elements);
64-
const typedNewElements: FixedArrayType =
65-
UnsafeCast<FixedArrayType>(newElements);
66-
CopyArrayElement(typedElements, typedNewElements, k - lengthDelta, k);
67-
k++;
68-
count--;
69-
}
70-
71-
// Fill rest of spliced FixedArray with the hole, but only if the
72-
// destination FixedArray is the original array's, since otherwise the array
73-
// is pre-filled with holes.
74-
if (elements == newElements) {
75-
const typedNewElements: FixedArrayType =
76-
UnsafeCast<FixedArrayType>(newElements);
77-
const limit: Smi = elements.length;
78-
while (k < limit) {
79-
StoreArrayHole(typedNewElements, k);
80-
k++;
81-
}
82-
}
83-
84105
// Update the array's length after all the FixedArray shuffling is done.
85106
a.length = newLength;
86107
}

‎src/builtins/base.tq‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -844,6 +844,8 @@ macro AllowNonNumberElements(kind: ElementsKind): ElementsKind {
844844
extern macro AllocateZeroedFixedArray(intptr): FixedArray;
845845
extern macro AllocateZeroedFixedDoubleArray(intptr): FixedDoubleArray;
846846

847+
extern macro CalculateNewElementsCapacity(Smi): Smi;
848+
847849
extern macro CopyFixedArrayElements(
848850
constexpr ElementsKind, FixedArray, constexpr ElementsKind, FixedArray,
849851
intptr, intptr, intptr): void;
@@ -879,6 +881,36 @@ extern macro ExtractFixedArray(
879881

880882
extern builtin ExtractFastJSArray(Context, JSArray, Smi, Smi): JSArray;
881883

884+
extern macro MoveElements(
885+
constexpr ElementsKind, FixedArrayBase, intptr, intptr, intptr): void;
886+
macro TorqueMoveElements(
887+
elements: FixedArray, dstIndex: intptr, srcIndex: intptr,
888+
count: intptr): void {
889+
MoveElements(HOLEY_ELEMENTS, elements, dstIndex, srcIndex, count);
890+
}
891+
macro TorqueMoveElements(
892+
elements: FixedDoubleArray, dstIndex: intptr, srcIndex: intptr,
893+
count: intptr): void {
894+
MoveElements(HOLEY_DOUBLE_ELEMENTS, elements, dstIndex, srcIndex, count);
895+
}
896+
897+
extern macro CopyElements(
898+
constexpr ElementsKind, FixedArrayBase, intptr, FixedArrayBase, intptr,
899+
intptr): void;
900+
macro TorqueCopyElements(
901+
dstElements: FixedArray, dstIndex: intptr, srcElements: FixedArray,
902+
srcIndex: intptr, count: intptr): void {
903+
CopyElements(
904+
HOLEY_ELEMENTS, dstElements, dstIndex, srcElements, srcIndex, count);
905+
}
906+
macro TorqueCopyElements(
907+
dstElements: FixedDoubleArray, dstIndex: intptr,
908+
srcElements: FixedDoubleArray, srcIndex: intptr, count: intptr): void {
909+
CopyElements(
910+
HOLEY_DOUBLE_ELEMENTS, dstElements, dstIndex, srcElements, srcIndex,
911+
count);
912+
}
913+
882914
macro LoadElementNoHole<T: type>(a: JSArray, index: Smi): Object
883915
labels IfHole;
884916

‎src/code-stub-assembler.cc‎

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4541,6 +4541,179 @@ void CodeStubAssembler::FillFixedDoubleArrayWithZero(
45414541
backing_store, IntPtrConstant(0), byte_length);
45424542
}
45434543

4544+
void CodeStubAssembler::JumpIfPointersFromHereAreInteresting(
4545+
TNode<Object> object, Label* interesting) {
4546+
Label finished(this);
4547+
TNode<IntPtrT> object_word = BitcastTaggedToWord(object);
4548+
TNode<IntPtrT> object_page = PageFromAddress(object_word);
4549+
TNode<IntPtrT> page_flags = UncheckedCast<IntPtrT>(Load(
4550+
MachineType::IntPtr(), object_page, IntPtrConstant(Page::kFlagsOffset)));
4551+
Branch(
4552+
WordEqual(WordAnd(page_flags,
4553+
IntPtrConstant(
4554+
MemoryChunk::kPointersFromHereAreInterestingMask)),
4555+
IntPtrConstant(0)),
4556+
&finished, interesting);
4557+
BIND(&finished);
4558+
}
4559+
4560+
void CodeStubAssembler::MoveElements(ElementsKind kind,
4561+
TNode<FixedArrayBase> elements,
4562+
TNode<IntPtrT> dst_index,
4563+
TNode<IntPtrT> src_index,
4564+
TNode<IntPtrT> length) {
4565+
Label finished(this);
4566+
Label needs_barrier(this);
4567+
const bool needs_barrier_check = IsObjectElementsKind(kind);
4568+
4569+
DCHECK(IsFastElementsKind(kind));
4570+
CSA_ASSERT(this, IsFixedArrayWithKind(elements, kind));
4571+
CSA_ASSERT(this,
4572+
IntPtrLessThanOrEqual(IntPtrAdd(dst_index, length),
4573+
LoadAndUntagFixedArrayBaseLength(elements)));
4574+
CSA_ASSERT(this,
4575+
IntPtrLessThanOrEqual(IntPtrAdd(src_index, length),
4576+
LoadAndUntagFixedArrayBaseLength(elements)));
4577+
4578+
// The write barrier can be ignored if {elements} is in new space, or if
4579+
// we have a SMI or double ElementsKind.
4580+
if (needs_barrier_check) {
4581+
JumpIfPointersFromHereAreInteresting(elements, &needs_barrier);
4582+
}
4583+
4584+
const TNode<IntPtrT> source_byte_length =
4585+
IntPtrMul(length, IntPtrConstant(ElementsKindToByteSize(kind)));
4586+
static const int32_t fa_base_data_offset =
4587+
FixedArrayBase::kHeaderSize - kHeapObjectTag;
4588+
TNode<IntPtrT> elements_intptr = BitcastTaggedToWord(elements);
4589+
TNode<IntPtrT> target_data_ptr =
4590+
IntPtrAdd(elements_intptr,
4591+
ElementOffsetFromIndex(dst_index, kind, INTPTR_PARAMETERS,
4592+
fa_base_data_offset));
4593+
TNode<IntPtrT> source_data_ptr =
4594+
IntPtrAdd(elements_intptr,
4595+
ElementOffsetFromIndex(src_index, kind, INTPTR_PARAMETERS,
4596+
fa_base_data_offset));
4597+
TNode<ExternalReference> memmove =
4598+
ExternalConstant(ExternalReference::libc_memmove_function());
4599+
CallCFunction3(MachineType::Pointer(), MachineType::Pointer(),
4600+
MachineType::Pointer(), MachineType::UintPtr(), memmove,
4601+
target_data_ptr, source_data_ptr, source_byte_length);
4602+
4603+
if (needs_barrier_check) {
4604+
Goto(&finished);
4605+
4606+
BIND(&needs_barrier);
4607+
{
4608+
const TNode<IntPtrT> begin = src_index;
4609+
const TNode<IntPtrT> end = IntPtrAdd(begin, length);
4610+
4611+
// If dst_index is less than src_index, then walk forward.
4612+
const TNode<IntPtrT> delta =
4613+
IntPtrMul(IntPtrSub(dst_index, begin),
4614+
IntPtrConstant(ElementsKindToByteSize(kind)));
4615+
auto loop_body = [&](Node* array, Node* offset) {
4616+
Node* const element = Load(MachineType::AnyTagged(), array, offset);
4617+
Node* const delta_offset = IntPtrAdd(offset, delta);
4618+
Store(array, delta_offset, element);
4619+
};
4620+
4621+
Label iterate_forward(this);
4622+
Label iterate_backward(this);
4623+
Branch(IntPtrLessThan(delta, IntPtrConstant(0)), &iterate_forward,
4624+
&iterate_backward);
4625+
BIND(&iterate_forward);
4626+
{
4627+
// Make a loop for the stores.
4628+
BuildFastFixedArrayForEach(elements, kind, begin, end, loop_body,
4629+
INTPTR_PARAMETERS,
4630+
ForEachDirection::kForward);
4631+
Goto(&finished);
4632+
}
4633+
4634+
BIND(&iterate_backward);
4635+
{
4636+
BuildFastFixedArrayForEach(elements, kind, begin, end, loop_body,
4637+
INTPTR_PARAMETERS,
4638+
ForEachDirection::kReverse);
4639+
Goto(&finished);
4640+
}
4641+
}
4642+
BIND(&finished);
4643+
}
4644+
}
4645+
4646+
void CodeStubAssembler::CopyElements(ElementsKind kind,
4647+
TNode<FixedArrayBase> dst_elements,
4648+
TNode<IntPtrT> dst_index,
4649+
TNode<FixedArrayBase> src_elements,
4650+
TNode<IntPtrT> src_index,
4651+
TNode<IntPtrT> length) {
4652+
Label finished(this);
4653+
Label needs_barrier(this);
4654+
const bool needs_barrier_check = IsObjectElementsKind(kind);
4655+
4656+
DCHECK(IsFastElementsKind(kind));
4657+
CSA_ASSERT(this, IsFixedArrayWithKind(dst_elements, kind));
4658+
CSA_ASSERT(this, IsFixedArrayWithKind(src_elements, kind));
4659+
CSA_ASSERT(this, IntPtrLessThanOrEqual(
4660+
IntPtrAdd(dst_index, length),
4661+
LoadAndUntagFixedArrayBaseLength(dst_elements)));
4662+
CSA_ASSERT(this, IntPtrLessThanOrEqual(
4663+
IntPtrAdd(src_index, length),
4664+
LoadAndUntagFixedArrayBaseLength(src_elements)));
4665+
CSA_ASSERT(this, WordNotEqual(dst_elements, src_elements));
4666+
4667+
// The write barrier can be ignored if {dst_elements} is in new space, or if
4668+
// we have a SMI or double ElementsKind.
4669+
if (needs_barrier_check) {
4670+
JumpIfPointersFromHereAreInteresting(dst_elements, &needs_barrier);
4671+
}
4672+
4673+
TNode<IntPtrT> source_byte_length =
4674+
IntPtrMul(length, IntPtrConstant(ElementsKindToByteSize(kind)));
4675+
static const int32_t fa_base_data_offset =
4676+
FixedArrayBase::kHeaderSize - kHeapObjectTag;
4677+
TNode<IntPtrT> src_offset_start = ElementOffsetFromIndex(
4678+
src_index, kind, INTPTR_PARAMETERS, fa_base_data_offset);
4679+
TNode<IntPtrT> dst_offset_start = ElementOffsetFromIndex(
4680+
dst_index, kind, INTPTR_PARAMETERS, fa_base_data_offset);
4681+
TNode<IntPtrT> src_elements_intptr = BitcastTaggedToWord(src_elements);
4682+
TNode<IntPtrT> source_data_ptr =
4683+
IntPtrAdd(src_elements_intptr, src_offset_start);
4684+
TNode<IntPtrT> dst_elements_intptr = BitcastTaggedToWord(dst_elements);
4685+
TNode<IntPtrT> dst_data_ptr =
4686+
IntPtrAdd(dst_elements_intptr, dst_offset_start);
4687+
TNode<ExternalReference> memcpy =
4688+
ExternalConstant(ExternalReference::libc_memcpy_function());
4689+
CallCFunction3(MachineType::Pointer(), MachineType::Pointer(),
4690+
MachineType::Pointer(), MachineType::UintPtr(), memcpy,
4691+
dst_data_ptr, source_data_ptr, source_byte_length);
4692+
4693+
if (needs_barrier_check) {
4694+
Goto(&finished);
4695+
4696+
BIND(&needs_barrier);
4697+
{
4698+
const TNode<IntPtrT> begin = src_index;
4699+
const TNode<IntPtrT> end = IntPtrAdd(begin, length);
4700+
const TNode<IntPtrT> delta =
4701+
IntPtrMul(IntPtrSub(dst_index, src_index),
4702+
IntPtrConstant(ElementsKindToByteSize(kind)));
4703+
BuildFastFixedArrayForEach(
4704+
src_elements, kind, begin, end,
4705+
[&](Node* array, Node* offset) {
4706+
Node* const element = Load(MachineType::AnyTagged(), array, offset);
4707+
Node* const delta_offset = IntPtrAdd(offset, delta);
4708+
Store(dst_elements, delta_offset, element);
4709+
},
4710+
INTPTR_PARAMETERS, ForEachDirection::kForward);
4711+
Goto(&finished);
4712+
}
4713+
BIND(&finished);
4714+
}
4715+
}
4716+
45444717
void CodeStubAssembler::CopyFixedArrayElements(
45454718
ElementsKind from_kind, Node* from_array, ElementsKind to_kind,
45464719
Node* to_array, Node* first_element, Node* element_count, Node* capacity,

‎src/code-stub-assembler.h‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1568,6 +1568,25 @@ class V8_EXPORT_PRIVATE CodeStubAssembler : public compiler::CodeAssembler {
15681568
SMI_PARAMETERS);
15691569
}
15701570

1571+
void JumpIfPointersFromHereAreInteresting(TNode<Object> object,
1572+
Label* interesting);
1573+
1574+
// Efficiently copy elements within a single array. The regions
1575+
// [src_index, src_index + length) and [dst_index, dst_index + length)
1576+
// can be overlapping.
1577+
void MoveElements(ElementsKind kind, TNode<FixedArrayBase> elements,
1578+
TNode<IntPtrT> dst_index, TNode<IntPtrT> src_index,
1579+
TNode<IntPtrT> length);
1580+
1581+
// Efficiently copy elements from one array to another. The ElementsKind
1582+
// needs to be the same. Copy from src_elements at
1583+
// [src_index, src_index + length) to dst_elements at
1584+
// [dst_index, dst_index + length).
1585+
void CopyElements(ElementsKind kind, TNode<FixedArrayBase> dst_elements,
1586+
TNode<IntPtrT> dst_index,
1587+
TNode<FixedArrayBase> src_elements,
1588+
TNode<IntPtrT> src_index, TNode<IntPtrT> length);
1589+
15711590
TNode<FixedArray> HeapObjectToFixedArray(TNode<HeapObject> base,
15721591
Label* cast_fail);
15731592

@@ -1741,6 +1760,10 @@ class V8_EXPORT_PRIVATE CodeStubAssembler : public compiler::CodeAssembler {
17411760
Node* CalculateNewElementsCapacity(Node* old_capacity,
17421761
ParameterMode mode = INTPTR_PARAMETERS);
17431762

1763+
TNode<Smi> CalculateNewElementsCapacity(TNode<Smi> old_capacity) {
1764+
return CAST(CalculateNewElementsCapacity(old_capacity, SMI_PARAMETERS));
1765+
}
1766+
17441767
// Tries to grow the |elements| array of given |object| to store the |key|
17451768
// or bails out if the growing gap is too big. Returns new elements.
17461769
Node* TryGrowElementsCapacity(Node* object, Node* elements, ElementsKind kind,

0 commit comments

Comments
 (0)