为什么pop比shift快？

Question

道格拉斯·克罗克福特在《JavaScript权威指南》一书中指出，“shift通常比pop慢得多”。jsPerf证实了这一点。是否有人知道为什么会出现这种情况？从一个不太复杂的角度来看，它们似乎正在做着类似的事情。

- zjmiller

---

在IE 6中，它不是这样的。 :-) - RobG

这是关于编程的内容，翻译成中文如下：对于搜索者来说，这是我发现的最干净的jsperf：http://jsperf.com/shift-vs-pop-and-reverse-plus-pop/1 - zamnuts

@zamnuts：该测试实际上未使用pop()或shift()的结果，因此现代浏览器会将其优化为无操作。这里是一个修改后的版本，显示了pop()确实比shift()更快：http://jsperf.com/shift-vs-pop-and-reverse-plus-pop/7 - Nate

几年后，您应该检查上面评论中的jsperf。在Chrome 61中， shift 实际上更快，尽管只是一点点。 - Brian Arsuaga

Answer 1

为了移除返回的项而无需重新寻址数组并使其失效，shift() 需要移动整个数组；而pop()则可以通过减少其长度来简单地删除最后一项。

- geekosaur

---

附录：据我所知，目前没有JavaScript的实现与Perl相同，保留起始偏移量以便shift函数可以简单地增加它。尽管如此，它“可能”做到这一点，这将消除这种减速。 - geekosaur

使用起始索引意味着获取每个索引需要额外的工作，因为您必须执行 "startIndex + index" 才能获取所需的索引。我怀疑如果移位操作真的很流行，就会实现 startIndex 或类似功能，但由于直接属性访问更受欢迎，所以最好针对它进行优化。 - RobG

@RobG：我并不是在问他们为什么没有这样做，而是解释为什么引用中说“通常”。 - geekosaur

实际上，这完全取决于两件事情，即读写操作的数量和数组的大小...较小的数组最好重新编号，而在不经常更改大小的数组中进行常量读写也最好重新编号，这只是一些想法。 - Sean_A91

Answer 2

shift()需要重新索引整个数组，而pop()则不需要。

pop()只是简单地移除了数组中的最后一个元素。因此，元素并没有发生移动；只需要更新.length即可。

shift()会移除数组中的第一个元素。这需要对数组中所有元素进行重新索引，使得[1]变成[0]等等。

- Andrew Moore

Answer 3

我在使用node (使用chrome v8引擎) 进行一些测试时发现，对于长度不超过120k的数组而言，shift方法和pop方法的性能相差不大。但是当数组长度超过120K时，shift方法的性能急剧下降。

var sum;
var tests = [125000,130000];

console.log(JSON.stringify(process.versions));

tests.forEach(function(count) {
    console.log('Testing arrays of size ' + count);
    var s1 = Date.now();
    var sArray = new Array(count);
    var pArray = new Array(count);
    for (var i = 0; i < count ; i++) {
      var num = Math.floor(Math.random() * 6) + 1
      sArray[i] = num;
      pArray[i] = num;
    }
    console.log(' -> ' + (Date.now() - s1) + 'ms: built arrays with ' + count + ' random elements');

    s1 = Date.now();
    sum = 0;
    while (pArray.length) {
      sum += pArray.pop();
    }
    console.log(' -> ' + (Date.now() - s1) + 'ms: sum with pop() ' + count + ' elements, sum = ' + sum);

    s1 = Date.now();
    sum = 0;
    while (sArray.length) {
      sum += sArray.shift();
    }
    console.log(' -> ' + (Date.now() - s1) + 'ms: sum with shift() ' + count + ' elements, sum = ' + sum);
});

输出：

{"http_parser":"1.0","node":"0.10.22","v8":"3.14.5.9","ares":"1.9.0-DEV","uv":"0.10.19","zlib":"1.2.3","modules":"11","openssl":"1.0.1e"} 
Testing arrays of size 125000
-> 14ms: built arrays with 125000 random elements
-> 2ms: sum with pop() 125000 elements, sum = 436673
-> 6ms: sum with shift() 125000 elements, sum = 436673 
Testing arrays of size 130000
-> 50ms: built arrays with 130000 random elements
-> 1ms: sum with pop() 130000 elements, sum = 455971
-> 54372ms: sum with shift() 130000 elements, sum = 455971

- bhirt

---

我在Chrome浏览器中没有看到这个。即使是对于小数组来说，shift方法似乎比pop方法慢得多：http://jsperf.com/push-pop-vs-unshift-shift/3 - UpTheCreek

我注意到Chromium 76在15044个元素及以上时开始出现不良的移位性能，而Firefox 69则快得多。 - Lonnie Best

Answer 4

这两者的差异可能微不足道——未经优化的执行器运行shift的速度可能比pop慢得多，但经过优化的执行器则不会。

您可以像这样进行优化：

let WrapArray = _=>{
  //Ensure no other ref to `_`.

  let numlike = _=>isNaN(_)?false:true
  let num = _=>Number(_)
  {
    let shift_q = 0
    return new Proxy(_, {
      get(first_t, k){
        switch(k){
          case 'shift': return (z={})=>(z.r=first_t[0 + shift_q], delete first_t[0 + shift_q++], z.r)
          break; case 'length': return first_t.length - shift_q
          break; default: return first_t[numlike(k)?num(k) +/*todo overflowguard*/shift_q:k]
        }
      },
      set(first_t, k, v){
        switch(k){
          case 'length': first_t.length = v + shift_q
          break; default: first_t[numlike(k)?num(k) +/*todo overflowguard*/shift_q:k] = v
        }
      }, 
      has(first_t, k){
        return (numlike(k)?num(k) +/*todo overflowguard*/shift_q:k) in first_t
      },
      deleteProperty(first_t, k){
        delete first_t[numlike(k)?num(k) +/*todo overflowguard*/shift_q:k];return 543
      },
      apply(first_t, t, s){
        first_t.call(t, s)
      },
      construct(first_t, s, t){
        new first_t(...s)
      },
    })
  }
}
(_=WrapArray(['a','b','c'])).shift()
console.log(_.length/*2*/, _[0]/*b*/, _[1]/*c*/, _[2]/*undefined*/)

- Pacerier

---

我不理解这个，但你能想到这个确实令人印象深刻。 - Alexander Dixon

Answer 5

由于 shift() 会重新索引数组，所以在大数组上使用 shift 方法会非常缓慢。

var array = [];
for(var i = 0;i< 1000000;i++){
    array.push(i)
}
var start = new Date().getTime()
for(var i = 0; i< 100000; i++){
 array.shift();
}
var duration = new Date().getTime() - start;// duration is so large, greater than 3 minutes

But the duration is just 8ms when using linked-queue

var LQueue = require('linked-queue')
var queue = new LQueue()
for(var i = 0;i< 1000000;i++){
    queue.enqueue(i);
}
console.log("Queue length:"+ queue.length);
var start = new Date().getTime()
queue.dequeueAll(function(data){
})
var end  = new Date().getTime();
console.log("Time:" + (end - start));// 8 ms
console.log("Queue length:"+ queue.length);

- hungnt

---

数组实验有一个错误。你只移动了100,000个元素，在推入1,000,000个元素之后。我想编辑，但改变太小了。很好，你把这个与队列联系起来了，但我想看到一个交替操作的例子。比如1000次推送后跟着1000次移动，重复10,000次（或更多）。我想数组的偏移优化迟早会消耗太多内存并需要重新分配。链表没有同样的问题。 - Elias Hasle

Answer 6

如果您要进行移位操作，则必须将数组中的所有元素向后复制。如果要执行弹出操作，则只需要将数组的长度减1。从技术上讲，实现可能会绕过此问题，但是您需要存储一个额外的“shift”变量，以便告诉您数组的真实起始位置在哪里。然而，这种类型的操作在实践中并没有被证明非常有用，因此大多数实现通过仅存储数组指针的起始位置和长度值来节省空间。

- Mikola

---

如果存储memStart、arrStart、memLength和arrLength，则开销不可能如此之大。然后，元素将作为arrStart +索引访问，如果0 <=索引< arrLength，则未定义。您不必在每次访问时计算arrStart。重新分配/GC可以遵循与数组另一端相同的逻辑。 - Elias Hasle