26

我尝试了下一个代码（它在 Google Chrome 和 nodejs 中显示了类似的结果）：

var t = new Array(200000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27839.499ms
undefined

我还运行了下一个测试：

var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 449.948ms
undefined
var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(undefined);} console.timeEnd('wtf');
wtf: 406.710ms
undefined

但在 Firefox 中，第一个变体看起来都很好：

>>> var t = new Array(200000); console.time('wtf'); ...{t.push(Math.random());} console.timeEnd('wtf');
wtf: 602ms

V8 会发生什么？

UPD *神奇地降低性能*

var t = new Array(99999); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 220.936ms
undefined
var t = new Array(100000); t[99999] = 1; console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1731.641ms
undefined
var t = new Array(100001); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1703.336ms
undefined
var t = new Array(180000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1725.107ms
undefined
var t = new Array(181000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27587.669ms
undefined
4

2 回答 2

59

如果您预先分配，请不要使用.push，因为您将创建一个由哈希表支持的稀疏数组。您可以预分配最多 99999 个元素的稀疏数组，这些元素将由 C 数组支持，之后它是一个哈希表。

对于第二个数组，您以从 0 开始的连续方式添加元素，因此它将由真正的 C 数组支持，而不是哈希表。

大致如此：

如果你的数组索引从 0 到 Length-1 很好，没有空洞，那么它可以用一个快速的 C 数组来表示。如果您的数组中有孔，那么它将由一个慢得多的哈希表表示。例外情况是，如果您预先分配了一个大小 < 100000 的数组，那么您可能在数组中有空洞，但仍会得到 C 数组的支持：

var a = new Array(N); 

//If N < 100000, this will not make the array a hashtable:
a[50000] = "sparse";

var b = [] //Or new Array(N), with N >= 100000
//B will be backed by hash table
b[50000] = "Sparse";
//b.push("Sparse"), roughly same as above if you used new Array with N > 0
于 2013-06-06T12:25:24.683 回答
4

稀疏数组来了！[2020]

在现代 JS 引擎中，完全支持稀疏数组。您可以使用[]或new Array(len)以任何您喜欢的方式使用，即使是随机访问。字典模式似乎已成为过去。

在当前的 Chrome 中（我猜是任何 V8 环境），数组的长度可以达到 2^32-1 并且分配是稀疏的（意味着空块不会占用任何内存）：

在此处输入图像描述

在此处输入图像描述

但是，有一个问题

一方面，for循环按预期工作，但是，Array内置的高阶函数（例如map、filter、find等some）会忽略未分配的元素。他们首先需要fill（或其他一些人口统计方法）：

const a = new Array(10);
const b = new Array(10).fill(0);

a.forEach(x => console.log(x)); // does nothing
b.forEach(x => console.log(x)); // works as intended

从Array 的构造函数代码、函数和常量来看，在SetLengthWouldNormalize使用kMaxFastArrayLength字典模式之前，它现在可以支持几乎任意数量（目前上限为 3200 万）的元素。

但是请注意，现在有更多的考虑因素在起作用，因为 V8 优化变得越来越复杂。这篇 2017 年的官方博客文章解释说，数组可以区分 21 种不同类型的数组（或者更确切地说，数组元素类型），并且 - 引用：

“每个都有自己的一组可能的优化”

如果“稀疏数组有效，我们就这样吧！” 对你来说还不够好，我会推荐以下内容：

原帖

如果您在 Chrome 或 Node（或更一般地，在 V8 中）中预先分配了一个包含超过 10000 个元素的数组，它们会退回到字典模式，从而使事情变得非常慢。

感谢这个线程中的一些评论，我能够追踪到object.h 的 kInitialMaxFastElementArray。

然后，我使用该信息在 v8 存储库中提交了一个问题，该问题现在开始获得一些关注，但仍需要一段时间。我引用：

我希望我们最终能够完成这项工作。但这可能还有很长的路要走。

于 2014-11-04T14:18:32.377 回答