classification
Title: GROWTH_RATE prevents dict shrinking
Type: resource usage Stage: resolved
Components: Interpreter Core Versions: Python 3.8, Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Mark.Shannon, Yury.Selivanov, eric.snow, inada.naoki, miss-islington, rhettinger, serhiy.storchaka, vstinner
Priority: normal Keywords: patch

Created on 2018-04-02 11:55 by inada.naoki, last changed 2018-04-17 17:22 by inada.naoki. This issue is now closed.

Files
File name Uploaded Description Edit
dict_rand.py inada.naoki, 2018-04-02 11:59
Pull Requests
URL Status Linked Edit
PR 6350 merged inada.naoki, 2018-04-02 16:00
PR 6503 merged miss-islington, 2018-04-17 06:54
Messages (6)
msg314806 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2018-04-02 11:55
GROWTH_RATE is changed from (used*2) to (used*2 + dk_size/2) in #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:

>>> d = dict.fromkeys(range(10900))
>>> len(d)
10900
>>> sys.getsizeof(d)
295008
>>> for i in range(10900):
...     del d[i]
...
>>> len(d)
0
>>> sys.getsizeof(d)
295008

`del d[i]` doesn't shrink the dict.  This is another issue (#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!

>>> for i in range(923):
...     d[i] = i
...
>>> sys.getsizeof(d)
295008

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*3` from `used*2 + dk_size/2`

In 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.

>>> import sys
>>> d = dict.fromkeys(range(10900))
>>> sys.getsizeof(d)
295008
>>> for i in range(10900):
...     del d[i]
...
>>> len(d)
0
>>> sys.getsizeof(d)
295008
>>> for i in range(923):
...     d[i] = i
...
>>> sys.getsizeof(d)
36968


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.
msg314807 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2018-04-02 11:59
# 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):
- rand_access(size=20): 2.67 ms +- 0.01 ms -> 2.80 ms +- 0.04 ms: 1.05x slower (+5%)
- rand_access(size=10): 2.70 ms +- 0.03 ms -> 2.80 ms +- 0.04 ms: 1.04x slower (+4%)

Faster (1):
- rand_access(size=50): 2.76 ms +- 0.06 ms -> 2.74 ms +- 0.02 ms: 1.01x 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)
msg314977 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2018-04-05 11:11
@Mark.Shannon, @rhettinger How do you think this?
msg315351 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-04-16 06:14
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.
msg315380 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2018-04-17 06:53
New changeset 5fbc511f56688654a05b9eba23d140318bb9b2d5 by INADA Naoki in branch 'master':
bpo-33205: dict: Change GROWTH_RATE to `used*3` (GH-6350)
https://github.com/python/cpython/commit/5fbc511f56688654a05b9eba23d140318bb9b2d5
msg315409 - (view) Author: miss-islington (miss-islington) Date: 2018-04-17 17:17
New changeset 902bb62d5af21526b68892a1032c63aa86ded247 by Miss Islington (bot) in branch '3.7':
bpo-33205: dict: Change GROWTH_RATE to `used*3` (GH-6350)
https://github.com/python/cpython/commit/902bb62d5af21526b68892a1032c63aa86ded247
History
Date User Action Args
2018-04-17 17:22:53inada.naokisetresolution: fixed
2018-04-17 17:22:43inada.naokisetstatus: open -> closed
stage: patch review -> resolved
2018-04-17 17:17:28miss-islingtonsetnosy: + miss-islington
messages: + msg315409
2018-04-17 06:54:43miss-islingtonsetpull_requests: + pull_request6198
2018-04-17 06:53:37inada.naokisetmessages: + msg315380
2018-04-16 06:14:27serhiy.storchakasetmessages: + msg315351
2018-04-05 11:11:02inada.naokisetmessages: + msg314977
2018-04-02 16:00:28inada.naokisetkeywords: + patch
stage: patch review
pull_requests: + pull_request6060
2018-04-02 14:24:24serhiy.storchakasetnosy: + serhiy.storchaka
2018-04-02 11:59:24inada.naokisetfiles: + dict_rand.py

messages: + msg314807
2018-04-02 11:56:14inada.naokilinkissue32623 dependencies
2018-04-02 11:55:51inada.naokicreate