Message277141
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). |
|
Date |
User |
Action |
Args |
2016-09-21 13:52:12 | serhiy.storchaka | set | recipients:
+ serhiy.storchaka, rhettinger, vstinner, methane, eric.snow |
2016-09-21 13:52:11 | serhiy.storchaka | set | messageid: <1474465931.98.0.374027560088.issue28239@psf.upfronthosting.co.za> |
2016-09-21 13:52:11 | serhiy.storchaka | link | issue28239 messages |
2016-09-21 13:52:11 | serhiy.storchaka | create | |
|