为什么array.push有时比array [n] = value更快？

作为测试一些代码的副作用,我编写了一个小函数来比较使用array.push方法与直接寻址(array [n] = value)的速度.令我惊讶的是,推送方法通常表现得更快,特别是在Firefox中,有时在Chrome中.只是出于好奇:任何人都有解释吗？您可以在此页面找到测试(单击"数组方法比较")

1> olliej..：

---

各种各样的因素都会发挥作用,大多数JS实现都会使用一个平面数组,如果以后有必要,它会转换为稀疏存储.

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

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

你应该添加一个额外的测试,在其中你将数组从索引0填充到索引n-1 - 它应该更快,更快.

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

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

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

此Object类型处理所有标准属性访问逻辑,原型链等.然后Array实现变为

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自己的存储器中,如果数据足够紧凑则引擎将使用平面阵列存储,在这种情况下插入(和检索)只是标准的数组索引操作,否则引擎将转换数组稀疏存储,并使用map来获取propertyName到value的位置.

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

Anyhoo,这是一个相当高级别的概述发生了什么,并留下了一些更icky细节,但这是一般的实现模式.有关如何调度附加存储以及如何调度put/get的细节因引擎而异 - 但这是我能够真正描述设计/实现的最清晰的.

一个小的加法点,虽然ES规范propertyName称为字符串JS引擎也倾向于专注于整数查找,因此someObject[someInteger]如果你正在查看具有整数属性的对象,则不会将整数转换为字符串.数组,字符串和DOM类型(NodeLists等).

2> Marco Demaio..：

---

这些是我通过测试得到的结果

在Safari上:

Array.push(n)1,000,000个值:0.124秒

数组[n .. 0] =值(降序)1,000,000个值:3.697秒

数组[0 .. n] =值(升序)1,000,000个值:0.073秒

在FireFox上:

Array.push(n)1,000,000个值:0.075秒

数组[n .. 0] =值(降序)1,000,000个值:1.193秒

数组[0 .. n] =值(升序)1,000,000个值:0.055秒

在IE7上:

Array.push(n)1,000,000个值:2.828秒

数组[n .. 0] =值(降序)1,000,000个值:1.141秒

数组[0 .. n] =值(升序)1,000,000个值:7.984秒

根据你的测试,推送方法似乎在IE7上更好(差异很大),并且由于在其他浏览器上差异很小,似乎推送方法确实是向阵列添加元素的最佳方式.

但是我创建了另一个简单的测试脚本来检查快速将值附加到数组的方法,结果让我感到惊讶,使用Array.length似乎比使用Array.push要快得多,所以我真的不知道是什么再说一遍,我一无所知.

顺便说一句:在我的IE7上你的脚本停止了,浏览器问我是否要让它继续下去(你知道典型的IE消息说:"停止运行这个脚本？...")我会重新尝试减少一点循环.

3> Christoph..：

---

push() 是更普遍的[[Put]]的特例,因此可以进一步优化:

在数组对象上调用[[Put]]时,必须首先将参数转换为无符号整数,因为所有属性名称(包括数组索引)都是字符串.然后必须将其与数组的长度属性进行比较,以确定是否必须增加长度.推送时,不需要进行这样的转换或比较:只需使用当前长度作为数组索引并增加它.

当然还有其他一些会影响运行时的东西,例如调用push()应该比调用[[Put]] via慢,[]因为必须检查原型链的前者.

---

正如olliej指出的那样:实际的ECMAScript实现将优化转换,即对于数字属性名称,不会进行从字符串到uint的转换,只需进行简单的类型检查.基本假设应该仍然有效,尽管其影响将小于我原先假设的影响.

---

所有JS引擎实际上都优化[[Put]]整数,假设如果你使用的是整数,它可能是一个具有Integer属性名称的特殊处理程序的类型 - 例如.数组,字符串以及DOM类型(NodeLists,CanvasPixelArray等)