CPython列表扩容1/8分配系数选择原因及缩容实现细节咨询

CPython列表扩容机制相关问题解答 #

1. 1/8扩容系数的选择逻辑 #

CPython的列表设计优先面向通用使用场景，1/8的系数是内存利用率和操作开销平衡后的结果：

• 内存利用率更高：翻倍扩容的最坏内存浪费为50%，而1/8扩容的最坏内存浪费仅为12.5%。Python日常开发中存在大量长度在几十到上百的小列表，小幅度扩容能大幅降低这类常见场景的内存浪费。
• 小列表的常数项补偿：扩容公式里的newsize < 9 ? 3 : 6常数项，保证了长度小于9的小列表不会频繁触发扩容，抵消了小系数带来的扩容次数上升问题。
• 摊销复杂度依然达标：1/8的扩容系数下，追加操作的摊销时间复杂度仍为O(1)，只是常数因子略高于翻倍扩容，通用场景下完全感知不到性能差异。

2. 小幅度扩容提升原地重分配成功率的推论是否正确 #

这个推论是正确的。
列表扩容调用的C标准库realloc函数，在当前列表内存块尾部有足够连续空闲空间时，会直接原地扩容，不需要拷贝已有元素；如果没有足够空间，才会申请新内存块并拷贝全量元素。
小幅度扩容每次申请的额外内存更少，当前内存块尾部刚好有足够空闲空间的概率更高，原地扩容成功的概率远高于翻倍扩容，反而可以抵消掉一部分扩容次数上升带来的开销。

3. 该实现的实际运行表现 #

这套扩容+缩容的策略已经在CPython中落地多年，经过了大量生产场景验证：

• 通用场景下表现非常均衡，无论是小列表的内存占用，还是大列表的操作性能，都能满足绝大多数开发需求。
• 仅在极端的持续追加百万级以上元素的写入密集场景下，性能会略低于翻倍扩容的实现，但这类场景属于特殊需求，通常会用预分配列表长度、使用更适合批量操作的库等方式优化，不属于通用列表的优先优化目标。

补充说明里提到的缩容逻辑设计也和扩容策略配套：只有实际使用量降到分配容量的一半时才触发缩容，就是为了避免“加一个元素扩容、删一个元素缩容”的频繁抖动问题。

内容的提问来源于stack exchange，提问作者Chris Z