15 — 滴答之间的状态变化在一个滴答内部世界是冻结的。系统读取其输入的一致快照修改被排队而不是被应用只有在滴答边界世界才通过一次原子转换向前迈出一步。这就是使第 14 节中的 DAG 真正起作用的规则。如果motion可以在next_event读取pos的同时修改pos那么数据是不一致的一半的生物已经移动一半还没有。即使调度按拓扑顺序是“正确的”每个系统读取的内容也不再是明确定义的。通过禁止在滴答内应用修改世界变成了一个清晰的函数world_{t1} step(world_t, inputs_t)。每个系统读取world_t每个系统写入一个缓冲区该缓冲区仅在滴答边界成为world_{t1}。具体来说apply_starve不会调用np.delete(creatures, slot)或从 Python 列表中弹出。它将注定要消失的槽位写入to_remove。creatures列在滴答的其余部分保持不变。在每个系统运行之后cleanup一起消费to_remove和to_insert在一次扫描中应用每个排队的更改。现在下一个滴答以一个一致的新世界状态开始。这种模式被称为双缓冲存在系统读取的世界world_t和变更缓冲区它成为下一个滴答读取的世界world_{t1}。这种模式随处可见——图形帧缓冲区、数据库事务、事件源系统。规则总是相同的写入累积然后提交。此规则防止的 Python 陷阱Python 有两个著名的就地修改陷阱上述规范消除了它们。迭代列表时修改列表的错误。在迭代列表时移除元素会静默地跳过元素。迭代器按索引前进list.remove将所有后续元素下移一位下一个元素现在位于迭代器已经通过的索引处# 反模式错误的creatures[c1,c2,c3,c4,c5]# 所有五个都在饥饿forcincreatures:ifc.energy0:creatures.remove(c)# 跳过 c2 和 c4 — 它们存活下来# 存活的生物5 个中的 2 个。饥饿系统被破坏模拟将永远运行下去。迭代字典时修改字典的错误。在迭代字典时移除元素会引发异常# 反模式错误的forcid,cincreatures.items():ifc.energy0:delcreatures[cid]# RuntimeError: dictionary changed size during iteration列表版本是危险的——它静默地失败并给你一个错误但有限的模拟。字典版本以不同的方式危险RuntimeError训练读者在本地修复它for cid in list(creatures.keys()):而从未认识到结构性问题。两者都是同一个教训在一段代码读取容器的同时修改它是错误无论语言是否捕获它。numpy 中规范化的等价物是每个缓冲区一个布尔掩码defapply_starve(energy:np.ndarray,to_remove:list[int])-None:starversnp.where(energy0)[0]# 只读扫描to_remove.extend(starvers.tolist())# 缓冲写入defcleanup(world:World,to_remove:list[int],to_insert:list[CreatureRow])-None:# 首先应用移除swap_remove 模式第 21 节然后插入...饥饿系统只写入to_remove。它从不接触creatures。当apply_starve返回时creatures列没有改变——当apply_eat和apply_reproduce返回时它们也没有改变。它们每个滴答只被修改一次由cleanup在每隔一个系统完成后进行。没有窗口能让系统看到不一致的世界。simlog 在生产环境中的样子.archive/simlog/logger.py中的参考实现是一个 700 行的列式日志记录器正是基于这种模式构建的。它维护两个Container——预先分配的 numpy 数组加上一个写入指针。模拟写入一个容器当该容器填满时simlog 原子地交换容器一个后台线程将已满的容器转储到磁盘。模拟永远不会观察到半刷新的缓冲区磁盘刷新线程永远不会观察到半写入的行。当本章内容被理解时阅读它它与本章教授的思想相同只是规模扩大到适合生产环境。成本和权衡需要吸收两个成本。首先每个修改都是推送到to_remove或to_insert缓冲区的额外一个条目。其次清理传递现在成为 DAG 中自己的系统。收益远远超过成本本书中的每个其他系统都干净地组合并行性变得容易。使用滴答内修改每个并行调度决策都变成一个竞争条件。使用缓冲修改竞争在结构上是不可能的——不相交的写集合在构造上就是不相交的。一个微妙的情况是插入。在一个滴答期间诞生的生物通过apply_reproduce在该滴答期间不会出现在任何系统的读集合中——它在to_insert中而不是在creatures中。新生儿在下一个滴答开始它的第一次生命。对于几乎所有的模拟来说这是正确的行为它给每个生物一个平等的生命中的第一个滴答。另一种方式——在滴答中间应用插入——是一个闭环的错误工厂。在一个系统内部写入可以在滴答内完成一个通过一次 numpy 调用为每个生物更新pos_x[:] pos_x vel_x * dt的系统在该系统内部“一次”应用所有写入因为系统的其余部分是唯一的读取者和唯一的写入者。缓冲规则适用于系统之间而不是一个系统内部的迭代之间。在一个系统内部写入是顺序的或向量化的在系统之间写入是批量的。由此产生的形态是在系统入口将所有内容读入本地数组进行工作在系统出口将输出写入缓冲区在滴答边界提交。它与音频引擎的帧缓冲区、数据库的事务提交以及版本控制文件系统的提交与合并的形态相同。它们都解决了同一个问题在世界变化时你如何读取一致的状态练习这些练习建立在模拟器框架之上。你的to_remove: list[int]和to_insert: list[CreatureRow]应该已经存在。列表错误。构建一个包含 100 个生物的列表其中 30 个具有energy 0。迭代列表每当c.energy 0时调用creatures.remove(c)。计算有多少饥饿者存活。为什么这个错误只影响其中一些提示每次移除都会使迭代器移动经过一个额外的元素。字典错误。构建一个包含 100 个相同 30 个饥饿者的dict[int, Creature]。迭代creatures.items()每当c.energy 0时调用del creatures[cid]。注意RuntimeError。现在用for cid in list(creatures.keys()):“本地”修复它——模拟现在产生正确的答案吗是的但仅仅是因为本地修复首先偶然地制作了一个完整的副本你以每个滴答一次 O(N) 分配的代价掩盖了结构性问题。缓冲修复。重写函数以计算starvers np.where(energy 0)[0]只读扫描并将结果追加到to_remove。循环完成后使用 swap_remove 模式第 21 节 的预览在一次传递中应用所有移除。验证所有 30 个饥饿者都死亡。清理传递。编写def cleanup(world, to_remove, to_insert)。首先应用移除在每个受影响的列上使用 swap_remove然后应用插入。为什么是这个顺序而不是另一个提示插入可能重用由移除释放的槽位——参见第 24 节。展示两个滴答。运行循环两个滴答。在滴答 1 之后记录种群。在滴答 2 之后再次记录。确认在滴答 1 的apply_starve中杀死的生物没有出现在滴答 2 的输入中——它们是在滴答边界处在两个滴答之间被移除的。插入是滴答延迟的。一个生物在滴答 5 繁殖父本在creatures中两个后代在to_insert中。在 cleanup 之后后代在creatures中。在滴答 6 中后代接收到它们的第一个系统传递。通过添加一个age_in_ticks列并观察后代在滴答 6 中从 0 开始而不是在滴答 5 中来确认这一点。挑战一个几乎可行的糟糕设计。尝试小心地在滴答内应用修改——首先收集死亡的生物然后以逆序索引处理它们以避免迭代器跳过错误。展示一个仍然会破坏状态的特定情况。提示一个繁殖产生一个后代其新索引与进行中的死亡冲突。挑战阅读 simlog。打开.archive/simlog/logger.py。找到两个Container实例。找到它们交换的行。找到后台线程运行的函数。注意日志记录器从不同时锁定两个容器——交换是原子的转储是在非活动容器上进行的。这是练习 3 所教内容的生产版本。接下来是什么第 16 节——由顺序决定的确定性 是缓冲规则保证的属性相同的输入相同的系统顺序相同的输出。可重复性是结构性的。16 — 由顺序决定的确定性如果相同的输入和相同的执行每次都产生相同的输出那么程序是确定性的。这听起来显而易见。但事实并非如此——大多数现代 Python 程序默认情况下不是确定性的。线程以操作系统调度的顺序运行。集合在进程之间以随机顺序迭代。系统时钟因运行而异。random.random()从一个全局实例读取其状态取决于导入顺序和先前的调用。在 ECS 架构中确定性是结构性的。滴答开始时的相同世界状态 相同的系统顺序 相同的输入事件、RNG 种子 滴答结束时的相同世界状态。比特完全相同。每次都是。这不是一个质量目标它是本书所依赖的几乎所有内容的先决条件回放。世界是解码的日志第 37 节。回放通过相同的系统序列重新运行输入来重建世界状态。没有确定性回放是不可能的。测试。一个属性测试固定一个 RNG 种子并断言模拟器在多次运行中行为相同。没有确定性每个测试都是不稳定的。分布式模拟。多台机器运行世界的相同副本。没有确定性它们在滴答 1 就会漂移分开。调试。在滴答 4783 处的一个 bug 应该在每次运行时都出现在滴答 4783 处。没有确定性调试实时 bug 变成了猜测。Python 版的配方确定性的配方是禁止内部系统中每个非确定性的来源。在 Python 中这些来源有具体的名称。不要直接迭代集合。根据code/measurement/set_iteration_order.py三个新的子进程迭代同一个六元素集合产生了三种不同的顺序run 1: delta,foxtrot,echo,bravo,charlie,alpha run 2: bravo,foxtrot,delta,echo,alpha,charlie run 3: echo,delta,foxtrot,charlie,bravo,alphaCPython 使用每个进程的随机种子对字符串进行哈希而set迭代顺序是哈希表桶布局的函数。跨进程布局不同迭代顺序不同。这是设计使然——它保护服务器免受哈希洪泛攻击——但它也是模拟器禁止的非确定性来源。永远不要在系统内部迭代集合。如果你需要一个迭代顺序使用一个排序列表、一个 numpy 数组或一个dict自 CPython 3.7 以来它按插入顺序排列并且通过了相同的测试run 1: alpha,bravo,charlie,delta,echo,foxtrot run 2: alpha,bravo,charlie,delta,echo,foxtrot run 3: alpha,bravo,charlie,delta,echo,foxtrot系统内部不要使用系统时钟。从输入事件获取时间而不是从time.time()或time.perf_counter()。时间是传入系统的值而不是从操作系统读取的。滴答循环的外部脚手架可以读取挂钟时间滴答内部的系统不能。一个 RNG带有种子。每个模拟器实例一个np.random.default_rng(seed)以定义的顺序使用。每个需要随机性的系统按 DAG 顺序从中读取。永远不要使用random.random()读取全局状态也不要使用没有 rng 对象的np.random.random()使用一个全局对象。将 rng 作为参数传递——它就像任何其他输入一样有一个声明的读集合。系统内部不要使用线程。一个系统在内部单线程运行。GIL 在这里并不能让你免于非确定性它序列化 Python 字节码但不序列化线程获取它的顺序。并行性发生在具有不相交写集合的系统之间第 31 节使用multiprocessing而不是在一个系统内部使用threading。缓冲修改。第 15 节 的规则修改在滴答边界应用而不是在滴答中间。一个 Python 特定的脚注hash()本身。自 CPython 3.3 以来对于str和bytes以及从中派生的容器包括frozenset哈希随机化默认是开启的。如果一个系统计算hash(some_string)并将该值用作其输出的一部分那么该输出在进程之间是非确定性的。当你在系统内部需要一个稳定的哈希时使用hashlib.blake2b(s.encode()).digest()——或任何确定性的哈希。这些规则是严格的。它们也是上述所有好处的代价。大多数现代 Python 程序拒绝支付这个代价并接受成本——不稳定的测试、不可复现的错误、发散的分布式模拟。本书支付了这个代价。成本在边界而不是在函数体内部确定性的成本不是绝对的。在一个系统内部实现可以自由使用任何它喜欢的东西——向量化的 numpy、低级别的优化甚至偶尔使用非确定性的库——只要输入和输出与抽象规范要求的比特完全相同。规范是在系统边界处在系统之间一切都必须是可重复的。在motion内部你可以使用pos_x vel_x * dtnumpy 批量操作确定性的或np.einsum或编写你自己的 Cython 内核。只要对于给定的输入输出pos_x在多次运行中是比特相同的无论其内部如何工作该系统都是确定性的。契约在函数边界处自由在内部。测试确定性确定性测试是具体的。使用相同的种子、相同的输入事件日志、相同的系统顺序运行模拟器两次。在 1,000 次滴答后对整个世界状态进行哈希——通过hashlib.blake2b(arr.tobytes()).hexdigest()输入每个 numpy 列并组合。如果哈希匹配你就是确定性的。如果它们不匹配找到输出首先不同的系统并追踪可变性的来源。通常是迭代了一个set、调用了time.time()、random.random()读取了全局状态。一个确定性的模拟器也是一个可以被测试的模拟器。一旦该属性成立其他每个质量目标——性能、并行性、分布——都可以安全地进行优化。没有确定性每个优化都是一次抛硬币。确定性的全部收益出现在第 11 节中命名的保存和加载阶段。模拟器可以被暂停其表序列化到磁盘稍后重新加载然后恢复——并且结果必须与从未暂停的运行无法区分。机制出现在第 36 节——持久性是表序列化一个快照是作为.npz文件写入的世界列——它们与内存中的字节相同。结合输入事件日志回放是结构性的——读取快照通过相同的 DAG 和相同的种子重放事件你就可以精确地重建任何稍后滴答的世界。确定性本节、序列化第 36 节和日志即世界第 37 节是回放的三条腿。练习运行迭代顺序示例。uv run code/measurement/set_iteration_order.py。观察集合行不同字典行相同。注意字典的存活不是对frozenset键、从集合派生的dict.values()或任何经过哈希桶顺序的操作的保证——只有表面上的“我按顺序添加了这些”模式才能存活。对世界进行哈希。编写def hash_world(world) - str它通过hashlib.blake2b(arr.tobytes()).update(...)输入每个列来生成一个十六进制摘要。使用它来比较多次运行中的世界状态。两次相同的运行。使用相同的 RNG 种子np.random.default_rng(42)和相同的输入事件运行模拟器两次。在滴答 100 时对世界进行哈希。确认它们是相等的。故意引入非确定性。将你带种子的default_rng(42)替换为np.random.default_rng()无种子——使用熵。运行两次。显示哈希不同。找出罪魁祸首。假设你的哈希不同。在 DAG 中的每个系统之后对世界进行哈希。识别哪个系统的输出首先不同以及它从哪个非确定性来源获取。常见的罪犯for k in some_set:、time.time()、random.random()、hash(some_string)。时间作为输入。找到一个使用time.perf_counter()的系统并将其重构为改为接受current_time: float作为参数。该系统现在是确定性的current_time的来源是唯一可以进入非确定性的地方。近距离观察集合陷阱。构建一个包含 1,000 个随机整数的set使用default_rng(42)以便集合内容是确定性的。在同一进程中迭代三次。顺序相同吗现在在两个新的 shell 中运行程序两次。顺序在多次运行中相同吗提示答案依次为是和否。陷阱是单个测试运行不会捕获错误两个 CI 工作器中的两次测试运行会。挑战一个属性测试。手工制作一个简单的属性测试生成 100 个随机种子。对于每个种子运行模拟器 100 个滴答。对结果世界进行哈希。验证相同的种子总是产生相同的哈希并且不同的种子通常产生不同的哈希。接下来是什么你已经完成了“时间与传递”。确定性是结构性的回放是架构性的下一个阶段是“基于存在性的处理”从第 17 节——存在性取代标志开始。模拟器的饥饿和死亡系统即将失去它们的布尔值。17 — 存在性取代标志一个生物可能处于饥饿状态。有三种建模方式。大多数 Python 程序员的第一反应是对象上的布尔字段每个Creature上的is_hungry: bool当能量低于阈值时设置为True当能量恢复时设置为False。每个关心饥饿的系统都会检查这个标志for c in creatures: if c.is_hungry: ...。这无处不在这是自然的选择这是大多数 Python 教程采用的方法。它也是三个选项中最差的一个——它既是 AoS每个生物一个对象又具有标志形态无论状态如何每个生物一个比特并且它迫使每个消费者扫描所有 N 个生物以找到 K 个饥饿的生物。中间选项——比每个实例的布尔值好但仍然不是规范化的选择——是一个布尔列。is_hungry np.zeros(N, dtypebool)与生物表的其余部分步调一致地索引。这是大多数读者在第二部分之后会采用的方法。它为每个生物支付一个字节numpy 的 bool 是一个字节而不是一个比特但这些字节是连续的numpy 向量化扫描SIMD 每个缓存行读取四十个生物。与每个对象的形式相比它快一到两个数量级。与下面的规范化形式相比无论有多少生物饥饿它仍然花费 N 个字节。数据导向的替代方案是成员资格。存在一个hungry表——一个长度为 K当前饥饿的生物数量的生物 id 的np.ndarray长度不超过它必须的长度。当且仅当生物 id 在hungry中时该生物才处于饥饿状态。该标志不存在作为一个字段它作为一个关于生物出现在哪个表中的事实而存在。# “这个生物饥饿吗”的三种表示is_hungry_attrcreatures[i].is_hungry# AoS 布尔字段is_hungry_maskbool(is_hungry[i])# SoA 布尔列O(N) 字节is_hungry_presencenp.isin(creature_ids[i],hungry)# 存在性表O(K) 字节这个替换看起来很小一个bool字段变成了另一个表中的一行。但其影响并非如此。随之而来的四个转变分发改变了形态。标志版本是每个消费系统内部的一个每个生物的过滤器——遍历所有生物检查标志如果为真则工作。成员资格版本跳过了过滤器——遍历hungry为每个条目工作。在 1,000,000 个生物中有 100,000 个饥饿的情况下标志版本处理 1,000,000 行成员资格版本处理 100,000 行——工作量相差 10 倍内存带宽也相差 10 倍。第 19 节 命名了这一点。存储改变了形态。一个np.bool_列无论标志是否设置都为每个生物存储一个字节。一个有八种可能状态的生物需要八个布尔列 每个生物 8 个字节一百万个生物存储 8 MB 的标志其中大部分是False。八个存在性表只存储被设置的条目——如果 10% 的生物饥饿hungry表的大小是标志列的 10%。持久性改变了形态。序列化一个标志列会写入每个生物的标志包括那些False的。序列化一个存在性表只写入存在的条目。后者也更接近事件日志的自然形态第 37 节每个条目一个hungry_added事件这就是全部。并发性改变了形态。同一生物表上的两个布尔列在内存中相邻对任一列的并发写入者会争用同一条缓存行第 33 节——伪共享。两个存在性表是物理上独立的 numpy 数组对不相交表的并发写入者永远不会冲突第 31 节。逆转表述这一转变的清晰方式是不再询问每个实体关于其状态而是询问状态表哪些实体具有该状态。查询被反转了查找被反转了工作量缩小了。大多数程序一生都在做错误的方向数据导向的思维模式就是反转它。一个生产示例在一个真实的 ECS 守护进程中一个准入决策是is_admitted peer_id in established_contacts。没有在 peer 上设置is_admitted: bool只有问题“这个 peer 的 id 在表中吗”。有了id_to_slot索引映射第 23 节这是 O(1)没有 I/O没有枚举。标志何时正确存在性并不是唯一有效的表示。布尔列有时是正确的——当几乎每个实体都设置了该状态时一个近乎通用的标志作为列没有任何浪费并节省了存在性扫描当谓词非常便宜可以在运行时即时计算以至于物化它是愚蠢的时is_positive_x pos_x 0当数据是短期的持久性不重要时当查找模式是“给我这个生物的状态”时每个生物的查询其中列查找是 O(1)但如果没有索引存在性表的成员资格扫描是 O(K)。在本书中存在性是默认选择标志是需要通过权衡来获得的选项。练习这些练习扩展了第 0 节的模拟器框架。添加一个hungry表。在你的世界添加hungry np.empty(0, dtypenp.uint32)。开始时为空。填充它。编写一个系统def classify_hunger(energy, ids) - np.ndarray返回所有energy[i] HUNGER_THRESHOLD的生物的 id。函数体是一行 numpyids[energy HUNGER_THRESHOLD]。每个滴答用结果替换世界的hungry。构建标志版本。添加一个并行的is_hungry np.zeros(N, dtypebool)由生物槽位索引。编写等效的分类系统设置布尔列。构建 AoS 版本。构建一个list[Creature]其中Creature是一个带有is_hungry: bool字段的dataclass(slotsTrue)。编写等效的分类——一个 Pythonfor循环。预示这是大多数教程教授的版本。在 1M 生物、10% 饥饿的情况下对三者计时。对classify_hunger存在性、布尔列版本标志和 AoS 版本计时。注意顺序和数量级。存在性和标志应该在彼此的约 2-5 倍之内都是 numpyAoS 版本应该比两者慢一到两个数量级解释器受限根据第 1 节。成员资格查询。编写def is_hungry_p(hungry, id) - bool存在性——bool(np.any(hungry id))和def is_hungry_f(is_hungry_col, slot) - bool标志——bool(is_hungry_col[slot])。在 1M 生物上对两者计时。注意没有索引映射的存在性是 O(K)标志是 O(1)。第 23 节——索引映射 是使存在性也变为 O(1) 的修复方法。“有多少生物饥饿”用三种方式编写。存在性len(hungry)。标志列int(is_hungry.sum())。AoSsum(1 for c in creatures if c.is_hungry)。在 1M 生物和 10% 饥饿的情况下比较挂钟时间。存在性版本是常数时间标志列版本作为一次 numpy 归约遍历所有 1MAoS 版本在每个步骤上都使用解释器分发遍历所有 1M。挑战持久化两者。使用np.save(is_hungry.npy, is_hungry)序列化标志列版本使用np.save(hungry.npy, hungry)序列化存在性版本。注意 1M 生物和 10% 饥饿时的磁盘大小。存在性文件约为 400 KB即使 90% 的位是0标志列文件也约为 1 MB。压缩缩小了部分差距但不是全部——np.savez_compressed对标志列的帮助比对存在性数组更大因为标志列有一长串零可以压缩而存在性数组已经很小了。接下来是什么第 18 节——添加/移除 插入/删除 命名了两种表示之间变化了什么在存在性世界中状态转换是表之间的结构性移动而不是标志的翻转。