DeepSeek总结的使用实体-组件-系统和基于存在性处理进行Python编程21-23

21 —swap_remove交换并移除来自第 17 节的“用存在性表代替标志”引发了一个我们推迟讨论的问题。当一个生物不再饥饿时你将其 ID 从hungry表中移除。当一个生物死亡时你将其行从每一个表中移除。从数组中间移除行的代价很高——后面的每一行都必须向左移动一位代价为 O(N)。对于一个拥有 1,000,000 个生物的模拟器如果每个滴答有 1,000 次死亡天真的移除操作每个滴答大约需要 10⁹ 次移动——远远超过任何实时循环的预算。Python 给你四个选项。两个是错的两个是对的——而正确的两个在不同的情况下正确。四个选项按优劣排序# 反模式错误的lst.pop(i)# O(N) —— 将后续每个元素左移np.delete(arr,i)# O(N) 加上一次新的内存分配 —— 通常是最慢的# 规范的带活跃计数器的 per-element swap_removearr[i]arr[n_active-1]# 将最后一个活跃元素移动到被释放的槽位n_active-1# “表”现在是 arr[:n_active]# 规范的且更快当手头有 K 个索引时进行批量过滤keep_masknp.ones(n_active,dtypebool)keep_mask[indices_to_remove]Falsearrarr[keep_mask]# 一次 C 级别的遍历幸存者保持原始顺序per-element 版本的机制很简单取最后一个活跃元素将其移动到被删除的槽位然后将活跃计数减一。两次内存写入和一次计数器递减。O(1)与 N 无关。“活跃计数器”模式意味着你在所需的最大大小处分配一次 numpy 列而n_active告诉你当前有多少行正在使用。表就是前缀arr[:n_active]。移除一行永远不会重新调整底层存储的大小只有计数器改变。插入一行会写入arr[n_active]并增加计数器。插入细节见第 24 节——仅追加与回收。批量过滤版本接受一批索引并在一次 numpy 调用中处理它们。它分配一个大小为n_active - K的新列但仅为整个批次支付一次分配成本而不是为每一行支付一次。它与第 22 节——变更缓冲区天然配对后者正是“在滴答期间收集 K 次移除在边界处一次性全部应用”的模式。批次是工作单元单次 numpy 调用是应用。来自第 6 节的 SoA 提醒仍然适用。上面的 per-element swap_remove 和批量过滤都是单列操作——而一个生物表有六列或八列而不是一列。移除生物i是在每个具有相同i的列上执行pos_x[i] pos_x[-1]; pos_y[i] pos_y[-1]; ...; n_active - 1。批量过滤形式具有相同的形态——一个keep_mask计算一次以步调一致的方式应用于具有相同索引的每一列。如果只将其应用于一半的列行就会失去对齐这正是第 9 节中的错误。规范与排序相同任何对任何列进行重新排序的操作都必须一起对该表的所有列进行重新排序。成本测量根据code/measurement/swap_remove.py在这台机器上从一个 1,000,000 行的表中移除 100,000 个中间行布局时间移除速率Python 列表,list.pop(i)3.456 秒28,938 次/秒numpy,np.delete(arr, i)21.880 秒4,570 次/秒numpy 活跃计数器顺序 swap_remove0.016 秒5,511,389 次/秒numpy 批量过滤arr[keep_mask]0.003 秒29,571,444 次/秒四种解读。np.delete是最差的。这会让那些因为听起来像“numpy 方式”而使用它的读者感到惊讶。事实并非如此——np.delete返回一个删除了元素后的新数组每次调用都会分配新的内存并复制幸存的元素。在一个 1M 行的数组上执行 100,000 次顺序删除你会分配 100,000 个逐渐缩小的数组。字节是类型化的操作是 C 级别的但它仍然比批量过滤慢 7,151 倍因为算法形态是错误的。list.pop(i)是 AoS 的中间地带但这仅仅是因为 Python 列表是指针数组——移动一个 N 元素的列表需要 N 次指针复制这比移动和重新分配一个 N 元素的类型化 numpy 数组要快。无论如何每次移除 O(N)比批量过滤慢 1,129 倍。顺序 swap_remove 每秒处理 550 万次移除。每次移除是 O(1)但驱动它的循环跨越了 Python-numpy 边界 100,000 次——每次迭代一次边界检查、一次赋值、一次n_active - 1。这个开销是阻止它成为表中最快行的唯一因素。批量过滤每秒处理 2950 万次移除——比顺序 swap_remove快 5 倍。布尔掩码传递和压缩都是对整个数组的单一 C 级操作。Python 解释器只被触碰一次而不是 100,000 次。这是模拟器的清理传递在有要移除的索引缓冲区时应该使用的版本。综合阅读表格当你确实只有一行要移除时很少见per-element swap_remove 是正确的工具。当你有一个包含 K 个索引的缓冲区时一旦缓冲就位这就是典型情况——第 22 节批量过滤是正确的工具。两种形式都比 AoS 的本能反应快几个数量级。它们之间的选择取决于第 22 节的缓冲模式是否已在上游发生。付出的代价顺序被牺牲了。如果你的代码依赖于行以任何特定顺序排列swap_remove会重新排序它们。两个具体后果迭代损坏。如果你在迭代表的过程中调用swap_remove你刚刚访问过的槽位现在持有不同的行但你的循环计数器已经越过了它。swap_remove之后的一半行会被不一致地跳过或重复访问。与第 15 节相同的“迭代时修改”的陷阱。外部引用失效。任何持有指向该表的槽位索引的代码现在都指向不同的行。这与第 9 节的错误相同重新排列会破坏基于槽位的引用。这两个问题都已经在书中有了命名的修复方法。迭代损坏由第 22 节——变更缓冲区修复swap_remove永远不会在迭代期间运行它在滴答边界的清理期间运行此时没有系统在迭代。外部引用问题由第 23 节——索引映射修复每当行移动时id_to_slot映射都会更新因此基于 ID 的引用能够幸存。生命周期阶段何时重要整个阶段——内存与生命周期——仅对数量可变的表重要。像 52 张牌堆这样的数量恒定的表从不增长或缩小从不不需要swap_remove从不不需要这个阶段中的任何机制。纸牌游戏在没有它的情况下运行了十章。从第 11 节开始的模拟器需要所有这些因为生物在每个滴答中出生和死亡。常量与变量的区别决定了程序员是否会进入生命周期工具箱。一旦你有一个行数在运行时变化的表这个阶段中的每个工具都成为承重结构。练习比较简单情况下的计时。构建一个长度为 1,000,000 的list。对 1,000 次lst.pop(0)前部删除最坏情况计时。使用swap_remove模式对相同操作计时lst[0] lst[-1]; lst.pop()。比率大致为 N。表中部删除。构建一个长度为 1,000,000 的 numpyint64数组。对 1,000 次np.delete(arr, 500_000)每次都重新绑定arr计时。对 1,000 次swap_remove模式计时arr[500_000] arr[n_active - 1]; n_active - 1。比率巨大——np.delete每次调用都会分配一个新数组。运行第 21 节的示例。uv run code/measurement/swap_remove.py。注意四行的顺序。确认尽管np.delete是“numpy 方式”但它是最慢的而不是最快的。注意顺序swap_remove和批量过滤之间的差距——两者在算法上都是 O(K)但批量版本只支付一次 Python 循环开销而不是 K 次。迭代的危险。构建一个长度为 100、值为0..100、n_active 100的 numpyint64数组。在一个正向循环中迭代i in range(n_active)并在arr[i] % 2 0时应用swap_remove。与预期输出只剩下奇数进行比较。你实际得到了什么剧透你错过了一半的偶数。一种形态的修复反向迭代。重复练习 4但迭代range(n_active - 1, -1, -1)。现在有效吗为什么有效另一种形态的修复延迟清理。重复练习 4但不在循环内部调用swap_remove而是将索引追加到to_remove。循环结束后将to_remove按相反顺序排序并应用swap_remove。这是第 22 节模式的缩影。对齐的 per-element swap_remove。构建模拟器的六个生物列pos_x, pos_y, vel_x, vel_y, energy, id。编写def delete_creature(world, slot)对每一列以步调一致的方式调用swap_remove。验证在一系列删除操作后所有列仍然对齐。对齐的批量过滤。取相同的六个生物列。编写def delete_batch(world, indices_to_remove)它构建一个keep_mask并将其应用于每一列。通过在一批删除操作前后抽查第 17 行(pos_x[17], pos_y[17], ..., id[17])元组来验证对齐性——其值应该与现在位于槽位 17 的原始行的值匹配。现在编写损坏的版本将掩码仅应用于部分列验证行对齐性如第 9 节所预测的那样被破坏。正文中显示的单列批量过滤是为了清晰表的版本总是读取一次掩码并在各处使用它。挑战带宽成本。计算在 1 GB 的 int64 数组上执行np.delete(arr, 0)所移动的字节数大约是整个 1 GB源数组减去删除元素后复制。计算swap_remove模式相同的成本大约 8 字节一次int64移动。比率是N / 1。使用tracemalloc或psutil进行验证。接下来是什么第 22 节——变更缓冲区清理是批量的 是使swap_remove可以安全使用的规则它永远不会在任何系统迭代时运行。22 — 变更缓冲区清理是批量的这个规则已经在十多个章节中被前向引用。现在是时候把它具体化了。滴答期间的变更不会立即应用它们排队并在滴答边界由一个单一的清理传递一次性应用所有变更。其形态dataclassclassCleanupBuffer:to_remove:list[int]# 此滴答要删除的生物 IDto_insert_pos_x:list[float]# 要插入的行数据的并行数组to_insert_pos_y:list[float]to_insert_vel_x:list[float]to_insert_vel_y:list[float]to_insert_energy:list[float]to_insert_id:list[int]插入侧每列有一个列表。根据第 6 节一行是索引处的元组这对插入缓冲区也同样适用——它是一个 SoA 缓冲区而不是Creature对象的列表。原因与模拟器其余部分采用 SoA 的原因相同当清理运行时numpy 可以直接处理这些字节。在滴答期间每个想要删除的系统将一个 ID 追加到to_remove。每个想要添加的系统将一行数据追加到并行的插入列中。没有系统会修改活跃表。清理传递在滴答结束时一个系统运行defcleanup(world:World,buffer:CleanupBuffer)-None:# 1. 移除构建一个 keep_mask一次性应用于每一列。ifbuffer.to_remove:ids_to_removenp.unique(np.array(buffer.to_remove,dtypenp.uint32))slotsworld.id_to_slot[ids_to_remove]# 见第 23 节keep_masknp.ones(world.n_active,dtypebool)keep_mask[slots]Falseforcol_nameinworld.column_names:colgetattr(world,col_name)col[:keep_mask.sum()]col[:world.n_active][keep_mask]world.n_activeint(keep_mask.sum())# 更新 id_to_slot — 在第 23 节中介绍。buffer.to_remove.clear()# 2. 插入将并行的插入列批量连接到表中。n_insertslen(buffer.to_insert_id)ifn_inserts:new_nworld.n_activen_inserts# 这些列在启动时已按最大容量分配大小# 我们现在写入先前未使用的尾部 [n_active : new_n)。world.pos_x[world.n_active:new_n]buffer.to_insert_pos_x world.pos_y[world.n_active:new_n]buffer.to_insert_pos_y world.vel_x[world.n_active:new_n]buffer.to_insert_vel_x world.vel_y[world.n_active:new_n]buffer.to_insert_vel_y world.energy[world.n_active:new_n]buffer.to_insert_energy world.id[world.n_active:new_n]buffer.to_insert_id world.n_activenew_n# 将新的 ID 追加到 id_to_slot — 第 23 节。forlstin(buffer.to_insert_pos_x,buffer.to_insert_pos_y,buffer.to_insert_vel_x,buffer.to_insert_vel_y,buffer.to_insert_energy,buffer.to_insert_id):lst.clear()两次传递都是批量操作。世界在结束时处于完全一致的状态。keep_mask构建一次并应用于每一列插入尾部通过每列一次切片赋值来填充。根据第 21 节在每滴答 K100,000 次变更的情况下批量过滤形式比 per-elementswap_remove快 5 倍——并且根据第 10 节正文中的“版本差异”框架以及其他地方的描述这正是 Python 版本的清理实际与 Rust 版本不同的地方Rust 第 22 节使用 per-elementswap_remove循环因为编译后的代码不支付解释器边界税Python 第 22 节使用批量掩码形式因为我们测量了边界成本并且它在规模上占主导地位。这解决了什么问题来自第 21 节的迭代损坏问题消失了因为在任何系统迭代时表都不会被修改。当清理运行时每个系统都已经完成。没有并发迭代会造成混淆。来自第 15 节的“迭代列表时修改列表”和“迭代字典时修改字典”的陷阱不会发生——在for c in creatures循环内部没有creatures.remove(c)因为滴答内部没有任何东西会修改活跃表。来自并发修改的竞争条件问题消失了。两个系统可能都想移除同一个生物两者都追加到to_remove清理使用np.unique去重。两个系统都不需要协调。来自第 14 节的组合问题消失了。系统读取一致的快照它们读取的世界是滴答开始时的世界而不是被其他系统重写了一半的世界。它付出了什么代价每次变更都是推送到侧边列表的一个额外条目。对于一个每滴答有 1,000 次死亡和 500 次繁殖的模拟器这意味着每滴答 1,500 条簿记条目——几千字节与运行系统本身相比完全可以忽略不计。清理传递是 DAG 中一个额外的系统。当没有变更排队时它是空的无工作第 20 节当有变更时它运行批量过滤和批量连接。该系统被连线一次永远不会被移除。它没有解决什么去重是系统的职责。两个系统如果独立检测到相同的死亡条件可能会将同一个ID 推送到to_remove。清理在计算槽位之前使用np.unique(to_remove)来减少为不同的 ID。成本是对一个小数组进行的一次 O(K log K) 排序——与批量过滤相比可以忽略不计。顺序很重要。在清理内部先执行删除然后执行插入。如果你先插入插入的行可能会落在你即将删除的槽位中。先删除可以释放尾部容量供后续插入重用——尽管槽位回收本身是一个独立的决策第 24 节。这个模式本身是通用的。数据库事务缓冲写入并在边界提交。图形渲染管线渲染到后台缓冲区并交换。版本控制的文件系统收集更改并提交。它们都解决同一个问题如何让许多独立操作修改共享状态而不会互相干扰答案总是相同的——累积然后原子地应用。练习实现侧边缓冲区。将to_remove: list[int]和并行的插入列表每列一个添加到你的模拟器的世界中。它们在每个滴答开始时为空。从apply_starve推入。修改你的饥饿系统使其追加到to_remove而不是直接修改表。验证系统不再接触活跃的creatures列。从apply_reproduce推入。修改繁殖系统使其将父本的后代行追加到并行的插入列表中。验证繁殖不再直接修改creatures。实现批量清理。按照正文编写清理系统。首先应用移除一个keep_mask应用于每一列然后应用插入每列一次切片写入。运行一个包含两种变更的滴答验证之后世界是一致的。比较清理形式。实现一个第二个清理它使用 Python 循环中的 per-elementswap_remove而不是批量掩码。在 1,000,000 个生物、每滴答 1,000 次变更的情况下对两者计时。根据第 21 节的数字批量形式应该胜出约 5 倍——在你的机器上确认。去重问题。在同一滴答中从两个不同的系统将 ID 42 推送到to_remove。运行没有np.unique步骤的清理。会发生什么提示id_to_slot[42]被查找两次如果第一次移除将另一行移动到了该槽位第二次查找可能会产生垃圾。现在添加np.unique并重新运行。结果是正确的。滴答延迟的可见性。在滴答 5 中插入的生物通过to_insert_*列表不会在滴答 5 的系统运行期间出现在活跃列中——只在最后在清理时出现。通过添加一个在每个滴答结束时递增的age_in_ticks列来验证新生物的值在滴答 6 中从 0 开始而不是滴答 5。挑战图形管道的类比。一个渲染管线在显示“前台缓冲区”时绘制到“后台缓冲区”。在一帧到下一帧的边界处缓冲区交换。论证为什么这与to_remove/to_insert加上cleanup的模式相同。提示这是相同的原子提交形态后台缓冲区正是侧边表。接下来是什么第 23 节——索引映射 是swap_remove和批量过滤清理发挥作用所缺失的部分一个并行数据结构跟踪每个 ID 当前所在的位置每当列移动时更新。23 — 索引映射来自第 17 节的“用存在性表代替标志”有其隐藏的问题。一个存在性查询——“生物 42 饥饿吗”——如果天真地实现为np.any(hungry 42)成本为 O(K)。在一个每滴答有数千次此类查询的 1,000,000 个生物的模拟器中这太慢了。解决方法是一个并行的数据结构一个将每个 ID 映射到其在表中当前槽位的索引映射。现在查找是 O(1)。Python 为你提供了两种合理的映射形态以及一个陷阱。两种有效的形态当 ID 密集时使用 numpy 数组。如果你的 ID 是[0, N_max)范围内的整数并且大多数都在使用中一个类型化的列就能完成工作INVALIDnp.iinfo(np.uint32).max# 4_294_967_295id_to_slotnp.full(N_max,INVALID,dtypenp.uint32)defslot_of(id_to_slot:np.ndarray,creature_id:int)-int|None:slotint(id_to_slot[creature_id])returnNoneifslotINVALIDelseslot哨兵值np.iinfo(np.uint32).max标记“没有槽位——此 ID 没有当前行”。在 1,000,000 个 ID 时为 4 MB每次查找一次 C 级别的内存读取通过花式索引进行的批量查找id_to_slot[ids_to_remove]以 numpy 速度运行并且正是清理所使用的第 22 节。每 16 个 ID 一个缓存行清理顺序地流式处理它。当 ID 稀疏时使用dict[int, int]。如果 ID 空间很大但使用的很少——ID 是字符串的哈希、外部系统的 UUID 转换为整数、截断为槽位的时间戳——Python 字典是正确的选择id_to_slot:dict[int,int]{}defslot_of(id_to_slot:dict[int,int],creature_id:int)-int|None:returnid_to_slot.get(creature_id)字典查找是 O(1) 摊销对于整数键大约为每秒 30-4000 万次操作根据code/measurement/float_or_int_tuple.py—— 注意哪个整数很重要在相同的映射大小下整数键比浮点元组键快 2.4 倍。字典每次查找都会支付哈希机制的开销每次访问一次指针追逐numpy 两者都不支付。但是字典只为实际存在的 ID 支付这对于稀疏 ID 空间来说是合适的形态。选择由 ID 密度决定而不是由个人偏好决定。来自第 10 节的模拟器的代理 ID 是密集的——每个生物一个全新的整数在槽位被重用时回收。numpy 数组是正确的选择。由 64 位哈希索引的审计日志将是稀疏的——字典是正确的选择。一种错误的形态# 反模式错误的fromscipy.sparseimportcsr_matrix mcsr_matrix(...)# 为稀疏二维矩阵运算而构建slotm[creature_id,0]# 这里用作一维点查找映射scipy.sparse家族——CSR、CSC、COO——不是索引映射。它们是稀疏矩阵数据结构为矩阵-向量乘积和切片整个行或列而优化。用于单个点查找它们非常慢。根据code/measurement/csr_matrix or python dict.py在 1000 × 1000、1% 密度的情况下Python 字典在随机标量查找上比 CSR 快大约 108 倍。该示例的标题是“CSR 矩阵比 Python 字典慢 108 倍”。对于该文件中的访问模式来说这是正确的*——但这是错误的解读。正确的解读是scipy 给你一个稀疏的矩阵而不是稀疏的映射。选择与你的访问模式匹配的数据结构。CSR 在 SpMV稀疏矩阵-向量乘积科学计算中常见的密集向量乘以稀疏矩阵的操作方面表现出色。它不擅长点对点查找因为其内部布局——indices、indptr、data三个数组——为跳过步幅而优化而不是为 O(1) 随机访问而优化。教训不是“CSR 慢”而是“错误的工作使用了错误的工具每次都这样由设计决定。”维护每当行移动时映射必须更新。本书中移动行的事件恰好有三个批量过滤清理第 22 节。每个被移除的槽位的 ID 都被设置为INVALID。每个槽位发生变化的幸存 ID 都会重写其条目——这些正好是在keep_mask压缩期间移动的行。追加。当新行落在槽位n时设置id_to_slot[new_row.id] n。清理传递在写入插入尾部时以步调一致的方式写入此映射。排序或重新洗牌为了局部性第 28 节。当表被重新排序时每个槽位都移动。映射与排序以步调一致的方式被完全重写。在 numpy 中这是一次赋值id_to_slot[ids[order]] np.arange(n_active)。来自第 22 节的清理系统是这些更新的自然归属。每次移除和每次插入都经过清理清理保持映射同步。成本numpy 数组为每个曾经发出的 ID 添加一个uint32包括当前已死亡但其槽位尚未被回收的 ID。对于一个在其生命周期内发出了一百万个 ID 但任何时候只有 100,000 个存活的模拟器映射大小为 4 MB。这是一个真实的成本——如果表的列很窄这比活跃表本身还要大。缓解措施代次 ID第 10 节加上一个单独的 ID 分配器回收已死的 ID将映射的大小限制在高水位线的存活 ID 数而不是总共发出的数量。通过回收映射保持在 100,000 × 4 400 KB。一个dict[int int]用常数因子的查找开销换取更紧凑的内存当 ID 稀疏时很有用如上所述。对于大多数具有回收机制的模拟器密集的np.ndarray是正确的形态。每 16 个 ID 一个缓存行批量查找id_to_slot[ids]是以 numpy 速度运行的带宽受限操作。现实世界中的模式每个 ECS 引擎都内置了一个索引映射。Bevy 的EntityRust是一个 64 位句柄其解包本质上是一次带有代次检查的槽位查找。slotmap的SlotMap维护一个内部映射。数据库引擎维护索引映射作为主键上的 B 树。这种形态——ID 到槽位的查找在每次移动时维护——是通用的。结合第 10 节的稳定 ID 和第 24 节的槽位回收索引映射是代次竞技场的第三部分——现代系统软件中规范的基于句柄的数据结构。练习构建映射。将id_to_slot np.full(N_max, INVALID, dtypenp.uint32)添加到你的模拟器中。当一个生物在槽位 N 被追加时设置id_to_slot[id] N。当一个生物的槽位在清理期间发生变化时相应地更新。O(1) 存在性查询。添加一个并行的hungry_membership np.zeros(N_max, dtypebool)当一个 ID 在hungry中时设置为True。现在is_hungry(id)是两次数组查找都是 O(1)。在批量过滤清理上维护。修改你的第 22 节的清理使其在keep_mask压缩后更新id_to_slot。最快的形式在id[: new_n] id[: n_active][keep_mask]之后运行id_to_slot[id[:new_n]] np.arange(new_n, dtypenp.uint32)——一次批量写入每个幸存的 ID 的槽位在一次传递中被重写。计时差异。在 1M 生物上重新运行模拟器每个滴答调用is_hungry(random_id)100,000 次。比较线性扫描版本第 17 节练习 6和索引版本。比率大约为 N——大约一百万。诚实地运行示例。uv run code/measurement/csr_matrix or python dict.py。阅读文件的标题“CSR 矩阵比 Python 字典慢 108 倍”。然后阅读本章的重新解读。通过你自己的一小段实验确认scipy 的 CSR 在它自己的工作上很快——csr.dot(some_dense_vector)对于一个 1000×1000 的矩阵——而在文件给它的任务上很慢。带宽成本。在 1M ID 时id_to_slot为 4 MB。清理在一个具有 1,000 次swap_remove和 500 次插入的滴答中的批量更新写入大约 1,500 个条目——6 KB。针对 30 Hz 的预算计算这些写入的清理成本以微秒为单位。与“为局部性排序”的兼容性。当creatures被排序时第 28 节的预览每个槽位都移动。使用一次批量 numpy 赋值以步调一致的方式重写id_to_slotid_to_slot[ids[order]] np.arange(n_active)。验证在排序后外部引用作为 ID 持有仍然是正确的。挑战一个从头开始的代次竞技场。将第 10 节的gens: np.ndarray、第 22 节的延迟清理以及第 23 节的id_to_slot映射组合到一个SlotMap类中。提供insert(row) - CreatureRef、remove(ref)、get(ref) - int | None。将形态与slotmap::SlotMapRust进行比较——相同的机制不同的组织方式。接下来是什么第 24 节——仅追加与回收 命名了在槽位被释放后对其处理的两种策略。选择由访问模式决定而不是由个人偏好决定。