[Python] How are small sets stored in memory?

If we look at the resize behavior for sets under 50k elements:

>>> import sys
>>> s = set()
>>> seen = {}
>>> for i in range(50_000):
... size = sys.getsizeof(s)
... if size not in seen:
... seen[size] = len(s)
... print(f"{size=} {len(s)=}")
... s.add(i)
...
size=216 len(s)=0
size=728 len(s)=5
size=2264 len(s)=19
size=8408 len(s)=77
size=32984 len(s)=307
size=131288 len(s)=1229
size=524504 len(s)=4915
size=2097368 len(s)=19661


This pattern is consistent with quadrupling of the backing storage size once the set is 3/5ths full, plus some presumably constant overhead for the PySetObject:

>>> for i in range(9, 22, 2):
... print(2**i + 216)
...
728
2264
8408
32984
131288
524504
2097368


A similar pattern continues even for larger sets, but the resize factor switches to doubling instead of quadrupling.

The reported size for small sets is an outlier. Instead of size 344 bytes, i.e. 16 * 8 + 216 (the storage array of a newly created empty set has 8 slots avail until the first resize up to 32 slots) only 216 bytes is reported by sys.getsizeof.

What am I missing? How are those small sets stored so that they use only 216 bytes instead of 344?

Continue reading...