[Python-Dev] A new dict for Xmas?

[Mark Shannon]

Martin v. Löwis wrote:
>> The current dict implementation is getting pretty old,
>> isn't it time we had a new one (for xmas)?
> 
> I like the approach, and I think something should be done indeed.
> If you don't contribute your approach, I'd like to drop at least
> ma_smalltable for 3.3.
> 
> A number of things about your branch came to my mind:
> - it would be useful to have a specialized representation for
>   all-keys-are-strings. In that case, me_hash could be dropped
>   from the representation. You would get savings compared to
>   the status quo even in the non-shared case.
It might tricky switching key tables and I dont think it would save much 
memory as keys that are widely shared take up very little memory anyway,
and not many other dicts are long-lived.

(It might improve performance for dicts used for keyword arguments)

> - why does _dictkeys need to be a full-blown Python object?
>   We need refcounting and the size, but not the type slot.
It doesn't. It's just a hangover from my original HotPy implementation 
where all objects needed a type for the GC.
So yes, the type slot could be removed.

> - I wonder whether the shared keys could be computed at compile
>   time, considering all attribute names that get assigned for
>   self. The compiler could list those in the code object, and
>   class creation could iterate over all methods (taking base
>   classes into account).
> 

It probably wouldn't be that hard to make a guess at compile time as to 
what the shared keys would be, but it doesn't really matter.
The generation of intermediate shared keys will only happen once per 
class, so the overhead would be negligible.

To cut down on that overhead, we could use a ref-count trick: If the 
instance being updating and its class hold the only two refs to an 
immutable keys(-set -table -vector?) then just treat it as mutable.

I'll modify the repo to incorporate these changes when I have a chance.

Cheers,
Mark.