为什么 array.push 有时比 array[n] = value 快? [英] Why is array.push sometimes faster than array[n] = value?

问题描述

作为测试一些代码的附带结果，我编写了一个小函数来比较使用 array.push 方法与直接寻址 (array[n] = value) 的速度.令我惊讶的是，推送方法通常显示出更快，尤其是在 Firefox 中，有时在 Chrome 中.只是出于好奇:有人对此有解释吗?你可以找到测试@这个页面(点击'数组方法比较')

As a side result of testing some code I wrote a small function to compare the speed of using the array.push method vs direct addressing (array[n] = value). To my surprise the push method often showed to be faster especially in Firefox and sometimes in Chrome. Just out of curiosity: anyone has an explanation for it? You can find the test @this page (click 'Array methods comparison')

推荐答案

各种因素都会起作用，大多数 JS 实现都使用平面数组，如果以后需要，它会转换为稀疏存储.

All sorts of factors come into play, most JS implementations use a flat array that converts to sparse storage if it becomes necessary later on.

基本上，变得稀疏的决定是基于正在设置的元素以及为了保持平坦而浪费多少空间的启发式方法.

Basically the decision to become sparse is a heuristic based on what elements are being set, and how much space would be wasted in order to remain flat.

在您的情况下，您首先设置最后一个元素，这意味着 JS 引擎将看到一个需要具有 n 长度但只有一个元素的数组.如果 n 足够大，这将立即使数组成为稀疏数组——在大多数引擎中，这意味着所有后续插入都将采用慢速稀疏数组的情况.

In your case you are setting the last element first, which means the JS engine will see an array that needs to have a length of n but only a single element. If n is large enough this will immediately make the array a sparse array -- in most engines this means that all subsequent insertions will take the slow sparse array case.

您应该添加一个额外的测试，在其中填充从索引 0 到索引 n-1 的数组——它应该会快得多.

You should add an additional test in which you fill the array from index 0 to index n-1 -- it should be much, much faster.

为了回应@Christoph 并出于拖延的愿望，这里描述了数组是如何(通常)在 JS 中实现的——具体情况因 JS 引擎而异，但一般原则是相同的.

In response to @Christoph and out of a desire to procrastinate, here's a description of how arrays are (generally) implemented in JS -- specifics vary from JS engine to JS engine but the general principle is the same.

所有 JS Object(不是字符串、数字、true、false、undefined 或 null)都继承自基本对象类型-- 确切的实现各不相同，可以是 C++ 继承，也可以是在 C 中手动执行(以任何一种方式执行都有好处)-- 基本 Object 类型定义了默认属性访问方法，例如.

All JS Objects (so not strings, numbers, true, false, undefined, or null) inherit from a base object type -- the exact implementation varies, it could be C++ inheritance, or manually in C (there are benefits to doing it in either way) -- the base Object type defines the default property access methods, eg.

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

该对象类型处理所有标准属性访问逻辑、原型链等.那么Array实现就变成了

This Object type handles all the standard property access logic, the prototype chain, etc. Then the Array implementation becomes

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js array
}

现在，当您在 JS 中创建数组时，引擎会创建类似于上述数据结构的内容.当您将对象插入 Array 实例时，Array 的 put 方法会检查属性名称是否为 0 到 2^32 之间的整数(或可以转换为整数，例如121"、2341"等)-1(或者可能是 2^31-1，我完全忘记了).如果不是，则将 put 方法转发到基础 Object 实现，并完成标准的 [[Put]] 逻辑.否则将值放入 Array 自己的存储中，如果数据足够紧凑，那么引擎将使用平面数组存储，在这种情况下，插入(和检索)只是一个标准的数组索引操作，否则引擎将转换数组稀疏存储，并放置/获取使用映射从 propertyName 获取值位置.

Now when you create an Array in JS the engine creates something akin to the above data structure. When you insert an object into the Array instance the Array's put method checks to see if the property name is an integer (or can be converted into an integer, e.g. "121", "2341", etc.) between 0 and 2^32-1 (or possibly 2^31-1, i forget exactly). If it is not, then the put method is forwarded to the base Object implementation, and the standard [[Put]] logic is done. Otherwise the value is placed into the Array's own storage, if the data is sufficiently compact then the engine will use the flat array storage, in which case insertion (and retrieval) is just a standard array indexing operation, otherwise the engine will convert the array to sparse storage, and put/get use a map to get from propertyName to value location.

老实说，我不确定在转换发生后是否有任何 JS 引擎当前从稀疏存储转换为平面存储.

I'm honestly not sure if any JS engine currently converts from sparse to flat storage after that conversion occurs.

Anyhoo，这是对所发生情况的相当高层次的概述，并遗漏了许多更棘手的细节，但这是一般的实现模式.额外存储的具体细节以及 put/get 的调度方式因引擎而异——但这是我能真正描述设计/实现的最清楚的部分.

Anyhoo, that's a fairly high level overview of what happens and leaves out a number of the more icky details, but that's the general implementation pattern. The specifics of how the additional storage, and how put/get are dispatched differs from engine to engine -- but this is the clearest i can really describe the design/implementation.

一个小的补充点，虽然 ES 规范将 propertyName 称为字符串 JS 引擎也倾向于专注于整数查找，所以 someObject[someInteger] 不会如果您正在查看具有整数属性的对象，请将整数转换为字符串，例如.数组、字符串和 DOM 类型(NodeLists 等).

A minor addition point, while the ES spec refers to propertyName as a string JS engines tend to specialise on integer lookups as well, so someObject[someInteger] will not convert the integer to a string if you're looking at an object that has integer properties eg. Array, String, and DOM types (NodeLists, etc).

这篇关于为什么 array.push 有时比 array[n] = value 快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！