Python dictionary and set memory allocation

user_94077 0
Viewed 1496

I found this excellent resource discussing memory usage of python dictionaries and sets, specifically:

By default, the smallest size of a dictionary or set is 8 (that is, if you are only storying 3 values, python will still allocate 8 elements). On resize, the number of buckets increases by 4x until we reach 50,000 elements, after which the size is increased by 2x. This gives the following possible sizes,

16, 64, 256, 1024, 4096, 16384, 65536, 131072, 262144, ...

It is important to note that resizing can happen to make a hash table larger OR smaller. That is, if sufficiently many elements of a hash table are deleted, the table can be scaled down in size. This is because the consideration for the table being 2/3rds full uses the total of inserted and deleted entries since the last resize. However, resizing only happens during an insert.

But this was published in September 2014 and thus likely written some time before that. Is this still accurate and relevant in the latest versions of Python? (3.6+)

memory memory-management python-3.x python
1 Answers

In CPython this is no longer true. This specific part of the dictionary implementation has changed a couple of times since what was written there was the case. The comment starting on this line right above the definition of GROWTH_FACTOR gives a little history.

/* GROWTH_RATE. Growth rate upon hitting maximum load.
 * Currently set to used*3.
 * This means that dicts double in size when growing without deletions,
 * but have more head room when the number of deletions is on a par with the
 * number of insertions.  See also bpo-17563 and bpo-33205.
 *
 * GROWTH_RATE was set to used*4 up to version 3.2.
 * GROWTH_RATE was set to used*2 in version 3.3.0
 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
 */

The information provided in the book had been out of date for about two years at the time it was published.

user_77377810
Related