为什么对于bytearray，b.pop(0)比del b[0]慢200多倍？

Question

让它们竞争三次（每次一百万次弹出/删除）：

from timeit import timeit

for _ in range(3):
    t1 = timeit('b.pop(0)', 'b = bytearray(1000000)')
    t2 = timeit('del b[0]', 'b = bytearray(1000000)')
    print(t1 / t2)

时间比例（在线尝试!）：

274.6037053753368
219.38099365582403
252.08691226683823

为什么pop执行相同操作的速度要慢那么多？

- Kelly Bundy

---

.pop() 函数至少涉及一个赋值操作，但是它的区别非常显著。 - roganjosh

可能与 pop() 必须返回该值有关，因此它必须进行引用计数并且还要转换返回值。在 Python 中进行属性访问需要很长时间 (b.pop --> 查找属性，然后调用是昂贵的，但可以通过 pop = b.pop 进一步改进)，而使用del则只需一个单独的字节码指令即可。 - Ashwini Chaudhary

@AshwiniChaudhary 不，这些东西并没有太大的差别。即使是 pop(0) 与 b[0]; del b[0]; b.pop 的区别仍然超过了100（参见https://tio.run/##dYxBDgIhDEX3c4rugMQozGyME09ijIHIKIlA03TD6RGFhRv/pv3ty8PCz5yWI1KtG@UIHKIPDCFiJh5tmrZMcIOQgGx6eLmo0wQtbOA8GCkwo9RK7EC4dnWFvSWyRRr9jVqhEZ/Pvk2humD@EbiLvq5w9y/oWwf/@oYCKSSWbA48q1rf）。 - Kelly Bundy

这仅适用于bytearray。而那些引用的时间比率是针对3.8的。3.9、3.10、3.11的数字是多少？ - smci

@smci 是的，只适用于bytearray。不确定你为什么这样说。标题已经说了“适用于bytearray”。我也检查了3.10并得到了类似的比率，我知道速度差异的原因，因此毫无疑问其他人在所有最新版本上都会看到类似的比率。我只是选择链接到TIO，因为它可以缓存结果。 - Kelly Bundy

Answer 1

当你运行b.pop(0)时，Python会像你预期的那样将所有元素向后移动一个位置。这需要O(n)的时间。

当你运行del b[0]时，Python只是简单地将对象的起始指针增加1。

在两种情况下，都会调用PyByteArray_Resize来调整大小。当新的大小小于分配大小的一半时，分配的内存将被缩小。在del b[0]的情况下，这是数据将被复制的唯一点。因此，这种情况将花费O(1)的平摊时间。

相关代码：

bytearray_pop_impl函数：总是调用

memmove(buf + index, buf + index + 1, n - index);

针对 del b[0]，调用 bytearray_setslice_linear 函数，其中 lo == 0，hi == 1，bytes_len == 0。它到达此代码（带有 growth == -1）：

if (lo == 0) {
    /* Shrink the buffer by advancing its logical start */
    self->ob_start -= growth;
    /*
      0   lo               hi             old_size
      |   |<----avail----->|<-----tail------>|
      |      |<-bytes_len->|<-----tail------>|
      0    new_lo         new_hi          new_size
    */
}
else {
    /*
      0   lo               hi               old_size
      |   |<----avail----->|<-----tomove------>|
      |   |<-bytes_len->|<-----tomove------>|
      0   lo         new_hi              new_size
    */
    memmove(buf + lo + bytes_len, buf + hi,
            Py_SIZE(self) - hi);
}

- interjay

---

好的回答。你知道为什么开发者没有选择对 b.pop(0) 也增加指针吗？ - Jérôme Richard

@JérômeRichard 我已经看到过很多次了。他们不想优化不常见的情况。这样做既可以避免稍微减慢常见情况（可能总体上会有损失！），也可以避免需要编写、测试、审查、维护、阅读额外代码的情况，可能引入错误，并可能使事情变得复杂。请参阅切片优化的原始讨论 ，这是一个完美的例子。 - Kelly Bundy

有人对切片优化（FIFO缓冲区）有使用案例，这引起了一些争议。有趣的是，他们在某个时候谈到了“弹出”，但并不是指pop()，而是指删除一个切片。他们从未谈论过弹出单个字节，我确实认为这对于bytearray来说非常罕见。尤其是当数组像我的这样巨大时。当数组变得更小时，我的速度比也要小得多。 - Kelly Bundy

@PM2Ring 嗯，我不这么认为。我们知道为什么切片删除被实现了，在链接的原始讨论中有提到。我怀疑（没有检查）单个索引的del被优化是一个副作用。至少在那次讨论中，从未提到过优化pop。 - Kelly Bundy

@PM2Ring 这个差异，以防有人想检查是否有明确的优化简单索引删除。 - Kelly Bundy

Answer 2

我必须承认，我自己也对这个时序感到非常惊讶。在我说服自己它们确实是正确的之后，我深入研究了CPython源代码，我认为我找到了答案- CPython通过将指针递增到数组的开头来优化del bytearr[0:x]：

    if (growth < 0) {
        if (!_canresize(self))
            return -1;

        if (lo == 0) {
            /* Shrink the buffer by advancing its logical start */
            self->ob_start -= growth;

您可以在这里找到关于 del bytearray[...] 的逻辑（通过使用 bytearray_setslice，其中的 values 为 NULL），代码实现见此处。该方法调用了 bytearray_setslice_linear，其中包含上述优化。

相比之下，bytearray.pop 没有实现此优化，源代码请参见此处。

- Dillon Davis