Python列表扩容超额分配策略为何异于其他语言？性能影响如何？

问题背景 #

我查阅了Python 3.4.2版本的源码，发现一段关于列表扩容超额分配策略的注释：

/* This over-allocates proportional to the list size, making room

• for additional growth. The over-allocation is mild, but is
• enough to give linear-time amortized behavior over a long
• sequence of appends() in the presence of a poorly-performing
• system realloc().
• The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
  */

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

我了解到Go、Rust、C#等语言的列表扩容普遍采用达到容量上限时翻倍的策略，而Python后续版本仅对该策略做了微调，核心逻辑未变。想知道Python为何采用这种独特的扩容方式，以及该策略对性能的影响。

原因分析 #

• 内存与扩容频率的平衡：翻倍策略虽然能大幅降低扩容次数，但会造成较多内存浪费——比如刚扩容到32的列表，若后续仅新增1个元素，剩余31个位置就会闲置。Python的策略是按当前所需大小的1/8额外分配，再搭配固定偏移（小列表加3，大列表加6），既避免了频繁扩容，又把内存浪费控制在更低水平，更适配Python中大量中小规模列表的使用场景。
• 兼容老旧系统的内存分配性能：注释里明确提到，针对部分realloc性能较差的系统，这种温和的扩容方式能减少大内存块的分配、拷贝开销，即使在这类系统上，连续append操作的分摊时间复杂度依然能保持线性（O(1)）。
• 历史设计延续：Python诞生于内存资源紧张的年代，翻倍扩容的内存开销在当时难以接受，这种紧凑的扩容策略是当时的最优选择，后续版本为了兼容性和稳定的性能表现，保留了核心逻辑。

性能影响 #

• 分摊时间复杂度仍为O(1)：虽然每次扩容的增量不是翻倍，但按比例+固定值的分配方式，能保证多次append操作的平均时间是常数级，不会出现频繁扩容导致的O(n²)最坏情况。
• 内存利用率更高：对于中小规模的列表，这种策略的内存闲置率远低于翻倍策略。比如列表增长到25元素时，Python的容量刚好是25；而如果用翻倍策略，16扩容后是32，会浪费7个元素的内存空间。
• 超大列表的扩容频率略高：当列表规模极大（如百万级以上）时，每次仅扩容1/8的容量，会比翻倍策略多几次扩容操作，但现代系统的内存分配效率已经很高，这种差异对实际性能的影响可以忽略，且Python场景下这类超大列表并非主流。

内容的提问来源于stack exchange，提问作者Shu ba