How to make Python dictionary shrink?

Question

I have experienced this in other languages. Now I have the same problem in Python. I have a dictionary in which there are many CRUD actions. It could be assumed that deleting elements from a dictionary should reduce its memory size. This is not true. When a dictionary grows in size (usually doubles), it never (?) Frees the allocated memory back. I conducted this experiment:

import random import sys import uuid a= {} for i in range(0, 100000): a[uuid.uuid4()] = uuid.uuid4() if i % 1000 == 0: print sys.getsizeof(a) for i in range(0, 100000): e = random.choice(a.keys()) del a[e] if i % 1000 == 0: print sys.getsizeof(a) print len(a) 

The last line of the first cycle is 6291736 . The last line of the second cycle is 6291736 . And the dictionary size is 0 .

So how to solve this problem? Is there a way to force free memory?

PS: no need to do random actions - I played with the range of the second cycle.

Answer 1

The way to do this is “replay”, so it uses less memory to create a new dictionary and copy the contents.

The implementation of the Python dictionary is very well explained in this video:

https://youtu.be/C4Kc8xzcA68

There is an attendee asking the same question ( https://youtu.be/C4Kc8xzcA68?t=1593 ), and the answer that the speaker gives:

Resizing is done only upon insertion; since the dictionary is compressed, it just gets a lot of dummy entries, and as it is filled, it just starts reusing these keys to store the keys. [...] you need to copy the keys and values ​​to the new dictionary

Answer 2

In fact, the dictionary may shrink when resizing, but resizing occurs only when the key is not deleted. Here's a comment from CPython source for dictresize :

Restructure the table by selecting a new table and entering all the items again. When records are deleted, the new table may actually be smaller than the old.

By the way, since another answer quoted Brandon Rhodes talks about the dictionary in PyCon 2010, and the quote seems to conflict with the above (which has been there for many years), I thought I would include the full quote, with the missing part in bold font.

Resizing is done only upon insertion. Since the dictionary is compressed, it just gets a lot of dummy entries, and when you replenish it, it will just start reusing these keys to store the keys. It will not change until you manage to make it two-thirds again filled in a larger size. So when changing the keys does not change. You have to do an insert to get it, it must understand that it has to cut.

Therefore, he says that the resize operation can "find out that [the dictionary] needs to be reduced." But this only happens when pasting. Apparently, when copying over all keys during resizing, dummy keys can be deleted, which reduces the size of the support array.

However, it is unclear how to do this, so Rhodes says to simply copy everything into a new dictionary.