Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement functools.lru_cache() using ordered dict #72426

Closed
serhiy-storchaka opened this issue Sep 21, 2016 · 6 comments
Closed

Implement functools.lru_cache() using ordered dict #72426

serhiy-storchaka opened this issue Sep 21, 2016 · 6 comments
Assignees
Labels
3.7 (EOL) end of life extension-modules C modules in the Modules dir type-feature A feature request or enhancement

Comments

@serhiy-storchaka
Copy link
Member

BPO 28239
Nosy @rhettinger, @vstinner, @ezio-melotti, @methane, @ericsnowcurrently, @serhiy-storchaka
Files
  • lru_cache-get-del-set.patch
  • lru_cache-pop-set.patch
  • lru_cache-move_to_end.patch
  • lru_cache-get-del-set-2.patch
  • lru_cache-pop-set-2.patch
  • lru_cache-move_to_end-2.patch
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = 'https://github.com/rhettinger'
    closed_at = <Date 2016-09-22.06:34:35.418>
    created_at = <Date 2016-09-21.13:52:11.914>
    labels = ['extension-modules', 'type-feature', '3.7']
    title = 'Implement functools.lru_cache() using ordered dict'
    updated_at = <Date 2017-12-24.20:47:45.528>
    user = 'https://github.com/serhiy-storchaka'

    bugs.python.org fields:

    activity = <Date 2017-12-24.20:47:45.528>
    actor = 'serhiy.storchaka'
    assignee = 'rhettinger'
    closed = True
    closed_date = <Date 2016-09-22.06:34:35.418>
    closer = 'serhiy.storchaka'
    components = ['Extension Modules']
    creation = <Date 2016-09-21.13:52:11.914>
    creator = 'serhiy.storchaka'
    dependencies = []
    files = ['44777', '44778', '44779', '47350', '47351', '47352']
    hgrepos = []
    issue_num = 28239
    keywords = ['patch']
    message_count = 6.0
    messages = ['277141', '277152', '277169', '277195', '277205', '309017']
    nosy_count = 6.0
    nosy_names = ['rhettinger', 'vstinner', 'ezio.melotti', 'methane', 'eric.snow', 'serhiy.storchaka']
    pr_nums = []
    priority = 'low'
    resolution = 'rejected'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'enhancement'
    url = 'https://bugs.python.org/issue28239'
    versions = ['Python 3.7']

    @serhiy-storchaka
    Copy link
    Member Author

    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).

    @serhiy-storchaka serhiy-storchaka added 3.7 (EOL) end of life extension-modules C modules in the Modules dir type-feature A feature request or enhancement labels Sep 21, 2016
    @rhettinger rhettinger self-assigned this Sep 21, 2016
    @rhettinger
    Copy link
    Contributor

    The problem is that cache hits now create "holes" in the compact dict and trigger periodic compaction. In contrast, the existing code leaves dicts unchanged when there is a cache hit.

    I prefer the current code. Though it took a little more effort to implement, that work is already done and done well. The linked lists are cheap and have consistent, predictable performance. I also like that the current implementation is only loosely coupled with dictionaries and not tightly tied to the compact dict with its evolving implementation details.

    @serhiy-storchaka
    Copy link
    Member Author

    I consider this issue as lying on the way to using the orderable of dict in OrderedDict implementation (the latter is very desirable because current OrderedDict implementation can be easily broken by using plain dict API). The main difficulty of implementing OrderedDict is the move_to_end() method (especially move_to_end(False)).

    In additional, the problem of holes is occurred for any often modified dictionary. Using ordered dict in lru_cache() give as good stress test for optimizing dict updating and resizing code.

    I don't suggest to change lru_cach() implementation just now. But after long testing ordered dicts during the developing stage of 3.7 (or even 3.8) we can make a decision.

    @rhettinger
    Copy link
    Contributor

    I don't suggest to change lru_cach() implementation just now

    For now, I would like to have this closed. It doesn't make sense at the current juncture (with the compact being new, being in flux, and not having guaranteed ordering semantics).

    Also, we should have a strong preference for loose coupling and high cohesion. The lru cache code is principally about tracking recent and should maintain primary responsibility for the action, and the dictionary implementation should be primarily about a clean mapping implementation without having code baggage just for the lru).

    Besides that, there isn't much motivation for change. The existing code is very good (clear, fast, decoupled, cohensive, and doesn't have compaction issues for cache hits).

    @methane
    Copy link
    Member

    methane commented Sep 22, 2016

    FYI: Here is interesting article. doubly-linked list is more inefficient than most people think.
    http://alex.dzyoba.com/programming/dynamic-arrays.html

    @serhiy-storchaka
    Copy link
    Member Author

    Since this theme has been raised again in bpo-32422 and old patches no longer apply clearly I have updated patches and benchmark results on 64 bit.

    $ ./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: Mean +- std dev: 3.03 ms +- 0.02 ms
    get-del-set: Mean +- std dev: 5.73 ms +- 0.04 ms
    pop-set: Mean +- std dev: 4.63 ms +- 0.04 ms
    move_to_end: Mean +- std dev: 3.57 ms +- 0.06 ms

    $ ./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: Mean +- std dev: 6.65 ms +- 0.11 ms
    get-del-set: Mean +- std dev: 15.5 ms +- 0.1 ms
    pop-set: Mean +- std dev: 15.4 ms +- 0.1 ms
    move_to_end: Mean +- std dev: 15.5 ms +- 0.2 ms

    All patches cause significant slowdown (around 2.3x) in the case of many misses.

    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.7 (EOL) end of life extension-modules C modules in the Modules dir type-feature A feature request or enhancement
    Projects
    None yet
    Development

    No branches or pull requests

    3 participants