在V8中使用数组(性能问题)

Question

我尝试了下一个代码(它在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

Answer 1

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

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

粗略地说:

如果你的数组索引很好地从0到长度-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

Answer 2

看似无限的数组 [2020]

在现代 V8 中，数组现在可以具有任意大小。您可以以任何您喜欢的方式使用[]或new Array(len)，甚至可以随机访问。

在当前的 Chrome（我猜是任何 V8 环境）中，数组的长度最多可达 2^32-1。

但是，有一些注意事项：

字典模式仍然适用

正如jmrk在评论中提到的，数组并不是神奇的存在。相反，较小的数组（达到某个阈值，显然现在达到几百万个元素）根本不稀疏，而只是看起来稀疏。因此，它们将耗尽其所有元素的实际内存。一旦达到阈值，数组就会退回到字典模式。

它们现在更容易使用，但它们内部的工作原理仍然与以前相同。

您需要初始化一个空数组

一方面，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

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

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

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

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

• 从那篇博客文章开始。
• 了解如何使用内置节点分析器工具。

原帖

如果您在 Chrome 或 Node 中（或者更一般地说，在 V8 中）预先分配带有 >100000元素的数组，它们会回退到字典模式，从而使速度变得非常慢。

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

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

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