Repository navigation
GROWTH_RATE prevents dict shrinking #77386
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 = None
closed_at = None
created_at = <Date 2018-04-02.11:55:50.970>
labels = ['interpreter-core', '3.7', '3.8', 'performance']
title = 'GROWTH_RATE prevents dict shrinking'
updated_at = <Date 2022-01-26.18:08:32.273>
user = 'https://github.com/methane'bugs.python.org fields:
activity = <Date 2022-01-26.18:08:32.273>
actor = 'brandtbucher'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2018-04-02.11:55:50.970>
creator = 'methane'
dependencies = []
files = ['47512']
hgrepos = []
issue_num = 33205
keywords = ['patch']
message_count = 8.0
messages = ['314806', '314807', '314977', '315351', '315380', '315409', '411534', '411716']
nosy_count = 8.0
nosy_names = ['rhettinger', 'methane', 'Yury.Selivanov', 'Mark.Shannon', 'eric.snow', 'serhiy.storchaka', 'miss-islington', 'brandtbucher']
pr_nums = ['6350', '6503']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'open'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue33205'
versions = ['Python 3.7', 'Python 3.8']
Activity
methane commentedon Apr 2, 2018
GROWTH_RATE is changed from (used*2) to (used*2 + dk_size/2) in bpo-17563, at Python 3.4.
It was for avoid resizing dict for massive del/insert use case, by increasing possibility of overwriting DUMMY entry.
From Python 3.6, there are no DUMMY entry. While there are dummy keys, we resize (repack) when entries are full.
So there are no benefit from "possibility of overwriting dummy entry".
(Of course, there are still benefit from slow repacking rate for new dict.
So I don't propose to change it back to (used*2), but (used*3).)
This GROWTH_RATE prevents dict is shrinked in insertion_resize().
For example, consider this dict:
del d[i]doesn't shrink the dict. This is another issue (bpo-32623).Current dk_size is 16384 and entries length is dk_size * 2 // 3 = 10922.
So dictresize will called when next 923 entries are added.
New dk_size is round_up_to_power_of_two(922 + 16384/2) = 16384.
So dict is not shrinked!
round_up_to_power_of_two(used + dk_size/2) means dict is shrinked only when used == 0.
I propose changing GROWTH_RATE again to
used*3fromused*2 + dk_size/2In case of dict growing without deletion, dk_size is doubled for each resize as current behavior.
When there are deletion, dk_size is growing aggressively than Python 3.3 (used*2 -> used*3). And it allows dict shrinking after massive deletions.
I want to backport this change to Python 3.7. While it's beta3, "dict can't be shrinked unless empty" behavior looks resource usage bug to me.
methane commentedon Apr 2, 2018
# cap2.json is master (used*2 + dk_size/2)
# used3.json is patched (used*3)
$ ./python-master -m perf compare_to cap2.json used3.json -G
Slower (2):
Faster (1):
Benchmark hidden because not significant (5): rand_access(size=2), rand_access(size=5), rand_access(size=100), rand_access(size=200), rand_access(size=500)
methane commentedon Apr 5, 2018
@Mark.Shannon, @rhettinger How do you think this?
serhiy-storchaka commentedon Apr 16, 2018
The capacity of the dict is 2/3 of its hashtable size: dk_usable < 2/3 * dk_size.
Currently the dict grows if dk_usable > 1/4 * dk_size, and preserves the size if dk_usable < 1/4 * dk_size. Note that it it can grow twice if dk_usable > 1/2 * dk_size.
With the proposed change the dict will grow only if dk_usable > 1/3 * dk_size, preserve the size if 1/6 * dk_size < dk_usable < 1/3 * dk_size, and shrink if dk_usable < 1/6 * dk_size. After growing once it will no need to grow again until the number of item be increased.
This LGTM.
methane commentedon Apr 17, 2018
New changeset 5fbc511 by INADA Naoki in branch 'master':
bpo-33205: dict: Change GROWTH_RATE to
used*3(GH-6350)5fbc511
miss-islington commentedon Apr 17, 2018
New changeset 902bb62 by Miss Islington (bot) in branch '3.7':
bpo-33205: dict: Change GROWTH_RATE to
used*3(GH-6350)902bb62
rhettinger commentedon Jan 25, 2022
Should this have been "filled*3" rather than "used*3"?
The intent was to give a larger resize to dict that had a lot of dummy entries and a smaller resize to dicts without deletions.
methane commentedon Jan 26, 2022
We do not have filled since Python 3.6.
There is a
dk_nentriesinstead. But wheninsertion_resize()is called,dk_nentriesis equal toUSABLE_FRACTION(dk_size)(dk_size is1 << dk_log2_sizefor now). So it is different from filled in the old dict.I chose
dk_used*3as GROWTH_RATE because it reserves more spaces when there are dummies than when there is no dummy, as I described in the same comment:For example, when current dk_size == 16 and USABLE_FRACTION(dk_size) == 10, new dk_size is:
(snip)
(snip)
As you can see, dict is more sparse when there is dummy than when there is no dummy, except used=5/dummy=5 case.
There may be a small room for improvement, especially for
used=5/dummy=5case. But I am not sure it is worth enough to use more complex GROWTH_RATE than used*3.Any good idea?