Wed, 16 Jul 2008

Python dictionary optimizations

In my recent journey through the book Beautiful Code, I came across a chapter devoted to Python's dictionary implementation. I found the whole thing quite facinating, due to the sheer simplicity and power of the design. The author mentions various special-case optimizations that the Python developers cater for in the CPython dictionary implementation, which I think are valuable to share.

Key lookups
In CPython, all PyDictObject's are optimized for dictionaries containing only string keys. This seems like a very common use case that is definitely worth catering for. The key lookup function pointer looks like this:

struct PyDictObject {
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);

ma_lookup is initially set to the lookdict_string function (renamed to lookdict_unicode in 3.0), which assumes that both the keys in the dictionary and the key being searched for are standard PyStringObject's. It is then able to make a couple of optimiziations, such as mitigating various error checks, since string-to-string comparison never raise exceptions. There is also no need for rich object comparisons either, which means we avoid calling PyObject_RichCompareBool, and always use _PyString_Eq directly.

This string-optimized key lookup function is utilized until you search for a non-string key. When lookdict_string detects this, it permanently changes the ma_lookup function to a slower, more generic lookdict function. Here is an example of how to trigger this degradation:

>>> d = {'foo': 'bar'}
>>> d.get(1) # Congratulations, your dictionary is now slower...
>>> d.get(u'foo') # Yes, even unicode objects trigger this degradation as well

Jython does not contain this optimization, however, it does have a string-specialized map object, org.python.core.PyStringMap, which is used for the __dict__ underpinning of all class instances and modules. User code that creates a dictionary utilizes a different class, org.python.core.PyDictionary, which is a heavyweight object that uses the java.util.Hashtable along with some extra indirection, allowing it to be subclassed.

Small dictionaries
Python's dictionary makes an effort to never be more than 2/3rds full. Since the default size of dict is 8, this allows you to have 5 active entries in your dict while avoiding an additional malloc. Dictionaries used for keyword arguments are usually within this limit, and thus are fairly efficient (along with the fact that they most likely come from a pool of cached unused dicts). This also can help improve cache locality. For example, the PyDictObject structure uses 124 bytes of space (on x86 w/gcc) and therefore can fit into two 64-byte cache lines.

So, the moral of the story: use dictionaries with string-only keys, and only look for string keys within them. If you can keep them small enough to avoid the extra malloc (<= 5), bonus. As expected, things get better in Python 3.0, as unicode keys will no longer slow your dictionary down.

posted at: 15:39 | link | Tags: , | 5 comments

Posted by Tambrey at Sun Jun 12 07:51:27 2011

Now that’s sbulte! Great to hear from you.

Posted by Rose at Sun Jun 12 09:44:50 2011

Great cmoomn sense here. Wish I’d thought of that.

Posted by fyezooytdlo at Sun Jun 12 16:16:34 2011

7X50kQ  ifepzgthklsl

Posted by MaurineDippy at Fri Jun 24 04:49:01 2011

oxazepam >:-PPP lexapro yetml

Posted by Mabrok at Fri Dec 5 13:13:30 2014

I noticed this too on #cherrypy. We had pelpoe new to python and new to CP adn TG in the channel asking smart questions and you could hear the  Ah ah' moments as they were enlightened.