JavaScript 中对象/数组的性能如何?(专门针对 Google V8)

IT技术 javascript arrays performance object v8
2021-01-17 22:24:06

与 JavaScript(尤其是 Google V8)中的数组和对象相关的性能记录将非常有趣。我在 Internet 上的任何地方都找不到关于此主题的综合文章。

我知道有些对象使用类作为它们的底层数据结构。如果属性很多,有时会被当成哈希表处理?

我也明白数组有时被视为 C++ 数组(即快速随机索引、缓慢删除和调整大小)。并且,其他时候,它们更像是对象(快速索引、快速插入/删除、更多内存)。而且,也许有时它们被存储为链表(即缓慢的随机索引,在开始/结束时快速删除/插入)

JavaScript 中数组/对象检索和操作的精确性能是什么?(专门针对 Google V8)

更具体地说,它对性能的影响是什么:

  • 向对象添加属性
  • 从对象中删除属性
  • 索引对象中的属性
  • 将项目添加到数组
  • 从数组中删除项目
  • 索引数组中的项目
  • 调用 Array.pop()
  • 调用 Array.push()
  • 调用 Array.shift()
  • 调用 Array.unshift()
  • 调用 Array.slice()

任何文章或更多细节的链接也将不胜感激。:)

编辑:我真的很想知道 JavaScript 数组和对象是如何在幕后工作的。另外,V8 引擎在什么情况下“知道”要“切换”到另一种数据结构?

例如,假设我创建了一个数组...

var arr = [];
arr[10000000] = 20;
arr.push(21);

这里到底发生了什么?

或者……这……怎么办????

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

对于传统阵列,性能会很糟糕;而如果使用了 LinkedList ......还不错。

4个回答

我创建了一个测试套件,正是为了探索这些问题(以及更多)存档副本)。

从这个意义上说,您可以在这个 50 多个测试用例测试器中看到性能问题(这将需要很长时间)。

顾名思义,它探索了使用 DOM 结构的本机链表特性的用法。

(目前已关闭,正在重建)我的博客上关于此的更多详细信息

总结如下

  • V8 阵列很快,非常快
  • 数组推送/弹出/移位比任何等效对象快约 20 倍以上。
  • 令人惊讶的Array.shift()是,它比数组弹出速度快约 6 倍,但比对象属性删除快约 100 倍。
  • 有趣的是,Array.push( data );它比Array[nextIndex] = data几乎快 20(动态阵列)到 10(固定阵列)倍。
  • Array.unshift(data) 比预期的要慢,并且比添加新属性慢约 5 倍。
  • 清空值array[index] = nulldelete array[index]在数组中删除它(未定义)快约 4x++。
  • 令人惊讶的是,将对象中的值清空obj[attr] = null比仅删除属性慢约 2 倍delete obj[attr]
  • 不出所料,中阵Array.splice(index,0,data)慢,非常慢。
  • 令人惊讶的是,Array.splice(index,1,data)已经过优化(没有长度变化)并且比拼接快 100 倍Array.splice(index,0,data)
  • 不出所料,divLinkedList 在所有扇区上都不如数组,除了dll.splice(index,1)删除(它破坏了测试系统的地方)。
  • 最大的惊喜[正如 jjrv 指出的],V8 阵列写入比 V8 读取略快 =O

注意:这些指标仅适用于 v8 没有“完全优化”的大型数组/对象。对于小于任意大小(24?)的数组/对象大小,可能存在非常孤立的优化性能情况。更多细节可以在几个谷歌 IO 视频中广泛看到。

注2:这些出色的性能结果并没有跨浏览器共享,尤其是 *cough*IE。测试也很大,因此我还没有完全分析和评估结果:请在 =) 中进行编辑

更新说明(2012 年 12 月):谷歌代表在 youtube 上有视频,描述了 chrome 本身的内部工作原理(比如当它从链表数组切换到固定数组时等),以及如何优化它们。有关更多信息,请参阅GDC 2012:从控制台到 Chrome

只是想在关于数组的视频讨论中添加确切的点:youtube.com/...
2021-03-22 22:24:06
@JustGoscha 好的,感谢信息:我通过从谷歌缓存重新创建它来修复它。
2021-03-23 22:24:06
其中一些结果看起来很奇怪。例如,在 Chrome 数组中,写入大约比读取快 10 倍,而在 Firefox 中则相反。在某些情况下,您确定浏览器 JIT 不会优化您的整个测试吗?
2021-03-31 22:24:06
JsPerf 站点不再存在:(
2021-03-31 22:24:06
@jjrv good gosh =O 你是对的......我什至更新了每个写入案例,使其增量唯一,以防止 JIT......老实说,除非 JIT 优化那么好(我觉得很难相信),这可能只是优化不佳的读取情况,或严重优化的写入(写入即时缓冲区?)...值得研究:lol
2021-04-09 22:24:06

在 JavaScript 领域的基本层面上,对象的属性是复杂得多的实体。您可以使用具有不同可枚举性、可写性和可配置性的 setter/getter 创建属性。数组中的项目不能以这种方式自定义:它要么存在,要么不存在。在底层引擎级别,这允许在组织表示结构的内存方面进行更多优化。

在从对象(字典)中识别数组方面,JS 引擎总是在两者之间做出明确的划分。这就是为什么有大量文章试图制作一个半假的类 Array 对象的方法,该对象的行为与一个类似但允许其他功能。这种分离甚至存在的原因是因为 JS 引擎本身以不同的方式存储两者。

属性可以存储在数组对象上,但这只是演示了 JavaScript 如何坚持将所有内容都设为对象。数组中的索引值的存储方式与您决定在表示底层数组数据的数组对象上设置的任何属性不同。

每当您使用合法的数组对象并使用操作该数组的标准方法之一时,您将访问底层数组数据。特别是在 V8 中,这些本质上与 C++ 数组相同,因此这些规则将适用。如果由于某种原因您正在使用引擎无法确定是一个数组的数组,那么您的处境就更加不稳定了。使用最新版本的 V8,还有更多的工作空间。例如,可以创建一个以 Array.prototype 作为其原型的类,并且仍然可以有效地访问各种本机数组操作方法。但这是最近的变化。

指向数组操作最近更改的特定链接在这里可能会派上用场:

作为额外的一点,这里是直接来自 V8 源代码的 Array Pop 和 Array Push,它们都是在 JS 本身中实现的:

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

我想通过对实现如何在增长数组方面的行为进行调查来补充现有答案:如果他们以“通常”的方式实现它们,人们会看到许多快速推送与罕见的、散布的缓慢推送,此时实现复制数组从一个缓冲区到更大缓冲区的内部表示。

你可以很好地看到这个效果,这是来自 Chrome:

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

即使对每个推送进行了分析,输出也只包含那些花费时间超过特定阈值的推送。对于每个测试,我自定义了阈值以排除所有似乎代表快速推送的推送。

所以第一个数字表示插入了哪个元素(第一行是第 17 个元素),第二个是花费了多长时间(对于许多数组,基准是并行完成的),最后一个值是第一个数字与前一行中的那个数字相同。

Chrome 排除了所有执行时间少于 2 毫秒的行。

您可以看到 Chrome 以 1.5 的幂增加数组大小,加上一些偏移量以解决小数组。

对于 Firefox,它是 2 的幂:

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

我不得不将 Firefox 的门槛提高很多,这就是我们从 #126 开始的原因。

使用 IE,我们得到了一个混合:

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

一开始是二的幂,然后变成五分之三的幂。

因此,所有常见的实现都对数组使用“正常”方式(例如,而不是用绳索发疯)。

这是基准代码,这是它所在的小提琴

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

在 node.js 0.10(基于 v8 构建)下运行时,我发现 CPU 使用率似乎超出了工作负载。我将一个性能问题追溯到一个正在检查数组中是否存在字符串的函数。所以我进行了一些测试。

  • 已加载 90,822 台主机
  • 加载配置需要 0.087 秒(数组)
  • 加载配置需要 0.152 秒(对象)

将 91k 条目加载到数组中(使用验证和推送)比设置 obj[key]=value 更快。

在下一个测试中,我查找了列表中的每个主机名一次(91k 次迭代,平均查找时间):

  • 搜索配置耗时 87.56 秒(数组)
  • 搜索配置花了 0.21 秒(对象)

这里的应用程序是 Haraka(一个 SMTP 服务器),它在启动时(和更改后)加载一次 host_list,随后在操作期间执行此查找数百万次。切换到一个对象是一个巨大的性能胜利。