[Python-Dev] A C implementation of OrderedDict

[Eric Snow]

On Sun, Oct 20, 2013 at 9:56 PM, Raymond Hettinger
<raymond.hettinger at gmail.com> wrote:
> I'll look at this in more detail after I've finishing my review of the
> TransformDict,
> but my initial impression is that the original show stopper hasn't been
> overcome:
> http://bugs.python.org/issue10977
>
> The concrete dict API is very old and is widely used in C extensions
> outside the standard library.  AFAICT, there is no way to prevent that code
> from bypassing your code and breaking the internal invariants of the
> ordered dict (that breakage could be silent are muck up the ordering
> or could fail loudly with a segfault).

Just to be clear, the patch I have up is meant to provide a nearly
exact duplicate of OrderedDict in C, minus the "private"
implementation details.  The current OrderedDict already suffers from
the same problems you described, since it is also a dict subclass (as
you know :-).  Those would definitely become show stoppers, as you
said, but only once we tried to actually use OrderedDict in the
interpreter in places where we currently use dict (which is something
we should mostly avoid).  Are you otherwise concerned that a C
implementation would send the wrong message to extension module
authors or cause problems for C extension modules that use
OrderedDict, beyond any they face with the pure Python implementation?

Regardless, I concur that we would need to find a solution to the
existing concrete API situation if OrderedDict were to be used in the
intepreter as a drop-in replacement for current dicts.  The same would
apply for any case of subclassing one of the fundamental types (like
str, which came up in a recent issue related to the email module).  In
the meantime, however, a C implementation of OrderedDict would offer a
performance improvement for anyone that uses it.  Furthermore, for the
couple of proposals I have cooking that make use of OrderedDict, the
concrete API problem does not factor in all that much, but having a
builtin C implementation does.  I will admit that things would be
easier for one of ideas if I could just drop OrderedDict in, but
that's a rats nest I stared at at one point and then backed away
slowly. <wink>

Ultimately, I don't feel any urgency WRT a C implementation of
OrderedDict.  I simply wanted to make others aware of the possibility
in case it would be useful to them in 3.4.  Otherwise I am perfectly
comfortable with taking any time you feel is necessary.

>
> If we really want a C implementation, I think the choices boil down to:
>
> 1) living with the problem and writing defensive code so that the
>     ordered dictionary won't segfault when fed to existing external C code
>     and so that the ordered dict notices whether the parent dictionary has
>     different keys than those in the internal linked list.

no thanks!  Dealing with re-entrancy was quite enough. :)

>
> or 2) biting the bullet and accepting an API change where ordered dicts
> are no longer a subclass of real dicts.

I know a few people that would argue for this regardless.

-eric