13-列表append的底层真相（上）-listobject源码中的预分配策略

列表 append 的底层真相（上）：预分配策略——为什么每次 append 不是真的加一个

📖文章简介：lst.append(1)是我们写得最多的 Python 操作之一，但你知道它底层做了什么吗？本文从 CPython 源码listobject.c出发，逐层拆解列表的内存布局——底层是一个 C 数组、ob_size和allocated两个字段的区别、以及append触发扩容时的增量策略（new_allocated = new_size + (new_size >> 3) + 3）。用图文对比讲清楚"列表为什么没有预定义长度"和"扩容为什么开空调 12.5%"。穿插真实经历：一个日志解析脚本因为忘了预分配列表导致频繁扩容，耗时从 2 秒骤增到 18 秒。

🎬 个人主页：源码骑士

❄专栏传送门：《Android开发基础》《python基础课程》

⭐️热衷从源码视角拆解技术底层原理，将复杂架构讲得通俗易懂

🎬 源码骑士的简介：
5年Android Framework系统开发经验，曾主导多项系统级性能优化专项
技术栈覆盖Android系统全链路（Binder/Handler/AMS/WMS/启动流程）及Java后端全家桶（Spring + MyBatis + Redis + Oracle）
累计产出原创技术文章100+篇，文章以源码拆解为特色，被读者评价为"看一篇胜过啃一周文档"

导入语

lst.append(1)——你一天写几十次的代码。我问一个简单的问题：Python 列表在底层是用什么实现的？

大部分人的答案：“链表。”——错的。“动态数组。”——对了一半，但说不出扩容倍数是多少。

列表是 Python 中使用频率最高的容器。但它的底层实现你了解得越深，性能调优的空间就越大。上篇聚焦listobject.c源码中的内存布局和预分配策略——讲清楚"Python 列表的 append 为什么可以做到（均摊）O(1)"。

写这篇文章的起因是一个早年的脚本——从 Redis 导出 50 万条日志解析后塞进列表，单次运行耗时 18 秒。同一个脚本加了一行lst = [None] * 500000替换lst = []— 耗时降到 2 秒。原因就是列表扩容。

1 ~> 列表的 C 数据结构——比你想的更简单

1.1 CPython 中列表的定义

在 CPython 源码的Include/listobject.h中，列表对象的结构体长这样（我简化了）：

typedefstruct{PyObject_VAR_HEAD// 包含 ob_size（当前元素个数）PyObject**ob_item;// 指向底层 C 数组（存指针）Py_ssize_t allocated;// 底层数组的"容量"（分配了多少槽位）}PyListObject;

关键就三个东西：

1.2 底层就是 C 数组

列表在 Python 层是"容器"，在 C 层就是一段连续的指针数组。也就是说 Python 列表本质不是链表——它是一段连续内存，存的是"指向堆中各元素的指针"。

Python 中： lst=[42,"abc",[1,2]]C 层 ↓ ob_item:[▮▮▮]← 三个指针 │ │ └──→ 指向堆里的 list 对象[1,2]│ └────→ 指向堆里的 str 对象"abc"└──────→ 指向堆里的 int 对象42ob_size:3← 当前有三个元素 allocated:3← 底层数组长度也是3

Java 的 ArrayList 底层也是数组——同样的设计思路。但 ArrayList 扩容倍数是 1.5x，Python 列表的扩容倍数不一样（下面讲）。

2 ~>allocated和ob_size的区别——你是真元素还是预留空间

2.1 用sys.getsizeof看容量变化

importsys lst=[]print(sys.getsizeof(lst))# 空列表，56 字节 ← 头部+指针开销lst.append(1)print(sys.getsizeof(lst))# 88 字节？ ← 有东西了，底层 C 数组已分配lst.append(2)print(sys.getsizeof(lst))# 88 字节 ← 和上面一样！说明容量没变lst.append(3)print(sys.getsizeof(lst))# 88 字节 ← 还是没扩容lst.append(4)print(sys.getsizeof(lst))# 144 字节？ ← 扩容了！

注意到——加了三个元素，getsizeof没变。加到第四个元素的时候跳变了。这是因为allocated（容量）大于ob_size（真实元素数），多出来的空间是预留在那的。

2.2 预分配的意义

如果每次 append 都要realloc（重新分配内存 + 拷贝现有元素），那连续 append 100 次的累积代价是巨大的——每个元素都要被复制多次。

Python 的做法是：每次扩容时多分配一些槽位，未来几次 append 直接写到预留空间里，不需要触发realloc。这就是"均摊 O(1)"的由来——单次 append 不是总 O(1)，但多次 append 的平均成本接近 O(1)。

3 ~> 扩容公式——new_allocated = new_size + (new_size >> 3) + 3

3.1 源码

CPythonObjects/listobject.c中list_resize函数里有一个公式：

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

翻译成人话：

• 新容量 = 新长度 + 新长度 / 8 + 一个修正值（取决于列表大小）
• >> 3是右移 3 位——等价于除以 8，即约 12.5% 的额外空间
• 小列表（< 9）额外加 3，大列表额外加 6

3.2 逐步推导

空列表 → append 第一个元素： new_size=1new_allocated=1+(1>>3)+3=1+0+3=4底层数组容量变成4append 第5个元素时： new_size=5new_allocated=5+(5>>3)+3=5+0+3=8底层数组容量变成8append 第9个元素时： new_size=9new_allocated=9+(9>>3)+6=9+1+6=16底层数组容量变成16

这个公式保证了：每次扩容后新容量大约是 112.5% 的新长度 + 一个修正值——避免了像 C++std::vector那样固定倍数（1.5x 或 2x）带来的极端浪费。

3.3 验证——推算扩容历程

importsys lst=[]prev=sys.getsizeof(lst)foriinrange(50):lst.append(i)curr=sys.getsizeof(lst)ifcurr!=prev:print(f"append 第{i}个元素时扩容：{prev}→{curr}")prev=curr

输出示例：

append 第 0 个元素时扩容：56 → 88 append 第 4 个元素时扩容：88 → 120 append 第 8 个元素时扩容：120 → 184 append 第 16 个元素时扩容：184 → 248 append 第 24 个元素时扩容：248 → 312 append 第 32 个元素时扩容：312 → 376 append 第 40 个元素时扩容：376 → 472

每 4 / 8 / 16 / 24 / 32 / 40 个触发一次扩容——间距变大，扩容也增长了。

4 ~> 为什么频繁扩容会吃性能——我的真实经历

4.1 背景

一个日志解析脚本：从 Redis 读取 50 万条日志行，每条经过正则解析后添加到结果列表：

# 原始版本：动态扩展results=[]forloginredis.lrange("logs",0,-1):parsed=parse_log(log)results.append(parsed)

运行耗时：18 秒。

4.2 排查

列表从 0 扩容到 500000，触发约 30 次realloc。每次realloc要：

1. 分配新的、更大的内存块
2. 把旧内存中所有元素的指针逐一复制到新区域
3. 释放旧内存

累计下来，50 万个指针被复制了约 4 百万次。这直接导致脚本慢了 9 倍。

4.3 修复

# 优化版本：提前分配固定大小的列表results=[None]*500000# 一次分配 50 万个槽位fori,loginenumerate(redis.lrange("logs",0,-1)):results[i]=parse_log(log)

运行耗时：2 秒。预分配避免了所有 realloc——底层 C 数组在开始前就已经是 50 万槽位。

4.4 什么时候该预分配

思考 && 总结

Python 列表不是链表——是 C 层的动态数组。它的 append 操作底层做了四个步骤：

1. 检查ob_size是否已达allocated上限
2. 如果容量不够 → 按new_size + (new_size >> 3) + 修正值计算新容量
3. 调用realloc分配新数组 → 复制旧元素 → 释放旧数组
4. 在新数组的ob_size位置写入新元素 →ob_size++

这套机制保证了单次 append 在大概率里 O(1)，但在扩容那一瞬间可能是 O(n)。了解扩容公式之后，你就知道什么时候该预分配列表。下篇继续拆——“pop、insert、remove 的底层代价为什么不一样”。

结尾

各位小伙伴，上篇到这里就结束了。源码骑士感谢阅读！

源码骑士 — 源码级拆解，从底层看透技术

👀关注：跟博主一起从源码视角深耕底层原理

❤️点赞：让优质内容被更多人看见

⭐收藏：核心知识点存好，随用随查

💬评论：分享你的经验或疑问，一起交流

🔄一键四连：别忘了给博主一键四连！

🗡️寄语：知道扩容公式在手，性能调优先看预分配。

结语：列表底层是 C 数组，append 不是 O(1) 是 O(1) 均值。记住扩容公式new_size + (new_size >> 3) + 3，这就是性能调优的密码。下篇继续！一键四连！