[Python-Dev] More compact dictionaries with faster iteration (original) (raw)

Christian Heimes christian at python.org
Mon Dec 10 08:48:02 CET 2012

Hello Raymond

Am 10.12.2012 02:44, schrieb Raymond Hettinger:

Another benefit is that resizing is faster and touches fewer pieces of memory. Currently, every hash/key/value entry is moved or copied during a resize. In the new layout, only the indices are updated. For the most part, the hash/key/value entries never move (except for an occasional swap to fill a hole left by a deletion).

With the reduced memory footprint, we can also expect better cache utilization.

On the other hand every lookup and collision checks needs an additional multiplication, addition and pointer dereferencing:

entry = entries_baseaddr + sizeof(PyDictKeyEntry) * idx

It's hard to predict how the extra CPU instructions are going to affect the performance on different CPUs and scenarios. My guts tell me that your proposal is going to perform better on modern CPUs with lots of L1 and L2 cache and in an average case scenario. A worst case scenario with lots of collisions might be measurable slower for large dicts and small CPU cache.

But this is pure speculation and my guts could be terrible wrong. :) I'm +1 to give it a shot.

Good luck! Christian

More information about the Python-Dev mailing list