PEP 509 – 为 dict 添加私有版本号

作者:: Victor Stinner <vstinner at python.org>
状态:: 已取代
类型:: 标准轨迹
创建:: 2016年1月4日
Python 版本:: 3.6
历史记录:: 2016年1月8日, 2016年1月11日, 2016年4月14日, 2016年4月19日
取代版本:: 699
决议:: Python-Dev 消息

摘要

为内置的 dict 类型添加一个新的私有版本号，在每次创建字典和每次修改字典时递增，以实现命名空间上的快速保护。

基本原理

在 Python 中，内置的 dict 类型被许多指令使用。例如，LOAD_GLOBAL 指令在全局命名空间或内置命名空间中查找变量（两次字典查找）。Python 使用 dict 来表示内置命名空间、全局命名空间、类型命名空间、实例命名空间等。局部命名空间（函数命名空间）通常被优化为数组，但它也可能是一个字典。

Python 难以优化，因为几乎所有东西都是可变的：内置函数、函数代码、全局变量、局部变量……都可以在运行时修改。实现尊重 Python 语义的优化需要检测何时“发生变化”：我们将这些检查称为“保护”。

优化的速度取决于保护检查的速度。本 PEP 提出为字典添加一个私有版本号，以实现命名空间上的快速保护。

如果版本没有改变，则可以跳过字典查找，这对于大多数命名空间来说是常见情况。版本是全局唯一的，因此检查版本也足以验证命名空间字典是否被替换为新的字典。

当字典版本没有改变时，保护的性能不依赖于被观察的字典条目的数量：复杂度为 O(1)。

优化示例：将全局变量的值复制到函数常量中。此优化需要对全局变量进行保护，以检查它是否在复制后被修改。如果全局变量没有被修改，则函数使用缓存的副本。如果全局变量被修改，则函数使用常规查找，并且可能还会使函数退化（以移除下次函数调用时保护检查的开销）。

有关使用保护机制来专门化函数的具体用法以及关于 Python 静态优化器的更一般的基本原理，请参阅 510 – 使用保护机制专门化函数。

保护示例

使用假设的 dict_get_version(dict) 函数检查字典条目是否被修改（创建、更新或删除）的快速保护的伪代码

UNSET = object()

class GuardDictKey:
    def __init__(self, dict, key):
        self.dict = dict
        self.key = key
        self.value = dict.get(key, UNSET)
        self.version = dict_get_version(dict)

    def check(self):
        """Return True if the dictionary entry did not change
        and the dictionary was not replaced."""

        # read the version of the dictionary
        version = dict_get_version(self.dict)
        if version == self.version:
            # Fast-path: dictionary lookup avoided
            return True

        # lookup in the dictionary
        value = self.dict.get(self.key, UNSET)
        if value is self.value:
            # another key was modified:
            # cache the new dictionary version
            self.version = version
            return True

        # the key was modified
        return False

字典版本的使用

加速方法调用

Yury Selivanov 编写了一个优化方法调用的补丁。该补丁依赖于 “在 ceval 中实现每个操作码的缓存” 补丁，该补丁要求字典版本在全局字典或内置字典被修改时使缓存失效。

缓存还需要字典版本是全局唯一的。可以在一个命名空间中定义一个函数，并在另一个命名空间中调用它，例如使用带有 globals 参数的 exec()。在这种情况下，全局字典被替换，缓存也必须失效。

使用保护机制的专门函数

PEP 510 提出一个 API 来支持带有保护机制的专门函数。它允许实现 Python 的静态优化器，而不会破坏 Python 的语义。

fatoptimizer 是 FAT Python 项目的一个静态 Python 优化器的示例。它实现了许多需要命名空间保护的优化

调用纯内置函数：要将 len("abc") 替换为 3，需要对 builtins.__dict__['len'] 和 globals()['len'] 进行保护
循环展开：要展开循环 for i in range(...): ...，需要对 builtins.__dict__['range'] 和 globals()['range'] 进行保护
等等。

Pyjion

根据 Pyjion 的两位主要开发者之一 Brett Cannon 的说法，Pyjion 可以从字典版本中受益，以实现优化。

Pyjion 是一个基于 CoreCLR（Microsoft .NET Core 运行时）的 Python JIT 编译器。

Cython

Cython 可以从字典版本中受益，以实现优化。

Cython 是一个针对 Python 编程语言和扩展的 Cython 编程语言的优化静态编译器。

Unladen Swallow

即使没有明确提到字典版本，优化全局变量和内置函数查找也是 Unladen Swallow 计划的一部分：“实现几种提议的方案之一，以加快全局变量和内置函数的查找速度。”（来源：Unladen Swallow 项目计划）。

Unladen Swallow 是 CPython 2.6.1 的一个分支，添加了一个使用 LLVM 实现的 JIT 编译器。该项目于 2011 年停止：Unladen Swallow 回顾。

变更

在 PyDictObject 结构中添加一个 ma_version_tag 字段，其 C 类型为 PY_UINT64_T，64 位无符号整数。还添加一个全局字典版本。

每次创建字典时，全局版本都会递增，并且字典版本被初始化为全局版本。

每次修改字典内容时，都必须递增全局版本并将其复制到字典版本。可以修改字典内容的字典方法

clear()
pop(key)
popitem()
setdefault(key, value)
__delitem__(key)
__setitem__(key, value)
update(...)

当字典方法没有更改其内容时，是否递增版本的选择留给 Python 实现。Python 实现可以决定不递增版本，以避免在保护中进行字典查找。字典方法不修改其内容的情况示例

clear() 如果字典已经为空
pop(key) 如果键不存在
popitem() 如果字典为空
setdefault(key, value) 如果键已经存在
__delitem__(key) 如果键不存在
__setitem__(key, value) 如果新值与当前值相同
update() 如果不带参数调用或新值与当前值相同

将键设置为等于旧值的新值也被视为修改字典内容的操作。

两个不同的空字典必须具有不同的版本，以便能够仅通过其版本来识别字典。它允许在保护中验证命名空间是否未被替换，而无需存储对字典的强引用。使用借用的引用不起作用：如果旧字典被销毁，则可能在同一内存地址分配一个新字典。顺便说一句，字典不支持弱引用。

版本递增必须是原子的。在 CPython 中，全局解释器锁 (GIL) 已经保护了 dict 方法以使更改原子化。

使用假设的 dict_get_version(dict) 函数的示例

>>> d = {}
>>> dict_get_version(d)
100
>>> d['key'] = 'value'
>>> dict_get_version(d)
101
>>> d['key'] = 'new value'
>>> dict_get_version(d)
102
>>> del d['key']
>>> dict_get_version(d)
103

该字段称为 ma_version_tag，而不是 ma_version，以建议使用 version_tag == old_version_tag 进行比较，而不是 version <= old_version，因为在整数溢出后后者将变得不正确。

向后兼容性

由于 PyDictObject 结构不是稳定 ABI 的一部分，并且新的字典版本在 Python 范围内没有公开，因此更改是向后兼容的。

实现和性能

问题 #26058：PEP 509：向 PyDictObject 添加 ma_version_tag 包含一个实现此 PEP 的补丁。

在 pybench 和 timeit 微基准测试中，补丁似乎没有在字典操作上增加任何开销。例如，以下 timeit 微基准测试在更改前后都花费了 318 纳秒

python3.6 -m timeit 'd={1: 0}; d[2]=0; d[3]=0; d[4]=0; del d[1]; del d[2]; d.clear()'

当版本没有改变时，PyDict_GetItem() 进行字典查找需要 14.8 ns，而一个保护检查只需要 3.8 ns。此外，一个保护可以监视多个键。例如，对于在一个函数中使用 10 个全局变量的优化，10 次字典查找需要 148 ns，而当版本没有改变时，保护检查仍然只需要 3.8 ns（快 39 倍）。

fat 模块实现了这样的保护：fat.GuardDict 基于字典版本。

整数溢出

实现使用 C 类型 PY_UINT64_T 存储版本：一个 64 位无符号整数。C 代码使用 version++。根据 C 标准，在整数溢出时，版本会回绕到 0（然后继续递增）。

整数溢出后，保护检查可能成功，而被监视的字典键已被修改。只有在上次保护检查后正好进行了 2 ** 64 次字典创建或修改时，才会在保护检查时发生此错误。

如果每纳秒修改一次字典，2 ** 64 次修改需要超过 584 年。使用 32 位版本，只需要 4 秒。这就是为什么即使在 32 位系统上也使用 64 位无符号类型的原因。C 级别上的字典查找需要 14.8 ns。

每 584 年出现一次错误的风险是可以接受的。

备选方案

在 Python 层面公开版本号，作为一个只读的 version 属性

PEP 的第一个版本提议在 Python 级别将字典版本公开为只读的 __version__ 属性，并将其添加到 collections.UserDict 中（因为此类型必须模仿 dict API）。

存在多个问题

为了保持一致性并避免意外情况，必须将版本添加到所有映射类型中。实现新的映射类型将需要额外的无用功，因为实际上只有 dict 类型需要版本。
所有 Python 实现都必须实现此新属性，这给其他实现带来了更多工作，而它们可能根本不使用字典版本。

在 Python 级别公开字典版本可能会导致对性能的错误假设。在 Python 级别检查 dict.__version__ 并不比字典查找快。Python 中的字典查找的成本为 48.7 ns，而检查版本的成本为 47.5 ns，差异仅为 1.2 ns（3%）。

$ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd["33"] == 33'
10000000 loops, best of 3: 0.0487 usec per loop
$ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd.__version__ == 100'
10000000 loops, best of 3: 0.0475 usec per loop

__version__ 可能会在整数溢出时回绕。这容易出错：使用 dict.__version__ <= guard_version 是错误的，应使用 dict.__version__ == guard_version 来降低整数溢出时出现错误的风险（即使在实践中整数溢出的可能性很小）。

关于属性名称的强制性讨论

__cache_token__：Alyssa Coghlan 提出的名称，来自 abc.get_cache_token()。
__version__
__version_tag__
__timestamp__

为每个字典条目添加一个版本号

每个字典一个版本需要对值保持强引用，这可能会使值比预期存活更长时间。如果我们还为每个字典条目添加一个版本，则保护检查只需要存储条目版本（一个简单的整数）以避免对值的强引用：只需要对字典和键保持强引用。

更改：向 PyDictKeyEntry 结构添加一个 me_version_tag 字段，该字段的 C 类型为 PY_UINT64_T。当创建或修改键时，条目版本将设置为字典版本，字典版本在任何更改（创建、修改、删除）时都会递增。

使用假设的 dict_get_version(dict) 和 dict_get_entry_version(dict) 函数检查字典键是否已修改的快速保护的伪代码

UNSET = object()

class GuardDictKey:
    def __init__(self, dict, key):
        self.dict = dict
        self.key = key
        self.dict_version = dict_get_version(dict)
        self.entry_version = dict_get_entry_version(dict, key)

    def check(self):
        """Return True if the dictionary entry did not change
        and the dictionary was not replaced."""

        # read the version of the dictionary
        dict_version = dict_get_version(self.dict)
        if dict_version == self.version:
            # Fast-path: dictionary lookup avoided
            return True

        # lookup in the dictionary to read the entry version
        entry_version = get_dict_key_version(dict, key)
        if entry_version == self.entry_version:
            # another key was modified:
            # cache the new dictionary version
            self.dict_version = dict_version
            self.entry_version = entry_version
            return True

        # the key was modified
        return False

此选项的主要缺点是对内存占用量的影响。它增加了每个字典条目的大小，因此开销取决于桶的数量（字典条目，已使用或未使用）。例如，在 64 位系统上，它使每个字典条目的大小增加了 8 字节。

在 Python 中，内存占用量很重要，并且趋势是减少它。示例

PEP 393 – 灵活的字符串表示
PEP 412 – 键共享字典

添加一个新的字典子类型

添加一个新的 verdict 类型，它是 dict 的子类型。当需要保护检查时，使用 verdict 作为命名空间（模块命名空间、类型命名空间、实例命名空间等），而不是 dict。

保持 dict 类型不变，以便在不使用保护检查时不添加任何开销（CPU、内存占用量）。

技术问题：大量的 C 代码（包括 CPython 核心）期望精确的 dict 类型。问题

exec() 需要一个 dict 作为全局变量和局部变量。许多代码使用 globals={}。无法将 dict 转换为 dict 子类型，因为调用者期望修改 globals 参数（dict 是可变的）。
C 函数直接调用 PyDict_xxx() 函数，而不是在对象是 dict 子类型时调用 PyObject_xxx()。
PyDict_CheckExact() 检查在 dict 子类型上失败，而某些函数需要精确的 dict 类型。
Python/ceval.c 并不完全支持命名空间的字典子类型。