[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

New submission from Serhiy Storchaka:

Since dict became ordered, this feature can be used in functools.lru_cache() implementation instead of linked list. This significantly simplifies the code.

The first implementation just uses _PyDict_GetItem_KnownHash() + _PyDict_DelItem_KnownHash() + _PyDict_SetItem_KnownHash() for moving existent key-value pair to the end of the dict.

The second implementation adds replaces the first two calls with one call of newly added _PyDict_PopItem_KnownHash() (this is just simplified copy of _PyDict_PopItem()).

The third implementation merges all three operations in one function _PyDict_MoveToEnd_KnownHash() that returns moved value if it exists, NULL without an exception set if there is no such key in a dict, and NULL with an exception set in case of error. Maybe this implementation is can be more optimized.

Benchmarking hits:

$ ./python -m perf timeit -s "from functools import lru_cache; f = lru_cache(512)(lambda x: x); a = list(range(500))*100" -- "list(map(f, a))"

Unpatched:    Median +- std dev: 13.5 ms +- 0.8 ms
get-del-set:  Median +- std dev: 21.7 ms +- 0.8 ms
pop-set:      Median +- std dev: 17.0 ms +- 0.6 ms
move_to_end:  Median +- std dev: 13.7 ms +- 0.5 ms

Benchmarking misses:

$ ./python -m perf timeit -s "from functools import lru_cache; f = lru_cache(512)(lambda x: x); a = list(range(50000))" -- "list(map(f, a))

Unpatched:    Median +- std dev: 31.5 ms +- 1.8 ms
get-del-set:  Median +- std dev: 58.6 ms +- 1.0 ms
pop-set:      Median +- std dev: 59.7 ms +- 1.1 ms
move_to_end:  Median +- std dev: 99.0 ms +- 0.5 ms

The get-del-set implementation is simple and don't need adding new functions to PyDict API, but it is 60-90% slower the baseline linked-list-based implementation. The pop-set implementation is slightly faster for hits. The move_to_end implementation is as fast as the baseline implementation for hits, but is much slower in case of misses (I think it can be tuned).

----------
components: Extension Modules
files: lru_cache-get-del-set.patch
keywords: patch
messages: 277141
nosy: eric.snow, haypo, methane, rhettinger, serhiy.storchaka
priority: low
severity: normal
status: open
title: Implement functools.lru_cache() using ordered dict
type: enhancement
versions: Python 3.7
Added file: http://bugs.python.org/file44777/lru_cache-get-del-set.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue28239>
_______________________________________