[Python-Dev] [RFC] Removing pure Python implementation of OrderedDict (original) (raw)

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:

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

Regards,

INADA Naoki <songofacandy at gmail.com>

More information about the Python-Dev mailing list