[issue32422] Make OrderedDict can be used for LRU from C

[INADA Naoki]

New submission from INADA Naoki <songofacandy at gmail.com>:

Currently, functools.lru_cache implement own doubly-linked list.

But it is inefficient than OrderedDict because each link node is GC object.
So it may eat more memory and take longer GC time.

I added two private C API for OrderedDict and make lru_cache use it.

* _PyODict_LRUGetItem(): Similar to PyDict_GetItemWithHash() + od.move_to_end(last=True).
* _PyODict_PopItem():  Similar to odict.popitem().

Why I didn't implement C version of move_to_end() is to reduce lookup.
 _PyODict_LRUGetItem(key) lookup key once while
od[key]; od.move_to_end(key) lookup key twice.

I'll benchmark it and report result here.

----------
components: Interpreter Core
messages: 308980
nosy: inada.naoki
priority: normal
severity: normal
status: open
title: Make OrderedDict can be used for LRU from C
versions: Python 3.7

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue32422>
_______________________________________