array.pushがarray[n] = valueより速い場合があるのはなぜですか？

質問

あるコードをテストした副次的な結果として、私は小さな関数を書きました。 array.push(value) メソッドと直接アドレス指定 array[n] = value . 驚いたことに、特にFirefoxや時にはChromeでは、プッシュメソッドの方が高速であることがしばしば示されました。好奇心だけですが、どなたかこの現象について説明できる方はいらっしゃいますか？ あなたは、テスト@を見つけることができます このページ (クリック '配列法の比較')

どのように解決するのですか？

様々な要因が絡んできますが、ほとんどのJSの実装では、後で必要になった場合にスパースストレージに変換されるフラット配列を使用しています。

基本的に、スパースになるという決定は、どの要素が設定されているか、そしてフラットのままではどれだけのスペースが無駄になるかに基づいたヒューリスティックなものです。

あなたのケースでは、最後の要素を最初に設定しています。これは、JSエンジンが、長さが n の長さを必要とする配列が、単一の要素だけであることを意味します。 もし n が十分に大きい場合、これは即座に配列をスパース配列にします -- ほとんどのエンジンでは、これはその後のすべての挿入が遅いスパース配列のケースを取ることを意味します。

インデックス0からインデックスn-1まで配列を埋める追加のテストを追加すべきです -- それははるかに、はるかに速くなるはずです。

Christophへの返答と、先延ばしにしたい欲求から、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 インスタンスにオブジェクトを挿入すると、Array の put メソッドは、プロパティ名が 0 から 2^32-1 (または 2^31-1 かもしれませんが、正確には忘れました) の間の整数 (または、 "121", "2341" など、整数への変換が可能) かどうかをチェックします。 もしそうでなければ、putメソッドはベースとなるObjectの実装に転送され、標準的な[[Put]]ロジックが実行されます。 もしデータが十分にコンパクトであれば、エンジンはフラット配列ストレージを使用し、その場合、挿入（および取得）は単に標準的な配列インデックス操作になります。

正直なところ、現在、どの JS エンジンも、その変換が発生した後にスパース ストレージからフラット ストレージに変換しているかどうかはわかりません。

とにかく、これは何が起こるかのかなりハイレベルな概要であり、より厄介な詳細の多くを省きますが、これが一般的な実装パターンです。 追加のストレージ、および put/get がどのようにディスパッチされるかの詳細は、エンジンによって異なりますが、これが私が設計と実装を本当に説明できる最も明確なものです。

細かい追加点ですが、ES仕様では propertyName を文字列として参照していますが、JSエンジンは整数のルックアップにも特化する傾向があるので、そのため someObject[someInteger] は整数のプロパティを持つオブジェクトを見ている場合、整数を文字列に変換しません。 例えば、配列、文字列、DOM 型 ( NodeList など)。