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

Related (regarding od.popitem()): https://bugs.python.org/issue27275

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

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

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.

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

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

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

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