Following system colour scheme Selected dark colour scheme Selected light colour scheme

Python 增强提案

PEP 412 – 共享键字典

作者:
Mark Shannon <mark at hotpy.org>
状态:
最终
类型:
标准跟踪
创建:
2012年2月8日
Python 版本:
3.3
历史记录:
2012年2月8日

目录

摘要

此 PEP 提出对内置字典类型 dict 实现的更改。新实现允许用作属性字典(对象的 __dict__ 属性)的字典与同一类的其他实例的属性字典共享键。

动机

当前的字典实现使用比作为对象属性容器时必要的更多的内存,因为键会为每个实例复制,而不是在同一类的多个实例之间共享。尽管如此,当前的字典实现经过精心调整,并且作为通用映射对象表现非常出色。

通过将键(和哈希值)与值分离,可以使多个字典共享键并提高内存使用率。通过确保仅在有益时才将键与值分离,可以在用作通用映射对象时保留当前字典实现的高性能。

行为

新字典的行为与旧实现相同。它完全符合 Python API、C API 和 ABI。

性能

内存使用

内存使用量的减少与任何时间存在的具有共享键的字典数量直接相关。这些字典通常是当前字典实现大小的一半。

基准测试表明,对于面向对象的程序,内存使用量减少了 10% 到 20%,而其他程序的内存使用量没有发生显着变化。

速度

新实现的性能主要受内存局部性影响。当键未共享(例如在模块字典和由 dict(){} 显式创建的字典中)时,性能与当前实现相比没有变化(在百分之一或二之内)。

对于共享键的情况,新实现倾向于将键与值分离,但减少了总内存使用量。这将在许多情况下提高性能,因为减少内存使用量带来的好处超过了局部性损失,但某些程序可能会出现轻微的减速。

基准测试表明,大多数基准测试的速度没有发生显着变化。面向对象的基准测试在创建大量相同类的对象时显示出少量加速(gcbench 基准测试显示速度提高了 10%;这可能是上限)。

实现

旧字典和新字典都由一个固定大小的 dict 结构和一个可调整大小的表组成。在新字典中,表可以进一步拆分为键表和值数组。键表保存键和哈希值,以及(对于非拆分表)值。它与原始实现的不同之处仅在于它包含一些以前在 dict 结构中的字段。如果表被拆分,则键表中的值将被忽略,而是将值保存在单独的数组中。

分表字典

当创建字典以填充对象的 __dict__ 槽时,它们将以拆分形式创建。键表缓存在类型中,可能允许一个类的所有实例的属性字典共享键。如果这些字典的键开始发生分歧,则各个字典将惰性地转换为组合表形式。这确保了在常见情况下良好的内存使用,以及在所有情况下都保证正确性。

调整拆分字典的大小时,它将转换为组合表。如果调整大小是存储实例属性的结果,并且只有一个类的实例,则字典将立即重新拆分。由于大多数 OO 代码将在 __init__ 方法中设置属性,因此所有属性都将在创建第二个实例之前设置,并且不再需要调整大小,因为所有后续的实例字典都将具有正确的大小。对于更复杂的用法模式,不可能知道哪种方法是最佳的,因此实现允许额外的插入直到调整大小,然后它恢复到组合表(非共享键)。

从拆分字典中删除不会更改键表,它只是从值数组中删除值。

组合表字典

显式字典(dict(){})、模块字典和大多数其他字典都创建为组合表字典。组合表字典永远不会变成拆分表字典。组合表与旧字典中的表布局方式非常相似,从而导致非常相似的性能。

实现

新的字典实现可在 [1] 中获得。

优缺点

优点

面向对象应用程序的内存节省显著。对于创建大量相似对象的程序,速度略有提高。

缺点

数据结构的更改:干预字典实现内部的第三方模块将中断。

对 repr() 输出和迭代顺序的更改:对于大多数情况,这将保持不变。但是,对于某些拆分表字典,迭代顺序将更改。

这两个缺点都不应该成为问题。干预字典实现内部的模块已经损坏,应该修复为使用 API。字典的迭代顺序从未定义过,并且始终是任意的;对于 Jython 和 PyPy,它是不一样的。

替代实现

拆分表的替代实现,可以节省更多内存,是在键表的 value 字段中存储索引(而不是忽略 value 字段)。此索引将明确说明在 value 数组中的哪个位置查找。然后,value 数组只需要为键表中的每个可用插槽提供 1 个字段,而不是为键表中的每个插槽提供 1 个字段。

此“索引”版本将使 value 数组的大小减少约三分之一。键表将需要一个额外的“values_size”字段,从而使组合字典的大小增加一个字。额外的间接寻址增加了代码的复杂性,可能会稍微降低性能。

此“索引”版本不会包含在此实现中,但应考虑延迟而不是拒绝,待进一步实验。

参考文献


来源:https://github.com/python/peps/blob/main/peps/pep-0412.rst

上次修改时间:2023年9月9日 17:39:29 格林尼治标准时间