18 — 添加/移除 插入/删除在标志的世界里状态转换是一次写入。让一个生物饥饿设置is_hungry True。让它不再饥饿设置is_hungry False。标志一直存在只有它的值改变了。在存在性的世界里状态转换是表之间的移动。让一个生物饥饿插入一行到hungry表中。让它不再饥饿移除这一行。该状态没有要翻转的字段它只有一个问题该生物当前是哪个表的一行。# 标志规范的 Python 教程defbecome_hungry_flag(is_hungry:np.ndarray,slot:int)-None:is_hungry[slot]True# 存在性defbecome_hungry_presence(hungry:list[int],creature_id:int)-None:hungry.append(creature_id)defstop_being_hungry_presence(hungry:np.ndarray,creature_id:int)-np.ndarray:posnp.where(hungrycreature_id)[0]ifpos.size:# swap_remove将最后一个条目移动到释放的槽位然后删除最后一个hungry[pos[0]]hungry[-1]returnhungry[:-1]returnhungry“但我只是设置了布尔值问题是什么”本章要求你放弃的 Python 惯用法比is_hungry更古老、更普遍。它是creature.alive False——软删除。每个介绍类的 Python 教程都会教它当一个东西应该停止被处理时设置一个布尔值并在处理它之前检查该布尔值。成千上万的生产代码库正是基于这种模式运行的。成本是真实的。根据code/measurement/alive_fraction.py在 1,000,000 个生物上不同存活率下的一次运动更新存活率AoSfor c if c.alivenumpy 布尔掩码numpy 存在性id掩码/存在性1.0 %10.12 毫秒0.684 毫秒0.067 毫秒10.2 ×10.0 %25.65 毫秒3.868 毫秒0.747 毫秒5.2 ×50.0 %23.78 毫秒9.470 毫秒2.426 毫秒3.9 ×90.0 %32.03 毫秒3.426 毫秒4.417 毫秒0.8 ×100.0 %34.16 毫秒1.616 毫秒4.968 毫秒0.3 ×阅读这些行。在 1% 存活率下——对于像“饥饿”、“濒死”或“刚刚生成”这样的瞬态状态的典型情况——存在性比布尔掩码版本快 10 倍比 AoS 版本快 150 倍。随着存活率的上升差距缩小大约在 80-90% 存活率时布尔掩码开始胜出在 100% 存活率时它更快numpy 发现全 True 掩码并使用连续的切片路径而不是花式索引。AoS 列在 25-35 毫秒之间持平与存活率无关。解释器遍历所有一百万个生物并在每个生物上支付getattr(c, alive)的成本即使 99% 的生物稍后被跳过。“软删除”模式节省了实际工作但从未逃脱每个元素的分发税。对表格的诚实解读存在性是瞬态状态的正确默认选择低存活率饥饿/濒死/即将醒来的睡眠状态的常见情况布尔掩码是近乎通用状态的正确默认选择存活率 ≥ 90%AoS 在所有存活率下都是错误的。没有任何规模范围能让解释器循环胜出。[!NOTE]“存活”比本章使用的范围更广。在一款大型多人在线角色扮演游戏中相关的生物集合是玩家渲染半径内的生物——当 CPU 紧张时半径本身可以动态缩小根据第 4 节的滴答预算余量来权衡可见生物数量。存在性表是一个查询而不是一个形而上学状态当系统提出不同问题时它的条目会改变。“存活”、“饥饿”、“在范围内”、“已订阅”、“本帧活跃”——相同的形态不同的问题。上面的交叉点数字适用于你的模拟正在提问的任何问题以及答案恰好具有的任何比例。值得命名的两个后果转换是结构性的。当一个生物越过饥饿阈值时hungry表中会实际出现或消失一行。没有就地修改表增加一行或减少一行。这就是为什么第 22 节变更缓冲区清理是批量的存在的原因——在一个滴答期间的添加和移除必须排队然后在边界处应用以便正在进行的迭代不会看到一半的更改。延迟清理模式诞生于本节。词汇消失了。没有set_hungry(True)没有set_hungry(False)没有is_hungry()访问器对。有become_hungry插入和stop_being_hungry移除甚至这些通常也被内联到检测转换的系统中。数据导向程序没有 getter 和 setter它有在表之间移动行的系统。没有property。没有__setattr__钩子。没有“验证存在于模型上”的装饰器。检测阈值的系统就是验证就是转换就是审计跟踪。一个有用的测试你能在不命名bool的情况下描述转换吗“这个生物变得饥饿了”——嗯有什么改变吗是的hungry表增加了一个条目。“这个生物不再饥饿了”——表减少了一个条目。系统中的每个状态变化都有一个结构性的对应物而这个结构性的对应物就是规范描述。多表转换相同的模式处理更丰富的转换。想象一个生物可以处于饥饿、困倦或死亡状态。三个表hungry、sleepy、dead。一个生物通过在它们之间移动来进行转换。在饥饿时变得困倦向sleepy表添加一行它可以同时处于两个状态。死亡从hungry和sleepy中移除该生物清理影响所有相关的存在性表并添加到dead中。转换是一个多表操作但每个表仍然只是一个 id 的 numpy 数组。这种形态——作为插入和移除的状态变化——是 EBP 为你提供的所有其他东西的先决条件。第 19 节 中的分发是直接遍历表因此表的内容作为世界的规范状态在结构上是必要的。没有需要咨询的标志只有现在表中有什么。练习饥饿转换。使用你来自第 17 节的hungry表。每个滴答读取energy对于任何低于阈值的生物追加到一个hungry_to_add缓冲区对于任何返回到高于阈值的生物追加到一个hungry_to_remove缓冲区在滴答边界应用两者。运行 100 个滴答能量随机变化验证hungry总是精确地包含当前能量低于阈值的生物。运行存活率示例。uv run code/measurement/alive_fraction.py。注意交叉行——布尔掩码开始击败存在性的存活率。注意 AoS 列没有交叉点它在每个比例下都失败。没有布尔值没有 setter。在你的代码中搜索生物上的任何布尔字段。用一个存在性表替换它。setter 和 getter 都消失了。搜索任何包装状态字段的property装饰器同样的命运。第二个存在性状态。添加一个sleepy表。一个生物是困倦的如果它的能量高到不需要立即进食。一个生物可以同时处于sleepy和hungry状态吗不——根据定义这两个条件是互斥的。或者设计它们使其互斥。通过在每滴答后检查np.intersect1d(hungry, sleepy).size 0来验证不变量。死亡。添加一个dead表。当一个生物的能量降到零以下时追加到dead并从hungry中移除如果存在也从sleepy中移除。清理逻辑现在是多表的引入一个小型的transition_to_dead(ids, hungry, sleepy, dead)辅助函数处理所有受影响的存在性表。转换日志。添加events: list[tuple[int, int, str]]滴答号生物 id事件名称。每次插入/移除都会产生一行。在 100 次滴答后事件日志是规范历史——记录的每个状态变化。这是第 37 节——日志就是世界的预览。挑战从日志重建。仅给定事件日志和初始生物 id重建最终的hungry、sleepy和dead表。重建是一次性的回放如果它产生与实时模拟相同的表那么你的转换被正确捕获了。挑战在你的机器上的交叉点。在 70% 到 95% 之间更精细地改变存活率重新运行示例——比如说在 70、75、80、85、90、95%。找到在你的硬件上掩码和存在性交叉的存活率。确切的交叉点取决于缓存大小、分支预测器和特定的 numpy 构建。接下来是什么第 19 节——EBP 分发 命名了表成员资格表示使其免费的分发形态。19 — EBP 分发一个需要对饥饿生物采取行动的系统有两种找到它们的方法。过滤迭代。遍历所有生物对于每个生物问“它饥饿吗”如果饥饿则进行工作forslotinrange(len(creatures)):ifis_hungry[slot]:drive_hunger_behaviour(slot)基于存在性的分发。直接遍历hungry表为每个条目进行工作forcreature_idinhungry:drive_hunger_behaviour(creature_id)在 numpy 中两种形态都提升为一次批量操作# 过滤的基于掩码energy[is_hungry]-HUNGER_BURN_RATE*dt# EBP基于存在性energy[hungry]-HUNGER_BURN_RATE*dt两者产生相同的结果。两者的成本非常不同。过滤版本为每个生物评估is_hungry——一次 1,000,000 字节的扫描以找到 100,000 个饥饿的生物。EBP 版本读取hungry的 100,000 个条目并直接索引。根据code/measurement/alive_fraction.py第 18 节的示例在 10% 的稀疏度下存在性版本比布尔掩码版本快 5 倍在 1% 时快 10 倍。大多数模拟器状态是稀疏的——在任何给定的滴答中一小部分生物在进食一小部分在繁殖一小部分在死亡——因此 EBP 的复合优势随处可见。一个有用的直觉这就像一个漫无目的的购物者试图记住他们需要什么和一个有购物清单的购物者之间的区别。清单版本更短、更快并且在构造上是正确的。你不会查看清单来问“这个过道在我的清单上吗”——你沿着清单走每个过道访问一次。简化为“过滤迭代”的三种 Python 反形态Python 教程教授了几种模式它们都相当于过滤迭代。每种在页面上看起来不同它们都咨询每个实体的谓词而不是遍历存在性表。1.isinstance链。当实体被建模为类层次结构时——Hungry(Creature)、Sleepy(Creature)、Dead(Creature)——分发通常遍历一个大列表# 反模式错误的forentityinentities:ifisinstance(entity,Hungry):drive_hunger(entity)elifisinstance(entity,Sleepy):drive_sleep(entity)elifisinstance(entity,Dead):# 无事可做pass列表包含每个实体函数体根据每个实体询问类型标签谓词。存在性表版本将其拆分为三个独立的系统每个系统遍历自己的表。2. 多态方法分发。“更 Pythonic”的版本使用动态分发# 反模式错误的forentityinentities:entity.update(dt)其中Creature.update在Hungry、Sleepy、Dead中被覆盖。if/elif从源代码中消失了它被隐藏在了 Python 的方法解析顺序中。每次迭代仍然支付属性查找、MRO 遍历和函数调用设置。谓词现在不可见了但仍然在每个实体上被咨询并且为每个子类类型跳入不同方法体的缓存损失是真实存在的。EBP 将其替换为三个显式函数每个函数作用于自己的表。3. 列表推导式过滤器。Pythonic 的函数式风格版本# 反模式错误的hungry_creatures[cforcincreaturesifc.is_hungry]forcinhungry_creatures:drive_hunger(c)这看起来像 EBP——有一个只有饥饿生物的列表——但列表是通过扫描所有 N 个生物并分配一个包含 K 个指针的新 Python 列表来构建的。过滤过程的成本与过滤迭代版本相同外加一次列表分配。EBP 避免了扫描因为存在性表在状态转换发生时第 18 节保持更新读取不需要重新计算它。所有三种反形态都在迭代时咨询谓词。EBP 安排世界使得谓词在系统运行之前就已经被回答了——表本身就是答案。EBP 作为一个系统的样子一个使用 EBP 的系统看起来像defdrive_hunger(hungry:np.ndarray,energy:np.ndarray,id_to_slot:np.ndarray,dt:float)-None:读集合hungry, id_to_slot. 写集合energy仅在由 hungry 索引的槽位。slotsid_to_slot[hungry]energy[slots]-HUNGER_BURN_RATE*dt读集合被声明。写集合被声明。没有每行的分支表就是分发器。签名就是契约——正是第 13 节中的系统形态。EBP 不是一个独立的概念它是当系统的输入是存在性表时所呈现的自然形态。EBP 也能干净地与并行性组合。一百万个有 100,000 个饥饿的生物可以跨多个进程分割——每个进程取hungry的一部分并完成其工作。进程永远不需要咨询不饥饿的生物它们的读取不冲突。第 31 节 在多进程 shared_memory 下对此进行了详细阐述。要点EBP 是第 17 节的存在性替换标志的替换所产生的结果。你不需要选择使用 EBP——一旦你的状态存在于存在性表中每个系统都会自然地遍历它们。过滤迭代版本甚至不会出现。练习重读你的存活率数字。从第 18 节练习 2 中你有 AoS、布尔掩码和存在性在五个存活率下的测量值。相同的数字讲述了 EBP 的故事存在性列就是EBP 分发路径。通过将第 18 节的行标签映射到第 19 节的词汇——“存在性” “EBP”“布尔掩码” “过滤迭代”来确认。在生物上实现两者。实现drive_hunger_filtered(creatures, is_hungry, dt)遍历生物检查布尔列应用消耗和drive_hunger_ebp(hungry, energy, id_to_slot, dt)遍历存在性表。在具有 10% 饥饿生物的 1M 生物世界上运行两者。使用timeit对两者计时。注意比率。isinstance陷阱。构建一个list[Creature]其中一些是Hungry(Creature)一些是Sleepy(Creature)一些是普通的Creature。通过if isinstance(c, Hungry)链实现分发。在 1M 生物和 10% 饥饿的情况下对其计时。现在实现 EBP 版本三个 numpy 存在性表三个系统函数。对其计时。比率是每个实体咨询谓词的成本。多态方法陷阱。将练习 3 转换为class Hungry(Creature): def update(self): ...和单个for c in creatures: c.update()。对其计时。注意源代码复杂度下降了if/elif消失了但运行时成本没有——谓词移入了 Python 的方法解析顺序在那里它仍然在每次迭代中被咨询。列表推导式过滤器。实现hungry [c for c in creatures if c.is_hungry]然后是for c in hungry: drive(c)。对其计时。与 EBP 进行比较。注意过滤过程的成本是过滤迭代版本的成本外加一次列表分配EBP 版本两者都不支付因为hungry表是在状态转换时维护的而不是在读取时。一个多状态系统。一个生物可以是hungry、sleepy、dead的任意组合。编写三个 EBP 系统drive_hunger、drive_sleep、drive_death。每个系统仅遍历自己的存在性表。与一个处理所有三种状态带有if/elif的单一过滤循环进行比较。注意 EBP 版本在三个系统之间没有共享状态并且可以平凡地并行运行它们第 31 节。挑战一个天真的 EBP 错误。一个在遍历hungry的同时也调用hungry.append的系统会破坏迭代。你从第 9 节和第 15 节知道了这一点。构建一个小案例来演示这个错误——一个在迭代中“变得饥饿”的生物。然后通过延迟清理修复它写入to_become_hungry在滴答边界应用。接下来是什么第 20 节——空表是免费的 命名了在规模上的结果成本与活跃行数成正比而不是与种群数量成正比。20 — 空表是免费的如果一个存在性表是空的那么遍历它的系统什么也不做。没有行没有工作。这是第 19 节在极限情况下的结果也是让模拟器在不断变化的状态下优雅扩展的属性。具体来说一个有 1,000,000 个生物、当前没有饥饿生物的模拟在drive_hunger中花费零个周期。该系统被连接到 DAG 中每个滴答运行获取一个长度为 0 的hungryid 的 numpy 数组执行一个对零个元素进行操作的批量操作然后返回。开销是一次函数调用和一次长度为零的花式索引——以微秒为单位测量而不是毫秒。这不是“在空情况下作为一种优化而快速”。这是“作为结构性结果在空情况下是免费的”。基于标志的版本即使在没有任何标志设置的情况下也会遍历整个生物表支付全部内存带宽来发现不需要做任何工作。EBP 版本通过一个空表的简单事实被告知没有工作。Python 默认的失败每个实体上的可选字段当一个属性可能不存在时Python 的教程反应是disease: Optional[Disease] None。每个Creature都带有这个字段健康的生物带有None。这看起来是免费的——毕竟None是一个单例——但每个实例仍然支付一个槽位每次迭代仍然支付一次getattr并且存储仍然与种群数量成正比而不是与流行率成正比。根据code/measurement/empty_tables.py一百万个带有disease字段的生物在四种流行率水平下流行率布局RSS进程滴答患病数量0.00 %带有Optional的list[Creature]105.9 MB7.46 毫秒00.00 %numpy SoA diseased存在性26.5 MB0.02 毫秒00.10 %带有Optional的list[Creature]106.1 MB11.63 毫秒1,0020.10 %numpy SoA diseased存在性26.7 MB0.06 毫秒1,0021.00 %带有Optional的list[Creature]106.7 MB9.00 毫秒10,0611.00 %numpy SoA diseased存在性26.5 MB0.12 毫秒10,06410.00 %带有Optional的list[Creature]113.4 MB19.17 毫秒99,84110.00 %numpy SoA diseased存在性26.6 MB0.48 毫秒99,714首先阅读0% 行。在零患病生物的情况下可选字段布局仍然消耗 105.9 MB 的 RAM 和每个滴答 7.46 毫秒的“处理疾病”时间。它为不存在的状态支付了全部种群价格。存在性布局支付 0.02 毫秒——函数调用加上一个空的花式索引——以及一个空的diseased数组额外消耗约 0 KB。在零流行率下可选布局比存在性布局慢 365 倍内存重 4 倍。可选布局不是在为正在发生的事情付费它是在为可能发生的事情付费。阅读10% 行。存在性布局支付 0.48 毫秒——与 100,000 个活跃行成正比。可选布局支付 19 毫秒——与一百万的完整种群成正比因为循环遍历每个生物以检查is None谓词。随着流行率的上升比率从 365 倍缩小到 40 倍但存在性布局始终胜出并且在典型的稀疏度下在任何特定滴答中任何特定状态下的种群比例 ≪ 10%差距保持很大。这个教训是普遍的。对于你可能认为是“可选状态”的每个条件——disease、held_item、target、cooldown_until、aimed_at、fingerprint、last_login_ip、parent_pointer——规范化的 Python 形式是一个单独的存在性表只包含当前拥有该状态的实体而不是每个实体上的一个Optional[X]字段。基于活动的成本这种效应在许多状态上复合。一个有二十种可能行为的模拟每种表示为一个存在性表只需为实际表现出每种行为的生物比例付费。在大多数滴答中大多数表几乎是空的。总工作量与所有表中活跃行数的总和成正比而不是与种群数量 × 行为数量成正比。对于一个稀疏活跃的世界这比等效的基于标志的设计便宜一到两个数量级。一个值得命名的微妙情况一个空系统不同于一个缺失的系统。一个遍历空hungry的drive_hunger系统仍然在 DAG 中仍然被调度仍然是程序契约的一部分。它只是在这个滴答中做了零行的工作。将其完全从 DAG 中移除会改变契约当表下一次获得一行时再将其添加回来将需要动态调度这比一个无操作调用更难。EBP 为你提供了廉价的空间系统而不是缺失的系统。三个含义基于活动的成本。模拟器的每滴答成本由活跃的内容决定而不是由存在的内容决定。一百万个休眠的生物被忽略的成本为零。只有活跃的生物消耗预算。生产中的大多数模拟器都依赖于此——拥有数十万个 NPC 但只有少数在活跃游戏中的游戏世界拥有数百万个代理但只有少数处于关键阶段的训练模拟拥有数千个传感器但只有少数处于警报状态的控制系统。结构稀疏性。世界被鼓励处于大部分休息状态。将活动分散到许多小型存在性表许多廉价的空间系统的设计优于将活动集中在一个大的“活跃生物”标志中的设计。数据导向的思维模式是增加状态的数量hungry、sleepy、mating、fighting、……而不是通过一个主开关来门控行为。持久性也是基于活动的。一个空的hungry表的快照在模式中是一行在数据中是零行。一个长度为 1,000,000 的is_hungry: np.ndarray的快照是 1 MB无论设置了多少位。备份、复制和重放都受益于相同的属性。基于标志的思维将空闲对象视为“仍然存在只是不活跃”。数据导向的思维将空闲对象视为不在表中。区别在于成本前者为存在的东西付费后者为正在发生的事情付费。练习对空情况计时。使用你来自第 19 节的模拟器运行一个hungry为空的滴答。对drive_hunger计时。它应该在微秒范围内——函数调用加上空的花式索引没有内部工作。在标志形式下对相同情况计时。在is_hungry.sum() 0的 1,000,000 个生物世界上运行布尔掩码版本的drive_hunger。对其计时。应该是毫秒级——掩码扫描仍然遍历整个列即使没有任何匹配。运行示例。uv run code/measurement/empty_tables.py。首先阅读 0% 行。注意当没有生物患病时可选布局的绝对成本。注意随着流行率下降可选/存在性的比率扩大。每活跃生物成本图。使用hungry大小在 0、100、1,000、10,000、100,000、1,000,000 范围内运行 EBP 模拟器。在每个大小上对drive_hunger计时。绘图。该线大致与 K 成线性关系从接近零开始。添加四个更多状态。添加sleepy、mating、fighting、idle作为存在性表每个都有自己的驱动程序系统。运行一个大多数表都是空大多数生物处于idle状态的滴答。确认每滴答成本大致仅为idle驱动程序的成本加上可忽略的每系统开销。活动直方图。在每个滴答为每个存在性表记录(滴答, 表名, len)。在 1000 次滴答后绘制len随时间的变化图。该图是模拟器的活动概况平坦的线意味着世界处于休息状态凸起意味着事件正在触发。挑战移除空闲系统论证为什么从 DAG 中移除一个空系统而不是让它以零工作运行是错误的做法。提示它会改变系统 DAG如果下一个滴答表非空则会破坏确定性并增加超过空调用开销的动态调度成本。挑战Optional[X]扫描。搜索你拥有的任何 Python 项目。统计数据类上的Optional[类型字段。对于每个字段问一下在运行时实际有多少比例的实例设置了它如果答案是“几乎没有”那么该字段就是存在性表的候选。接下来是什么你已经完成了“基于存在性的处理”。下一个阶段是“内存与生命周期”从第 21 节——swap_remove开始。模拟器即将开始对其表进行结构性更改——大规模的生产级的出生和死亡——而生命周期阶段将使这些更改变得廉价。