为什么有时的Array.push比数组[n] =值更快？ [英] Why is array.push sometimes faster than array[n] = value?

问题描述

由于测试一些code的侧面结果，我写了一个小功能比较使用的Array.push方法VS直接寻址（数组[n] =值）的速度。令我惊讶的push方法往往表明会更快尤其是在Firefox，有时在Chrome中。只是出于好奇：任何人都有它的解释吗？
你可以找到测试@ 此页面（点击'阵列方法比较'）

解决方案

有多种因素在起作用，大多数JS实现使用平板阵列转换为稀疏存储，如果有必要稍后。

基本上成为稀疏的决定是一种启发式的基础上正在建立什么样的元素，又有多少空间会以浪费持平。

在你的情况，你第一次在最后一个元素，这意味着JS引擎会看到，需要有 N ，但仅一个元件的长度的数组。如果 N 够这将立即使数组稀疏数组大 - 在大多数的引擎，这意味着所有的后续插入将采取缓慢稀疏数组的情况下

您应该添加在你从索引0数组填补到索引n-1的额外的测试 - 它应该是多少，更快

在回应@Christoph进出拖延的愿望，这里有一个如何阵列（一般）的JS实现的描述 - 细节有所不同的JS引擎，JS引擎，但总的原则是一样的。

所有的JS 对象 S（所以不是字符串，数字，真，假，未定义或空）从基本对象类型继承 - 确切的实施而改变，它可能是C ++继承或手动C（也有在任何一种方式做）的好处 - 基对象类型定义默认属性访问方法，如：

 接口对象{
    把（propertyName的，值）
    得到（propertyName的）
私人的：
    地图属性; //地图（树，哈希表，等等）从propertyName的价值
}
 

该对象类型处理所有标准的属性访问逻辑，原型链等。
那么阵列实现变得

 接口数组：对象{
    覆盖放（propertyName的，值）
    覆盖GET（propertyName的）
私人的：
    地图sparseStorage; //整数索引和值之间的映射
    值[] flatStorage; //基本上值的原生阵列1:1
                         // JS指数和存储指数的对应关系
    值长; //将JS数组的`length`
}
 

现在当您创建JS数组的引擎创建一个类似于上面的数据结构。当您如果属性名称是一个整数对象插入阵列实例的阵列的put方法检查，看看（或可转换为整数，如121，2341等）0和2 ^ 32之间-1（也可能是2 ^ 31-1，我忘了完全一致）。如果不是，则put方法被转发到基对象的实现，并在[[穿戴]逻辑被完成。否则该值被放置到阵列的自己的存储，如果数据是足够紧凑那么发动机将使用平坦阵列存储，在这种情况下，插入（和检索）仅仅是一个标准阵列索引操作，否则发动机将阵列转换稀疏存储和PUT / GET使用地图从propertyName的去价值定位。

我真的不知道如果有JS引擎目前由疏转换为平面仓库的转换发生了。

安美居，这是发生了什么，并留下了一些更细节恶心相当高度概括，但这是一般的实现模式。如何附加存储的具体内容，以及如何PUT / GET分派从发动机引擎有所不同 - 但是这是最清楚的，我可以真正说明设计/实施

一个不起眼的新增点，而ES规​​范是指 propertyName的作为一个字符串JS引擎往往专注于整数查询一样，所以 someObject [someInteger] 不会整数，如果你正在寻找一个具有整数性能，如对象转换为字符串。数组，字符串，和DOM类型（节点列表 S，等等）。

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')

解决方案

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.

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.

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.

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.

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
}

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
}

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.

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

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.

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比数组[n] =值更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！