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

文章目录列表 append 的底层真相上预分配策略——为什么每次 append 不是真的加一个导入语1 ~ 列表的 C 数据结构——比你想的更简单1.1 CPython 中列表的定义1.2 底层就是 C 数组2 ~ allocated 和 ob_size 的区别——你是真元素还是预留空间2.1 用 sys.getsizeof 看容量变化2.2 预分配的意义3 ~ 扩容公式——new_allocated new_size (new_size 3) 33.1 源码3.2 逐步推导3.3 验证——推算扩容历程4 ~ 为什么频繁扩容会吃性能——我的真实经历4.1 背景4.2 排查4.3 修复4.4 什么时候该预分配思考 总结结尾列表 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;关键就三个东西字段含义访问方式ob_size当前列表实际元素个数Python中len(lst)ob_item指向底层 C 数组的指针不能直接访问allocated底层数组的容量分配的最大槽位数不能直接访问但可通过sys.getsizeof推算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← 底层数组长度也是3Java 的 ArrayList 底层也是数组——同样的设计思路。但 ArrayList 扩容倍数是 1.5xPython 列表的扩容倍数不一样下面讲。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) 33.1 源码CPythonObjects/listobject.c中list_resize函数里有一个公式new_allocatednew_size(new_size3)(new_size9?3:6);翻译成人话新容量 新长度 新长度 / 8 一个修正值取决于列表大小 3是右移 3 位——等价于除以 8即约 12.5% 的额外空间小列表 9额外加 3大列表额外加 63.2 逐步推导空列表 → append 第一个元素 new_size1new_allocated1(13)31034底层数组容量变成4append 第5个元素时 new_size5new_allocated5(53)35038底层数组容量变成8append 第9个元素时 new_size9new_allocated9(93)691616底层数组容量变成16这个公式保证了每次扩容后新容量大约是 112.5% 的新长度 一个修正值——避免了像 Cstd::vector那样固定倍数1.5x 或 2x带来的极端浪费。3.3 验证——推算扩容历程importsys lst[]prevsys.getsizeof(lst)foriinrange(50):lst.append(i)currsys.getsizeof(lst)ifcurr!prev:print(fappend 第{i}个元素时扩容{prev}→{curr})prevcurr输出示例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):parsedparse_log(log)results.append(parsed)运行耗时18 秒。4.2 排查列表从 0 扩容到 500000触发约 30 次realloc。每次realloc要分配新的、更大的内存块把旧内存中所有元素的指针逐一复制到新区域释放旧内存累计下来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 什么时候该预分配场景建议知道大概的元素个数如从数据库 COUNT 查询用[None]*n预分配不知道个数但可以从上面或总量推算出来用lst [] 做完了做一次.extend()不知道个数也无可估量用lst []Python 的 12.5% 扩容公式性能已经很好了思考 总结Python 列表不是链表——是 C 层的动态数组。它的 append 操作底层做了四个步骤检查ob_size是否已达allocated上限如果容量不够 → 按new_size (new_size 3) 修正值计算新容量调用realloc分配新数组 → 复制旧元素 → 释放旧数组在新数组的ob_size位置写入新元素 →ob_size这套机制保证了单次 append 在大概率里 O(1)但在扩容那一瞬间可能是 O(n)。了解扩容公式之后你就知道什么时候该预分配列表。下篇继续拆——“pop、insert、remove 的底层代价为什么不一样”。结尾各位小伙伴上篇到这里就结束了。源码骑士感谢阅读源码骑士 — 源码级拆解从底层看透技术关注跟博主一起从源码视角深耕底层原理❤️点赞让优质内容被更多人看见⭐收藏核心知识点存好随用随查评论分享你的经验或疑问一起交流一键四连别忘了给博主一键四连️寄语知道扩容公式在手性能调优先看预分配。结语列表底层是 C 数组append 不是 O(1) 是 O(1) 均值。记住扩容公式new_size (new_size 3) 3这就是性能调优的密码。下篇继续一键四连