js native array.flat depth=1 慢吗？

Question

这个 gist 是我写的一个小型基准测试，用于比较 4 个备选方案的性能，用于展平数组 depth=1 in JS（代码可以原样复制到google控制台）。如果我没有遗漏任何东西，本机 Array.prototype.flat 的性能是迄今为止最差的 - 比任何替代方案慢 30-50 倍。

更新：我在 jsperf.

上创建了一个基准

应该注意的是，此基准测试中的第 4 个实施始终是性能最高的 - 通常实现的性能要好 70 倍。代码在节点 v12 和 Chrome 控制台中进行了多次测试。

这个结果在一个大的子集中最为突出 - 请参阅下面测试的最后 2 个阵列。考虑到 spec, and the V8 implementation which seems to follow the spec by the letter. My C++ knowledge is non-existent, as is my familiarity with the V8 rabbit hole, but it seems to me that given the recursive definition, once we reach a final depth subarray, no further recursive calls are made for that subarray call (the flag shouldFlatten is false when the decremented depth reaches 0, i.e., the final sub-level) and adding to the flattened result includes iterative looping over each sub-element, and a simple call to this method，这个结果非常令人惊讶。因此，我看不出为什么 a.flat 会在性能上遭受如此大的损失。

我认为也许在原生平面中结果的大小不是预先分配的这一事实可能解释了差异。该基准测试中的第二个实现（未预先分配）表明仅凭这一点无法解释差异 - 它的性能仍然是原生平面的 5-10 倍。这可能是什么原因？

测试的实现（代码中的顺序相同，存储在实现数组中 - 我写的两个在代码片段的末尾）：

我自己的展平实现包括预先分配最终的展平长度（从而避免重新分配大小）。请原谅命令式代码，我正在寻求最高性能。
最简单的天真实现，遍历每个子数组并推入最终数组。（因此冒着许多大小重新分配的风险）。
Array.prototype.flat (native flat)
[ ].concat(...arr) (=展开数组，然后将结果连接在一起。这是完成 depth=1 扁平化的一种流行方式。

测试的数组（代码中的顺序相同，存储在基准对象中）：

1000 个子数组，每个子数组包含 10 个元素。（总共 10 个）
10 个子数组，每个子数组有 1000 个元素。（总共 10 个）
10000 个子数组，每个子数组有 1000 个元素。（总共 1000 万）
100 个子数组，每个子数组有 100000 个元素。（总计 1000 万）

let TenThouWideArray = Array(1000).fill().map(el => Array(10).fill(1));
let TenThouNarrowArray = Array(10).fill().map(el => Array(1000).fill(1));
let TenMilWideArray = Array(10000).fill().map(el => Array(1000).fill(1));
let TenMilNarrowArray = Array(100).fill().map(el => Array(100000).fill(1));

let benchmarks = { TenThouWideArray, TenThouNarrowArray, TenMilWideArray, TenMilNarrowArray };
let implementations = [
    flattenPreAllocated,
    flattenNotPreAllocated,
    function nativeFlat(arr) { return Array.prototype.flat.call(arr) },
    function spreadThenConcat(arr) { return [].concat(...arr) }
];

let result;
Object.keys(benchmarks).forEach(arrayName => {
    console.log(`\n............${arrayName}............\n`)
    implementations.forEach(impl => {
        console.time(impl.name);
        result = impl(benchmarks[arrayName]);
        console.timeEnd(impl.name);
    })
    console.log(`\n............${arrayName}............\n`)
})


function flattenPreAllocated(arr) {
    let numElementsUptoIndex = Array(arr.length);
    numElementsUptoIndex[0] = 0;
    for (let i = 1; i < arr.length; i++)
        numElementsUptoIndex[i] = numElementsUptoIndex[i - 1] + arr[i - 1].length;
    let flattened = new Array(numElementsUptoIndex[arr.length - 1] + arr[arr.length - 1].length);
    let skip;
    for (let i = 0; i < arr.length; i++) {
        skip = numElementsUptoIndex[i];
        for (let j = 0; j < arr[i].length; j++)
            flattened[skip + j] = arr[i][j];
    }
    return flattened;
}
function flattenNotPreAllocated(arr) {
    let flattened = [];
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr[i].length; j++) {
            flattened.push(arr[i][j])
        }
    }
    return flattened;
}

Answer 1

（此处为 V8 开发人员。）

关键是您发现的 Array.prototype.flat 的实现根本没有优化。如您所见，它几乎完全遵循规范——这就是您如何获得正确但缓慢的实现的方式。（实际上对性能的判断并不那么简单：这种实现技术有很多优点，比如从第一次调用开始就可靠的性能，而不管类型反馈如何。）

优化意味着添加额外的快速路径，尽可能采用各种捷径。 .flat() 的这项工作尚未完成。它 .concat() 已经完成，V8 有一个高度复杂、超级优化的实现，这就是为什么这种方法如此快的原因。

您提供的两个手写方法假设通用 .flat() 必须检查（他们知道他们正在遍历数组，他们知道所有元素都存在，他们知道深度为 1)，因此他们需要执行的检查要少得多。作为 JavaScript，他们也（最终）受益于 V8 的优化编译器。（它们在一段时间后得到优化的事实部分解释了为什么它们的性能起初看起来有些变化；在更稳健的测试中，您实际上可以非常清楚地观察到这种效果。）

综上所述，在大多数实际应用程序中，您可能不会注意到实践中的差异：大多数应用程序不会花时间展平具有数百万个元素的数组，而对于小型数组（数十、数百或数千）元素）差异低于噪音水平。

js native array.flat depth=1 慢吗？

Is js native array.flat slow for depth=1?

javascript

performance

benchmarking

v8

flatten