CPython利用虚构结构体偏移寻址 压缩内存池换取CPU缓存命中率

【python】短短一行代码都读不明白？python源代码中技巧与荒谬模糊的界限 — 码农高天

码农高天

CPython内存管理通过伪造结构体基地址将usedpools压缩为纯指针数组，用反直觉的指针算术抹去链表头冗余元数据，以可读性为代价最大化高频小内存分配下的CPU缓存效率。

AI-assisted summary of 【python】短短一行代码都读不明白？python源代码中技巧与荒谬模糊的界限 — original source. Check the original for full context.

Source published:

Key ideas

  • CPython 的小内存分配核心结构 usedpools 并非直接存放链表头结构体数组，而是被压缩成仅存放双向链表 next 与 prev 指针的连续指针数组。 (0:00)
  • 源码借助 PTA 宏通过指针算术反向偏移 2 个指针宽度，捏造出虚拟的 pool 结构体基地址，使结构体成员偏移恰好命中数组元素以完成哨兵节点初始化。 (5:00)
  • 向池链表插入和删除节点时，表面上在操作 pool 结构体指针，底层却通过内存地址重合悄然修改 usedpools 数组内的指针记录。 (10:00)
  • 该黑魔法设计的核心动机在于最大化 CPU 缓存友好性，剔除庞大结构体中的冗余元数据，以最小内存体积支撑高频小内存分配。 (10:00)

Detailed notes

## Background 该内容由码农高天于 2024 年 4 月 7 日发布在 YouTube 频道上。视频未提供详细简介，主题聚焦于剖析 CPython 源码中一行极度晦涩却技巧拉满的内存管理代码。

## TL;DR 本期视频深入拆解了 CPython 小内存分配机制中的核心数据结构 usedpools 及其背后的黑魔法。通常被理解为链表头数组的 usedpools，实际仅紧凑存放了每个尺寸池所需的 next 与 prev 指针。源码通过 PTA 宏执行激进的指针算术，凭空“幻想”出一个在物理上并不存在的 pool 结构体头结点，利用字段偏移量巧妙重定向到数组内部以完成双向循环链表操作。这种看似荒谬且难以阅读的设计，本质上是为了在小内存高频分配的场景下极度压榨内存占用，从而换取极高的 CPU 缓存（Cache）命中率。

## Atmosphere & style 视频整体呈现出一种技术硬核、层层剥茧且带有一丝黑色幽默的极客氛围。码农高天以冷静透彻的语调抽丝剥茧，带领观众直面 C 语言底层指针算术的“天书”现场。随着推演深入，观众能清晰感受到从对复杂宏定义的困惑，到领悟“幻想链表头”精妙时的豁然开朗，再到对这种为了缓存优化不惜给后人留下阅读“噩梦”的极端工程手法的由衷惊叹与叹服。

## Bulletin - [00:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=0s) CPython 的小内存分配核心结构 usedpools 并非直接存放链表头结构体数组，而是被压缩成仅存放双向链表 next 与 prev 指针的连续指针数组。 - [05:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=300s) 源码借助 PTA 宏通过指针算术反向偏移 2 个指针宽度，捏造出虚拟的 pool 结构体基地址，使结构体成员偏移恰好命中数组元素以完成哨兵节点初始化。 - [10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) 向池链表插入和删除节点时，表面上在操作 pool 结构体指针，底层却通过内存地址重合悄然修改 usedpools 数组内的指针记录。 - [10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) 该黑魔法设计的核心动机在于最大化 CPU 缓存友好性，剔除庞大结构体中的冗余元数据，以最小内存体积支撑高频小内存分配。

## Key takeaways - [00:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=0s) CPython 内部的 usedpools 是负责根据 size index 索引空闲小内存池（pool）的核心数组。 - [00:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=0s) usedpools 数组大小在计算时采用了向上取整至 8 的倍数并乘 2 的技巧，内部实际存储的是链表头的成对指针而非完整结构体。 - [00:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=0s) 每个 size class 占用数组中相邻的两个指针槽位，分别对应哨兵头结点的 next 和 prev 指针，因此访问时索引都需乘以 2（如 size + size）。 - [00:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=0s) 访问 usedpools[size + size] 取得的是对应双向链表头结点的 next 指针，即链表中首个有可用空间的真实内存池。 - [05:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=300s) 核心宏 PTA 接收 size index 后，取 usedpools 元素地址并强制向低地址偏移两个指针宽度，将其强转为 pool 结构体指针。 - [05:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=300s) 真实 pool 结构体内部 nextpool 与 prevpool 成员前有两个指针占位，使得幻想头结点的成员偏移刚好精准覆盖到 usedpools 数组中的对应位置。 - [05:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=300s) 初始状态下 usedpools 元素存储的值等于其自身地址减去 16 字节，使幻想哨兵头结点的 next 和 prev 均指向自己，完成了紧凑的空循环链表构建。 - [10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) insert_to_usedpool 宏在插入新 pool 时完全沿用标准结构体赋值语法，通过幻想头的地址重叠机制隐式更新底层数组元素。 - [10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) 释放与删除 pool 节点的过程同样完全依赖结构体偏移的逆向指针写入，避免了显式维护数组下标的代码开销。 - [10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) CPython 源码注释坦承该实现极其复杂难懂，其根本原因是将结构体体积从数十字节压缩至两个指针大小，大幅提高了 CPU L1/L2 缓存命中率。

## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=0s) Python 内存管理中的 C 代码天书与 `usedpools` 数组

码农高天在开场提到，之前曾做过一期视频简要梳理 Python 的内存管理机制，当时特意跳过了 CPython 的源码，因为那部分源码出了名的晦涩难懂。本期视频通过极具代表性的短短几行代码，展示 C 代码能够写得多么离奇与抽象。为了便于理解，观众需要对 Python 内存管理以及带有头结点的双向循环链表有基本认识。屏幕上展示的主角从逻辑上说其实仅有一行代码，外面包裹着两个 `#define` 宏定义；而后续展开的一行定义也因结构极其冗长，被折成了好几段。这一段代码定义的核心就是此前提到过的 `usedpools`。

```mermaid flowchart LR accTitle: usedpools 数组与双向链表映射关系 accDescr: 展示 usedpools 数组中每两个连续指针如何分别对应一个 pool list 的 next 和 prev。 subgraph S0["Size Class 0 (1-8 Bytes)"] direction TB P0["usedpools[0]: next"] P1["usedpools[1]: prev"] end subgraph S1["Size Class 1 (9-16 Bytes)"] direction TB P2["usedpools[2]: next"] P3["usedpools[3]: prev"] end subgraph S2["Size Class 2 (24 Bytes)"] direction TB P4["usedpools[4]: next"] P5["usedpools[5]: prev"] end S0 --> S1 --> S2 ```

在通常的概念模型中，`usedpools` 常被直观理解为“包含有一堆链表头的数组”。但真正深入源码会发现，虽然它确实是一个数组，但里面的元素类型让人摸不着头脑。回顾小内存分配流程：当 Python 需要分配一块较小的内存时，它会先根据申请的字节大小算出对应的 size index，再以此 index 从 `usedpools` 找到有空余空间的内存池（pool）。代码末尾有一个常见的 C 语言向上取整技巧：`(size + 7) / 8 * 8`。其作用是强制让 index 的总数始终为 8 的倍数——当需要 1 到 8 个 index 时会分配 8 个，需要 9 到 16 个时会分配 16 个。然而令人困惑的是，这个计算出来的数量前面居然被生生乘以了 2。

更诡异的是，`usedpools` 内部定义的每一个元素为 `PT(0)`、`PT(1)`，而展开后的每个 `PT` 宏又包含两个 `PTA`，同样存在一次乘 2 的操作。码农高天揭示了其中的玄机： > “也就是说这个数组里面实际存放的并不是一堆链表头，而是这些链表头的 prev 和 next。”

每个尺寸对应的链表头只需要向前和向后的指针，因此数组中为每个尺寸分配了两个连续的位置。例如在 `usedpools` 中，索引 0 和 1 处保存的是 block size 为 8 字节的 pool list 头结点的 `next` 和 `prev` 指针。因此，在源码中所有访问 `usedpools` 的地方，只要计算出实际尺寸的 index，都必须将其翻倍： - 请求 8 字节，对应 index 0，访问 `usedpools[0 + 0]` 即索引 0； - 请求 16 字节，对应 index 1，访问 `usedpools[1 + 1]` 即索引 2； - 请求 24 字节，对应 index 2，访问 `usedpools[2 + 2]` 即索引 4。

在双向循环链表中，哨兵头结点本身不包含有效数据，仅作为结构枢纽存在。因此每次通过 `size + size` 访问 `usedpools` 时，拿到的实际上就是头结点的 `next` 指针，也就是链表中第一个真正有空闲空间的内存池。

[05:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=300s) 核心宏 `PTA` 与凭空捏造的“幻想链表头”

既然数组里存的全是散碎的指针，那么正规的链表头结构体到底放在哪里？码农高天直言： > “这个链表头的实现是整个这一段代码里面最有技巧性，或者从另外一个角度讲最荒谬的地方。”

其黑魔法的核心深植于 `PTA` 宏的一长串定义中。宏接收一个代表 size index 的参数 `x`，它先访问 `usedpools[2 * x]`，对该变量取地址，强转为字节指针（`char *` 或 `byte *`），随后在地址上减去两个 `sizeof(block *)`。在 64 位系统下，一个指针占用 8 字节，两个指针就是 16 字节；在 32 位系统下则是 8 字节。最后，代码将这个往低地址偏移后的地址强制类型转换成 `poolp`（即指向 `pool` 结构体的指针 `pool *`）。

```mermaid flowchart TD accTitle: 幻想链表头结构与内存偏移 accDescr: 示意图说明幻想链表头是如何利用结构体偏移反向定位到 usedpools 数组内部的。 subgraph VirtualPool["幻想出来的 pool 结构体 (从 0x1000 开始)"] M1["前两个未使用的成员占位 (16 Bytes: 0x1000 ~ 0x100F)"] M2["nextpool 成员偏移处 (0x1010)"] M3["prevpool 成员偏移处 (0x1018)"] end subgraph UsedPoolsArray["真实的 usedpools 数组内存布局"] UP2["usedpools[2] (地址 0x1010, 存 0x1000)"] UP3["usedpools[3] (地址 0x1018, 存 0x1000)"] end M2 -.->|"内存地址重合"| UP2 M3 -.->|"内存地址重合"| UP3 ```

为了彻底讲透这一反直觉的设计，码农高天将 `pool` 结构体进行了简化剖析。真实的 `pool` 结构体内部成员繁杂，但核心是一对 `nextpool` 与 `prevpool` 指针。在结构体的内存布局中，前面还有两个其他成员的指针占位，紧接着才是 `nextpool` 和 `prevpool`。通过具体数值推导可以清晰看到设计者的思路： - 假设 `usedpools` 数组首地址为 `0x1000`； - `usedpools[0]` 和 `usedpools[1]` 初始化时存入的值，是 `&usedpools[0]` 减去两个指针的宽度（16 字节），即 `0x1000 - 16 = 0x0FF0`； - `usedpools[2]` 位于 `0x1010`，`usedpools[3]` 位于 `0x1018`。它们被初始化的值同样是 `&usedpools[2] - 16`，即 `0x1010 - 16 = 0x1000`。

这种骚操作的本质在于“凭空幻想出一个链表头”。链表头除 `next` 与 `prev` 外的所有字段都无意义，因此 CPython 根本没有为头结点分配完整结构体内存。如果把 `head` 设为 `0x1000`，虽然 `0x1000` 处根本不存在真实的 `pool`，但当代码通过结构体指针访问 `head->nextpool` 时，C 语言编译器会根据字段偏移量寻址——`nextpool` 恰好在结构体头偏移两个指针（16 字节）的位置，也就是 `0x1000 + 16 = 0x1010`，正好命中 `usedpools[2]`。同理，`head->prevpool` 偏移三个指针（24 字节），命中 `0x1018` 即 `usedpools[3]`。在初始状态下，`usedpools[2]` 和 `usedpools[3]` 里面存的值都是 `0x1000`，也就是说幻想头结点的 `next` 和 `prev` 都指向自己，极其巧妙地完成了一个空双向循环链表的紧凑初始化。

[10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) 插入与释放节点的指针流转，以及“缓存友好”的终极代价

在向池链表中插入节点时，CPython 调用 `insert_to_usedpool` 宏。流程非常明确：先根据大小拿到 index，将其乘 2 后从 `usedpools` 提取对应的指针值，而该值永远指向当前链表头所记录的第一个有效 pool。

```mermaid flowchart TD accTitle: 插入新 pool 时的指针重定向逻辑 accDescr: 描述插入 pool 0x2000 时，幻想头与真实 pool 之间的链接建立流程。 Start["插入 Pool (地址 0x2000)"] --> GetNext["next = usedpools[2] (初始为 0x1000 / 幻想头)"] GetNext --> GetPrev["prev = next->prevpool (即 usedpools[3]，值为 0x1000)"] GetPrev --> LinkPool["pool->next = 0x1000<br/>pool->prev = 0x1000"] LinkPool --> UpdateTail["next->prevpool = pool<br/>(底层执行 usedpools[3] = 0x2000)"] UpdateTail --> UpdateHead["prev->nextpool = pool<br/>(底层执行 usedpools[2] = 0x2000)"] ```

假设现在插入一个首地址为 `0x2000` 的新 pool： 1. 取出 `next = usedpools[2]`（初始为 `0x1000`，即幻想头）； 2. 提取 `prev = next->prevpool`，依据偏移访问的是 `usedpools[3]`，拿到 `0x1000`； 3. 将新 pool 的 `next` 与 `prev` 都指向 `0x1000`； 4. 执行 `next->prevpool = pool`：由于 `next` 是幻想头 `0x1000`，对它的 `prevpool` 赋值在底层就是往其偏移位置 `0x1018`（即 `usedpools[3]`）写入 `0x2000`； 5. 执行 `prev->nextpool = pool`：同理，修改的是 `0x1010`（即 `usedpools[2]`），写入 `0x2000`。

整个过程看似纯粹在操作 `pool` 结构体成员，甚至表面上从未显式调用过修改数组的代码，但受指针偏移映射的影响，`usedpools[2]` 和 `usedpools[3]` 的内容已经被悄然重写为 `0x2000`。下次再次访问 `usedpools[2]` 时，取出的就是新插入的 `0x2000`。从链表中删除节点也是完全镜像的逆向过程，依然通过幻想头偏移修改底层数组的指针。

码农高天感叹，如果对 C 语言底层指针算术不熟悉，面对这种代码往往只能一知半解。面对“为什么不规规矩矩存一个完整链表头数组，非要搞得如此晦涩”的疑问，其实连源码注释里都留下了吐槽：原作者甚至直言自己也不完全清楚为何非要写得这么复杂，但给出了一个极有说服力的技术推测——**缓存（Cache）优化**。

- 在 Python 运行时中，小内存分配发生得极其高频，`usedpools` 会被反复密集访问； - 若按常规思路在 `usedpools` 中存放完整的 `pool` 结构体头结点，数组所需内存为 `index 数量 × sizeof(pool)`； - 真实 `pool` 结构体包含大量管理元数据，尺寸庞大，但作为链表头起作用的仅仅是 `next` 和 `prev` 两个指针； - 通过捏造不存在的结构体基地址，强行将各尺寸池的指针严密拼接为一个纯指针数组，大幅压缩了内存体积，从而极大地提升了 CPU L1/L2 Cache 的命中率。

码农高天在结尾总结道：“可能正因如此，有一个非常熟悉 C 的人写了这么一套很紧凑的缓存友好的内存管理机制，给后来学习 CPython 源码的人带来了无数的噩梦。”虽然机制精密无比，但其实现的荒谬与晦涩同样令人叹为观止。

## Notable quotes > [10:00](https://www.youtube.com/watch?v=thV-FcEJLNk&t=600s) 有一个非常熟悉 C 的人写了这么一套很紧凑的缓存友好的内存管理机制，给后来学习 CPython 源码的人带来了无数的噩梦。 — 码农高天

## Mentioned 码农高天, Python, CPython, C 语言, usedpools, PT, PTA, insert_to_usedpool

[Source](https://www.youtube.com/watch?v=thV-FcEJLNk)

中文简报

CPython利用虚构结构体偏移寻址 压缩内存池换取CPU缓存命中率 CPython内存管理通过伪造结构体基地址将usedpools压缩为纯指针数组，用反直觉的指针算术抹去链表头冗余元数据，以可读性为代价最大化高频小内存分配下的CPU缓存效率。 本期视频深入拆解了 CPython 小内存分配机制中的核心数据结构 usedpools 及其背后的黑魔法。通常被理解为链表头数组的 usedpools，实际仅紧凑存放了每个尺寸池所需的 next 与 prev 指针。源码通过 PTA 宏执行激进的指针算术，凭空“幻想”出一个在物理上并不存在的 pool 结构体头结点，利用字段偏移量巧妙重定向到数组内部以完成双向循环链表操作。这种看似荒谬且难以阅读的设计，本质上是为了在小内存高频分配的场景下极度压榨内存占用，从而换取极高的 CPU 缓存（Cache）命中率。 CPython 的小内存分配核心结构 usedpools 并非直接存放链表头结构体数组，而是被压缩成仅存放双向链表 next 与 prev 指针的连续指针数组。 (0:00) 源码借助 PTA 宏通过指针算术反向偏移 2 个指针宽度，捏造出虚拟的 pool 结构体基地址，使结构体成员偏移恰好命中数组元素以完成哨兵节点初始化。 (5:00) 向池链表插入和删除节点时，表面上在操作 pool 结构体指针，底层却通过内存地址重合悄然修改 usedpools 数组内的指针记录。 (10:00) 该黑魔法设计的核心动机在于最大化 CPU 缓存友好性，剔除庞大结构体中的冗余元数据，以最小内存体积支撑高频小内存分配。 (10:00)

Reading summary

码农高天通过解析 CPython 源码中用于管理小内存池的核心数组 `usedpools`，揭示了开发者如何利用 C 语言指针偏移“凭空捏造”出双向循环链表头；这种看似荒谬晦涩的黑魔法，本质上是为了压缩内存体积以换取极高的 CPU 缓存命中率。 usedpools 数组与双倍索引机制 (0:00) 在通常的概念模型中，CPython 管理小内存池的 `usedpools` 常被直观理解为存放完整链表头结构体的数组，但源码中其实仅存储了散碎的指针。当 Python 分配较小内存时，系统会根据字节大小计算 size index，并利用 `(size + 7) / 8 * 8` 保证数量始终对齐为 8 的倍数。然而，最终声明的数组大小以及内部宏展开均包含一次乘 2 操作。 这一设计的根源在于：`usedpools` 数组内部存放的并非完整的链表头，而仅仅是每个尺寸链表头所对应的 `next` 和 `prev` 两个指针。例如索引 0 和 1 分别对应 8 字节尺寸的 `next` 与 `prev`。因此，源码中每次通过尺寸 index 检索时都必须翻倍（如 8 字节查索引 0，16 字节查索引 2）。在空闲链表中，通过双倍索引取出的首个指针即是链表头的 `next`，直接指向链表中首个真正可用的内存池。 PTA 宏与“幻想链表头”构造 (5:00) 为避免为仅作为枢纽的哨兵头结点分配完整结构体，CPython 通过核心宏 `PTA` 创造了“幻想链表头”。该宏接收 size index，在获取对应 `usedpools` 元素地址后，强行在字节层面减去两个指针的宽度（64 位系统下为 16 字节），并将其强制类型转换为指向 `pool` 结构体的指针。 这一操作利用了 `pool` 结构体本身的内存布局：其核心成员 `nextpool` 与 `prevpool` 前方刚好有两个指针大小的占位。尽管减去偏移后的虚拟基地址并不存在真实的结构体实例，但当程序通过该虚构指针访问 `head->nextpool` 和 `head->prevpool` 时，编译器依据字段偏移计算出的寻址位置，恰好精准重合在 `usedpools` 数组内对应的连续元素上。在初始化时，数组元素填入该虚构基地址，便以零额外内存开销完成了空双向循环链表的闭环。 隐式状态更新与 CPU 缓存收益 (10:00) 在向池链表插入新节点时，宏 `insert_to_usedpool` 按照常规双向循环链表逻辑调整前后指针。但由于参与链接的头结点是一个虚构地址，当代码对其成员 `next->prevpool` 与 `prev->nextpool` 进行赋值时，底层实际上借助结构体偏移量，悄然覆写了 `usedpools` 数组对应槽位中的值。整个过程中表面未见任何显式修改数组的代码，数组内容却已完成同步重定向。 源码注释与分析指出，这种极端设计的主要动机在于 CPU 缓存（Cache）优化。Python 运行时小内存分配发生得极其高频，若规规矩矩保存庞大的完整结构体头结点，数组会占用大量内存；将其压缩为纯指针数组，大幅削减了内存体积，从而显著提升了 CPU L1 与 L2 缓存的命中效率。 码农高天总结认为，CPython 这种游走在精妙技巧与荒谬代码界限上的设计，展现了对 C 语言底层指针算术的极致压榨；它在微观层面换取了高度紧凑且缓存友好的性能优势，但也因反直觉的抽象机制，给后来的源码阅读者与维护者带来了巨大的认知负担。

Source quotes

[10:00] 码农高天: 有一个非常熟悉 C 的人写了这么一套很紧凑的缓存友好的内存管理机制，给后来学习 CPython 源码的人带来了无数的噩梦。

Original transcript

[0:00] 在之前的一期视频里呢,我们简单的聊了一下Python的内存管理机制在那期视频里呢 我跟大家说 我们先不看这个cpython的原代码 因为这个原代码比较难读那今天我们就用一个小小的例子短短的几行代码来让大家感受一下它的C代码有可能会有多么难读那在看这期视频之前除了我刚才提到的之前做的那期python内存管理的视频之外还推荐大家去看一下我前面做的有头双向循环链表的视频因为我们也用得到OK 那在画面中的就是我们今天的主角了这个部分从逻辑上说其实只有一行代码当然他做了两个pound define对吧那下面的一行代码呢也因为比较长给分成了很多个部分那这行代码呢就是我们之前视频里提到的used pools我们之前说我们可以把这个used push 理解为包含有很多链表头的数组现在我们当然能看得出来它是一个数组但这数族里面是什么东西啊完全摸不到头脑那在之前内存管理的视频里面我们介绍过当python需要用到一块比较小的内存的时候他首先会根据他申请内存的大小找到一个index然后根据这个index从usedpools里拿到一块有内存的pool我们看后面这个部分一个长量加7除以8再乘以8这个是index的总数还记不记得我们说我index0是1-8个byteindex1是9个byte到16个byte这里的加7除8再乘8就是C里面还蛮常用的一个小trick它本质上相当于一个取者通过这个操作呢它可以让index的总数永远是8的倍数当我需要一个到8个index的时候我永远会有8个index当我需要9个到16个index时候我永远会有16个index这个部分还比较好想啊 大家可以自己过一下脑子那有了这个index的数量前面乘以2是个什么东西同时我们可以看到这个usedPulse里面写的每一个element是一个pt0pt1而在上面每一个PT实际上是两个PTA这里也有一个非常诡异的成二那这个部分我可以提前告诉大家这里之所以需要放两个指针因为这两个指针分别代表着链表头的上一个和链表头的下一个也就是说这个数族里面实际存放的并不是一堆链表头而是这些炼表头的pref和next举个例子 在这个used pools这个数组里面 index0和index1的位置分别保存着block size是8的那个pool list的链表头The Next和Prev我们可以看到在所有使用used pools的地方他在计算出了我使用的size之后都要把它做一个乘2比如说我现在需要的size是8个byte对应的真正的index0然后我就要从这个usedpulls0+0也就是0里边去找如果我要拿16个byte它对应的size的index应该是1我就在used pools里面的1+1也就是2去找如果我要24个byte他对应的index是2我就要在2加2也就是4里面去找因为每一个size对应的index在这个usedPulls里面实际上保存了两个指针前面那个指针是练表头的Next后面那个指针是练表头的pref我们知道恋表头是没有含义的他在那只是为了实现方便所以我们每一次拿这个usedPullsize+size的时候我们实际上是拿到的链表头的next也就是第一个有空间的铺那么接下来问题就来了这个链表头在哪呢这个链表头的实现是整个这一段代码里面最有技巧性或者从另外一个角度讲最荒谬的地方它的核心逻辑在PTA里面 也就是这一长创代码这一长圈代码的输入是一个X也就是这个S [5:00] Size所对应的index的大小然后这里他做了一个套娃他去access这个used pools的2乘以x然后把这个变量进行取值取指完了 cast到一个byte形上面那这一整个部分的操作实际上就是Use the Pulse里面的第0个跟第1个都去找第0个的地址而第二个和第三个都去找第二个的地址以此类推在找到这个地址之后他减去了两个size of block星那block 显然是一个指针对不对 size of 指针在64位系统上就是8个byte在32位系统上就是4个byte最后他把求得的这个结果给Cast到了一个铺屁上面POOP就是 pointer to poo就是一个指向2的指针说到这里我相信所有人都懵了所以我们把它具体化一下我给大家举个例子我们看首先我们把Pool这个struck给做了一个简化那真正的Pullstruck是这样的但是在这个结构里面我们用到的是前面这个部分我们看到它这里面有一个非常明确的链表结构就是next pool跟prev pool我们把它简化之后变成这个样子这个strut前两个member是两个指针接下来就是他的next跟prep根据我们刚才usedPulse规则我们尝试写几个首先在我们定义这个usedPulse变量的时候 它会有一个地址我们假设这个地址是0x1000根据刚才的规则used Pulse 0和used Pulse 1保存的是同一个值这个值是usedpus 0的地址减去两个指针的大小usedpus 0的地址就是0x1000每一个指针是8个byte所以这两个地方在初始化的时候保存的就是0xFF0也就是0x1000-16个byte那接下来两个used push2和used push3保存的就是usedpus2的地址减去两个指针的大小UsePulse2的地址是0x1010剪完之后这两个就是0X1000那这样做的目的是什么这样做的目的,实际上,是幻想了一个炼表头我们知道一个有头链表里面的链表头除了next跟prev之外 其他的东西是没有意义的 我们不会使用到所以在这里他幻想了一个链表头的struct这个链表头的地址就是我保存的这个next的地址往上走两个指针的位置为什么是往上走两个指针因为这个链表头的struct是先有的两个指针然后是next指针和priv指针比如我们做了一个head等于used pulse2那usedPulse2就是0x1000对不对那0x1000这个位置实际上并没有保存我们任何的链表头但是如果我们幻想这个位置有一个链表头的话当我们做head箭头next pool的时候它实际上是会根据这个next pool的offset进行一个de-reference当head是0x1000的时候他会计算OK那next pool应该是这个位置往下数两个指针也就恰好是used pus2这个位置也就是0x1010这个位置而这里面保存的数据就是我们初始化的0x1000同意的PREV POOL是从我这个位置 0x1000往下数两个指针再往下数一个指针也就是usedpus3这个位置它保存的数据也是0x1000也就是说这种方式把一堆幻想头唯一有用的next跟pref给紧凑的拼到一起了我们可以看到在初始化之后我们实际上是把这个幻想头给初始化成了一个空链表的因为这个头的地址就是他的next的地址也是他的Prev的地址而当我们取usedPulse2的时候我们实际上拿到的是这个幻想头的next就这个used pools2 [10:00] 永远是我们的幻想头的Next也就是第一个合法的数据当我们要插入真正的Pool的时候我们是使用这个 insert to use pool我们可以看到他首先拿到了size也就是这个大小所对应的index然后把size成了个2从usedPulse里面拿这个值出来那这个值我们提前讲过它永远是幻想头的next然后他拿到了这个Next Prep Pool我们知道由于next永远是幻想头的下一个所以prive实际上永远会是这个幻想头的位置接下来这个操作就很简单了就是把pool给放到幻想头和之前的第一个合法值之间这里我们注意一下尽管我们没有显示的修改used pools但由于我们幻想头的next跟prev实际上是指向usedpulls的地址的所以当我们做prev next pull=pull的时候我们是修改了usedPools的size加size的我们再尝试把这件事拆解一下我们假设现在有一个新的铺要插入进来这个pool的地址是零差2006我们根据刚才的操作,首先拿到Next=usedPools2在当前这个状态下 usedpulse2是0x1000 也就是我们的幻想头的地址那prev等于nextprevpoo由于nex是0x1000所以接着是几个扑是0x1018 也就是used push 3 也是0x1000这个时候我们先把pull的next跟pull的pref都设置好也就是PUL现在的NEXT跟PREV都是我们这个幻想头 0x1000接着我们做了一个nextprevpull这个操作本质上相当于usedpulse3=0x2000然后我们又做了一个prev next pool等于pool这个操作实际上等于used plus 2=0x2000那做完了这一套操作之后在下一次你再access used pools 2的时候你实际上就是拿到了我们现在插入的这个pool你会得到的地址是0x2000当我们把这个Pool从链表里面拿掉的时候我们会做一波相似的操作由于POO的上一个是幻想头所以当我们做幻想头的下一个等于pull的下一个的时候 我们还是改了usedpulls2同样的道理used push 3也会一直被修改 指向这个链表实际上的尾端我不知道我有没有把这个机制给讲明白我已经尽了最大的努力了但是如果你对C语言不是很熟悉的话你可能听完我说这些也就是一直半解因为在这个实现里面确实用到了很多C的trick尤其是在内存地址上面的trick那这也就是为什么我经常说C语言是一门非常值得学习的语言因为学了它之后呢很多底层的东西你就知道它到底是怎么运行的了那肯定有人会问明明一个很简单的形式为什么Python要做成这样那肯定有人会问确实他这个used push 数组里面完全可以就保存一大堆空的链表头就好了我们每一次拿到的都是实际的一个真实的链表头然后我们找他的Next这样会让整个代码的实现变得容易理解非常多实际上如果你去看前面的注释注释里面写了我也不知道为什么这个used post要写的这么复杂他给出了一个可能的解释他说这件事可能跟cash也就是缓存有关那我们知道由于python里面的内存操作非常多所以这个used pools是会被大量的使用的如果我们能把这个 used to pulse给尽可能的缩小我们占用的缓存数量就会变小我们刚才给出了一个方案是让usedPulls里面直接保存所有的空链表头这样的话一个used pulse需要的大小就是index*链表头的size而我们刚才看到了一个PullStruct里面包含着大量的乱七八糟的数据而对于链表头来说只有next和pref是我们实际上会用到的那可能正面 [15:00] 如此有一个非常熟悉C的人写了这么一套很紧凑的缓存友好的内存管理机制给后来学习Cpython圆满的人带来了无数的噩梦好那这期视频内容确实比较硬核如果看不懂也不要为难自己感谢大家的收看如果喜欢的话记得点一下关注别忘了一键三连哦