classification
Title: LRU class given as example in OrderedDict docs not work on pop
Type: Stage: resolved
Components: Documentation Versions: Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Dennis Sweeney, docs@python, eric.snow, maximeLeurent, miss-islington, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2021-07-30 16:22 by maximeLeurent, last changed 2021-08-02 18:38 by miss-islington. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 27536 merged rhettinger, 2021-08-02 00:42
PR 27566 merged miss-islington, 2021-08-02 18:16
PR 27567 merged miss-islington, 2021-08-02 18:16
Messages (9)
msg398571 - (view) Author: Maxime LEURENT (maximeLeurent) Date: 2021-07-30 16:22
Hello,

I try to use a dictionnary with limited size, and I use class LRU given in docs on OrderedDict.

Unfortunately this class is, somehow, not working on pop method.

I say somehow because if I do OrderedDict pop method by hand I don't get any Exception. I do not understand how LRU.__getitem__ is call after del, and why "value = super().__getitem__(key)" work, when "self.move_to_end(key)" don't

Code tested on python3.7 and python3.8:


from collections import OrderedDict

class LRU(OrderedDict):
    'Limit size, evicting the least recently looked-up key when full'

    def __init__(self, maxsize=128, *args, **kwds):
        self.maxsize = maxsize
        super().__init__(*args, **kwds)

    def __getitem__(self, key):
        value = super().__getitem__(key)
        self.move_to_end(key) #<=== Bug here
        return value

    def __setitem__(self, key, value):
        if key in self:
            self.move_to_end(key)
        super().__setitem__(key, value)
        if len(self) > self.maxsize:
            oldest = next(iter(self))
            del self[oldest]


d = LRU()
d["foo"] = "bar"
d.pop("foo") #<= KeyError on mode_to_send in LRU.__getitem__ method

#pop method by "hand"  
d["foo2"] = "bar"
if "foo2" in d :
    result = d["foo2"]
    del d["foo2"]
    print(result) #work fine
msg398604 - (view) Author: Dennis Sweeney (Dennis Sweeney) * (Python triager) Date: 2021-07-30 19:10
Related (regarding od.popitem()): https://bugs.python.org/issue27275
msg398630 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-07-31 04:33
I'm thinking that the current LRU() recipe should be changed to lru_cache() API using an OrderedDict internally rather than inheriting from it.   The current recipe was intended to be a sketch rather than a complete class; otherwise, methods like get() would also need to have been provided.

Also, the resolution of issue 27275 doesn't look correct.  The pop() method should not depend on the subclasses' __getitem__ method.   In this regard, the pure python code for OrderedDict is correct and matches what regular dictionary's do (overriding __getitem__ has no effect on other methods).  This leaves to the class "open for extension but closed for modification".  Most of our container classes follow this pattern unless specifically documented to the contrary (i.e. a framework pattern).
msg398703 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-08-01 14:57
Possible replacement recipes:

-- Implement as a class -----------------

class LRU:

    def __init__(self, func, maxsize=128):
        self.func = func
        self.d = OrderedDict()

    def __call__(self, *args):
        if args in self.d:
            value = self.d[args]
            self.d.move_to_end(args)
            return value
        value = self.func(*args)
        if len(self.d) >= self.maxsize:
            self.d.popitem(False)
        self.d[args] = value
        return value

-- Implement as a closure ---------------

def lru_cache(maxsize):
    def deco(func):
        d = OrderedDict()
        def inner(*args):
            if args in d:
                d.move_to_end(args)
                return d[args]
            answer = func(args)
            d[args] = answer
            if len(d) > maxsize:
                d.popitem(False)
            return answer
        return inner
    return deco
msg398716 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2021-08-01 17:19
I agree that composition is methodologically more correct than inheritance for implementing a variant of lru_cache(). But if you need lru_cache() why not use lru_cache() from the stdlib? I think that instead of showing a poor version of the lru_cache() decorator, it is better to show a tool which can be used for LRU caching. The key and the value should be evaluated externally. In other word, class LRU with methods __contains__(), __getitem__() and __setitem__() (or get() and set()). It should use composition.

Alternatively we can add a comment that it is just an example, and some methods (like pop()) can not work.
msg398723 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-08-02 00:48
> But if you need lru_cache() why not use lru_cache() 
> from the stdlib?

This gives a foundation for people who want to roll their own variants of the standard library lru_cache().  From here, people can experiment with pickle support, dynamic resizing, invalidation methods, max age parameters, other ways to construct a key, tests for total available memory, direct access to cache entries, or any of the other feature requests we've declined because they weren't appropriate for the standard library.

Also, it nicely shows-off the original motivating use case for move_to_end().
msg398792 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-08-02 18:15
New changeset 54f185b6d321a6354aef2b2886c766677f487ecb by Raymond Hettinger in branch 'main':
bpo-44782: Improve OrderedDict recipe for LRU cache variants (GH-27536)
https://github.com/python/cpython/commit/54f185b6d321a6354aef2b2886c766677f487ecb
msg398795 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-08-02 18:37
New changeset c50a672eebb16cf778d9a3b22b72d506c3f54ced by Miss Islington (bot) in branch '3.9':
bpo-44782: Improve OrderedDict recipe for LRU cache variants (GH-27536) (GH-27567)
https://github.com/python/cpython/commit/c50a672eebb16cf778d9a3b22b72d506c3f54ced
msg398796 - (view) Author: miss-islington (miss-islington) Date: 2021-08-02 18:38
New changeset c6e7c9860d5ac968c7a1073fdbfbd44e0e87f582 by Miss Islington (bot) in branch '3.10':
bpo-44782: Improve OrderedDict recipe for LRU cache variants (GH-27536)
https://github.com/python/cpython/commit/c6e7c9860d5ac968c7a1073fdbfbd44e0e87f582
History
Date User Action Args
2021-08-02 18:38:18miss-islingtonsetmessages: + msg398796
2021-08-02 18:37:45rhettingersetmessages: + msg398795
2021-08-02 18:30:49rhettingersetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2021-08-02 18:16:11miss-islingtonsetpull_requests: + pull_request26074
2021-08-02 18:16:05miss-islingtonsetnosy: + miss-islington
pull_requests: + pull_request26073
2021-08-02 18:15:53rhettingersetmessages: + msg398792
2021-08-02 00:48:48rhettingersetmessages: + msg398723
2021-08-02 00:42:29rhettingersetkeywords: + patch
stage: patch review
pull_requests: + pull_request26046
2021-08-01 17:19:51serhiy.storchakasetmessages: + msg398716
2021-08-01 14:57:27rhettingersetmessages: + msg398703
2021-07-31 04:37:00rhettingersetnosy: + eric.snow
2021-07-31 04:33:09rhettingersetnosy: + serhiy.storchaka
messages: + msg398630
2021-07-30 23:00:52rhettingersetassignee: docs@python -> rhettinger

nosy: + rhettinger
2021-07-30 19:10:45Dennis Sweeneysetnosy: + Dennis Sweeney
messages: + msg398604
2021-07-30 16:22:59maximeLeurentsettitle: LRU class given as example in OrderedDict example not work on pop -> LRU class given as example in OrderedDict docs not work on pop
2021-07-30 16:22:34maximeLeurentcreate