Repository navigation
Add a version number to dict keys. #88372
Description
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = 'https://github.com/markshannon'
closed_at = <Date 2021-08-02.13:54:55.652>
created_at = <Date 2021-05-21.15:38:13.729>
labels = ['release-blocker', 'performance']
title = 'Add a version number to dict keys.'
updated_at = <Date 2021-08-02.13:54:55.651>
user = 'https://github.com/markshannon'bugs.python.org fields:
activity = <Date 2021-08-02.13:54:55.651>
actor = 'pablogsal'
assignee = 'Mark.Shannon'
closed = True
closed_date = <Date 2021-08-02.13:54:55.652>
closer = 'pablogsal'
components = []
creation = <Date 2021-05-21.15:38:13.729>
creator = 'Mark.Shannon'
dependencies = []
files = []
hgrepos = []
issue_num = 44206
keywords = ['patch']
message_count = 18.0
messages = ['394120', '394121', '394187', '394252', '394253', '394255', '394278', '394301', '394326', '394644', '394702', '394783', '398677', '398735', '398740', '398746', '398770', '398771']
nosy_count = 6.0
nosy_names = ['vstinner', 'methane', 'Mark.Shannon', 'pablogsal', 'brandtbucher', 'erlendaasland']
pr_nums = ['26333', '26432', '26440', '27542']
priority = 'release blocker'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue44206'
versions = []
Activity
markshannon commentedon May 21, 2021
Add a version number to dict keys.
PEP-509 added a version number to dicts. Unfortunately this is no use for optimizing attribute loads and store on instances.
We need to know whether the keys are as expected, not the dict as that is likely to be different each time.
We can add a 32 bit version number and actually reduce memory use by taking advantage of the redundancy in the rest of the keys object.
markshannon commentedon May 21, 2021
The memory saving comes from converting:
to:
uint8_t dk_log2_size;
uint8_t dk_loopup_kind; /* Only 3 possible values */
uint32_t dk_version;
which saves 8 bytes on a 64 bit machine (no saving on a 32 bit machine).
vstinner commentedon May 22, 2021
Is the version on the key or on the value? Does the version change if a value is changed like d[1]="a"; d[1]="b"?
markshannon commentedon May 24, 2021
The version is on the dict keys. It changes if the dict keys object changes in a meaningful way.
So, no it doesn't change if a value is changed.
Nor would it change if the keys were shared and a new key-value pair is added to a dict, but that key was already in the shared keys.
vstinner commentedon May 24, 2021
I don't understand how such "key version" would be useful. Can you please elaborate?
markshannon commentedon May 24, 2021
http://theses.gla.ac.uk/2975/1/2011shannonphd.pdf page 128.
It means we don't need to cache a pointer to the keys, just the version number.
The version number is half the size (for 64 bit machines) and using it means that we don't leak keys.
vstinner commentedon May 25, 2021
Can't you please explain which kind of optimizations do you want to implement using such dict key version?
methane commentedon May 25, 2021
For class dict, there is a method cache.
For instance dict, there is a LOAD_ATTR optimization.
cpython/Python/ceval.c
Line 3458 in b11a951
So I want to see the performance gain of the optimization using dk_version before adding dk_version.
Additionally, I am not sure why 32bit is enough for dk_version. It is another reason I want to see the optimization before adding dk_version.
markshannon commentedon May 25, 2021
Which optimizations?
LOAD_GLOBAL:
Using a keys version instead of a whole dict version means that LOAD_GLOBAL won't leak references. It also means that we can (in the future) remove the PEP-509 version and save 8 bytes per dict.
LOAD_ATTR:
_PyDict_GetItemHint() still has to do quite a lot of work compared to a version check.
The hint approach can't quickly tell us whether a name is not in a dictionary, which is needed for optimizing non-descriptor class attributes.
LOAD_METHOD:
Because functions are non-overriding descriptors we need to quickly check that the instance does not have an attribute shadowing the method.
Why is 32 bits enough?
Because the version is reset to zero, whenever the dict keys changes, and only set to non-zero when we explicitly ask for it when optimizing. 4 billion optimization events is a lot.
It can't overflow, it just becomes useless when we reach UINT_MAX.
Using 64 bits would just waste memory.
Overall, versioning the dictionary's keys is more useful and more compact than versioning the dictionary as a whole.
markshannon commentedon May 28, 2021
New changeset f8a95df by Mark Shannon in branch 'main':
bpo-44206: Add a version number to dictionary keys (GH-26333)
f8a95df
pablogsal commentedon May 28, 2021
New changeset 1a672a5 by Pablo Galindo in branch 'main':
bpo-44206: Fix compiler warnings in dictobject.c (GH-26440)
1a672a5
1 remaining item
pablogsal commentedon Aug 1, 2021
Reopening this and marking as a release blocker. Seems that a buildbot has found some cases where an assert fails:
https://buildbot.python.org/all/#/builders/562/builds/110/steps/5/logs/stdio
..python: Objects/dictobject.c:350: dictkeys_set_index: Assertion `keys->dk_version == 0' failed.
Fatal Python error: Aborted
Current thread 0x00007f7dba340740 (most recent call first):
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/test_importlib/test_api.py", line 290 in test_reload_location_changed
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/case.py", line 549 in _callTestMethod
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/case.py", line 592 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/case.py", line 652 in __call__
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 122 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 84 in __call__
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 122 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 84 in __call__
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 122 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 84 in __call__
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 122 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 84 in __call__
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 122 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/suite.py", line 84 in __call__
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/unittest/runner.py", line 176 in run
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/support/init.py", line 979 in _run_suite
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/support/init.py", line 1104 in run_unittest
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/runtest.py", line 261 in _test_module
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/refleak.py", line 90 in dash_R
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/runtest.py", line 295 in _runtest_inner2
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/runtest.py", line 335 in _runtest_inner
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/runtest.py", line 215 in _runtest
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/runtest.py", line 245 in runtest
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/main.py", line 334 in rerun_failed_tests
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/main.py", line 712 in _main
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/main.py", line 655 in main
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/libregrtest/main.py", line 733 in main
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/test/main.py", line 2 in <module>
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/runpy.py", line 86 in _run_code
File "/home/buildbot/buildarea/3.x.cstratak-RHEL7-x86_64.refleak/build/Lib/runpy.py", line 196 in _run_module_as_main
markshannon commentedon Aug 2, 2021
Pablo,
There is another failure on that buildbot: test_inspect fails with
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/mark/repos/cpython/Lib/inspect.py", line 1154, in walktree
classes.sort(key=attrgetter('__module__', '__name__'))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'str' and 'module'
I can reproduce that failure with a debug build and either of
./python -m test -R 3:3 test_inspect
./python -m test test_inspect -F
Known issue or should I file a new issue? This issue is also present in 3.10.
pablogsal commentedon Aug 2, 2021
Can you open a different issue, please?
pablogsal commentedon Aug 2, 2021
Opened https://bugs.python.org/issue44808
pablogsal commentedon Aug 2, 2021
New changeset e06ae75 by Mark Shannon in branch 'main':
bpo-44206: Make sure that dict-keys's version is set to zero when value is popped (GH-27542)
e06ae75
pablogsal commentedon Aug 2, 2021
Closing for now unless we see the error again