Circular graphs of collections.OrderedDict are uncollectable due to the presence of OrderedDict.__del__.

>>> from collections import OrderedDict
>>> import gc
>>> left, right = OrderedDict(), OrderedDict()
>>> left['other'] = right
>>> right['other'] = left
>>> assert not gc.garbage
>>> del left, right
>>> gc.collect()
10
>>> assert not gc.garbage
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError

Not an issue in 3.1.1, have not verified with 3.1.2.

This is an unfortunate aspect of using __del__.
I don't see a way around it without reintroducing
weak references.

Of course, your code can also use weak ref proxies
to avoid creating uncollectible circular garbage.

I find the behavior surprising compared to dict and other containers, where this is not an issue and weakrefs are not required in user code.  I would not be surprised, however, to have to wait for a gc.collect() to clean up my cycles like I do for regular objects.

For what it's worth, the pure-python alternative linked in the docs uses neither __del__ nor weakrefs, though it is undoubtably less efficient than this implementation.  And the workaround 'del OrderedDict.__del__' seems to work as well, if one is willing to wait for a gc collection.

On #python-dev, Raymond, Amaury and Benjamin agreed that __del__ should be removed, with the rationale that this method should be used to release resources other than memory.

Éric, I've got this one.  Thx.

For 2.7, removed __del__ in r84725.
For 3.2, replaced __del__ with weakrefs in r84727.