深度= 1 时，js 原生array.flat 速度慢吗？

Question

这个要点是我写的一个小型基准测试，用于比较JS中深度为 1 的扁平数组的 4 种替代方案的性能 （代码可以按原样复制到谷歌控制台）。如果我没有遗漏任何东西，那么本机 Array.prototype.flat 迄今为止的性能最差 - 比任何替代品慢 30-50 倍。

更新：我在jsperf上创建了一个基准。

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

这个结果在一个大的子集中最为突出 - 请参阅下面测试的最后 2 个数组。考虑到规范和似乎完全遵循规范的V8 实现，这个结果非常令人惊讶。我的 C++ 知识不存在，因为我对 V8 兔子洞很熟悉，但在我看来，鉴于递归定义，一旦我们到达最终深度子数组，就不会对该子数组调用进行进一步的递归调用（标志当递减的深度达到 0 时，shouldFlatten 为假，即最终的子级别）并且添加到扁平结果包括迭代循环每个子元素，以及对该方法的简单调用。因此，我看不出为什么 a.flat 应该在性能上受到如此大的影响。

我想也许在原生公寓中结果的大小没有预先分配的事实可能解释了这种差异。此基准测试中的第二个实现（未预先分配）表明，仅凭这一点无法解释差异 - 它的性能仍然是原生 flat 的 5-10 倍。这可能是什么原因？

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

1. 我自己的展平实现包括预先分配最终展平的长度（从而避免所有重新分配的大小）。原谅命令式风格的代码，我是为了最大的性能。
2. 最简单的实现，循环遍历每个子数组并推入最终数组。（因此冒着许多大小重新分配的风险）。
3. Array.prototype.flat（原生平面）
4. [ ].concat(...arr)（=展开数组，然后将结果连接在一起。这是一种实现深度=1 展平的流行方法）。

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

1. 1000 个子数组，每个子数组 10 个元素。（共10人）
2. 10 个子数组，每个子数组 1000 个元素。（共10人）
3. 10000 个子数组，每个子数组 1000 个元素。（共 1000 万）
4. 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 的优化编译器。（它们在一段时间后得到优化的事实是为什么它们的性能起初看起来有些变化的部分原因；在更强大的测试中，您实际上可以非常清楚地观察到这种效果。）

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