JavaScript 中对象/数组的性能如何？（专门针对 Google V8）

What is the performance of Objects/Arrays in JavaScript? (specifically for Google V8)

提问by BMiner

Performance associated with Arrays and Objects in JavaScript (especially Google V8) would be very interesting to document. I find no comprehensive article on this topic anywhere on the Internet.

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

I understand that some Objects use classes as their underlying data structure. If there are a lot of properties, it is sometimes treated as a hash table?

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

I also understand that Arrays are sometimes treated like C++ Arrays (i.e. fast random indexing, slow deletion and resizing). And, other times, they are treated more like Objects (fast indexing, fast insertion/removal, more memory). And, maybe sometimes they are stored as linked lists (i.e. slow random indexing, fast removal/insertion at the beginning/end)

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

What is the precise performance of Array/Object retrievals and manipulations in JavaScript?(specifically for Google V8)

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

More specifically, what it the performance impact of:

更具体地说，它对性能的影响是什么：

• Adding a property to an Object
• Removing a property from an Object
• Indexing a property in an Object
• Adding an item to an Array
• Removing an item from an Array
• Indexing an item in an Array
• Calling Array.pop()
• Calling Array.push()
• Calling Array.shift()
• Calling Array.unshift()
• Calling Array.slice()

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

Any articles or links for more details would be appreciated, as well. :)

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

EDIT:I am really wondering how JavaScript arrays and objects work under the hood. Also, in what contextdoes the V8 engine "know" to "switch-over" to another data structure?

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

For example, suppose I create an array with...

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

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

What's really going on here?

这里到底发生了什么？

Or... what about this...???

或者……这个怎么办……？？？

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...
}

For conventional arrays, the performance would be terrible; whereas, if a LinkedList was used... not so bad.

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

回答by PicoCreator

I created a test suite, precisely to explore these issues (and more)(archived copy).

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

And in that sense, you can see the performance issues in this 50+ test case tester (it will take a long time).

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

Also as its name suggest, it explores the usage of using the native linked list nature of the DOM structure.

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

(Currently down, rebuilt in progress) More details on my blog regarding this.

（目前已关闭，正在重建）我的博客上关于此的更多详细信息。

The summary is as followed

总结如下

• V8 Array is Fast, VERY FAST
• Array push / pop / shift is ~approx 20x+ faster than any object equivalent.
• Surprisingly Array.shift()is fast ~approx 6x slower than an array pop, but is ~approx 100x faster than an object attribute deletion.
• Amusingly, Array.push( data );is faster than Array[nextIndex] = databy almost 20 (dynamic array) to 10 (fixed array) times over.
• Array.unshift(data)is slower as expected, and is ~approx 5x slower than a new property adding.
• Nulling the value array[index] = nullis faster than deleting it delete array[index](undefined) in an array by ~approx 4x++ faster.
• Surprisingly Nulling a value in an object is obj[attr] = null~approx 2x slower than just deleting the attribute delete obj[attr]
• Unsurprisingly, mid array Array.splice(index,0,data)is slow, very slow.
• Surprisingly, Array.splice(index,1,data)has been optimized (no length change) and is 100x faster than just splice Array.splice(index,0,data)
• unsurprisingly, the divLinkedList is inferior to an array on all sectors, except dll.splice(index,1)removal (Where it broke the test system).
• BIGGEST SURPRISEof it all [as jjrv pointed out], V8 array writes are slightly faster than V8 reads =O

• V8 阵列很快，非常快
• 数组推送/弹出/移位比任何等效对象快约 20 倍以上。
• 令人惊讶的Array.shift()是，它比数组弹出速度快约 6 倍，但比对象属性删除快约 100 倍。
• 有趣的是，Array.push( data );它比Array[nextIndex] = data几乎快 20（动态阵列）到 10（固定阵列）倍。
• Array.unshift(data)比预期的要慢，并且比添加新属性慢约 5 倍。
• 清空值array[index] = null比delete 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

Note:These metrics applies only to large array/objects which v8 does not "entirely optimise out". There can be very isolated optimised performance cases for array/object size less then an arbitrary size (24?). More details can be seen extensively across several google IO videos.

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

Note 2:These wonderful performance results are not shared across browsers, especially *cough*IE. Also the test is huge, hence I yet to fully analyze and evaluate the results : please edit it in =)

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

Updated Note (dec 2012):Google representatives have videos on youtubes describing the inner workings of chrome itself (like when it switches from a linkedlist array to a fixed array, etc), and how to optimize them. See GDC 2012: From Console to Chromefor more.

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

回答by BMiner

At a basic level that stays within the realms of JavaScript, properties on objects are much more complex entities. You can create properties with setters/getters, with differing enumerability, writability, and configurability. An item in an array isn't able to be customized in this way: it either exists or it doesn't. At the underlying engine level this allows for a lot more optimization in terms of organizing the memory that represents the structure.

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

In terms of identifying an array from an object (dictionary), JS engines have always made explicit lines between the two. That's why there's a multitude of articles on methods of trying to make a semi-fake Array-like object that behaves like one but allows other functionality. The reason this separation even exists is because the JS engines themselves store the two differently.

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

Properties can be stored on an array object but this simply demonstrates how JavaScript insists on making everything an object. The indexed values in an array are stored differently from any properties you decide to set on the array object that represents the underlying array data.

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

Whenever you're using a legit array object and using one of the standard methods of manipulating that array you're going to be hitting the underlying array data. In V8 specifically, these are essentially the same as a C++ array so those rules will apply. If for some reason you're working with an array that the engine isn't able to determine with confidence is an array, then you're on much shakier ground. With recent versions of V8 there's more room to work though. For example, it's possible to create a class that has Array.prototype as its prototypeand still gain efficient access to the various native array manipulation methods. But this is a recent change.

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

Specific links to recent changes to array manipulation may come in handy here:

指向数组操作最近更改的特定链接可能会在此处派上用场：

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

As a bit of extra, here's Array Pop and Array Push directly from V8's source, both implemented in JS itself:

作为额外的一点，这里是直接来自 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;
}

回答by John

I'd like to complement existing answers with an investigation to the question of how implementations behave regarding growing arrays: If they implement them the "usual" way, one would see many quick pushes with rare, interspersed slow pushes at which point the implementation copies the internal representation of the array from one buffer to a larger one.

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

You can see this effect very nicely, this is from Chrome:

你可以很好地看到这个效果，这是来自 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

Even though each push is profiled, the output contains only those that take time above a certain threshold. For each test I customized the threshold to exclude all the pushes that appear to be representing the fast pushes.

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

So the first number represents which element has been inserted (the first line is for the 17th element), the second is how long it took (for many arrays the benchmark is done for in parallel), and the last value is the division of the first number by that of the one in the former line.

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

All lines that have less than 2ms execution time are excluded for Chrome.

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

You can see that Chrome increases array size in powers of 1.5, plus some offset to account for small arrays.

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

For Firefox, it's a power of two:

对于 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

I had to put the threshold up quite a bit in Firefox, that's why we start at #126.

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

With IE, we get a mix:

使用 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

It's a power of two at first and then it moves to powers of five thirds.

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

So all common implementations use the "normal" way for arrays (instead of going crazy with ropes, for example).

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

Here's the benchmark code and here's the fiddleit's in.

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

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;
    }
}

回答by Matt Simerson

While running under node.js 0.10 (built on v8) I was seeing CPU usage that seemed excessive for the workload. I traced one performance problem to a function that was checking for the existence of a string in an array. So I ran some tests.

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

• loaded 90,822 hosts
• loading config took 0.087 seconds (array)
• loading config took 0.152 seconds (object)

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

Loading 91k entries into an array (with validate & push) is faster than setting obj[key]=value.

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

In the next test, I looked up every hostname in the list one time (91k iterations, to average the lookup time):

在下一个测试中，我查找了列表中的每个主机名一次（91k 次迭代，平均查找时间）：

• searching config took 87.56 seconds (array)
• searching config took 0.21 seconds (object)

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

The application here is Haraka (a SMTP server) and it loads the host_list once at startup (and after changes) and subsequently performs this lookup millions of times during operation. Switching to an object was a huge performance win.

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