[Python-Dev] [RFC] Removing pure Python implementation of OrderedDict

INADA Naoki songofacandy at gmail.com
Tue Sep 5 04:38:06 EDT 2017

Hi, all.

Currently, deque and defaultdict have only C implementation.
Python implementations should provide _collections.deque
and _collections.defaultdict.

Like that, how about removing OrderedDict Pure Python implementation
from stdlib and require it to implementation?

## Pros

### Thread safety

AFAIK, there are no thread safety guarantee in OrderedDict.
I don't look carefully, but some methods seems thread unsafe.

I'm considering adding `OrderedDict.lru_get(key, default=None)`  which
atomically lookup key and move the key to end if found.

It can be used when functools.lru_cahce can't be used.
(see http://bugs.python.org/issue28193 )
And thread safety is very important for such method.

Anyway, thread safety will improve usability of OrderedDict significantly,
like defaultdict.

### Less maintenance cost of test_ordered_dict.

I'm sending pull request for removing doubly linked list from C OrderedDict,
for faster creatin, iteration, and reduce memory usage by 1/2.
See https://bugs.python.org/issue31265

While implementing it, I noticed that current test_ordered_dict has some
tests about implementation detail without @cpython_only decorator.

For example:


While current test expects KeyError, my pull request (and PyPy's OrderedDict)
doesn't raise KeyError because inconsistency between doubly linked list
and dict never happens.

PyPy changed the test:

My pull request has same change:

Maintain compatibility with odd behavior of Pure Python implementation
is not constructive job not only for us, but also other Python implementations.

### `import collections` bit faster.

Pure Python implementation has 5 classes (OrderedDict, _Link,
_OrderedDictKeyViews, _OrderedDictItemsView, and _OrderedDictValuesView).

Three of them inheriting from ABC.  So it makes importing collections
bit slower.

## Cons

* All Python 3.7 implementations should provide _collections.OrderedDict
  PyPy has it already.  But I don't know about micropython.


INADA Naoki  <songofacandy at gmail.com>

More information about the Python-Dev mailing list