[New-bugs-announce] [issue29961] More compact sets and frozensets created from sets

[Serhiy Storchaka]

New submission from Serhiy Storchaka:

For now new set and frozenset objects can allocate 2 times larger table than necessary when are created from set or dict. For example if the size n of the original set is the power of two, resulting set will allocate the table of 4*n rather that 2*n. Up to 20% of new sets use twice more memory than necessary.

Proposed patch makes set_merge() allocating the table of size n*5/3 instead of n*2. This is the minimal size necessary for inserting all elements with fill ration <=60%.

$ ./python -c 'N = 6000; from sys import getsizeof; s = [getsizeof(frozenset(set(range(n)))) for n in range(N)]; print( [(n, s[n]) for n in range(N) if not n or s[n] != s[n-1]] )'
Unpatched:  [(0, 112), (5, 240), (8, 368), (16, 624), (32, 1136), (64, 2160), (128, 4208), (256, 8304), (512, 16496), (1024, 32880), (2048, 65648), (4096, 131184)]
Patched:    [(0, 112), (5, 240), (9, 368), (19, 624), (38, 1136), (77, 2160), (153, 4208), (307, 8304), (614, 16496), (1229, 32880), (2457, 65648), (4915, 131184)]

----------
components: Interpreter Core
messages: 290980
nosy: inada.naoki, rhettinger, serhiy.storchaka
priority: normal
severity: normal
stage: patch review
status: open
title: More compact sets and frozensets created from sets
type: resource usage
versions: Python 3.7

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue29961>
_______________________________________