Speedup empty dict creation and reduce its memory usage

@tim-one

BPO	30040
Nosy	@tim-one, @rhettinger, @terryjreedy, @vstinner, @bitdancer, @methane, @markshannon, @serhiy-storchaka, @MojoVampire, @zhangyangyu, @mlouielu
PRs	bpo-30040: New empty dict uses key-sharing dict. #1080 bpo-30040: optimize inserting into empty dict #12307 bpo-30040: remove shared empty key #12308 bpo-30040: update news entry #12324 bpo-38525: Fix segfault when using reverse iterators of empty dict literals #16847

^{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 = <Date 2019-03-18.11:46:24.978>
created_at = <Date 2017-04-11.09:39:20.110>
labels = ['interpreter-core', '3.8', 'performance']
title = 'Speedup empty dict creation and reduce its memory usage'
updated_at = <Date 2019-10-19.15:00:56.151>
user = 'https://github.com/methane'

bugs.python.org fields:

activity = <Date 2019-10-19.15:00:56.151>
actor = 'pablogsal'
assignee = 'none'
closed = True
closed_date = <Date 2019-03-18.11:46:24.978>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2017-04-11.09:39:20.110>
creator = 'methane'
dependencies = []
files = []
hgrepos = []
issue_num = 30040
keywords = ['patch']
message_count = 34.0
messages = ['291470', '291471', '291477', '291481', '291482', '291483', '291485', '291489', '291494', '291506', '291507', '291521', '291683', '291776', '291777', '291791', '291817', '337726', '337751', '337766', '337778', '337791', '337794', '337797', '337800', '337812', '337816', '337849', '337900', '337902', '337908', '337969', '338196', '338202']
nosy_count = 11.0
nosy_names = ['tim.peters', 'rhettinger', 'terry.reedy', 'vstinner', 'r.david.murray', 'methane', 'Mark.Shannon', 'serhiy.storchaka', 'josh.r', 'xiang.zhang', 'louielu']
pr_nums = ['1080', '12307', '12308', '12324', '16847']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue30040'
versions = ['Python 3.8']

dict.clear() make the dict to empty key-sharing dict to reduce it's size.
New dict can use same technique.

$ ./python.default 
Python 3.7.0a0 (heads/master:6dfcc81, Apr 10 2017, 19:55:52) 
[GCC 6.2.0 20161005] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> d = {}
>>> sys.getsizeof(d)
240
>>> d.clear()
>>> sys.getsizeof(d)
72

$ ./python.patched 
Python 3.7.0a0 (heads/master-dirty:6dfcc81, Apr 11 2017, 18:11:02) 
[GCC 6.2.0 20161005] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof({})
72

performance impact

best case:
$ ./python.patched -m perf timeit --compare-to=pwd/python.default -- '{}'
python.default: ..................... 36.9 ns +- 0.9 ns
python.patched: ..................... 25.3 ns +- 0.7 ns
Mean +- std dev: [python.default] 36.9 ns +- 0.9 ns -> [python.patched] 25.3 ns +- 0.7 ns: 1.46x faster (-31%)

worst case:
$ ./python.patched -m perf timeit --compare-to=pwd/python.default -- 'x={}; x["a"]=1'
python.default: ..................... 73.3 ns +- 1.2 ns
python.patched: ..................... 82.8 ns +- 1.8 ns
Mean +- std dev: [python.default] 73.3 ns +- 1.2 ns -> [python.patched] 82.8 ns +- 1.8 ns: 1.13x slower (+13%)

Isn't the latter case the more common one? Creating an empty dict and then populate it.

Isn't the latter case the more common one? Creating an empty dict and then populate it.

This is memory usage optimization, not performance optimization.
(But I think memory efficiency makes multi process application faster because L3 cache size is limited resource.)
Later case shows how performance penalty is large.

macro bench result:

$ ./python.default -m perf compare_to -G --min-speed=1 default.json patched.json
Slower (11):
- scimark_lu: 362 ms +- 13 ms -> 383 ms +- 22 ms: 1.06x slower (+6%)
- unpickle_pure_python: 882 us +- 18 us -> 924 us +- 18 us: 1.05x slower (+5%)
- regex_v8: 45.4 ms +- 0.6 ms -> 46.7 ms +- 3.1 ms: 1.03x slower (+3%)
- mako: 40.4 ms +- 0.4 ms -> 41.4 ms +- 0.4 ms: 1.03x slower (+3%)
- meteor_contest: 200 ms +- 1 ms -> 204 ms +- 2 ms: 1.02x slower (+2%)
- genshi_text: 88.8 ms +- 1.2 ms -> 90.1 ms +- 1.6 ms: 1.01x slower (+1%)
- scimark_monte_carlo: 255 ms +- 6 ms -> 258 ms +- 7 ms: 1.01x slower (+1%)
- richards: 176 ms +- 4 ms -> 178 ms +- 8 ms: 1.01x slower (+1%)
- pickle: 24.2 us +- 0.5 us -> 24.4 us +- 0.7 us: 1.01x slower (+1%)
- sympy_str: 438 ms +- 3 ms -> 442 ms +- 3 ms: 1.01x slower (+1%)
- genshi_xml: 196 ms +- 3 ms -> 198 ms +- 2 ms: 1.01x slower (+1%)

Faster (7):

logging_silent: 746 ns +- 12 ns -> 722 ns +- 11 ns: 1.03x faster (-3%)
xml_etree_generate: 272 ms +- 4 ms -> 264 ms +- 4 ms: 1.03x faster (-3%)
telco: 20.7 ms +- 0.7 ms -> 20.2 ms +- 0.4 ms: 1.02x faster (-2%)
xml_etree_parse: 311 ms +- 13 ms -> 305 ms +- 12 ms: 1.02x faster (-2%)
nqueens: 266 ms +- 4 ms -> 262 ms +- 2 ms: 1.02x faster (-2%)
unpack_sequence: 123 ns +- 1 ns -> 122 ns +- 2 ns: 1.01x faster (-1%)
raytrace: 1.27 sec +- 0.01 sec -> 1.25 sec +- 0.01 sec: 1.01x faster (-1%)

Benchmark hidden because not significant (46)

I mean creating a solo empty dict doesn't seem to make much sense. Although it saves memory, but when it's populated, it's resized and the memory occupation comes back.

And this makes PyDict_New() hard to understand. :-(

Use "--duplicate 100" when making microbenchmarks for such fast operations. The overhead of iterating can be significant and comparable with the time of the operation.

While I think it's preferable that {} and d.clear() have same memory footprint,
I need real world example which empty dict affects overall memory usage.

I'll check memory usage difference with application I used in this ML thread.
https://mail.python.org/pipermail/python-dev/2017-January/147194.html

I've worked on an application (proprietary, unfortunately) that created a lot of empty dictionaries that only sometimes got populated. It involved sqlalchemy, but I don't remember if the dicts came from sqlalchemy itself or from the code that used it. That application did care about memory, and the shared-key dicts were a big benefit to it.

Thank you for your reply.
Would you try to check how the patch [1] affects memory usage of your application?
I think the patch can be applied to 3.6 easily.

[1] https://patch-diff.githubusercontent.com/raw/python/cpython/pull/1080.patch

Sorry, but I no longer have access to that application (I'm a consultant, and the owner is no longer a client).

I mean creating a solo empty dict doesn't seem to make much sense. Although it saves memory, but when it's populated, it's resized and the memory occupation comes back.

But sometimes it's not populated.

class A:
    def __init__(self, **kwargs):
        self._extra = kwargs

xa = [A() for _ in range(1000)]

So problem is (a) how many empty dicts, and (b) how much memory this patch saves.

And this makes PyDict_New() hard to understand. :-(

Yes, but it is not new complexity because it's same to d.clear().

Hmm, while 2x faster temporal empty dict is nice,
10% slower case can be mitigated.
I will try more micro benchmarks and optimizations.

I hate to see you working so hard to make this work. IMO, the effort is futile. Dicts were intentionally designed to do a single memory allocation and memset(0) to be fully ready to store data. This PR is undoing that decision and will make Python worse rather than better. The PR is optimizing for the wrong thing. The space used by empty dicts is something we care much less about than the cost of the first assignment.

No "mitigations" are going to help. If there is a second malloc and we incur the cost of switching from sharing-to-non-sharing, that is additional work that will have be done by every single dictionary that actually gets used. Nothing will get that lost work back.

FWIW, if we were going to optimize for space used by empty dicts, the table pointer could just be set to NULL. That would be better than key sharing which is not only slower but also conceptually wrong (outside the context of instance creation, dicts will never be shared).

For the record, legitimate case when many empty dicts are
created, and few are populated, is the collections-free
approach to defaultdict(dict):

While it is helpful to know that there is some possible application that would benefit, we don't optimize for the rare case, we optimize for the common case where dicts get used. A substantial fraction of the language is implemented using dicts. For the most part, we use NULL values when the dict isn't actually needed; so, the normal case is that dicts do get used.

In general, I agree with Raymond that this is likely to counter-productive.

But let's not guess, let's measure :)

I expect that there are few live empty dicts at any time for most programs. In which case there is no point in any change that attempts to save memory use for empty dicts.

But I could be wrong. If there commonly are lots of live empty dicts,
then some sort of optimisation could be appropriate.

I should also add that dict.clear() uses a key-sharing dict to avoid allocation, because PyDict_Clear() is a void function so there is no way to handle an allocation failure.

Serhiy, for {'a': None} the dict is created using _PyDict_NewPresized() so this makes no difference.

Some of my thoughts on this.

Conceptually, I expected that clearing a normal dict should make it an empty normal dict. I presume that making it instead an empty shared key dict is a matter of efficiency and code simplicity. If the 'anomaly' is to be corrected, changing .clear would be an alternative.

The fact that this patch 'rescues' people who use .setdefault when collections.defaultdict would be better does not especially persuade me (msg291817). The dict method doc and docstring could refer to defaultdict for such situations.

In 3.8.0a2, empty sets, like empty dicts, are ready to add. Empty lists in a2 are *not*, so pre-allocation is not universal in CPython for mutable collections.

On Wed, Mar 13, 2019 at 4:46 AM Raymond Hettinger
<[email protected]> wrote:

Raymond Hettinger <[email protected]> added the comment:

I hate to see you working so hard to make this work. IMO, the effort is futile. Dicts were intentionally designed to do a single memory allocation and memset(0) to be fully ready to store data. This PR is undoing that decision and will make Python worse rather than better.

Please that this PR is not do it. From Python 3.6, dict uses two
allocations. No embedded small table.
This PR just move 2nd allocation from dict creation to first insertion.

I created two PRs. PR 12307 just optimize inserting to empty dict.
PR 12308 has same optimization and removes shared empty key (ma_keys = NULL).

I confirmed PR 12307 is faster than before about d = {}; d["a"]=None.
I'll benchmark them later.

Benchmark result is here.

https://github.com/methane/sandbox/tree/master/2019.01/empty-dict

notes:

Overhead introduced by PR 1080 (https://bugs.python.org/issue30040#msg337778) is cancelled by first insert optimization. It is now faster than before.
PR 12307 (first insert optimization) is about 2x faster on creating & destroy empty dict. Other performance diff is small.
PR 12308 (use keys=NULL instead of shared empty keys) is more faster than PR 12307 on some cases, while it requires much if (md->ma_keys == NULL) checks.

I do not like how much code is needed for such minor optimization.

New changeset 3fe7fa3 by Inada Naoki in branch 'master':
bpo-30040: update news entry (GH-12324)
3fe7fa3

I do not like how much code is needed for such minor optimization.

PR 12307 is +46 lines. Benefit is about 10ns when first insertion.

$ cpython/python.opt -m perf timeit --compare-to master/python.opt --python-names master:empty-dict2 --duplicate 100 'd={};d["a"]=1'
master: ..................... 62.6 ns +- 1.1 ns
empty-dict2: ..................... 52.5 ns +- 1.0 ns

Mean +- std dev: [master] 62.6 ns +- 1.1 ns -> [empty-dict2] 52.5 ns +- 1.0 ns: 1.19x faster (-16%)

While "1.19x faster" is significant, I agree that this optimization is "minor".
_PyDict_NewPresized() is used for important cases. So this optimization doesn't work in most case.

But I came up with an idea. _PyDict_NewPresized(n) skips preallocation when n fit in minsize table.
93906f1

With this idea, "first insertion optimization" works. Additionally, it may help branch prediction
for while (newsize < minsize) { newsize <<= 1 } loop.

Total diff is still +46 lines. But it affects more cases.

$ alias compare='cpython/python.opt -m perf timeit --compare-to master/python.opt --python-names master:empty-dict2'

$ compare -s 'def f(x, **kw): pass' --duplicate 10 -- 'f(4)'  # No table
Mean +- std dev: [master] 65.4 ns +- 2.3 ns -> [empty-dict2] 64.5 ns +- 1.5 ns: 1.01x faster (-1%)

$ compare -s 'def f(x, **kw): pass' --duplicate 10 -- 'f(4, a=1)'  # minsize table is allocated
Mean +- std dev: [master] 152 ns +- 3 ns -> [empty-dict2] 144 ns +- 4 ns: 1.05x faster (-5%)

$ compare -s 'def f(x, **kw): pass' --duplicate 10 -- 'f(4, a=1,b=2)'
Mean +- std dev: [master] 211 ns +- 3 ns -> [empty-dict2] 186 ns +- 3 ns: 1.13x faster (-12%)

$ compare -s 'def f(x, **kw): pass' --duplicate 10 -- 'f(4, a=1,b=2,c=3)'
Mean +- std dev: [master] 248 ns +- 3 ns -> [empty-dict2] 223 ns +- 3 ns: 1.11x faster (-10%)

$ compare -s 'def f(x, **kw): pass' --duplicate 10 -- 'f(4, a=1,b=2,c=3,d=4,e=5)'
Mean +- std dev: [master] 327 ns +- 6 ns -> [empty-dict2] 301 ns +- 6 ns: 1.09x faster (-8%)

$ compare -s 'def f(x, **kw): pass' --duplicate 10 -- 'f(4, a=1,b=2,c=3,d=4,e=5,f=6)'  # minsize*2 table is allocated
Mean +- std dev: [master] 431 ns +- 8 ns -> [empty-dict2] 406 ns +- 8 ns: 1.06x faster (-6%)

Now I think PR 12307 is not so minor. Of course, same idea can be applied to PR 12308.

New changeset 2ddc7f6 by Inada Naoki in branch 'master':
bpo-30040: optimize inserting into empty dict (GH-12307)
2ddc7f6

I merged PR-12307 instead of PR-12308 because:

PR-12308 adds much code, it makes difficult to maintain dict (I faced many SEGV while creating PR-12308)
PR-12308 is based on PR-12307. So they are not mutually exclusive.

And I close this issue because there are no more drawbacks about first insertion.
If you really hate ma_keys == Py_EMPTY_KEYS and prefer ma_keys == NULL to it, please reopen this issue and PR 12308. I won't remove empty-dict3 branch for a while.

Navigation Menu

Repository navigation

Speedup empty dict creation and reduce its memory usage #74226

14 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Speedup empty dict creation and reduce its memory usage #74226

Description

Activity

methane commented on Apr 11, 2017

methane commented on Apr 11, 2017

zhangyangyu commented on Apr 11, 2017

methane commented on Apr 11, 2017

methane commented on Apr 11, 2017

zhangyangyu commented on Apr 11, 2017

serhiy-storchaka commented on Apr 11, 2017

methane commented on Apr 11, 2017

bitdancer commented on Apr 11, 2017

methane commented on Apr 11, 2017

bitdancer commented on Apr 11, 2017

methane commented on Apr 12, 2017

14 remaining items

rhettinger commented on Mar 12, 2019

markshannon commented on Mar 12, 2019

markshannon commented on Mar 12, 2019

terryjreedy commented on Mar 12, 2019

methane commented on Mar 12, 2019

methane commented on Mar 13, 2019

methane commented on Mar 14, 2019

serhiy-storchaka commented on Mar 14, 2019

methane commented on Mar 14, 2019

methane commented on Mar 15, 2019

methane commented on Mar 18, 2019

methane commented on Mar 18, 2019

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions