对象、属性、映射，眼花缭乱

# 对象、属性、映射，天哪！ 原文：https://bernsteinbear.com/blog/object-shapes/ 或者，*IC UC 我们都是 C 中的 IC*。 在许多动态类型编程语言中，对象看起来就像一个庞大的名称到值的映射。这些语言鼓励这种灵活性。以 Python 为例： `` class C: def __init__(self): self.a = 1 self.b = 2 ``` 或者 Ruby： `` class C def initialize @a = 1 @b = 2 end end ``` 或者 JavaScript1 (https://bernsteinbear.com/blog/object-shapes/#fn:js-synonyms)： `` let obj = {}; obj.a = 1; obj.b = 2; ``` 这可能会鼓励虚拟机实现者使用哈希表来建模对象属性。毕竟，哈希表非常擅长将名称映射到值。 以下是一个 Python 草图，展示这种对象模型的样子。因为这是一个草图，它使用 `write_attr` 和 `read_attr` 而不是你的编程语言自带的更常见的语法。 `` MISSING = object() class Instance: def __init__(self): # TODO: 你的对象系统的其余部分 self.cls = ... self._fields = {} def read_attr(self, fieldname): return self._fields.get(fieldname, MISSING) def write_attr(self, fieldname, value): self._fields[fieldname] = value obj = Instance() obj.write_attr("a", 1) obj.write_attr("b", 2) print(obj.read_attr("a") + obj.read_attr("b")) ``` 这有一些好处： - 它非常容易理解 - ……呃，好吧，也许就这些 它也有一些缺点： - 它对一个非常常见的操作使用了哈希表：虽然这在技术上是 O(1)，但哈希和探测非常慢 - 它存在间接层：从对象跳转到其独立的哈希表字段存储需要大量依赖性内存加载。对象属性被频繁访问，因此应该内联存储在对象上，而不是距离另一次内存访问（以及潜在的缓存未命中）之外 这是一个哈希表没有内部碎片问题的好例子。这意味着字面上每个 `a.b` 操作都在执行数百或数千条 CPU 指令，包括多次依赖性内存加载。这对性能来说*可不是好事*。 因此，运行时实现者倾向于实现一种叫做映射（maps）、布局（layouts）、形状（shapes）、隐藏类（hidden classes）、结构（structures）的东西，或者可能还有一个我不知道的秘密第六名称，以优化属性的读取、写入和存储。 但这种形状代码长什么样？它究竟如何帮助性能？许多大型生产运行时有着非常复杂的代码和领域特定的边缘情况，因此可能无助于掌握基础。而许多博客文章，虽然优秀的高级概述，但缺乏实现细节。于是我们又一次在这里写博客，写在其他所有人都已经写过的地方。运气好的话，你应该能够写出一页代码，并在脑中同时掌握整个系统。 ## 500 行或更少 我决定再一次认真阅读 CF Bolz-Tereick 的 A Simple Object Model (https://aosabook.org/en/500L/a-simple-object-model.html)。过去我尝试过几次都半途而废，因为它以相当高的保真度建模了 Python，而 Python 的对象模型*真的非常复杂*。 但这次我认真读了吗？嗯，没有。这次我允许自己跳过了类和方法相关的部分，而是专注于实例属性和映射部分。在 CF 的文章中，有一个非常干净的映射系统的核心，我想对它进行实验，所以我把它提取了出来。 CF 的文章开头与我们自己的草图非常相似，将对象建模为属性的无序映射。它还填补了我之前省略的关于类的 TODO 部分。我会在这里复制我的简化实现，让你看看： `` # 基础对象模型代码： class Base: def __init__(self, cls, fields): self.cls = cls self._fields = fields def read_attr(self, fieldname): return self._read_dict(fieldname) def write_attr(self, fieldname, value): return self._write_dict(fieldname, value) def _read_dict(self, fieldname): return self._fields.get(fieldname, MISSING) def _write_dict(self, fieldname, value): self._fields[fieldname] = value MISSING = object() class Instance(Base): def __init__(self, cls: "Class"): super().__init__(cls, {}) class Class(Base): def __init__(self, name, base_class, fields, metaclass): super().__init__(metaclass, fields) self.name = name self.base_class = base_class OBJECT = Class(name="object", base_class=None, fields={}, metaclass=None) TYPE = Class(name="type", base_class=OBJECT, fields={}, metaclass=None) TYPE.cls = TYPE OBJECT.cls = TYPE ``` 你可以这样使用它（测试代码同样来自 CF 的文章）： `` A = Class(name="A", base_class=OBJECT, fields={}, metaclass=TYPE) obj = Instance(A) obj.write_attr("a", 1) assert obj.read_attr("a") == 1 obj.write_attr("b", 5) assert obj.read_attr("a") == 1 assert obj.read_attr("b") == 5 obj.write_attr("a", 2) assert obj.read_attr("a") == 2 assert obj.read_attr("b") == 5 ``` `Base` 类中有一些委托，因为这篇文章已经预见到我们即将做的事情：为了获得更好的性能，用 `_read_dict` 和 `_write_dict` 替换 `Instance` 的实现。 ## 制图 好的，让我们添加这个"映射"数据结构。映射的目的有三个： 1. 在快速路径中摆脱字符串处理和哈希。我们希望改为对小整数进行操作。 2. 消除间接层。我们希望将属性内联存储在对象中，而不是存储在内存的其他位置。 3. 成为/拥有一个描述特定对象布局的稳定标识符。 **对于第一点**，我们可以将对象的映射字段视为一个（数据库）索引或写透缓存。它负责反映给定对象的布局： 这个模型*基本上*到位了……你可以向映射提问，比如"这个对象有哪些属性？"以及"属性 `a` 相对于对象起始位置在哪里？" 仅看图表，这可能看起来很傻：毕竟，我们把一个哈希表换成了另一个。然而，有一个很大的区别，那就是在形状模型中，我们*不必*总是使用哈希表。如果我们记住上次在形状中查找时的偏移量，就可以重用该偏移量。这主要体现在一个叫做内联缓存的解释器特性中。 这带我们到**第二部分**：如果我们有了对象内的偏移量，就可以直接从中读取。不需要再从内存的另一个区域进行第二次加载。我们手上已经有了对象，并且希望它已经在缓存中了。 ……至少在映射*改变*之前是这样。那时我们就不能重用偏移量了。记住，这些语言鼓励灵活性。对象可以在任何时候增加或减少一个属性。那该怎么办？理想情况下，我们有一个非常快速的检查来告诉我们对象的内存布局是否发生了变化。 这带我们到**第三部分**。我们需要能够依赖映射的不可变性、实时性，以及它作为给定内存布局的稳定标识符的能力。这样我们就可以在加载之前做一个非常快速的检查（"映射是否和上次读取的一样？"）。 这意味着当我们向对象添加一个新属性时，需要给它一个新的映射。映射实际上是*树*（trie？），像持久化数据结构一样被分配。每个新对象都从一个空映射开始。随着程序添加属性，它沿着树中的边查找或创建新的映射。 图片来源：CF Bolz-Tereick，CC BY 3.0。我建议阅读[关于映射的章节](https://aosabook.org/en/500L/a-simple-object-model.html#instance-optimization)，因为它有更详细的说明。 记住所有这些，让我们看看 CF 的带映射对象以及映射本身的 Python 实现： `` class Instance(Instance): def __init__(self, cls: "Class"): super().__init__(cls) self.map = EMPTY_MAP self.storage = [] def _read_dict(self, fieldname): index = self.map.get_index(fieldname) if index == -1: return MISSING return self.storage[index] def _write_dict(self, fieldname, value): index = self.map.get_index(fieldname) if index != -1: self.storage[index] = value else: new_map = self.map.next_map(fieldname) self.storage.append(value) self.map = new_map class Map: def __init__(self, attrs): self.attrs = attrs self.next_maps = {} def get_index(self, fieldname): return self.attrs.get(fieldname, -1) def next_map(self, fieldname): assert fieldname not in self.attrs if fieldname in self.next_maps: return self.next_maps[fieldname] attrs = self.attrs.copy() attrs[fieldname] = len(attrs) result = self.next_maps[fieldname] = Map(attrs) return result EMPTY_MAP = Map({}) ``` 你可能注意到存储不是内联的，正如我最初承诺的那样。这是因为我们在 Python 中没有那种对象布局控制能力。当用 C++ 或 Rust 等语言实现时，属性存储通常与对象头内联。 不过，忽略这一点，我们可以看到常见情况仍然似乎是使用字符串名称读取和写入属性。怎么回事？好吧，让我们按照设计意图使用索引存储，在一个*内联缓存*中。 ## 内联缓存 让我们先看看字符串属性 API。我们会创建一个 Point 类并读取 `x` 属性。我们会保持属性名称不变，因为在程序中这通常是固定的：`obj.x` 通常看起来像某个字节码 `LOAD_ATTRIBUTE, "x"`，其中名称 `x` 以某种方式嵌入在字节码中。 这对内联缓存来说很重要：改变接收者是一回事，但改变被查找的名称会增加更多复杂性。这可行但很烦人。 `` Point = Class(name="Point", base_class=OBJECT, fields={}, metaclass=TYPE) P = Instance(Point) P.write_attr("x", 5) P.write_attr("y", 6) # 字符串 API :( P.read_attr("x") # 总是在查找索引 :( P.read_attr("x") # 每次都是 :( P.read_attr("x") ``` 然后我们将做一个内存/速度的权衡。我们将为前面提到的*预期映射*和前面提到的*缓存索引*分配空间。这让我们可以在（希望是）常见情况下先做一个非常快速的检查，然后进行索引加载。 逻辑如下： - 如果我们有匹配的映射，太好了！从存储中加载。 - 如果没有，按字符串名称查找值和索引。 - 然后缓存映射/索引的组合以供下次使用。 如果属性缺失，我们不会（目前？）缓存负查找。希望这种情况很少见。 `` class InlineCache: def __init__(self): self.map = None self.idx = None def read(self, obj, fieldname): obj_map = obj.map if obj_map is self.map: return obj.storage[self.idx] index = obj_map.get_index(fieldname) if index == -1: return MISSING self.map = obj_map self.idx = index return obj.storage[index] IC = InlineCache() # 通过字符串查找 :( IC.read(P, "x") # 映射命中！通过索引查找！:) IC.read(P, "x") # 映射命中！通过索引查找！:) IC.read(P, "x") ``` 你可能注意到我用了 `is`（指针相等）而不是 `==`（用户定义的/深度相等）。这是有意为之！因为我们保证映射是不可变的，所以我们不需要检查映射字段的相等性；只需要检查它的指针/数字 ID。 这个 `InlineCache` 类基本上只是内联缓存所做事情的一个"草图"。它是一个"解释器型内联缓存"。如果你确保快速路径被内联而慢速路径被外联，这种形态可以对你的解释器帮助很大。它确实能改善性能——我建议对一个简单的属性查找函数进行基准测试——但大多数带有内联缓存的运行时也带有 JIT 编译器。这些编译器试图消除内联缓存实现中的"解释"特性。例如参见： - Slava 的[文章](https://mrale.ph/blog/2015-01-11-whats-up-with-monomorphism.html)，用 IR 草图和类 JS 伪代码进行解释——以及这篇[更早的文章](https://mrale.ph/blog/2012-06-03-explaining-js-vms-in-js-inline-caches.html)，类似 - Caio 的[文章](https://caiolima.github.io/jsc/2020/03/12/jsc-inline-cache.html)，用 x86 汇编解释 JavaScriptCore 中的样子 - Matthew 的[文章](https://www.mgaudet.ca/technical/2018/6/5/an-inline-cache-isnt-just-a-cache)，用伪汇编解释投机数值加法的样子——大多数运行时不会做这种自修改汇编内联缓存，因为 W^X 保护，而且还需要刷新指令缓存 另一件需要注意的事情是**顺序很重要**。以不同顺序添加属性（例如先 `a` 后 `b` 对比先 `b` 后 `a`）会导致不同的形状。另一个常见的原因是条件性地存储属性，例如在初始化中（如 `if cond: self.a = 1`）。 这种形状和缓存行为对应用程序程序员来说并不真正可见，除了在性能回归2 (https://bernsteinbear.com/blog/object-shapes/#fn:attribute-order)中，要么你的内联缓存会频繁未命中，要么你不会有最优的（单态的）缓存。这听起来可能不吓人，但在热路径中缓存命中和缓存未命中的差异可能意味着 2 倍或更多的性能差距，值得在你的应用程序中调查。 另外，**数量很重要**。虚拟机实现者经过测量确定，大多数对象都很小（不到 20 个字段）。你可能会发现给对象放太多字段会导致它被降级并放回"哈希表模式"。例如 Ruby 在其形状变得"复杂"之前有一个固定数量的对象内实例变量（属性）。 最后，注意这个缓存不是特定于这个对象的；任意数量的 `Point` 实例都可以获得缓存命中。实际上，仔细看，对象甚至不一定非得是 `Point`…… ## 类与形状 不同类的两个对象可以拥有相同的形状意味着什么？ `` Foo = Class(name="Foo", base_class=OBJECT, fields={}, metaclass=TYPE) F = Instance(Foo) F.write_attr("x", 1) F.write_attr("y", 2) Bar = Class(name="Bar", base_class=OBJECT, fields={}, metaclass=TYPE) B = Instance(Bar) B.write_attr("x", 3) B.write_attr("y", 4) # 相同的形状/映射！ assert F.map is B.map # 但不同的类！ assert F.cls != B.cls ``` 首先，这意味着内联缓存可能有更高的命中率。例如，共享代码的子类实例在内联缓存中可能仍被视为*单态的*。 这也意味着你不能用形状来代替对类的了解。如果你有类似 Ruby 中的 `attr_reader`，虚拟机为查找实例变量专门生成一个合成方法，你需要做两件事： 1. 基于*对象的类*解析方法，以发现它是 `attr_reader` 2. 基于*对象的形状*解析实例变量 这种两阶段查找增加了复杂性和运行时开销。如果我们专门化映射，使得不同的类意味着不同的映射，我们就可以用一次字段加载来专门化这个两阶段分派。 这是一个有趣的想法：我们还能在映射上专门化什么？ ## 存储策略 也许不出所料，CF Bolz-Tereick 与 Lukas Diekmann 和 Laurence Tratt 再次一起出现在 Storage Strategies for Collections in Dynamically Typed Languages (https://dl.acm.org/doi/pdf/10.1145/2544173.2509531)（PDF，2013）中。 主要思想是关于对象的一些事实（属性、字段，哈哈）既是： - 值得