[Python-Dev] More compact dictionaries with faster iteration

[Christian Heimes]

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