JavaScriptのキュー最適化-shiftとpop

最近webpackのソースコードを見て、webpackパッケージのArayQue種類の中で、実現した行列の出し方dequeueは配列の長さが16より大きい時、Shftの代わりにreverse+popを採用します.

dequeue() {
    if (this._listReversed.length === 0) {
        if (this._list.length === 0) return undefined;
        if (this._list.length === 1) return this._list.pop();
        if (this._list.length < 16) return this._list.shift();
        const temp = this._listReversed;
        this._listReversed = this._list;
        this._listReversed.reverse();
        this._list = temp;
    }
    return this._listReversed.pop();
}

benchmarkテスト
benchmarkを採用して、二つの方式の性能テストを行います.

const Benchmark = require("benchmark");
const suite = new Benchmark.Suite();
suite
  .add("shift", function () {
    let arr = [];
    for (let i = 0; i < 100000; i++) {
      arr[i] = i;
    }
    let length = arr.length;
    for (let i = 0; i < length; i++) {
      arr.shift();
    }
  })
  .add("reverse-pop", function () {
    let arr = [];
    for (let i = 0; i < 100000; i++) {
      arr[i] = i;
    }
    let length = arr.length;
    arr.reverse();
    for (let i = 0; i < length; i++) {
      arr.pop();
    }
  })
  .on("cycle", function (event) {
    console.log(String(event.target));
  })
  .on("complete", function () {
    console.log("Fastest is " + this.filter("fastest").map("name"));
  })
  .run({ async: true });

配列長が10の場合、テスト結果:

shift x 12,899,872 ops/sec ±1.55% (88 runs sampled)
reverse-pop x 14,808,207 ops/sec ±1.31% (92 runs sampled)
Fastest is reverse-pop

配列長が1000の場合、テスト結果:

shift x 13,518 ops/sec ±1.42% (88 runs sampled)
reverse-pop x 117,351 ops/sec ±1.03% (85 runs sampled)
Fastest is reverse-pop

配列長が100000の場合、テスト結果:

shift x 1.02 ops/sec ±5.80% (7 runs sampled)
reverse-pop x 523 ops/sec ±3.62% (84 runs sampled)
Fastest is reverse-pop

配列長が大きいほど、2つの方式の性能の差が大きいです.
原因検索
shiftメソッドは、呼び出しごとに配列を巡回して、配列を一度に並進します.時間の複雑さはO(n)です.ポップメソッドは呼び出しごとに、最後の要素の処理を行うだけで、時間の複雑さはO(1)です.
具体的には、ECMAScript langer specificationでアラy.prototype.shift()とアラy.prototype.pop()を参照してください.