关于优化CPython list.pop(0)时间复杂度的技术问询

我在研究CPython的list.pop(k)方法实现时发现，移除列表第k个元素的时间复杂度为O(n-k)，因为需要将后续元素左移一位。那移除第一个元素时，能不能通过直接将列表指针偏移至第二个元素来提升性能？

当前实现代码片段 #

PyObject **items = self->ob_item;
v = items[index];
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
if (size_after_pop == 0) {
    Py_INCREF(v);
    list_clear(self);
    status = 0;
}
else {
    if ((size_after_pop - index) > 0) {
        memmove(&items[index], &items[index+1], (size_after_pop - index) * sizeof(PyObject *));
    }
    status = list_resize(self, size_after_pop);
}

设想的优化实现 #

PyObject **items = self->ob_item;
v = items[index];
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
if (size_after_pop == 0) {
    Py_INCREF(v);
    list_clear(self);
    status = 0;
}
else {
    if ((size_after_pop - index) > 0) {
        if (index == 0) {
            self->ob_item = &items[1];    // 此处为修改点
        } else {
            memmove(&items[index], &items[index+1], (size_after_pop - index) * sizeof(PyObject *));
        }
    }
    status = list_resize(self, size_after_pop);
}

这个优化思路的问题 #

直接偏移ob_item指针的做法看似能省去memmove的开销，但实际上违背了CPython list的核心内存设计，会引发一系列问题：

• 内存管理错误：CPython list的ob_item指向的是通过内存分配函数申请的连续内存块起始地址。如果修改ob_item指向中间位置，后续调用list_resize或内存释放逻辑时，会因为使用错误的指针导致内存泄漏、双重释放等严重问题。
• 索引逻辑破坏：list的所有元素访问、遍历操作都依赖ob_item作为起始基准。偏移指针后，原索引0会对应到原来的索引1，彻底打乱list的索引逻辑，除非同步修改其他内部状态，但这会大幅增加实现复杂度，引入更多潜在bug。
• resize操作异常：list_resize在缩小列表时可能会重新分配更小的内存块，此时需要将原数据拷贝到新内存。如果ob_item已经偏移，拷贝过程会漏掉原内存块的起始部分（即便这部分元素已经被移除），导致数据拷贝错误。

综上，这个优化思路不可行，CPython现有的实现是基于内存安全和逻辑一致性的合理设计。

内容的提问来源于stack exchange，提问作者Osniel Teixeira