How much space a Python dictionary entry uses
June 6, 2011
There are a number of built in Python types that have variable sized
instances, such as tuples, lists, and longs (or ints, in Python 3).
For some of these, there is a simple answer to how much space a given
instance will take up, based on how many items you put in an instance;
you can determine this from using
Dictionaries are not this simple, because like lists they do not simply add their entries on the end of their basic C level blob of data (well, it's a C structure). As a result a number of things affect the size of a particular dictionary, and in turn affect when adding entries will actually make the dictionary use more memory.
In the abstract, a dictionary entry is three pointers; one for the key, one for the value, and a third to store the value of the key's hash. On a 32-bit machine this makes it 12 bytes and on a 64-bit machine, 24 bytes. However, dictionaries do not add entries one by one; instead there are two complications.
First, the basic dictionary structure comes with enough room for up
to five entries. If you watch
Second, dictionaries enlarge (and shrink) in discontinuous jumps. Each dictionary has a table for entries, which is always a power of two in size and at most 2/3rds used; when you add an entry that would push the table over 2/3rds used, CPython enlarges the dictionary table instead. Dictionary tables that are not that large quadruple when they're resized; large tables merely double.
Let's put this in concrete terms. On a 64-bit machine with Python 2.7,
Note that all of this is of course implementation dependent, although
the CPython dictionary implementation has been refined enough that it
doesn't seem to change much. Python 3.1.2 reports the same numbers, for
example. The real lesson here is that
(Also note that size reported by
Written on 06 June 2011.
* * *