27 — 工作集与缓存一个循环的工作集是它每次遍历所接触的数据。缓存层次结构第 1 节是保存这些数据的地方。两者共同决定了循环的速度——一旦你进入了 numpy。在纯 Python 中解释器分发的开销占主导地位悬崖是不可见的。当你的内部循环落入一个批量 numpy 操作时悬崖是真实存在的并且就在硬件所指示的位置。如果工作集适合 L1通常每核心 32 KB循环以接近内存带宽的速度运行约 0.1-0.5 纳秒/元素。如果适合 L2通常每核心 1-2 MB约 0.5-2 纳秒。如果适合 L3通常共享 16-32 MB约 1-5 纳秒。如果溢出到 RAM顺序访问降至约 3-10 纳秒预取器有帮助随机访问降至 50-200 纳秒预取器无帮助。这些范围不是理论上的。它们是你的机器实际所做的在第 1 节的cache_cliffs.py示例中测量得到。在该示例中这台机器上的数字Nnumpy 顺序numpy 收集收集/顺序10,0000.54 纳秒1.47 纳秒2.7 ×100,0000.18 纳秒2.88 纳秒16.4 ×1,000,0000.21 纳秒3.51 纳秒17.0 ×10,000,0000.19 纳秒10.33 纳秒53.7 ×100,000,0000.16 纳秒11.80 纳秒72.2 ×悬崖在gather收集列。10K 和 100K 行适合 L1 / L2收集比率约 2-16 倍10M 和 100M 行溢出到 RAM比率 54-72 倍。numpy顺序行大致保持平坦因为预取器向前预取并摊销了成本——这就是这台机器上“带宽受限”的样子。计算你的工作集计算是机械的。运动Motion的内部循环读取pos_x: float32 4 字节、pos_y: float32 4 字节、vel_x: float32 4 字节、vel_y: float32 4 字节、energy: float32 4 字节。总计每个生物 20 字节。在 N 个生物时工作集 20 × N 字节。N工作集模式本机1,00020 KB适合 L110,000200 KB适合 L2100,0002 MBL2/L3 边界1,000,00020 MB适合 L3溢出 L210,000,000200 MB溢出 L3命中 RAM当访问模式是随机时每次转换大约会使每元素时间增加 3-5 倍。顺序访问在很大程度上受到预取器的保护但仅限于 RAM 带宽——在 1000 万生物及以上预取器不再隐藏延迟只是跟上 RAM 所能提供的速度。这就是第 4 节关于“悬崖”的内容针对你的模拟器进行了具体化。转换点不是魔术——它们是对你的缓存大小的算术运算。从第 1 节练习 1中你已经记下了这些数字。为什么 numpy 隐藏了它但这个教训仍然重要大多数 numpy 代码从不考虑缓存大小因为内部循环受带宽限制并且“足够快”。这种直觉在工作集离开 L3 之前一直成立——此时每元素成本增加 5-10 倍而源代码没有任何改变。一个为 100 万生物编写并在 10 万生物上测试的模拟器从未注意到这个悬崖当模拟器规模扩大到 1000 万并且错过截止时间时它就会出现。热/冷分离第 26 节缩小了工作集。运动的工作集从每个生物 40 字节整行减少到 20 字节仅热列。这将悬崖向外推了 2 倍一个 200 万生物的模拟器现在以 L3 驻留速度运行而不是 RAM 驻留速度。在纯 numpy 的 SoA 中这是分离的主要切实好处——并且第 26 节的警告适用仅当内部循环确实遇到带宽上限时分离才会移动悬崖。设计规范在模式之前确定目标 N。模式必须适合适合 N 的缓存。审计内部循环。对每行接触的字节求和。与你的缓存大小进行比较。当你越过一个转换点时测量——不要假设。预取器和操作系统有时会拯救你有时不会。Numpy 的批量操作阈值也随版本变化在你交付的确切技术栈上进行基准测试。容纳该值的最窄 dtype第 2 节不是审美问题它是悬崖的距离。np.float32相比np.float64使余量加倍np.uint8用于[0, 256)范围内的索引每个缓存行可容纳 64 个。这不是过早优化。这是布局感知设计——使模式适合将运行它的机器。忽略缓存的模式对于小 N 有效但在模拟器预期的规模下会失效。练习计算你的工作集。对于你模拟器中的每个系统计算 N 1K、10K、100K、1M、10M 时的每行字节数 × N。注意在你的机器上每个 N 落在哪一级缓存使用第 1 节练习 1 中的lscpu | grep -i cache。找到你的悬崖。uv run code/measurement/cache_cliffs.py第 1 节的示例给出了你的机器上顺序和收集访问在不同大小下的每元素纳秒数。绘制收集列。转换点应与你的缓存大小匹配。减少工作集。在组织上应用热/冷分离第 26 节使得运动只读取热列。在你从练习 2 中找到的悬崖大小处对运动计时。悬崖移动了吗在纯 numpy 的 SoA 中答案是“没有因为这些列已经是分离的”——参见第 26 节的框架。更宽的 dtype。将energy: float32改为energy: float64。重新计算工作集。对运动计时。悬崖应该向内移动更靠近更小的 N。你的机器上的随机与顺序访问。重新阅读 cache_cliffs 表中针对你的输出的 gather/seq 比率。跨大小的 2.7 倍 → 72 倍的增长是你的机器的缓存与 RAM 成本差距。记住这个数字它是“在这台硬件上一次随机访问比一次顺序访问贵多少”这个问题的答案。挑战L1 最佳点。找到 N使得运动的工作集将 L1 填充到大约 75%。紧密重复运行运动循环连续调用 1000 次调用之间无其他工作。在整个运行期间L1 驻留的循环应以稳定的约 0.2 纳秒/元素运行。最近的仅 L2 邻居应慢 3-5 倍。接下来是什么第 28 节——为局部性排序 明确地让缓存工作重新排列你的行使访问变得更加顺序。28 — 为局部性排序在第 9 节中你学到了“排序会破坏索引”的错误。在第 10 节中你使用稳定的 ID 修复了它。在第 23 节中你使 ID 到槽位的查找变成了 O(1)。有了这三个部分模拟器现在可以做一些以前做不到的事情为局部性重新排列其行。原理很简单。在时间上彼此接近访问的行应该在内存中彼此靠近。两个相互作用的生物碰撞、查询邻居、进行粗粒度相交测试应该落在相邻的缓存行上。经典的技术是空间排序。每个生物的位置被哈希到一个空间单元格生物表按单元格排序。读取“单元格 C 中的所有生物”变成了一个连续的区间读取。defspatial_cell(pos_x:np.ndarray,pos_y:np.ndarray,cell_size:float)-np.ndarray:返回每个生物的 uint32 单元格 ID。将 (x, y) 单元格 打包成一个整数。Z-order 或 Hilbert 曲线也可以。cx(pos_x/cell_size).astype(np.int32)cy(pos_y/cell_size).astype(np.int32)return((cx0xFFFF)16)|(cy0xFFFF)defsort_creatures_for_locality(world,cell_size:float)-None:cellsspatial_cell(world.pos_x,world.pos_y,cell_size)ordernp.argsort(cells,kindstable)# 将相同的排列应用于每一列步调一致——第 6 节的规则。world.pos_x[:]world.pos_x[order]world.pos_y[:]world.pos_y[order]world.vel_x[:]world.vel_x[order]world.vel_y[:]world.vel_y[order]world.energy[:]world.energy[order]world.id[:]world.id[order]# 步调一致地重建 id_to_slot——第 23 节。world.id_to_slot[world.id]np.arange(world.id.size,dtypenp.uint32)同一空间单元格中的两个生物现在在pos_x和pos_y中是相邻的。下一个事件系统会检查每个生物与其空间邻居的关系它步进通过pos_x并从同一条缓存行读取邻居。为什么这在 numpy 中很重要局部性差距不是理论上的。从第 1 节的cache_cliffs.py中在 1 亿个元素时收集随机索引读取在这台机器上比顺序读取慢 72 倍。这个比率是每个缓存不友好的访问模式的代价——每次以非空间顺序访问生物的迭代都会付出这个代价。空间排序将收集形态的读取转换为顺序读取这正是该比率所衡量的操作。代价是排序本身。对于 100 万个uint32键np.argsort需要约 10-30 毫秒具体取决于输入分布。如果每个滴答都这样做代价会太高——但通常排序每约 100 个滴答进行一次或当累积运动超过某个阈值时摊销到每个滴答约 0.1-0.3 毫秒。内部循环的节省远大于排序的成本。其他排序顺序及其收益时机按 ID 排序。跨运行稳定对调试有好处但除非 ID 与访问模式相关否则没有局部性好处。按访问频率排序。热点优先冷点最后。仅当内部循环尊重顺序时才有用——而大多数 numpy 批量操作不尊重它们遍历整列。按行为排序。所有饥饿的生物在一起所有困倦的生物在一起。在基于存在性的系统第 19 节中大多是多余的因为饥饿驱动程序直接遍历hungry。排序频率本身是一个决策。如果世界大部分是静止的每个滴答都排序是浪费工作。如果世界漂移只在启动时排序一次是错误的。大多数模拟器在自上次排序以来的累积运动超过单元格大小的一小部分时触发重新排序。本课所依赖的组件排序与前面的三节课相互作用步调一致的重新排序第 6 节第 9 节。每一列都应用相同的排列。world.pos_x[:] world.pos_x[order]形式是就地重新绑定到相同的底层数组——它不分配内存也不会破坏其他地方持有的别名。对每一列逐个执行此操作是规范形式。稳定的 ID第 10 节。排序外部的代码持有ID而不是槽位排序移动槽位而id_to_slot映射sort_creatures_for_locality的最后一行使 ID 保持正确。索引映射第 23 节。id_to_slot的重建是一次批量 numpy 赋值每次排序运行 O(N) 次而不是每个 ID O(N) 次。这些组件组合在一起。这是 Bevy、Unity DOTS、Unreal 的 Mass Entities 以及大多数生产级 ECS 引擎在底层使用的模式。局部性是预先支付的一次排序并在许多缓存友好的内部循环中摊销。练习计算空间单元格。按照正文编写spatial_cell(pos_x, pos_y, cell_size)。将其应用于一个包含 1,000 个生物、具有随机位置的世界。打印单元格 ID 的np.bincount这是每个单元格中有多少生物分布的直方图。按单元格排序。使用步调一致的列重新排序实现sort_creatures_for_locality。运行它。验证打印排序后的前十个(pos_x, pos_y)——这些应该是近邻位置而不是随机的。维护id_to_slot。确认id_to_slot[world.id] np.arange(N)的重写正确解析。从排序前获取一个持有的 ID在排序后查找其槽位确认pos_x[slot]与之前的值相同它只是移动了。比较next_event在排序前后的时间。编写一个next_event系统对于每个生物扫描pos_x, pos_y的下 100 个条目以寻找碰撞。在 100,000 个生物上比较排序前与排序后的时间。排序后的版本应该明显更快——快多少取决于扫描恰好落在同一条缓存行中的程度。排序频率。运行一个 100 次滴答的模拟每个滴答都排序。运行相同的模拟每 10 个滴答排序一次以及每 100 个滴答排序一次。比较总成本排序成本 邻居扫描成本。找到排序成本等于邻居扫描节省的频率——这是你的最佳点。挑战Z-order 曲线。用 Z-order莫顿哈希替换简单的(x, y)打包——交错cx和cy的位。比较next_event的时间。Z-order 使空间上接近的单元格在线性顺序中也保持接近它通常优于简单的条纹打包因为水平相邻的两个单元格保持相邻。接下来是什么第 29 节——10K → 1M 的墙 是这些技术开始发挥作用的地方。在 10K 时运行良好的代码在 1M 时停止良好运行这一节是关于找出墙的位置和原因。