程序创建的每个链表节点、树节点或订单，都来自某个分配器，而分配器决定它们得到哪些地址。通用的 malloc 靠头部信息，再加上程序自己产生的临时对象，把小对象摊得很开；内存池则把它们紧紧排在一起。本讲为两者建模，并说明同一个链表从内存池遍历，缓存缺失少 3.3 倍。
地址从哪里来？
程序为一个对象申请内存时，分配器给它一块内存并返回地址。通用分配器必须记住每块有多大，所以在每块前面放一小段头部，并把块大小向上取整到 16 字节的倍数，这样什么类型的值都能存进去。最简单的模型从不重用内存：每次请求就紧接在上一块之后取一块，程序得到的是头部之后的那个地址。
def round_up(n, align): return -(-n // align) * aligndef malloc_addresses(sizes, header=HEADER_BYTES, align=ALIGN): addresses = [] start = 0 for size in sizes: addresses.append(start + header)1 start += round_up(size + header, align) return addressesprint(malloc_addresses([24, 100, 24]))print([round_up(size + 16, 16) for size in (24, 100)])
[16, 64, 192] [48, 128]
- 1块大小是请求加头部，再向上取整到 16 的倍数：24 字节需要 48 字节的块，100 字节需要 128 字节。
一个 24 字节的节点（一个收盘价、一个成交量和一个 next 指针，各 8 字节）拿到 48 字节的块，是需要的两倍；一个 100 字节的临时对象拿到 128 字节。三个地址是 16、64 和 192：第二次请求从第一块（48 字节）之后开始，第三次从第二块（128 字节）之后开始。
临时对象会把你的节点摊开
真实的代码不会凭空构造链表。两个节点之间，它要格式化一条消息、构造一个键或解析一行文本，这些临时对象也要分配内存。用一个从不重用内存的简单分配器，它们就夹在节点之间。下面第一个函数构造请求计划：一个节点后面跟三个 100 字节的临时对象；第二个函数执行这个计划，只保留节点的地址。作为对比，我们还写了一个内存池，它把固定大小的槽位一个紧接一个地发出去。
def alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes): sizes = [] node_index = [] for _ in range(n_nodes): node_index.append(len(sizes)) sizes.append(node_bytes) sizes.extend([garbage_bytes] * garbage_per_node) return sizes, node_indexdef node_addresses(n_nodes, garbage_per_node, garbage_bytes, node_bytes): sizes, node_index = alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes) addresses = malloc_addresses(sizes) return [addresses[i] for i in node_index]def pool_addresses(n, slot_bytes, base=0): return [base + i * slot_bytes for i in range(n)]print(node_addresses(3, 3, 100, 24))print(node_addresses(3, 0, 100, 24))print(pool_addresses(3, 24))
[16, 448, 880] [16, 64, 112] [0, 24, 48]
每个节点带三个临时对象时，节点之间相隔 432 字节：节点本身 48，加上 3 × 128 的垃圾。没有临时对象时相隔 48 字节。在内存池里相隔 24 字节，正好是一个节点的大小，没有头部也没有垃圾。一条 64 字节的缓存行，在分散的情形里装 1 个节点，只有头部时装 1.3 个，在内存池里装 2.7 个。现在我们遍历 3,000 个节点，读每个节点的第一个和最后一个字节，经过前面几个主题里的缓存。
def traversal_misses(addresses, node_bytes): cache = Cache() for address in addresses: cache.access(address) cache.access(address + node_bytes - 1) return cache.missesn = 3000for name, addresses in (("scattered", node_addresses(n, 3, 100, 24)), ("headers only", node_addresses(n, 0, 100, 24)), ("pool", pool_addresses(n, 24))): print(name, traversal_misses(addresses, 24), "misses, last node at", addresses[-1] // 1024, "KB")
scattered 3750 misses, last node at 1265 KB headers only 2250 misses, last node at 140 KB pool 1125 misses, last node at 70 KB
分散的链表缺失 3,750 次，铺开 1,265 KB。装着完全相同的 3,000 个节点的内存池，只缺失 1,125 次，只占 70 KB：少了 3.3 倍，节点甚至能放进二级缓存。程序、数据和遍历顺序都没变，变的只是地址。
内存池从一整块连续内存里发出大小相同的槽位，并通过空闲链表收回它们。内存区（arena）只把一个指针往前移，不带头部，任何大小都能发，并一次性全部释放。两者都能让一起使用的对象挨在一起。
一个含 3,000 个浮点数的 Python 列表，存的是指向 3,000 个独立浮点对象的指针，这些对象被分配器散落各处；而 NumPy 数组把这 3,000 个值挨着存放。遍历数组只碰几百条缓存行，遍历列表要碰几千条。这是 NumPy 快的又一个原因。
内存池要求对象大小一致，并要能大致估计数量；内存区则没法提前只释放某一个对象。把它们用在程序里的热点结构上，比如订单簿或逐笔列表，其余交给通用分配器。
你要实现什么
实验沿着本讲走：取整、简单的通用分配器、内存池、带临时对象的请求计划、节点地址、一次遍历的缺失计数，以及对 SPY 交易日链表的研究。
- 函数 · 问题依赖
- round_up(n, align)n 向上取整到倍数是多少？简单算术
- malloc_addresses(sizes)通用分配器把每个块放在哪里？round_up
- pool_addresses(n, slot_bytes)内存池呢？简单算术
- alloc_plan(...)程序会发出哪些请求？简单算术
- node_addresses(...)节点最终落在哪里？alloc_planmalloc_addresses
- traversal_misses(addresses, node_bytes)一次遍历要缺失多少次？Cache
- study(bars)内存池在 SPY 链表上能省多少？node_addressespool_addressestraversal_misses
下一个主题：到目前为止每一项代价都来自内存。本技能的最后一个硬件效应来自处理器的猜测。在分支预测里，你要为预测器建模，在带 if 的循环里数出它猜错的次数，并看清为什么同一个循环在排好序的数据上更快。
实验：评分内容
7 个任务 · 100 分- 向上取整5 分
- 简单的通用分配器20 分
- 内存池10 分
- 程序的请求15 分
- 节点的地址10 分
- 一次遍历的代价15 分
- 基于 SPY 表的研究25 分