Following system colour scheme - Python 增强提案 Selected dark colour scheme - Python 增强提案 Selected light colour scheme - Python 增强提案

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__槽时,它们以分离形式创建。键表缓存在类型中,这可能允许一个类的所有实例的属性字典共享键。如果这些字典的键开始分化,则单个字典将惰性地转换为合并表形式。这确保了常见情况下的良好内存使用,并在所有情况下保持正确性。

当调整分离字典的大小时,它会被转换为合并表。如果调整大小是由于存储实例属性,并且只有一个类的实例,那么字典将立即重新分离。由于大多数面向对象代码将在__init__方法中设置属性,所有属性将在创建第二个实例之前设置,并且不需要更多调整大小,因为所有后续实例字典都将具有正确的大小。对于更复杂的使用模式,无法知道最佳方法是什么,因此实现允许在调整大小之前进行额外插入,然后它恢复到合并表(非共享键)。

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

合并式字典

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

实施

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

优点和缺点

优点

面向对象应用程序的显著内存节省。为创建大量相似对象的程序带来小的速度提升。

缺点

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

repr()输出和迭代顺序的更改:对于大多数情况,这将保持不变。然而,对于某些分离表字典,迭代顺序将发生变化。

这些缺点都不应该是问题。干扰字典实现内部结构的模块已经中断,应该修正以使用API。字典的迭代顺序从未定义,并且始终是任意的;它在Jython和PyPy中是不同的。

替代实现

分离表的替代实现,可以节省更多内存,是在键表的值字段中存储一个索引(而不是忽略值字段)。该索引将明确说明在值数组中的何处查找。然后,值数组只需要键表中每个可用槽的一个字段,而不是键表中每个槽。

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

“索引”版本不会包含在此实现中,但应被视为推迟而不是拒绝,有待进一步实验。

参考资料


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

最后修改:2025-02-01 08:59:27 GMT