Skip to content

Commit db79b71

Browse files
sosukesuzukisosukesuzuki
committed
[JSC] Implement Array.prototype.copyWithin in C++
https://bugs.webkit.org/show_bug.cgi?id=289237 Reviewed by Yusuke Suzuki. This patch implements `Array#copyWithin` in C++ using `memmove`. TipOfTree Patched array-prototype-copyWithin-contiguous 451.9835+-25.0049 ^ 258.7830+-1.3483 ^ definitely 1.7466x faster array-prototype-copyWithin-double 386.9415+-1.3776 ^ 258.2341+-4.6019 ^ definitely 1.4984x faster array-prototype-copyWithin-int32 345.7076+-2.5341 ^ 244.2431+-1.7288 ^ definitely 1.4154x faster * JSTests/microbenchmarks/array-prototype-copyWithin-int32.js: Added. (test): * Source/JavaScriptCore/runtime/ArrayPrototype.cpp: (JSC::ArrayPrototype::finishCreation): (JSC::JSC_DEFINE_HOST_FUNCTION): * Source/JavaScriptCore/runtime/CommonIdentifiers.h: * Source/JavaScriptCore/runtime/JSArray.cpp: (JSC::JSArray::fastCopywithin): * Source/JavaScriptCore/runtime/JSArray.h: Canonical link: https://commits.webkit.org/291766@main
1 parent 59699ab commit db79b71

11 files changed

Lines changed: 259 additions & 59 deletions

‎JSTests/microbenchmarks/array-prototype-copyWithin-contiguous.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
function test(array, target, start, end) {
2+
array.copyWithin(target, start, end);
3+
}
4+
noInline(test);
5+
6+
let array = new Array(1024);
7+
for (let j = 0; j < array.length; j++)
8+
array[j] = { j };
9+
10+
for (let i = 0; i < 1e6; i++) {
11+
array.copyWithin(i % 512, 256, 768);
12+
}

‎JSTests/microbenchmarks/array-prototype-copyWithin-double.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
function test(array, target, start, end) {
2+
array.copyWithin(target, start, end);
3+
}
4+
noInline(test);
5+
6+
let array = new Array(1024);
7+
for (let j = 0; j < array.length; j++)
8+
array[j] = j + 0.5;
9+
10+
for (let i = 0; i < 1e6; i++) {
11+
array.copyWithin(i % 512, 256, 768);
12+
}

‎JSTests/microbenchmarks/array-prototype-copyWithin-int32.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
function test(array, target, start, end) {
2+
array.copyWithin(target, start, end);
3+
}
4+
noInline(test);
5+
6+
let array = new Array(1024);
7+
for (let j = 0; j < array.length; j++)
8+
array[j] = j;
9+
10+
for (let i = 0; i < 1e6; i++) {
11+
array.copyWithin(i % 512, 256, 768);
12+
}

‎JSTests/stress/array-prototype-copyWithin-contiguous.js‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
function compareArray(a, b) {
2+
if (a.length !== b.length)
3+
throw new Error(`Expected length ${b.length} but got ${a.length}`);
4+
for (let i = 0; i < a.length; i++) {
5+
if (a[i] !== b[i])
6+
throw new Error(`${i}: Expected ${b[i]} but got ${a[i]}`);
7+
}
8+
}
9+
10+
{
11+
let obj1 = { a: 1 };
12+
let obj2 = { b: 2 };
13+
let arr = [obj1, "hello", 123, obj2, null, "end"];
14+
arr.copyWithin(1, 3, 5);
15+
compareArray(arr, [obj1, obj2, null, obj2, null, "end"]);
16+
}
17+
18+
{
19+
let obj1 = {};
20+
let obj2 = {};
21+
let arr = ["x", "y", "z", obj1, obj2, "tail"];
22+
arr.copyWithin(2, 1);
23+
compareArray(arr, ["x", "y", "y", "z", obj1, obj2]);
24+
}
25+
26+
{
27+
let obj = { test: 123 };
28+
let arr = [null, obj, "aaa", 42];
29+
arr.copyWithin(1, 2, 2);
30+
compareArray(arr, [null, obj, "aaa", 42]);
31+
}

‎JSTests/stress/array-prototype-copyWithin-double.js‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
function compareArray(a, b) {
2+
if (a.length !== b.length)
3+
throw new Error(`Expected length ${b.length} but got ${a.length}`);
4+
for (let i = 0; i < a.length; i++) {
5+
if (a[i] !== b[i])
6+
throw new Error(`${i}: Expected ${b[i]} but got ${a[i]}`);
7+
}
8+
}
9+
10+
{
11+
let arr = [1.5, 2, 3.25, 4, 5.75, 6, 7.125, 8];
12+
arr.copyWithin(3, 0, 2);
13+
compareArray(arr, [1.5, 2, 3.25, 1.5, 2, 6, 7.125, 8]);
14+
}
15+
16+
{
17+
let arr = [100.5, 200.1, 300, 400.9, 500];
18+
arr.copyWithin(3, 1, 3);
19+
compareArray(arr, [100.5, 200.1, 300, 200.1, 300]);
20+
}
21+
22+
{
23+
let arr = [1, 2, 3.3, 4.4];
24+
arr.copyWithin(0, 3, 2);
25+
compareArray(arr, [1, 2, 3.3, 4.4]);
26+
}

‎JSTests/stress/array-prototype-copyWithin-int32.js‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
function compareArray(a, b) {
2+
if (a.length !== b.length)
3+
throw new Error(`Expected length ${b.length} but got ${a.length}`);
4+
for (let i = 0; i < a.length; i++) {
5+
if (a[i] !== b[i])
6+
throw new Error(`${i}: Expected ${b[i]} but got ${a[i]}`);
7+
}
8+
}
9+
10+
{
11+
let arr = [0, 1, 2, 3, 4, 5, 6, 7];
12+
arr.copyWithin(0, 3);
13+
compareArray(arr, [3, 4, 5, 6, 7, 5, 6, 7]);
14+
}
15+
16+
{
17+
let arr = [100, 200, 300, 400];
18+
arr.copyWithin(2, 0, 2);
19+
compareArray(arr, [100, 200, 100, 200]);
20+
}
21+
22+
{
23+
let arr = [10, 11, 12, 13, 14];
24+
arr.copyWithin(-2, -3);
25+
compareArray(arr, [10, 11, 12, 12, 13]);
26+
}
27+
28+
{
29+
let arr = [0, 1, 2, 3, 4, 5];
30+
arr.copyWithin(2, 3);
31+
compareArray(arr, [0, 1, 3, 4, 5, 5]);
32+
}

‎Source/JavaScriptCore/builtins/ArrayPrototype.js‎

Lines changed: 0 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -273,63 +273,6 @@ function findLastIndex(callback /*, thisArg */)
273273
return -1;
274274
}
275275

276-
@linkTimeConstant
277-
function maxWithPositives(a, b)
278-
{
279-
"use strict";
280-
281-
return (a < b) ? b : a;
282-
}
283-
284-
@linkTimeConstant
285-
function minWithMaybeNegativeZeroAndPositive(maybeNegativeZero, positive)
286-
{
287-
"use strict";
288-
289-
return (maybeNegativeZero < positive) ? maybeNegativeZero : positive;
290-
}
291-
292-
function copyWithin(target, start /*, end */)
293-
{
294-
"use strict";
295-
296-
var array = @toObject(this, "Array.prototype.copyWithin requires that |this| not be null or undefined");
297-
var length = @toLength(array.length);
298-
299-
var relativeTarget = @toIntegerOrInfinity(target);
300-
var to = (relativeTarget < 0) ? @maxWithPositives(length + relativeTarget, 0) : @minWithMaybeNegativeZeroAndPositive(relativeTarget, length);
301-
302-
var relativeStart = @toIntegerOrInfinity(start);
303-
var from = (relativeStart < 0) ? @maxWithPositives(length + relativeStart, 0) : @minWithMaybeNegativeZeroAndPositive(relativeStart, length);
304-
305-
var relativeEnd;
306-
var end = @argument(2);
307-
if (end === @undefined)
308-
relativeEnd = length;
309-
else
310-
relativeEnd = @toIntegerOrInfinity(end);
311-
312-
var finalValue = (relativeEnd < 0) ? @maxWithPositives(length + relativeEnd, 0) : @minWithMaybeNegativeZeroAndPositive(relativeEnd, length);
313-
314-
var count = @minWithMaybeNegativeZeroAndPositive(finalValue - from, length - to);
315-
316-
var direction = 1;
317-
if (from < to && to < from + count) {
318-
direction = -1;
319-
from = from + count - 1;
320-
to = to + count - 1;
321-
}
322-
323-
for (var i = 0; i < count; ++i, from += direction, to += direction) {
324-
if (from in array)
325-
array[to] = array[from];
326-
else
327-
delete array[to];
328-
}
329-
330-
return array;
331-
}
332-
333276
@linkTimeConstant
334277
function flatIntoArray(target, source, sourceLength, targetIndex, depth)
335278
{

‎Source/JavaScriptCore/runtime/ArrayPrototype.cpp‎

Lines changed: 69 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,7 @@ static JSC_DECLARE_HOST_FUNCTION(arrayProtoFuncToReversed);
6969
static JSC_DECLARE_HOST_FUNCTION(arrayProtoFuncToSorted);
7070
static JSC_DECLARE_HOST_FUNCTION(arrayProtoFuncWith);
7171
static JSC_DECLARE_HOST_FUNCTION(arrayProtoFuncIncludes);
72+
static JSC_DECLARE_HOST_FUNCTION(arrayProtoFuncCopyWithin);
7273

7374
// ------------------------------ ArrayPrototype ----------------------------
7475

@@ -127,7 +128,7 @@ void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
127128
JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().findIndexPublicName(), arrayPrototypeFindIndexCodeGenerator, static_cast<unsigned>(PropertyAttribute::DontEnum));
128129
JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().findLastIndexPublicName(), arrayPrototypeFindLastIndexCodeGenerator, static_cast<unsigned>(PropertyAttribute::DontEnum));
129130
JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->includes, arrayProtoFuncIncludes, static_cast<unsigned>(PropertyAttribute::DontEnum), 1, ImplementationVisibility::Public, ArrayIncludesIntrinsic);
130-
JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().copyWithinPublicName(), arrayPrototypeCopyWithinCodeGenerator, static_cast<unsigned>(PropertyAttribute::DontEnum));
131+
JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->copyWithin, arrayProtoFuncCopyWithin, static_cast<unsigned>(PropertyAttribute::DontEnum), 2, ImplementationVisibility::Public);
131132
JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().atPublicName(), arrayPrototypeAtCodeGenerator, static_cast<unsigned>(PropertyAttribute::DontEnum));
132133
JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->toReversed, arrayProtoFuncToReversed, static_cast<unsigned>(PropertyAttribute::DontEnum), 0, ImplementationVisibility::Public);
133134
JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->toSorted, arrayProtoFuncToSorted, static_cast<unsigned>(PropertyAttribute::DontEnum), 1, ImplementationVisibility::Public);
@@ -146,7 +147,7 @@ void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
146147
unscopables->convertToDictionary(vm);
147148
const Identifier* const unscopableNames[] = {
148149
&vm.propertyNames->builtinNames().atPublicName(),
149-
&vm.propertyNames->builtinNames().copyWithinPublicName(),
150+
&vm.propertyNames->copyWithin,
150151
&vm.propertyNames->builtinNames().entriesPublicName(),
151152
&vm.propertyNames->fill,
152153
&vm.propertyNames->builtinNames().findPublicName(),
@@ -2202,6 +2203,72 @@ JSC_DEFINE_HOST_FUNCTION(arrayProtoFuncIncludes, (JSGlobalObject* globalObject,
22022203
return JSValue::encode(jsBoolean(false));
22032204
}
22042205

2206+
JSC_DEFINE_HOST_FUNCTION(arrayProtoFuncCopyWithin, (JSGlobalObject* globalObject, CallFrame* callFrame))
2207+
{
2208+
VM& vm = globalObject->vm();
2209+
auto scope = DECLARE_THROW_SCOPE(vm);
2210+
2211+
JSValue thisValue = callFrame->thisValue().toThis(globalObject, ECMAMode::strict());
2212+
RETURN_IF_EXCEPTION(scope, { });
2213+
2214+
if (UNLIKELY(thisValue.isUndefinedOrNull()))
2215+
return throwVMTypeError(globalObject, scope, "Array.prototype.copyWithin requires that |this| not be null or undefined"_s);
2216+
auto* thisObject = thisValue.toObject(globalObject);
2217+
RETURN_IF_EXCEPTION(scope, { });
2218+
2219+
uint64_t length = toLength(globalObject, thisObject);
2220+
RETURN_IF_EXCEPTION(scope, { });
2221+
2222+
uint64_t to = argumentClampedIndexFromStartOrEnd(globalObject, callFrame->argument(0), length);
2223+
RETURN_IF_EXCEPTION(scope, { });
2224+
uint64_t from = argumentClampedIndexFromStartOrEnd(globalObject, callFrame->argument(1), length);
2225+
RETURN_IF_EXCEPTION(scope, { });
2226+
uint64_t finalIndex = argumentClampedIndexFromStartOrEnd(globalObject, callFrame->argument(2), length, length);
2227+
RETURN_IF_EXCEPTION(scope, { });
2228+
2229+
if (finalIndex < from)
2230+
return JSValue::encode(thisValue);
2231+
2232+
ASSERT(to <= length);
2233+
ASSERT(from <= length);
2234+
2235+
uint64_t count = std::min(length - std::max(to, from), finalIndex - from);
2236+
ASSERT(count <= length);
2237+
if (!count)
2238+
return JSValue::encode(thisObject);
2239+
2240+
if (LIKELY(isJSArray(thisObject))) {
2241+
JSArray* thisArray = asArray(thisObject);
2242+
if (thisArray->fastCopywithin(globalObject, from, to, count, length))
2243+
return JSValue::encode(thisValue);
2244+
}
2245+
2246+
int8_t direction = 1;
2247+
if (from < to && to < from + count) {
2248+
direction = -1;
2249+
from = from + count - 1;
2250+
to = to + count - 1;
2251+
}
2252+
2253+
for (uint64_t i = 0; i < count; ++i, from += direction, to += direction) {
2254+
if (thisObject->hasProperty(globalObject, from)) {
2255+
JSValue fromValue = thisObject->getIndex(globalObject, from);
2256+
RETURN_IF_EXCEPTION(scope, { });
2257+
thisObject->putByIndexInline(globalObject, to, fromValue, true);
2258+
RETURN_IF_EXCEPTION(scope, { });
2259+
} else {
2260+
bool success = thisObject->deleteProperty(globalObject, to);
2261+
RETURN_IF_EXCEPTION(scope, { });
2262+
if (UNLIKELY(!success)) {
2263+
throwTypeError(globalObject, scope, UnableToDeletePropertyError);
2264+
return { };
2265+
}
2266+
}
2267+
}
2268+
2269+
return JSValue::encode(thisObject);
2270+
}
2271+
22052272
} // namespace JSC
22062273

22072274
WTF_ALLOW_UNSAFE_BUFFER_USAGE_END

‎Source/JavaScriptCore/runtime/CommonIdentifiers.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -103,6 +103,7 @@
103103
macro(constructor) \
104104
macro(count) \
105105
macro(counters) \
106+
macro(copyWithin) \
106107
macro(dateStyle) \
107108
macro(day) \
108109
macro(days) \

‎Source/JavaScriptCore/runtime/JSArray.cpp‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -819,6 +819,68 @@ std::optional<bool> JSArray::fastIncludes(JSGlobalObject* globalObject, JSValue
819819
}
820820
}
821821

822+
bool JSArray::fastCopywithin(JSGlobalObject* globalObject, uint64_t from64, uint64_t to64, uint64_t count64, uint64_t length64)
823+
{
824+
VM& vm = globalObject->vm();
825+
826+
uint32_t from = static_cast<uint32_t>(from64);
827+
uint32_t to = static_cast<uint32_t>(to64);
828+
uint32_t count = static_cast<uint32_t>(count64);
829+
uint32_t length = static_cast<uint32_t>(length64);
830+
831+
ASSERT(from + count <= length);
832+
ASSERT(to + count <= length);
833+
834+
bool canDoFastPath = this->canDoFastIndexedAccess()
835+
&& this->getArrayLength() == length
836+
&& from64 == from
837+
&& to64 == to
838+
&& count64 == count;
839+
840+
if (!canDoFastPath)
841+
return false;
842+
843+
if (isCopyOnWrite(indexingMode()))
844+
convertFromCopyOnWrite(vm);
845+
846+
auto type = this->indexingType();
847+
switch (type) {
848+
case ArrayWithInt32:
849+
case ArrayWithContiguous: {
850+
auto data = this->butterfly()->contiguous().data();
851+
852+
if (containsHole(data, length))
853+
return false;
854+
855+
std::span<WriteBarrier<Unknown>> destination { data + to, count };
856+
std::span<const WriteBarrier<Unknown>> source { data + from, count };
857+
858+
if (type == ArrayWithInt32)
859+
memmoveSpan(destination, source);
860+
else {
861+
ASSERT(type == ArrayWithContiguous);
862+
gcSafeMemmove(destination.data(), source.data(), count * sizeof(JSValue));
863+
vm.writeBarrier(this);
864+
}
865+
return true;
866+
}
867+
case ArrayWithDouble: {
868+
auto data = this->butterfly()->contiguousDouble().data();
869+
870+
if (containsHole(data, length))
871+
return false;
872+
873+
std::span<double> destination { data + to, count };
874+
std::span<double> source { data + from, count };
875+
876+
memmoveSpan(destination, source);
877+
return true;
878+
}
879+
default:
880+
return false;
881+
}
882+
}
883+
822884
bool JSArray::appendMemcpy(JSGlobalObject* globalObject, VM& vm, unsigned startIndex, IndexingType otherType, std::span<const EncodedJSValue> values)
823885
{
824886
auto scope = DECLARE_THROW_SCOPE(vm);

0 commit comments

Comments
 (0)