Skip to content

Commit 7b9df2f

Browse files
sosukesuzukisosukesuzuki
committed
[JSC] Implement Array.prototype.flat in C++
https://bugs.webkit.org/show_bug.cgi?id=294503 Reviewed by Yusuke Suzuki. This patch implements `Array.prototype.flat` in C++. The new fast path for `Array#flat` first calculates the length of the resulting array using O(n) `calculateFlattenedLength`, then directly sets values into the butterfly buffer of the resulting array using O(n) `fastFlatIntoBuffer`. TipOfTree Patched array-prototype-flat-depth-1-string 395.8826+-4.5561 ^ 147.9479+-3.7062 ^ definitely 2.6758x faster array-prototype-flat-large-nested 111.9910+-4.9277 ^ 30.5805+-0.2314 ^ definitely 3.6622x faster array-prototype-flat-sparse-array 198.6802+-2.0652 ^ 133.4569+-3.7686 ^ definitely 1.4887x faster array-prototype-flat-small-arrays 9.0792+-0.4023 ^ 4.8345+-0.1067 ^ definitely 1.8780x faster array-prototype-flat-depth-1-double 600.7011+-40.1338 ^ 105.1259+-1.4612 ^ definitely 5.7141x faster array-prototype-flat-depth-1-int32 447.6045+-6.5491 ^ 106.2142+-7.6386 ^ definitely 4.2142x faster array-prototype-flat-depth-infinity 524.9275+-4.1636 ^ 141.2842+-5.6371 ^ definitely 3.7154x faster array-prototype-flat-depth-2 522.6723+-2.1402 ^ 118.4029+-5.5013 ^ definitely 4.4144x faster array-prototype-flat-huge-arrays 43.4337+-3.9484 ^ 10.1096+-0.1294 ^ definitely 4.2963x faster array-prototype-flat-depth-1-mixed 450.7441+-18.1260 ^ 136.2629+-0.7525 ^ definitely 3.3079x faster array-prototype-flat-depth-3 526.4249+-2.3837 ^ 124.7195+-4.6807 ^ definitely 4.2209x faster * JSTests/microbenchmarks/array-prototype-flat-depth-1-double.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-depth-1-int32.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-depth-1-mixed.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-depth-1-string.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-depth-2.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-depth-3.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-depth-infinity.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-huge-arrays.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-large-nested.js: Added. (shouldBe): (createLargeNestedArray): * JSTests/microbenchmarks/array-prototype-flat-small-arrays.js: Added. (shouldBe): * JSTests/microbenchmarks/array-prototype-flat-sparse-array.js: Added. (shouldBe): * JSTests/stress/array-prototype-flat-hole.js: Added. (shouldBe): * JSTests/stress/array-prototype-flat-nested-proxy-array.js: Added. (shouldBe): (const.handler.has): * Source/JavaScriptCore/builtins/ArrayPrototype.js: (flat): Deleted. * Source/JavaScriptCore/runtime/ArrayPrototype.cpp: (JSC::ArrayPrototype::finishCreation): (JSC::flatIntoArray): (JSC::JSC_DEFINE_HOST_FUNCTION): * Source/JavaScriptCore/runtime/CommonIdentifiers.h: * Source/JavaScriptCore/runtime/JSArray.cpp: (JSC::calculateFlattenedLength): (JSC::fastFlatIntoBuffer): (JSC::JSArray::fastFlat): * Source/JavaScriptCore/runtime/JSArray.h: Canonical link: https://commits.webkit.org/298127@main
1 parent 96d4563 commit 7b9df2f

18 files changed

Lines changed: 575 additions & 20 deletions

‎JSTests/microbenchmarks/array-prototype-flat-depth-1-double.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
array.fill(99.99);
8+
array[512] = [1.1, 2.2, 3.3, 4.4, 5.5];
9+
10+
let r;
11+
for (let i = 0; i < 1e5; i++) {
12+
r = array.flat();
13+
}
14+
15+
shouldBe(r.length, 1023 + 5);

‎JSTests/microbenchmarks/array-prototype-flat-depth-1-int32.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
array.fill(99);
8+
array[512] = [1, 2, 3, 4, 5];
9+
10+
let r;
11+
for (let i = 0; i < 1e5; i++) {
12+
r = array.flat();
13+
}
14+
15+
shouldBe(r.length, 1023 + 5);

‎JSTests/microbenchmarks/array-prototype-flat-depth-1-mixed.js‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
for (let i = 0; i < array.length; i++) {
8+
if (i % 3 === 0) array[i] = i;
9+
else if (i % 3 === 1) array[i] = `str${i}`;
10+
else array[i] = i * 1.1;
11+
}
12+
array[256] = [true, false, null, undefined, {}];
13+
array[512] = [42, "hello", 3.14, BigInt(100), Symbol.for("test")];
14+
array[768] = [[], {a: 1}, new Date(), /regex/, function() {}];
15+
16+
let r;
17+
for (let i = 0; i < 1e5; i++) {
18+
r = array.flat();
19+
}
20+
21+
shouldBe(r.length, 1021 + 5 + 5 + 5);

‎JSTests/microbenchmarks/array-prototype-flat-depth-1-string.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
array.fill("test");
8+
array[512] = ["hello", "world", "from", "webkit", "test"];
9+
10+
let r;
11+
for (let i = 0; i < 1e5; i++) {
12+
r = array.flat();
13+
}
14+
15+
shouldBe(r.length, 1023 + 5);

‎JSTests/microbenchmarks/array-prototype-flat-depth-2.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
array.fill(99);
8+
array[256] = [[1, 2], [3, 4], [5, 6]];
9+
array[512] = [[7, 8, 9], [10, 11, 12]];
10+
array[768] = [[13], [14, 15], [16, 17, 18]];
11+
12+
let r;
13+
for (let i = 0; i < 1e5; i++) {
14+
r = array.flat(2);
15+
}
16+
17+
shouldBe(r.length, 1021 + 6 + 6 + 6);

‎JSTests/microbenchmarks/array-prototype-flat-depth-3.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
array.fill(99);
8+
array[256] = [[[1, 2]], [[3], [4, 5]], [[[6]]]];
9+
array[512] = [[[7, 8, 9]], [[[10]], [[11, 12]]]];
10+
array[768] = [[[[13]]], [[[14, 15]], [[16]]], [[[17], [18]]]];
11+
12+
let r;
13+
for (let i = 0; i < 1e5; i++) {
14+
r = array.flat(3);
15+
}
16+
17+
shouldBe(r.length, 1037);

‎JSTests/microbenchmarks/array-prototype-flat-depth-infinity.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(1024);
7+
array.fill(99);
8+
array[256] = [[[[[1, 2]]]], [[[3], [4, 5]]], [[[[[[6]]]]]]];
9+
array[512] = [[[[[[7, 8, 9]]]]], [[[[[10]]], [[[11, 12]]]]]];
10+
array[768] = [[[[[[[13]]]]]], [[[[[[14, 15]]]], [[[16]]]], [[[[17], [18]]]]]];
11+
12+
let r;
13+
for (let i = 0; i < 1e5; i++) {
14+
r = array.flat(Infinity);
15+
}
16+
17+
shouldBe(r.length, 1021 + 6 + 6 + 6);

‎JSTests/microbenchmarks/array-prototype-flat-huge-arrays.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = new Array(100000);
7+
array.fill(42);
8+
for (let i = 0; i < 1000; i++) {
9+
array[i * 100] = [1, 2, 3, 4, 5];
10+
}
11+
12+
let r;
13+
for (let i = 0; i < 1e2; i++) {
14+
r = array.flat();
15+
}
16+
17+
shouldBe(r.length, 99000 + 1000 * 5);

‎JSTests/microbenchmarks/array-prototype-flat-large-nested.js‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
function createLargeNestedArray(depth, width) {
7+
if (depth === 0) {
8+
return Array(width).fill(1);
9+
}
10+
const arr = [];
11+
for (let i = 0; i < width; i++) {
12+
arr.push(createLargeNestedArray(depth - 1, width));
13+
}
14+
return arr;
15+
}
16+
17+
const array = new Array(512);
18+
array.fill(99);
19+
array[100] = createLargeNestedArray(3, 10);
20+
array[200] = createLargeNestedArray(2, 20);
21+
array[300] = createLargeNestedArray(4, 5);
22+
23+
let r;
24+
for (let i = 0; i < 1e3; i++) {
25+
r = array.flat(Infinity);
26+
}
27+
28+
shouldBe(r.length, 21634);

‎JSTests/microbenchmarks/array-prototype-flat-small-arrays.js‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
function shouldBe(a, b) {
2+
if (a !== b)
3+
throw new Error(`Expected ${b} but got ${a}`);
4+
}
5+
6+
const array = [1, [2, 3], 4, [5], 6, [7, 8, 9], 10];
7+
8+
let r;
9+
for (let i = 0; i < 1e5; i++) {
10+
r = array.flat();
11+
}
12+
13+
shouldBe(r.length, 10);

0 commit comments

Comments
 (0)