24 — 仅追加与回收

当一行从表中被移除时，其槽位就被释放了。对于这个槽位会发生什么，有两种策略。

仅追加。 旧槽位永远保持有效。表单调增长。新行总是被追加到末尾。

回收。 被释放的槽位会被重用。表的长度保持有界。在表增长之前，新行会先进入被释放的槽位。

每种策略都是正确的；它们具有非常不同的访问模式和成本。

你何时需要考虑槽位重用

在讨论策略之前，先简短提一下 Python。大多数 Python 代码从不考虑槽位重用，因为语言隐藏了它：del obj 让垃圾回收器回收内存，下一次 obj = something() 可能会也可能不会落在同一个地址——你不知道也不关心。运行时决定。

numpy 列则相反。你在启动时分配了一次 np.empty(N_max, dtype=...)。槽位是位置的：槽位 17 是偏移量 17 * 4 处的字节。没有垃圾回收器来回收它们；只有 n_active 和关于槽位 17 一旦被释放后是被重用还是保持为空直到表被重建的规范。Python 版本的“生命周期”阶段正是运行时通常为你做的工作，由于 numpy 不会做，所以被显式化了。

仅追加

在以下情况下使用仅追加：

• 历史很重要。 来自 code/sim/SPEC.md 的模拟器的 eaten、born、dead 日志都是仅追加的——它们记录发生的事情。被移除的条目将是丢失的历史。
• 旧引用必须永远保持有效。 一些基于槽位指针的设计假设表永远不会收缩。
• 总量受限于经过的时间，而不是种群数量。 一个 30 秒、30 Hz 的模拟最多产生 900 帧；一个仅追加的帧日志最多有 900 行。无需回收。

其代价是单调的内存增长。一个长时间运行的、带有仅追加 eaten 日志的模拟器会在数小时内累积数百万行。缓解措施：

1. 定期快照 + 截断（日志被最近的片段替换）。
2. 分层存储——最近的在内存中，较旧的流式传输到磁盘（第 30 节）。
3. 如果运行时间短，就接受内存占用。

回收

在以下情况下使用回收：

• 即使总插入量很大，稳态大小也很小。 模拟器的 creatures 表，保持 100,000 存活，每秒有 100,000 次死亡和 100,000 次出生——净流量为零，但总发出量线性增长。回收使内存保持有界。
• 内存很重要。 回收将表限制在活跃行的高水位线。

其代价是引用稳定性的复杂性。一个回收槽位中的新行与之前被移除的行具有相同的槽位。持有旧槽位引用的代码会静默地解引用到新行。解决方法是代次 ID（第 10 节）：每个槽位有一个代次计数器，每次回收时递增。引用持有 (id, gen)；解引用时检查代次。陈旧的引用无法通过检查。

一个槽位分配器看起来像：

class SlotPool:
    """分配固定容量的槽位索引，回收被释放的。
       每次释放时代次递增，因此旧的 (slot, gen) 引用可以检测到它们已过时。"""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.free_slots: list[int] = []          # 被释放槽位的栈
        self.next_slot: int = 0                  # 高水位线
        self.gens = np.zeros(capacity, dtype=np.uint32)

    def allocate(self) -> tuple[int, int]:
        if self.free_slots:
            slot = self.free_slots.pop()         # 重用一个被释放的
        else:
            slot = self.next_slot                # 增长
            self.next_slot += 1
            assert self.next_slot <= self.capacity, "池已耗尽"
        return slot, int(self.gens[slot])

    def free(self, slot: int) -> None:
        self.gens[slot] += 1                     # 使旧引用失效
        self.free_slots.append(slot)

allocate 如果有可用的被释放槽位则弹出一个，否则增长。free 增加代次并将槽位添加回空闲列表。陈旧引用（带有旧代次）无法解引用到被回收的行。

空闲列表是一个用作 LIFO 栈的 Python list——append 和 pop 都是 O(1)。代次列使用 numpy，因为它在清理（第 22 节）中以步调一致的方式被访问，并且当许多槽位同时被释放时，可以从批量 numpy 操作中受益。

在两者之间选择

根据表的角色匹配策略：

表	策略	理由
creatures	回收	有界的种群数量
eaten	仅追加	历史记录
born	仅追加	历史记录
dead	仅追加	历史记录
pending_event	回收	每个滴答重建
food	回收	有界
food_spawner	常量	无移除

在一个模拟器中混合策略是正常的。规范在于明确哪个表属于哪种类型，并对每个表应用正确的机制。

练习

1. 两个仅追加日志。 将 eaten 和 born 实现为具有各自 n_active 计数器的仅追加 numpy 列。在 1,000 次滴答后，检查其长度并验证它们单调增长。
2. 一个回收池。 实现上面的 SlotPool。分配 1,000 个槽位，释放 500 个，再分配 500 个。打印第二次 allocate 批返回的槽位索引。池是重用了被释放的槽位，还是增长了？
3. 陈旧引用检测。 使用 (slot, gen=0) 分配一个槽位。释放它。在同一槽位分配一个新行——其代次为 1。尝试使用旧的 (slot, 0) 针对活跃的 gens 列进行解引用；确认检查失败。
4. 将 creatures 切换为仅追加。 将 creatures 作为仅追加（无回收，每次出生都会使表增长）运行模拟器。在稳定的出生和死亡下运行 10,000 个滴答。随时间绘制 n_active 和 next_slot 的图表——n_active 大致平坦（死亡与出生平衡），next_slot 单调增长。内存成本：next_slot * row_size。
5. 将 eaten 切换为回收。 使用回收的 eaten 运行。在 100 次滴答后，所有“这个生物在滴答 50 吃了什么”的查询都会失败，因为这些行已被重用。历史丢失了。这个失败模式使得仅追加成为日志的正确选择。
6. （挑战） 一个容量感知的分配器。 修改 SlotPool.allocate，使其在池满时返回 None 而不是触发断言。现在模拟器必须将“没有可用槽位”作为真实情况来处理——这意味着什么？（提示：世界已达到其种群容量；要么重建一个更大的池，要么丢弃新实体，要么删除最旧的实体以腾出空间。）

接下来是什么

第 25 节——表的所有权 是使该阶段所有其他规范工作的规则：每个表恰好有一个写入者。

25 — 表的所有权

每个表恰好有一个写入者。

这条规则很小。其后果却是一切。

它为何有效。 一行是一个元组（第 6 节）——其字段通过索引对齐。表的列必须一起修改以保持对齐。单一的写入者保证了这一点：代码中只有一个地方会改变这个表，因此只有一个地方可能违反对齐，所以测试一个地方就足够了。

一个有两个写入者的表有两个可能违反对齐的地方。如果它们并发运行，对齐会被非确定性地违反。如果它们顺序运行，顺序很重要并且必须被指定。无论哪种方式，正确处理的成本都随着写入者数量的增加而超线性增长。

Python 特有的问题：没有机制强制它

Rust 有一个借用检查器。&mut [T] 是单写入者所有权的类型级表达；一次只能存在一个可变引用，编译器会拒绝违反此规则的代码。Python 没有等价物。没有 &mut，没有独占访问类型，没有编译时检查。任何拥有 numpy 数组引用的人都可以修改它。单写入者规则是你通过约定强制执行的规范，而不是语言为你强制执行的约束。

这使得这条规则在 Python 中更重要，而不是更不重要。没有编译时强制执行，违规行为会在运行时表现为该规则本应防止的错误：间歇性的、静默的、延迟绑定的。规范是架构和错误之间的屏障。

numpy 视图陷阱

在 Python 中，最难处理的违规形式是 numpy 视图。numpy 数组的一个切片不是一个副本——它是一个指向相同底层字节的视图。通过视图写入会修改父数组：

# 反模式：错误的！
arr = np.zeros(10)
view = arr[2:5]    # 看起来像一个新数组；实际上是一个视图
view[0] = 42       # 同时写入了 arr[2] = 42

一个接收 view 的函数无法从变量名或其 np.ndarray 类型知道它与别人的表共享内存。没有编译时的信号。修改 view 看起来像是局部操作；对 arr 的副作用直到其他东西读取它时才可见。这是在字节级别违反单写入者规则，隐藏在一个看起来像新分配的切片后面。

三种缓解措施：

# 将数据交给可能修改它的函数时显式复制
foreign_function(arr[2:5].copy())

# 在父数组上设置只读标志（通过任何视图写入都会引发 ValueError）
arr.flags.writeable = False

# 在函数签名中记录所有权，并让其存在于契约中
def motion(pos_x: np.ndarray, vel_x: np.ndarray, dt: float) -> None:
    """读集合: vel_x, dt.   写集合: pos_x.
       pos_x 和 vel_x 不得互为别名，也不得与任何其他列互为别名。"""

前两种是运行时机制。第三种是本书所依赖的约定。函数的文档字符串声明了读集合和写集合（第 13 节）；调用者 有责任不将别名的数组传递给假设没有别名的函数。如果调用者不能保证无别名，它们会传递一个副本。

依赖于它的规范

所有这些都需要单写入者所有权才能工作：

• 第 31 节——不相交的写集合可自由并行化。 具有不相交写集合的两个系统可以在不同的进程上运行。该规则保证了没有共享的修改。
• 第 22 节——变更缓冲区。 一个侧表写入者（清理）是 creatures 的唯一写入者。所有其他系统推送到它们拥有的 to_remove 和 to_insert。
• 第 43 节——测试是系统。 一个测试系统读取一切，写入无。所有权规则保证了其读取看到一致的状态。
• InspectionSystem 模式。 一个调试检查器持有每个表的只读引用。只读访问与单写入者所有权组合，使竞争在结构上不可能发生。

实践中规则的样子

def motion(pos_x: np.ndarray, pos_y: np.ndarray,
           vel_x: np.ndarray, vel_y: np.ndarray, dt: float) -> None:
    """读集合: vel_x, vel_y, dt.   写集合: pos_x, pos_y."""
    pos_x += vel_x * dt
    pos_y += vel_y * dt

def next_event(pos_x: np.ndarray, food_x: np.ndarray,
               pending: np.ndarray) -> None:
    """读集合: pos_x, food_x.   写集合: pending."""
    ...

def apply_eat(pending: np.ndarray, food: np.ndarray,
              to_remove: list[int], energy: np.ndarray) -> None:
    """读集合: pending, food.   写集合: to_remove (追加), energy."""
    ...

对于每个表，恰好允许一个写入者：

• pos_x, pos_y：仅由 motion 写入。
• pending：仅由 next_event 写入。
• to_remove, to_insert：由许多系统写入，但每个系统仅追加其自己排队的变更；在清理之前没有人读取它们。
• creatures, food：仅由 cleanup 写入，它物化所有其他系统排队的变更。

多个系统可以通过追加到其侧缓冲区来贡献给一个表；活跃表的实际单一写入者是清理。即使许多系统提议变更，该架构也保留了这条规则。

由违规引起的错误

两个系统写入同一列会产生不一致的状态。这个错误通常是间歇性的（取决于调度）、静默的（没有错误报告，只有坏数据）和延迟绑定的（在远离原因的地方表现出来）。它们是任何并发系统中最难处理的错误之一。单写入者规则通过构造消除了它们。在语言不会捕获违规行为的 Python 中，这条规则是挡在你和错误之间的唯一屏障。

该规则递归适用。一个其条目派生自另一个表的视图表继承了所有权规则：hungry: np.ndarray 由分类饥饿的系统拥有；没有其他系统写入它。

这是结束“内存与生命周期”的规则。没有它，缓冲、swap_remove、索引映射和槽位回收在任何并发或并行上下文中都是不安全的。有了它，一切都可以组合。

练习

1. 识别写入者。 对于你模拟器中的每个表（creatures, food, food_spawner, pending_event, eaten, born, dead, hungry, to_remove, to_insert），命名唯一一个写入它的系统。如果你发现一个表有两个写入者，则违反了规则——进行调查。
2. 在你的指尖体验视图陷阱。 构建 arr = np.arange(10)。获取 view = arr[2:5]。设置 view[0] = 999。打印 arr。确认 arr[2] == 999。现在获取 cpy = arr[2:5].copy()，设置 cpy[0] = 0，打印 arr——确认 arr 没有改变。切片是视图；.copy() 不是。
3. 只读标志缓解措施。 构建 arr = np.arange(10)。设置 arr.flags.writeable = False。尝试赋值 arr[3] = 42。捕获 ValueError。现在从只读父数组派生 view = arr[2:5]——注意 view.flags.writeable 也是 False。只读属性会传播。
4. 一个构造的违规。 编写两个函数，都修改 energy。在同一个数组上顺序调用它们；结果是第二个写入的任何值。现在在两个通过 multiprocessing.shared_memory 共享数组的 multiprocessing.Process 工作器中运行它们；观察到没有引发错误，并且错误是静默的。这是单写入者规则防止的失败模式——Python 不会警告你。
5. 使用缓冲区进行重构。 取练习 4 中的一个违规行为，添加一个侧缓冲区，让一个函数写入而另一个函数读取。这两个函数现在是写入者不相交的，即使它们触及相同的逻辑概念。
6. 构建一个 InspectionSystem。 编写一个函数，它接受一个 World（一个包含所有表的数据类），读取每一列，并返回一个快照字典。在调用期间，通过 arr.flags.writeable = False 将每个输入数组标记为只读。该系统通过构造是只读的，并且不能违反规则。
7. （挑战） 作为规范写入者的清理系统。 在你的模拟器中审计：creatures、food 等的每一次修改都流经清理。每个其他系统仅写入 to_remove、to_insert 或它自己的输出。验证审计对模拟器端到端成立。请注意，这在 Python 中比在 Rust 中更难，因为没有东西为你检查它——编写一个单元测试，断言除清理外没有系统修改活跃表。

接下来是什么

你已经完成了“内存与生命周期”。模拟器的机制现在已经完整：它可以增长、收缩、回收、并行化和重放。下一个阶段是“规模”，从第 26 节——热/冷分离开始。模拟器的每滴答成本将被置于显微镜下。

26 — 热/冷分离

模拟器的 creature 表有六列：pos、vel、energy、birth_t、id、gen。运动系统读取六列中的三列（pos、vel、energy）。饥饿系统只读取 energy。清理系统读取 id 和 gen。出生日志读取 birth_t。没有一个系统会读取所有六列。

如果这些列存储在一起——相同的内存区域，相同的预取器拉取——那么每次加载都会带入内部循环忽略的字段。在缓存溢出的大小下，被忽略的字段会产生真实的带宽成本。

解决方法是一种分离：热路径上触及的字段放入一个表；很少读取的字段放入另一个表。两个表，相同的长度，相同的 id 对齐。

为什么这个教训在 Python+numpy 中更温和

在 Rust 中，每个生物的字段结构布局中，pos、vel、energy、birth_t、id、gen 都相邻存储在内存中。当运动系统读取 pos 时，它拉取的缓存行还包含 birth_t、id 和 gen——无论你是否需要，预取器都会加载它们。热/冷分离通过将冷字段移动到不同的内存区域来打破这种相邻性。

在带有 numpy SoA 的 Python 中，情况已经不同。每列都是自己连续的 numpy 数组，由各自的 np.empty(...) 调用分配。当运动系统读取 pos_x 时，它拉取的缓存行只包含 pos_x 值。它根本不会触及 birth_t 的内存。在 numpy 的 SoA 中，这些列在物理上已经是分离的。 因此，热/冷分离对于 numpy 中的 SoA 在很大程度上是组织性的——一种命名和分组具有相同访问模式的列的方式——而不是一种内存布局优化。

当布局不是 numpy 中的 SoA 时，分离确实很重要：

• AoS 数据类列表（带有属性的 list[Creature]）。从每个实例读取 c.pos_x 会将整个 Creature 对象（包括 c.birth_t 和 c.id）拉入缓存。拆分为两个并行的数据类列表（一个热 Creature 和一个冷 Creature）可以节省缓存带宽——但你已经支付了首先成为 AoS 的更大成本。根据第 11 节的 tick_budget.py，在 1M 生物时，AoS 形式的每滴答成本为 28 毫秒，而 SoA 为 0.6 毫秒。AoS 形式内部的热/冷分离可能会恢复部分差距；切换到 numpy SoA 可以恢复全部差距。
• Numpy 结构化数组——np.dtype([('pos', np.float32, 2), ('vel', np.float32, 2), ('birth_t', np.float64), ...])。这是穿着 numpy 外衣的 AoS——一个生物的字节是相邻的。读取 arr['pos'] 会步进通过缓冲区，一次跳过一行 birth_t 的字节。步进访问比 Python 循环快，但比连续的 numpy 列慢。分离有帮助；使用非结构化列更有帮助。

本书自第 7 节以来建立的 numpy 中 SoA 的规范意味着 Rust 中热/冷分离提供的大部分带宽优势，Python+numpy 已经免费给你了。 本章之所以存在，是因为两个仍然承重的原因。

分离仍然能带来什么

1. 代码组织的清晰性。 motion(pos_x, pos_y, vel_x, vel_y, energy, dt) 的读者不应该还必须知道 birth_t 在哪里。将热列放在一个 CreatureHot 命名空间下，冷列放在 CreatureCold 下，可以使第 13 节中的读集合/写集合声明更短，并使第 14 节中的依赖图更稀疏。编译器不强制执行它；规范强制执行。
2. 清理的摊销。 当槽位移动时，清理（第 22 节）写入每一列。六列意味着每次清理需要六次批量过滤操作。分离为热（4 列）和冷（2 列）不会减少总工作量，但它允许你在“影响生物”和“不影响生物”的清理阶段之间跳过冷表的清理。如果一个滴答只有食物死亡（没有生物死亡），creature_cold 的清理以零成本运行（第 20 节）——空表免费的属性与分离复合。
3. 持久化和检查。 用于重放（第 37 节）的快照需要每一列。一个实时的调试检查器可能只想要冷的元数据。分离允许检查器只读取它需要的内容，并避免为交互式查询加载热列。

分离的成本是一个额外表的成本：一个额外的名称，清理中一个额外的簿记点，以及一个必须维护对齐的额外地方。两个长度相同的表共享一个 ID 分配器；影响两者的更新必须步调一致地应用。

何时分离是错误的

• 纯 numpy 中的 SoA，内部循环在亚毫秒级别。 如果现有布局已经将每一列都作为自己的 numpy 数组，并且内部循环在以 numpy 速度运行时受带宽限制，分离不会有明显的帮助。一开始就没有浪费带宽。
• 全字段工作负载。 一个读取每个字段的调试检查系统会读取所有内容；分离增加了组织开销而没有减少访问成本。
• 行很小。 如果整行已经只有 16-24 字节，分离的开销超过了其收益。
• 频繁重新平衡。 如果哪些字段是“热”的每个滴答都在变化，固定的分离就变得无益。热/冷是一个静态决策，针对给定的目标工作负载做出一次。

决策取决于测量。在目标规模下对模拟器进行性能分析；识别内部循环实际触及的列；当分离改变了可测量的数字时才进行分离。分离是由数据赢得的，而不是由美学决定的。

一个有用的测试：在编写分离之前就命名它。“我将把 birth_t 移到一个冷表中，因为没有内部循环读取它” 是一个合理的设计选择。“我将把 birth_t 移到一个冷表中，因为 ECS 引擎就是这样做的” 则不是。

练习

这些练习扩展了模拟器的 creature 表。

1. 审计访问模式。 对于你模拟器中的每个系统，列出它读取哪些列以及它写入哪些列。每个滴答都读取的列是热的；其余的是冷的。
2. 组织性地构建分离。 将 creature 重构为 creature_hot（一个持有 pos_x, pos_y, vel_x, vel_y, energy 的类）和 creature_cold（一个持有 birth_t, id, gen 的类）。两者共享 ID 分配器。验证每行的字段在两个类之间保持对齐。
3. 在 1M 生物时对运动计时。 分离前：对运动计时。分离后：对运动计时。如果你从 numpy SoA 开始，两者应该几乎相同。分离是组织性的，而不是节省带宽的。
4. 在 numpy 结构化数组形式下对运动计时。 使用 arr = np.zeros(N, dtype=np.dtype([('pos_x', 'f4'), ('pos_y', 'f4'), ('vel_x', 'f4'), ('vel_y', 'f4'), ('energy', 'f4'), ('birth_t', 'f8'), ('id', 'u4'), ('gen', 'u4')])) 构建相同的世界。运行运动 arr['pos_x'] += arr['vel_x'] * dt。对其计时。与未分离的 SoA 版本进行比较。结构化数组版本较慢，因为它在每次读取时都会步进经过每个冷字段——这才是热/冷分离实际有帮助的布局。
5. 清理必须触及两者。 当生物死亡时，修改清理，将 keep_mask（第 22 节）应用于 creature_hot 和 creature_cold 的列。之后验证对齐性。
6. 一个糟糕的分离。 构造一个分离，其中错误的字段变为冷的（例如，energy 在冷表中）。对运动计时。每个滴答访问 energy 的缓存行程成本应该会抹杀掉其他任何地方的节省。
7. （挑战） 全字段情况。 编写一个读取每个字段的系统（例如，一个序列化器）。对分离版本计时。讨论为什么分离的开销在这里是真实的，以及为什么这是一个很好的权衡：大多数滴答并不运行这个系统。

接下来是什么

第 27 节——工作集与缓存 用数字回答了本节隐含提出的问题：内部循环的足迹有多大，以及它适合哪一级缓存？