来源https://root-11.codeberg.page/intro-book-python/7 — 数组结构 (SoA)你的牌堆有三个 numpy 列suits、ranks、locations。每个字段都存在于自己的数组中由实体索引。这种布局被称为数组结构——SoA。相反的布局——一个单一的list[Card]其中每个元素是一个包含所有三个字段的dataclass——被称为结构数组——AoS。它们是关于相同数据存放在何处的不同选择。# SoA: 三列索引步调一致suitsnp.zeros(52,dtypenp.uint8)ranksnp.zeros(52,dtypenp.uint8)locationsnp.zeros(52,dtypenp.uint8)# AoS: 一个对象列表dataclassclassCard:suit:intrank:intlocation:intcards:list[Card][...]# 52 个实例大多数 Python 程序员默认会选择 AoS。这是每个入门教程都会教的为实体定义一个类将实例放入列表。问题在于在实际的循环中“实体”是内部循环读取的任何东西而不是数据模型认为应该放在一起的东西。一个计算玩家 1 手牌中牌数的系统只读取location列——它根本不需要suit或rank。“只读一列”的实际成本使用 SoA这个计数是一个 numpy 原语held_by_p1int(np.sum(locations1))该调用遍历locations的N 字节生成一个 N 字节的布尔掩码并对其进行求和——所有操作都在 C 语言内部进行没有 Python 级别的迭代。在这台机器上当 N 1,000,000 张牌时调用大约需要 0.5 毫秒。使用 AoS同样的计数是一个 Pythonfor循环held_by_p1sum(1forcincardsifc.location1)该循环为每张牌支付一次字节码分发、一次getattr、一次比较和一次增量。根据 §1解释器分发约为 5 纳秒/元素而getattr还会增加更多。当 N 1,000,000 时同样的计数需要 30-50 毫秒——对于相同数据上的相同答案慢了两个数量级。这就是来自 §4 的带宽受限与解释器受限模式的区别。SoA 将内部循环推入 C 语言并遍历连续的字节AoS 将内部循环保留在解释器中。SoA 调用可以在 30 Hz 滴答33 毫秒预算内处理 100 万个实体并使用不到 2% 的预算。AoS 调用在 100 万个实体时就消耗了整个滴答预算没有为模拟的其余部分留下空间。Python AoS 的惩罚不会随宽度缩小在 Rust 的 AoS 布局中成本随结构体的大小增长一个 19 字节的Card用一个缓存行容纳三张牌而不是六十四字节的locations。一个不需要suit和rank的读取器无论如何都要为它们付费因为它们在同一条缓存行中进入。添加一个 16 字节的nickname字段会使差距扩大。在 Python 中情况不同。dataclass的每个字段都是一个PyObject*指针因此一个“更宽”的Card并不会在同一缓存行中放入更多的字节——它放入更多的指针。c.location的成本不是“额外的缓存流量”而是 Python 属性查找的固定开销。添加你不读取的字段会使每个Card在绝对值上更重更多的分配更多的引用计数但不会减慢每属性访问的速度。惩罚是固定的由解释器分发和getattr决定。这使得 SoA 在 Python 中的优势是绝对的而不仅仅是量化的。numpy 原语完全脱离了解释器而 AoS 循环则不能。任何数量的dataclass(slotsTrue)规范都无法消除每属性的分发成本。根据 §6槽减少了构建成本和每实例内存但每次读取c.location仍然要通过 Python 的属性机制。SoA 是默认选择因此SoA 是本书中的默认选择。AoS 有时是正确的选择——例如当每个系统在每个滴答中读取每个实体的每个字段时很少见或者当 N 非常小以至于无论布局如何循环开销都占主导地位时想想几十个项目而不是几百万。但这是一个需要通过测量来赢得的权衡而不是通过习惯来假设。首先编写 SoA只有在基准测试迫使你时才切换到 AoS。§3 的示例code/measurement/aos_vs_soa_footprint.py是本章的参考测量值。重新阅读其对第 0 列求和的这一行元组列表AoS 的双胞胎对一百万个十字段行的第 0 列求和需要 30 毫秒numpy SoA 只需 0.4 毫秒就能完成相同的操作。对于规范的“系统读取一列”操作速度快 75 倍。这就是本书其余部分中你的内部循环将处于的模式。[!NOTE]numpy 存储行pandas 存储列。numpy 数组默认是行主序的可以通过orderF使用列主序。pandas 则相反——底层是面向列的每列连续存储这就是为什么 DataFrame 沿列操作很快而沿行操作很慢。两种布局都不是对所有用途都最优的当循环读取许多行的少数几个字段时SoA 胜出当循环一次处理整个记录时行存储胜出。练习其中一些练习需要使用time.perf_counter()。构建两种布局。从 §5 获取你的deck.py并添加一个 AoS 双胞胎一个包含 52 个条目的list[Card]其中Card是一个包含三个整数字段的dataclass。构建两者并验证它们编码了相同的逻辑内容。用两种方法计算玩家手中的牌数。使用np.sum(locations player)编写count_held_soa(locations, player)并使用 Python 生成器表达式编写count_held_aos(cards, player)。确认它们在相同的牌堆上返回相同的数字。在 10,000 个条目时计时。将你的牌堆复制到长度为 10,000。使用timeit对两个函数计时例如numpy 版本使用number1000AoS 版本使用number100。注意每纳秒每元素的比率。扩展到 1,000,000 个条目。在长度 1,000,000 时重复。SoA 版本读取 1 MB 的字节AoS 版本通过 Python 的属性机制遍历一百万个指针追逐。注意其比率。在大多数机器上它在 50-200 倍范围内。Python 版的热/冷情况。用nickname: str 字段和dealt_at: int -1字段扩展Card——总共五个字段而不是三个。重新构建两者。再次对计数计时。注意SoA 时间不变计数仍然只遍历locations而AoS 时间也大致不变解释器分发无论如何都占主导地位。与本章的 Rust 版本进行比较在 Rust 版本中 AoS 时间会随着行大小而增长——Python 的惩罚是以不同的方式固定的。AoS 不会输的情况。编写一个更新一张特定卡片的所有字段的函数。SoA 写入三个或五个不同的列AoS 写入一个 Python 对象。对于“更新一张卡片的所有字段”的情况——单个实体没有循环——AoS 具有竞争力或更好。对它计时。注意这种情况没有内部循环这就是为什么 §4 中的模式区分不适用。先构建后读取。从 §6 中你知道构建dataclass实例很慢。计时构建一次百万条目的 AoS 列表然后对位置查询求和 1000 次。与构建一次百万条目的 SoA然后求和 1000 次进行比较。构建成本会在多次读取中摊销对于短寿命的数据即使是 SoA 的构建时间也会成为一个因素。提示这是 §22 — 变更缓冲区 的预兆。挑战一个从头开始的SoaDeck类。将列suits, ranks, locations, dealt_at包装到一个拥有它们所有的一个 Python 类中。提供reorder(self order)作为唯一的公共修改器。你在正确性方面获得了什么在灵活性方面失去了什么提示你刚刚提前四章重建了 §25 — 表的所有权 中的契约。接下来是什么§8 — 有了一就有了多 是普适性原则。牌堆隐含地教会了它下一节将为其命名。8 — 有了一就有了多代码是为数组编写的。对单个实体操作的函数只是 N 1 的特例它不需要自己的抽象。一个有 52 张牌的纸牌游戏是三个数组——花色、点数、位置——而不是 52 个对象。一个有 100 个生物的模拟是六个长度为 100 的数组而不是 100 个Creature实例。复数形式是基本单位单数形式是平凡的情况。模式很简单。首先编写数组版本。单例作为一个元素的切片出现。要洗一张牌你在order数组中交换两个索引——就像洗整副牌一样。要找到玩家 1 手中点数最高的牌你扫描小的手牌数组——与扫描所有 52 张牌的形状相同。要发一张牌你写入locations中的一个单元格——与发很多牌的形状相同。命名的 OOP 本能这与大多数 Python 程序员第一天就习得的本能背道而驰编写card.shuffle()或creature.update()的冲动然后思考如何对许多对象执行此操作。几乎每个 Python 教程都将行为建模为对象上的方法然后介绍对象列表作为拥有许多的自然方式然后介绍for c in creatures: c.update()作为对每个对象做某事的自然方式。三个步骤每一步在局部都是合理的但它们一起构建了本章要求你放弃的模式。当你从一开始就为数组编写代码时这个难题就不存在了。shuffle(deck)是一个适用于任何牌堆的函数包括只有一张牌的牌堆。update(creatures)——将列作为 numpy 数组接受——是一个适用于任何种群的函数包括种群数量为 1 的情况。对象上的方法形式严格来说比函数加切片形式有更多的代码它需要一个类、一个__init__、一个在数组级别什么都不做的self参数以及一个阻止内部循环离开解释器的调用约定。一个有用的测试当你发现自己在为一个类编写方法时问一问这在数组上看起来像什么如果数组版本更短则放弃该方法。如果数组版本长度相同则将其保留为一个对 numpy 数组的自由函数——def shuffle(suits, ranks, locations, order)而不是class Deck: def shuffle(self): ...。无论哪种方式单例从来都不是正确的代码单元。性能论据还有一个性能原因——在 Python 中比在任何编译语言中都更尖锐。每次操作一个实体的方法会强制使用它的系统调用 N 次该方法。根据code/measurement/cache_cliffs.py无论数据大小如何Python 每元素工作成本约为 5 纳秒numpy 批量工作成本约为 0.2 纳秒/元素。在任何大小下比率都约为25 倍而这仅仅是分发成本——在你添加每次调用getattr(creature energy)的成本、每次返回时的引用计数工作以及 numpy 在连续字节上使用 SIMD 指令的损失机会之前。在编译语言中对creatures.iter().for_each(|c| c.update())的“显而易见”的内部循环是优化器通常可以挽救的——内联该方法将函数体融合到循环中对结果进行自动向量化。在 Python 中优化器是字节码分发器它无法做到这些。每个方法调用的形式本质上是该语言提供的最坏情况。首先为数组编写代码是解释器可以满足的请求——它可以将工作交给 numpy并完全退出循环。为单例和迭代编写代码是一个将工作固定在内核中的请求每个元素都要在解释器内部处理。因此“有了一就有了多”不是一个架构口号而是一种日常实践。第一次这样做没有任何成本。第一次忘记它时会付出一切代价。练习这些练习再次扩展了deck.py。目的是在第三部分转变为本书其余部分之前让你的指尖感受到数组优先的模式。函数加切片。编写def highest_rank_in_hand(hand, ranks)其中hand是一个包含牌索引的 numpy 数组ranks是牌堆的点数列。函数体应该是一行int(ranks[hand].max())。在 5 张牌的手牌上使用它。然后在 1 张牌的手牌上使用它。然后在空手牌上使用它。同一个函数三个 N 值。逆转冲动。给定一个存在于假设的Card类上的 OOP 风格的def is_face_card(self) - bool将其重写为def face_cards(ranks)返回一个形状为(N,)的 numpy 布尔掩码。在一次调用中将其应用于所有 52 张牌mask face_cards(ranks); face_count int(mask.sum())。N 0 的情况。当hand为空时highest_rank_in_hand会做什么在空数组上调用arr.max()会引发异常。选择一种行为——返回None返回一个哨兵值引发异常——并证明选择的合理性。提示大多数用法可以通过if hand.size 0: return None进行短路。对单个值的谓词。假设你想判断一张牌是否是红色花色 0 和 1 是红心/方块。首先编写数组版本def red_mask(suits)——一行(suits 2)。然后说服自己单例情况是red_mask(np.array([suit]))[0]——数组版本覆盖了它。计数开销。计时sum(is_face_card_per_row(suits[i], ranks[i]) for i in range(52))与int(face_cards(ranks).sum())对比。在 52 时数组版本应该明显更快在 100,000 时快得多。记录比率。通过复制牌堆在 N 100,000 时重复。重新审视 dataclass 双胞胎。从 §7 练习 1 中获取你的list[Card]。将face_count_aos(cards)编写为生成器表达式求和将face_count_soa(ranks)编写为 numpy 版本。在 1,000,000 个实体上对两者计时。你在这里测量的比率与 §7 中为count_held测量的比率相同——它不是特定于一个查询而是你在纯 Python 中编写的任何内部循环的每元素分发成本。挑战来自教程。找到任何使用带有方法__init__、is_face、__repr__等的class Card的 Python 教程。将他们的完整纸牌游戏重写为三个或四个numpy 数组加上自由函数。比较代码行数。比较清晰度。比较当你想查询“桌面上所有的花牌”时会发生什么——一次 numpy 调用与对每个卡牌方法调用的循环。接下来是什么你已经完成了“身份与结构”。卡片按照规则行事行对齐布局是 SoA单例被推导出来。下一个阶段是“时间与传递”从 §11 — 滴答 开始。来自code/sim/SPEC.md的生态系统模拟器即将开始运行。
