Skip to content

Reduce lru_cache memory overhead. #76603

Closed
Closed
Reduce lru_cache memory overhead.#76603
Assignees
rhettinger
Labels
3.7 (EOL)end of lifeinterpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

Description

@methane
methane
opened on Dec 24, 2017
BPO 32422
Nosy @rhettinger, @methane, @serhiy-storchaka
PRs
  • bpo-32422: Reduce lru_cache memory usage. #5008
    		•
    Files
  • lru_bench.py
    		•

    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 2017-12-25.17:03:57.561>
created_at = <Date 2017-12-24.05:19:02.014>
labels = ['interpreter-core', '3.7', 'performance']
title = 'Reduce lru_cache memory overhead.'
updated_at = <Date 2017-12-25.17:03:57.561>
user = 'https://github.com/methane'

    bugs.python.org fields:

    activity = <Date 2017-12-25.17:03:57.561>
actor = 'methane'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2017-12-25.17:03:57.561>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2017-12-24.05:19:02.014>
creator = 'methane'
dependencies = []
files = ['47348']
hgrepos = []
issue_num = 32422
keywords = ['patch']
message_count = 13.0
messages = ['308980', '308981', '308985', '308986', '309003', '309006', '309007', '309013', '309016', '309029', '309031', '309032', '309039']
nosy_count = 3.0
nosy_names = ['rhettinger', 'methane', 'serhiy.storchaka']
pr_nums = ['5008']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue32422'
versions = ['Python 3.7']

    Activity

    1. methane commented on Dec 24, 2017

      @methane
      methane
      on Dec 24, 2017
      MemberAuthor

      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.

    2. methane
      added
      3.7 (EOL)end of life
      interpreter-core(Objects, Python, Grammar, and Parser dirs)
      on Dec 24, 2017

    3. methane commented on Dec 24, 2017

      @methane
      methane
      on Dec 24, 2017
      MemberAuthor

      Current implementation (no news entry yet):
      https://github.com/methane/cpython/pull/10/files

    4. serhiy-storchaka commented on Dec 24, 2017

      @serhiy-storchaka
      serhiy-storchaka
      on Dec 24, 2017
      Member

      This is a duplicate of bpo-28239.

    5. serhiy-storchaka
      closed this as completedon Dec 24, 2017

    6. serhiy-storchaka commented on Dec 24, 2017

      @serhiy-storchaka
      serhiy-storchaka
      on Dec 24, 2017
      Member

      Ah, sorry, you use OrderedDict instead of just ordered dict. It should have different timing and memory consumption.

    7. serhiy-storchaka
      reopened this on Dec 24, 2017

    8. methane commented on Dec 24, 2017

      @methane
      methane
      on Dec 24, 2017
      MemberAuthor

      Hmm, it seems my implementation is 30% slower when many mishit scenario.
      Maybe, dict is faster than OrderedDict about massive insert/discard. But I need to profile it.

      On the other hand, GC speed looks about 2x faster as expected.

      $ ./python -m perf compare_to master.json patched.json  -G
Slower (5):
- lru_1000_100: 217 ns +- 6 ns -> 302 ns +- 6 ns: 1.39x slower (+39%)
- lru_10000_1000: 225 ns +- 4 ns -> 309 ns +- 2 ns: 1.37x slower (+37%)
- lru_100_1000: 114 ns +- 5 ns -> 119 ns +- 1 ns: 1.05x slower (+5%)
- lru_100_100: 115 ns +- 6 ns -> 119 ns +- 1 ns: 1.03x slower (+3%)
- lru_1000_1000: 134 ns +- 6 ns -> 136 ns +- 1 ns: 1.02x slower (+2%)

      Faster (4):

      • gc(1000000): 98.3 ms +- 0.3 ms -> 37.9 ms +- 0.2 ms: 2.59x faster (-61%)
      • gc(100000): 11.7 ms +- 0.0 ms -> 5.10 ms +- 0.02 ms: 2.29x faster (-56%)
      • gc(10000): 1.48 ms +- 0.02 ms -> 1.04 ms +- 0.01 ms: 1.41x faster (-29%)
      • lru_10_100: 149 ns +- 6 ns -> 147 ns +- 2 ns: 1.02x faster (-2%)

    9. methane commented on Dec 24, 2017

      @methane
      methane
      on Dec 24, 2017
      MemberAuthor

      I found odict.pop() and odict.popitem() is very inefficient because
      it look up key multiple times.
      odict seems not optimized well and very slow than dict in some area...

      I'll try to optimize it in holidays.

    10. rhettinger commented on Dec 24, 2017

      @rhettinger
      rhettinger
      on Dec 24, 2017
      Contributor

      Please stop revising every single thing you look at. The traditional design of LRU caches used doubly linked lists for a reason. In particular, when there is a high hit rate, the links can be updated without churning the underlying dictionary.

    11. rhettinger commented on Dec 24, 2017

      @rhettinger
      rhettinger
      on Dec 24, 2017
      Contributor

      FWIW, I'm the original author and designer of this code, so it would have been appropriate to assign this to me for sign-off on any proposed changes.

    12. rhettinger
      self-assigned this
      on Dec 24, 2017

    13. serhiy-storchaka commented on Dec 24, 2017

      @serhiy-storchaka
      serhiy-storchaka
      on Dec 24, 2017
      Member

      FWIW, I'm the original author and designer of this code, so it would have
      been appropriate to assign this to me for sign-off on any proposed changes.

      Not me (the C implementation)? ;-)

    14. methane commented on Dec 25, 2017

      @methane
      methane
      on Dec 25, 2017
      MemberAuthor

      Please stop revising every single thing you look at. The traditional design of LRU caches used doubly linked lists for a reason. In particular, when there is a high hit rate, the links can be updated without churning the underlying dictionary.

      I don't proposing removing doubly linked list; OrderedDict uses
      doubly-linked list too, and I found no problem for most-hit scenario.

      On the other hand, I found problem of OrderedDict for most mis hit
      scenario.

      Now I think lru_cache's implementation is better OrderedDict.
      PyODict is slower than lru_cache's dict + linked list because of
      historical reason (compatibility with pure Python implemantation.)

      So I stop trying to remove lru_cache's own implementation.
      I'll try to reduce overhead of lru_cache, by removing GC header
      from link node.

    15. methane
      changed the title [-]Make OrderedDict can be used for LRU from C[/-] [+]Reduce lru_cache memory overhead.[/+] on Dec 25, 2017

    16. methane commented on Dec 25, 2017

      @methane
      methane
      on Dec 25, 2017
      MemberAuthor

      PR-5008 benchmark:

      $ ./python -m perf compare_to master.json patched2.json -G
Faster (9):
- gc(1000000): 98.3 ms +- 0.3 ms -> 29.9 ms +- 0.4 ms: 3.29x faster (-70%)
- gc(100000): 11.7 ms +- 0.0 ms -> 3.71 ms +- 0.03 ms: 3.14x faster (-68%)
- gc(10000): 1.48 ms +- 0.02 ms -> 940 us +- 6 us: 1.57x faster (-36%)
- lru_10_100: 149 ns +- 6 ns -> 138 ns +- 1 ns: 1.08x faster (-8%)
- lru_100_100: 115 ns +- 6 ns -> 108 ns +- 1 ns: 1.07x faster (-6%)
- lru_1000_1000: 134 ns +- 6 ns -> 127 ns +- 1 ns: 1.05x faster (-5%)
- lru_100_1000: 114 ns +- 5 ns -> 108 ns +- 1 ns: 1.05x faster (-5%)
- lru_1000_100: 217 ns +- 6 ns -> 212 ns +- 4 ns: 1.03x faster (-2%)
- lru_10000_1000: 225 ns +- 4 ns -> 221 ns +- 5 ns: 1.02x faster (-2%)

    17. serhiy-storchaka commented on Dec 25, 2017

      @serhiy-storchaka
      serhiy-storchaka
      on Dec 25, 2017
      Member

      LGTM.

    18. serhiy-storchaka
      added
      performancePerformance or resource usage
      on Dec 25, 2017

    19. methane commented on Dec 25, 2017

      @methane
      methane
      on Dec 25, 2017
      MemberAuthor

      New changeset 3070b71 by INADA Naoki in branch 'master':
      bpo-32422: Reduce lru_cache memory usage (GH-5008)
      3070b71

    20. methane
      closed this as completedon Dec 25, 2017
    21. ezio-melotti
      transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    3.7 (EOL)end of lifeinterpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions