[Python-Dev] A new dictionary implementation

[Mark Shannon]

Antoine Pitrou wrote:
> On Sun, 29 Jan 2012 09:56:11 -0500
> Benjamin Peterson <benjamin at python.org> wrote:
> 
>> 2012/1/29 Mark Shannon <mark at hotpy.org>:
>>> Hi,
>>>
>>> Now that issue 13703 has been largely settled,
>>> I want to propose my new dictionary implementation again.
>>> It is a little more polished than before.
>> If you're serious about changing the dictionary implementation, I
>> think you should write a PEP. It should explain the new dicts
>> advantages (and disadvantages?) and give comprehensive benchmark
>> numbers. Something along the lines of
>> http://www.python.org/dev/peps/pep-3128/ I should think.
> 
> "New dictionary implementation" is a misnomer here. Mark's patch merely
> allows to share the keys array between several dictionaries. The lookup
> algorithm remains exactly the same as far as I've read. It's actually
> much less invasive than e.g. Martin's AVL trees-for-hash-collisions
> proposal.
> 

Antoine is right. It is a reorganisation of the dict, plus a couple of 
changes to typeobject.c and object.c to ensure that instance 
dictionaries do indeed share keys arrays.
The lookup algorithm remains the same (it works well).

Cheers,
Mark