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

[INADA Naoki]

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:

https://github.com/python/cpython/blob/fcd97d44382df520e39de477a5ec99dd89c3fda8/Lib/test/test_ordered_dict.py#L522-L530

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:
https://bitbucket.org/pypy/pypy/src/ac3e33369ba0aa14278a6a3e8f2add09590d358c/lib-python/3/test/test_ordered_dict.py?at=py3.6&fileviewer=file-view-default#test_ordered_dict.py-525:542

My pull request has same change:
https://github.com/methane/cpython/pull/9/files#diff-23c28e7fa52967682669d9059dc977ed


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.


Regards,

INADA Naoki  <songofacandy at gmail.com>