33 — 伪共享你对表进行了分区。每个进程写入自己不相交的切片。工作负载是平衡的。加速比……在 8 个核心上只有 1.2 倍。并行性去哪了很可能是伪共享导致的。CPU 缓存以 64 字节的缓存行为单位工作。当一个进程写入地址 X 时缓存一致性协议会使其他每个核心缓存中的那一行失效——它们必须丢弃自己的副本并重新加载。如果两个进程写入不同的地址但这些地址位于同一个缓存行中那么每次写入都会触发另一个进程缓存的失效。这些进程在没有逻辑冲突的情况下互相拖慢速度。一个病态案例八个进程各自递增multiprocessing.shared_memory中一个长度为 8 的int64数组中的一个条目。该数组正好是 64 字节——一个缓存行。所有八个进程都写入该行。每次写入都会使其他七个缓存失效。这些进程一起运行比单个进程运行更慢——真正的负扩展。为什么这在 Python multiprocessing 中很重要Python 的直觉是 GIL 是唯一的并发危险。伪共享是硬件级别的危险GIL 无法保护你免受其害因为一旦你进入multiprocessing.shared_memory多个操作系统级别的进程就在多个核心上运行命中相同的物理字节。GIL 没有介入——它从不跨越进程边界。而缓存一致性协议会。好消息是来自第 31 节和第 32 节的分区模式默认避免了伪共享因为分区很大。parallel_motion.py装置使用N/n_workers 10M/16 ≈ 625K个float32值作为每个工作进程的块——每个块 2.5 MB每个块 40,000 个缓存行。块之间的边界相隔数兆字节。伪共享需要在 64 字节窗口内的相邻写入而分区不会产生这种情况。当每进程状态很小时伪共享就会出现。值得命名的三种情况共享内存中的每进程计数器。如果每个工作进程在共享数组中写入counters[my_id]并且数组是int64类型那么 8 个工作进程占用 64 字节——正好一个缓存行。任何工作进程的每次递增都会使其他每个工作进程的缓存副本失效。真正的负扩展。# 反模式错误的countersnp.ndarray((8,),dtypenp.int64,buffershm.buf)defworker(my_id:int)-None:for_inrange(1_000_000):counters[my_id]1# 所有 8 个计数器都适合一个缓存行靠近边界的每进程累加器。一个在其分区边界更新一行的进程例如在空间排序中应用边界效应时第 28 节可能与相邻工作进程的第一行落在同一个缓存行中。这就是为什么区域分解代码中的光环区域通常被填充到缓存行大小。一个共享区域中的许多小型的每进程缓冲区。如果你将 N 个相邻的小型每进程临时数组放在一个共享内存块中边界处很可能发生伪共享。解决方法是每个进程拥有自己的共享内存块或者在区域之间填充。修复方法使每进程状态在结构上分离。每个进程获得自己的multiprocessing.shared_memory.SharedMemory块或自己的私有 numpy 数组默认情况——工作进程看不到彼此栈分配的内存。在所有工作进程完成后在__main__中合并结果。来自第 31 节的每进程to_remove段模式就是这样做的——每个进程写入自己的np.ndarray然后__main__运行np.concatenate进行合并。将共享的每进程状态填充到缓存行。如果你必须有一个共享的每进程状态数组将条目间隔 64 字节# 8 个工作进程每个拥有 counters_padded[my_id * 8]每个缓存行一个 int64counters_paddednp.ndarray((8*8,),dtypenp.int64,buffershm.buf)defworker(my_id:int)-None:for_inrange(1_000_000):counters_padded[my_id*8]1# 每个都在自己的缓存行上在缓存行边界上进行分区。在将类型化数组分配给工作进程时将边界舍入到64 // dtype.itemsize的倍数——对于int32/float32是 16对于int64/float64是 8。对于任何大于约 16 个元素的块大小上面的 numpy 分区已经这样做了只有在非常小的块时边界才会落在一行内。伪共享是硬件问题而不是 Python 问题。Python 解释器认为八个进程写入八个不相交的地址没有问题硬件则看到一个缓存行并序列化访问。该错误在语言级别是不可见的。它仅在性能上表现出来——并行版本莫名其妙地很慢。检测在你的模拟器上使用perf stat -e cache-references,cache-missesLinux进行性能分析perfstat-ecache-references,cache-misses -- python my_sim.py尽管写入看似不相交伪共享会产生高cache-misses。如果性能分析显示你的并行系统具有异常高的缓存流量——例如每秒钟的缓存未命中数超过工作集在一次传递中可能产生的数量——伪共享很可能是原因。要点即使对于逻辑上不相交的数据物理布局也很重要。如果两个写入不同的共享内存地址的写入操作在 64 字节内则它们不能自由并行化。解决方法是分离或填充。检测方法是性能分析。练习病态计数器。使用multiprocessing.shared_memory构建 8 进程案例一个长度为 8 的int64数组每个工作进程在一个紧密循环中递增自己的槽位。将并行版本与执行相同总工作量的单进程循环进行时间比较。并行版本应该更慢——真正的负扩展。提示当每滴答的工作量足够小时即使是产生进程也更慢选择一个具有数百万次递增的紧密内部循环以看到缓存效应占主导地位。填充版本。将每个计数器填充到自己的缓存行使用长度为8 * 8 64的int64数组让每个工作进程写入索引my_id * 8。重新运行。现在并行版本应该随着工作进程数量接近线性扩展。一个真实例子。在你模拟器的每进程to_remove段中第 31 节练习 4检查两个工作进程的段追加是否可能落在同一个缓存行中。它们通常不会——每个进程独立的 numpy 数组位于不同的共享内存块中——但如果性能出乎意料地差这是一个需要检查的地方。共享内存中的相邻数组。构建一个包含两个int64的共享数组。产生两个工作进程一个写入索引 0一个写入索引 1在紧密循环中运行。与每个工作进程写入自己独立的multiprocessing.shared_memory块的时间进行比较。挑战找到你的缓存行大小。在 Linux 上使用getconf LEVEL1_DCACHE_LINESIZE。验证它是 64 字节一些芯片使用 128 字节——尤其是在某些级别的 Apple Silicon 上。如果你使用的是其中之一填充到 64 是不够的你需要 128。挑战对你的装置运行perf stat。perf stat -e cache-references,cache-misses -- uv run code/measurement/parallel_motion.py。比较 1 个工作进程和 8 个工作进程的未命中率。未命中率应该大致相同没有伪共享确认装置的设备分区足够大以避免陷阱。接下来是什么第 34 节——顺序是契约 将并行性带回到第 16 节的确定性规则并行性在步骤内部是允许的跨步骤则永远不允许。34 — 顺序是契约第 31、32 和 33 节解锁了并行性。自然的诱惑是一切都并行运行——让操作系统调度器决定哪个系统何时运行将系统分散到所有可用的核心上以提高吞吐量。这是错误的。系统 DAG第 14 节是模拟器行为的契约。写集合重叠的两个系统必须以定义的顺序运行。在同一 DAG 级别上的两个系统可以并行运行——但它们都必须在任何读取它们输出的系统开始之前完成。并行性在一个阶段内部是允许的跨阶段是永远不允许的。原因是确定性第 16 节。相同的输入 相同的系统顺序 相同的输出。如果apply_eat、apply_reproduce和apply_starve以未定义的顺序运行——比如说第一个完成的系统首先写入to_remove——那么cleanup在不同运行中会看到不同的to_remove顺序并且滴答结束时的世界状态是不可重现的。回放会中断。测试变得不稳定。分布式模拟会漂移分离。调度看起来像┌── apply_eat ────┐ │ │ next_event ────┼── apply_repro ──┼─→ cleanup → inspect │ │ └── apply_starve ─┘next_event首先运行它的输出是所有三个应用器所需要的。三个应用器并行运行——它们的写入是不相交的每个写入to_remove自己的部分或自己的表第 31 节。cleanup在所有三个完成后运行永远不会在任何它们之前运行。inspect最后运行。调度由 DAG 固定。并行性发生在 DAG 允许的结构内部而不是围绕它。需要命名的两种反模式“让操作系统决定”反模式。将每个系统分散为一个进程并让它们竞争是以错误的方式快速运行。某些运行产生一个结果某些运行产生另一个结果。错误是间歇性的原因难以找到而用锁“修复”它会重新引入第 31-33 节努力避免的成本。# 反模式错误的withPool(processes8)aspool:pool.starmap_async(motion,...)pool.starmap_async(food_spawn,...)# 与 motion 并发运行pool.starmap_async(next_event,...)# 可能在 motion 完成之前完成pool.starmap_async(apply_eat,...)# 读取 pending_event可能看到部分# ... 没有等待没有屏障 ...pool.close()pool.join()# 唯一的屏障所有操作都在竞争“提前开始”反模式。在其先决条件完成之前启动一个系统——即使数据“看起来准备好了”——是在打赌调度不会改变。在实践中这个赌注通常是赢的直到有一天缓冲区比平时稍晚填满世界的状态以没有测试捕捉到的方式发生变化。等待每个先决条件的显式完成。# 反模式错误的deftick(world):motion_futurepool.apply_async(motion,...)next_event(world)# 在 motion 完成之前开始apply_eat(world)# 读取 pos但 motion 正在更新它motion_future.wait()# 太晚了读取已经错误Python 的第三种反形态——大多数读者会忍不住尝试的——是在系统上使用asyncio.gather# 反模式错误的asyncdeftick(world):awaitasyncio.gather(motion(world),next_event(world),apply_eat(world),apply_reproduce(world),apply_starve(world),cleanup(world),)这种形态看起来像一个调度器。但它不是。asyncio.gather以它们合作让步的任何顺序运行可等待对象直到完成并且不了解它们之间的依赖关系。DAG 的结构——cleanup 必须等待应用器应用器必须等待 next_event——对gather是不可见的。第一个完成的系统完成其余的在竞争。与多进程版本相同的失败模式但增加了混淆因为表面语法看起来像是正确的形态。通风机就是调度器第 32 节的通风机模型正是本章所需的调度器。重新阅读 DAG 即数组阶段 1: [1] # next_event 阶段 2: [1, 2, 3] # apply_eat, apply_reproduce, apply_starve 并行 阶段 3: [1] # cleanup 阶段 4: [1] # inspect这些阶段是屏障。在一个阶段内工作并行运行。在阶段之间主进程在增加代次计数器之前等待每个工作进程的确认。阶段边界强制执行 DAG阶段内并行性使用第 31-33 节的架构。一个机制两种解读并行调度和确定性执行顺序是同一个文档。大多数生产级 ECS 引擎正是实现了这一点——Bevy 的World::run_schedule、Unity DOTS 的JobHandle.Complete、Unreal 的 Mass Entities 调度器。该模式类似于并行的make按顺序构建依赖项并行构建独立项绝不在先决条件完成之前开始目标。并行区域内的确定性一个更微妙的问题即使阶段边界得到尊重工作进程本身也必须产生确定性输出。根据第 16 节配方适用于每个工作进程内部不要使用读取全局状态的random.random()。每个工作进程持有自己的np.random.default_rng(seed)在启动时确定性地设置种子例如default_rng(base_seed my_id)。系统内部不要使用系统时钟。时间作为dt从主进程传递而不是在工作进程内部从time.perf_counter()读取。依赖于顺序的归约是错误的。一个工作进程执行sum(arr)没问题一个工作进程执行for x in arr: total float_func(x)可能会根据arr当时恰好的内容产生不同的位级输出如果arr是共享的。对于任何其结果反馈回世界的归约坚持使用 numpy 批量操作。不要迭代集合。第 16 节的集合迭代陷阱在每个工作进程内部独立适用。来自第 25 节的单写入者规则处理了其余问题工作进程只写入自己的分区因此无论它们碰巧何时运行两个工作进程都不能破坏彼此的字节。回放测试一个有用的测试你能回放一个滴答到位相同的输出吗如果可以你的调度器遵守了契约。如果不能则没有遵守——某个地方有一个系统以未定义的顺序运行并且该错误将在最糟糕的调试窗口中显现。该测试是具体的defreplay_test(world_factory,n_ticks:int)-bool:world_aworld_factory(seed42)for_inrange(n_ticks):tick(world_a)hash_ahash_world(world_a)world_bworld_factory(seed42)for_inrange(n_ticks):tick(world_b)hash_bhash_world(world_b)returnhash_ahash_b在对模拟器进行每次更改后运行它。在 N1、N2、N4、N8 个工作进程下运行它。跨机器运行它。如果哈希值跨机器不同则存在一个非确定性依赖一台机器以某种方式解决另一台机器以另一种方式解决——几乎总是set迭代、挂钟读取或未设置种子的 RNG。结束第七部分此规则结束了“并发”部分。模拟器现在可以使用机器上的每个核心而不会牺牲第 16 节保证的确定性。DAG 既是并行调度也是确定性执行顺序一个文档两种解读。通风机模型实现了这两者。练习构建调度。编写一个tick(world, dt)它运行next_event然后是一个三个应用器的并行块使用你的第 32 节通风机模式然后是cleanup然后是inspect。验证边界cleanup必须在所有三个应用器完成之前启动。测试确定性。使用相同的种子运行模拟器两次。在 100 次滴答后对世界进行哈希。即使应用器并行运行哈希值也必须是相同的。破坏契约。构建一个调度其中cleanup在apply_starve完成之前启动例如在主进程中跳过阶段之间的等待确认步骤。运行两次。哈希值有时应该不同。该错误的间歇性就是教训。找到你的阶段边界。根据code/sim/SPEC.md勾勒出你模拟器的完整 DAG。识别每个阶段彼此之间没有传递依赖关系的系统集合。每个阶段是一个并行批次每个边界是一个同步点。亲身体验 asyncio 陷阱。使用asyncio.gather在系统上实现tick。运行确定性测试。观察哈希值在不同运行中发生偏离。注意失败的形态不是崩溃只是错误的答案。跨机器确定性。如果你可以访问另一台机器在那里使用相同的种子运行相同的模拟器。哈希值必须匹配。如果不匹配找出差异——PYTHONHASHSEED、挂钟、glibc 版本、硬件浮点行为。每一个都是可能的来源。挑战一个最小调度器。编写def topo_phases(systems: list[tuple[str, set[str], set[str]]]) - list[list[str]]接受(name, read_set, write_set)三元组返回一个阶段列表每个阶段是一个可以并行运行的系统名称列表。大约 30 行 Python 代码。该调度器只是一个带有级别分组功能的拓扑排序。接下来是什么你已经完成了“并发”部分。模拟器现在可以在多个核心上运行而不会失去确定性。下一个阶段是“I/O 与持久性”从第 35 节——边界即是队列开始。模拟器即将开始与其滴答之外的世界对话。