Sherfiter's wiki for fun第 12 章 · 内存视角
这是全课的收官章,做一件前面十一章刻意不做的事:不再把数据结构当成抽象模型,而是当成本子上真实的字节。第 2 章那个「链表输给数组百倍」的实验悬案、堆排输给快排的原因、Trie 吃内存的病根,所有「理论与实测不符」的账,都要在内存这一层结算。配合计算机组成课的第 7、8 章(Cache、虚拟内存)食用,效果最佳。
12.1 顺序表:栈上的门牌,堆上的地皮
typedef struct { int *data; int len, cap; } SeqList;
一个顺序表变量本身只是三个字段(栈上 12 字节的门牌),真正的数据在 malloc 出来的堆块里:
栈 堆
┌─────────────┐ ┌─────────────────────────────┐
│ data ●──────┼─────▶│ [1][2][3][4]...[n] [空余...] │
│ len cap │ └─────────────────────────────┘
└─────────────┘ ↑ 一块连续内存,可能是 4096 字节的整数倍
a[i] 的机器级行为(计组第 4 章):地址 = data + i×4,一次算术加一次解引用,编译成一条 mov。连续性的真正红利在 Cache:读 a[i] 时,CPU 顺手把该缓存行(64 字节 = 16 个 int)整个搬进 L1,接下来 15 次访问全在缓存里打转,这是「顺序访问快」的硬件账本。
12.2 链表:散落的孤岛
typedef struct Node { int val; struct Node *next; } Node;
每个节点独立 malloc,堆管理器把它们撒在整片堆上,地址毫无规律:
栈 堆(散布)
┌──────┐ 0x55c1a00: [val|next●]──┐
│ head●┼─▶ 0x55c9f40: [val|next●]──┼──▶ 0x55b3210: [val|NULL]
└──────┘ (不相邻,相隔随机) │
遍历链表的每一步 p = p->next 都是一次不确定地址的解引用:目标多半不在缓存里,一次 cache miss,去内存拿(几十纳秒,第 7 章的延迟表),拿回来只用到 16 字节却污染了一条缓存行。这就是 2.3 跑分百倍差距的账目明细:数组遍历的访存几乎全命中,链表几乎全 miss。树、图、跳表全是同一模型的推广,「指针越多、跳跃越频繁,miss 越惨」,快排(顺序扫描)赢堆排(上下跳跃)、B+ 树把节点做成一页一页(一次 IO 拿一大块)全是这条物理法则在不同层级的体现。
补一个内存视图下的「链表翻案」机会:如果节点是批量分配、地址连续的(比如从预分配数组里切节点),链表的 miss 会大幅减少。这是「对象池」「arena 分配器」的原理,也是第 2 章练习里内存池实验的理论依据。数据结构的性能不只取决于「结构」,还取决于「节点从哪来」。
12.3 栈与堆:生命周期就是所有权
| 栈 | 堆 | |
|---|---|---|
| 分配 | 编译器自动(move rsp) | malloc/free |
| 生命周期 | 函数返回即消失 | 手动控制 |
| 速度 | 一条指令 | 池化后快,碎片后慢 |
| 适合 | 局部变量、小缓冲 | 需要「活过函数」的数据 |
数据结构的选型经常被生命周期决定:链表节点、树节点必须放堆(它们要活过创建它们的函数);纯函数内的临时数组放栈(自动回收)。堆的真正代价不是 malloc 那几纳秒,是碎片:频繁增删不同大小的节点,堆被切得七零八落,后来大块申请无连续空间可给(操作系统课第 6 章的外部碎片在用户态重演)。这也是「能用数组就不用链表」的另一层理由:数组的一次大块分配对堆最友好。
12.4 每个结构的「指针税」
按「每存一个元素多花几个字节」重新盘点一遍全课结构:
| 结构 | 每元素额外开销 | 花在哪 |
|---|---|---|
| 顺序表(满载) | 0 | 纯数据 |
| 顺序表(负载 50%) | ≈ 4 字节/元素 | 预留空间 |
| 单链表 | 8 字节 | next |
| 双向链表 | 16 字节 | prev + next |
| 二叉树 | 16 字节 | left + right |
| 哈希(链地址) | 8 字节 + 桶数组均摊 | next + 桶 |
| Trie(26 叉) | 208 字节/字符! | 26 个指针 |
| 跳表 | ≈ 8~16 字节 | 期望两层的 next |
一张 sizeof 就能验证的账:
printf("%zu %zu\n", sizeof(int), sizeof(Node)); // 4 和 16
// 存一个 int 花了 16 字节:75% 是指针税
Trie 的 208 字节/字符解释了第 11 章「为什么工程实现要压缩」:一亿单词的 Trie,裸指针版要几十 GB,双数组 Trie 压到几百 MB。指针税是空间,miss 是时间,两种税交多交少,决定了每个结构在真实机器上的命运。
12.5 全课收官:三个视角的合一
现在可以把整门课的三个视角叠在一起了。算法视角(第 1 章):数操作次数,O(n²) 不能忍。结构视角(第 2~11 章):选对组织方式,O(n) 变 O(log n)。内存视角(本章):同一结构,布局不同,常数差百倍。三张账本一起算,才算真的会做工程决策:比如「LRU 缓存」的经典实现是哈希表 + 双向链表(哈希 O(1) 定位,链表 O(1) 摘挂),听起来指针税高、miss 多,但它的操作模式(命中后把节点摘到队头)恰好只需要改指针、不需要大规模移动数据,这两次 O(1) 指针操作,比把整个数组搬家划算。没有最好的结构,只有最匹配访问模式的布局,这句话就是数据结构课的全部。
常见错误
- 以为 malloc 的内存是清零的。malloc 只管给地,不打扫(里面是上次用剩的垃圾);要零初始化用 calloc。未初始化的堆内存读出来是随机值,这也是「程序有时对有时错」的经典来源。
- sizeof 量的是类型不是「用到的大小」。
sizeof(seq)永远是 12(三个字段),不包含堆上那块数据;评估内存占用要把堆块一并算。 - 在栈上开巨大的局部数组。
int a[1000000]直接 4MB 栈,递归里开直接爆栈(8MB 上限);大块数据上堆。
练习
- 手算:64 字节缓存行,int 数组一次行加载覆盖几个元素?Node(val 4 + next 8 + 对齐 = 16 字节)呢?据此估算「遍历 10 万元素」两者的 cache miss 数量级差。
- 动手:写程序遍历同一个大数组的「按序」和「按随机下标」两种方式,计时(第 7 章计算机组成 Cache 的实验翻版),差距应该在一个数量级,解释原因。
- 动手:实现「数组池化链表」(节点从预分配数组取,下标代替指针),重跑第 2 章的链表插入实验,对比裸 malloc 版,写一句结论。
- 思考:用本章的语言重新解释第 8 章的「堆排输给快排」:两者的数组访问模式各是什么?哪个对缓存行更友好?再想想为什么操作系统第 3 章的 CFS 用红黑树而不担心 miss(提示:树遍历在缓存里常驻的路径很短)。