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 <rep...@bugs.python.org> <http://bugs.python.org/issue28239> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
