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

Question

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

Answer 1

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

基本上，变得稀疏的决定是一种启发式方法，它基于要设置哪些元素，以及为了保持平坦会浪费多少空间。

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

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

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

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

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

此对象类型处理所有标准属性访问逻辑、原型(prototype)链等。那么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 自己的存储中，如果数据足够紧凑则引擎将使用平面数组存储，在这种情况下插入(和检索)只是标准的数组索引操作，否则引擎将转换数组到稀疏存储，并使用映射从 propertyName 到值位置放置/获取。

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

无论如何，这是对所发生情况的相当高层次的概述，并省略了一些更棘手的细节，但这是一般的实现模式。关于如何额外存储以及如何分配 put/get 的细节因引擎而异——但这是我能真正描述设计/实现的最清晰的。

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