[Python-3000] Specializing the dicts in __dict__

[Guido van Rossum]

On 4/18/06, Jack Diederich <jack at performancedrivers.com> wrote:
> I mentioned then and would like to resurrect now the idea of making
> a dict-alike that has two extra properties:
>
>   1: the keys can only be str or unicode (py3k: just unicode)

This seems useful -- although the current dict type is already
optimized for keys consisting solely of strings (8-bit only) so I'm
skeptical about the obtainable speed-up.

>   2: the dict-alike is ordered

I've recently figured out what people mean by an "ordered dict" --
most people seem to agree that it's a dict that behaves like you
describe:

> The suggested order would be by key creation so that reassigning
> a key after manipulation would maintain the original order as in
> the Thing.b case above.

Unfortunately I don't think you can implement this without
significantly slowing things down. This belief is in part based on my
own prototype and the ordereddict implementations I found through a
bit of searching on Google; in part because if such an algorithm
existed (i.e. an ordered dict faster than hashing) it would be very
popular -- but I've never heard of one.

So I'm against making the class dict an ordereddict by default (but
I'd be for making it a symdict if we can implement one that's faster
than a plain dict). Instead, I'd focus on changing the way the class
statement works so that the metaclass can provide the dict object to
be used for the local namespace in the class body. The API might be
something like a class method on 'type' that takes some metadata like
the proposed class name and the tuple of base classes, and returns a
dict or a dict-ish object. The default implementation on 'type' could
ignore the arguments and return a fresh symdict instance (or a dict
instance if we find we can't implement a faster symdict).

In order to be useful for Py3k, the symdict should focus exclusively
on Unicode strings. However I'm not sure that we'll keep the current
Unicode implementation exactly. So perhaps it's too early to attempt
to produce one for Py3k -- but you could work the 'type' API details
and changes to the class statement easily.

PS: if this change to the class statement were to happen, the crowd
discussing the 'make' PEP (which I don't like but don't have the power
to stop being discussed) should take notice. Or perhaps they could run
with the idea and make it the focal point of their proposal. Or
whatever. :-)

--
--Guido van Rossum (home page: http://www.python.org/~guido/)