[Python-Dev] Add LRUCache class to stdlib

Nadeem Vawda nadeem.vawda at gmail.com
Mon Jun 6 08:06:36 CEST 2011


I would like to propose adding a class to the stdlib to provide a more flexible
LRU caching mechanism. As things stand, the functools.lru_cache() decorator is
fine for memoization of pure functions, but does not accommodate situations
where cache entries become stale and must be invalidated/updated (e.g.
filecmp.cmp(); cf. issue #11802).

I was thinking it would be a good idea to factor out the the replacement code
into a separate class that could then be reused by code for which the
lru_cache() decorator is not applicable. The implementation of lru_cache()
itself would also become considerably simpler.

Implementation:

    class LRUCache:
        """Least-recently-used cache class.

        See:  http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used

        """

        def __init__(self, maxsize):
            """Initialize an LRUCache.

            If *maxsize* is None, the LRU replacement mechanism is disabled,
            and the cache can grow without bound.

            """
            if maxsize is None:
                self.cache = dict()
            else:
                self.cache = OrderedDict()
            self.lock = Lock()
            self.hits = self.misses = 0
            self.maxsize = maxsize

        def __getitem__(self, key):
            with self.lock:
                try:
                    value = self.cache[key]
                except KeyError:
                    self.misses += 1
                    raise
                else:
                    self.hits += 1
                    if self.maxsize is not None:
                        self.cache.move_to_end(key)
                    return value

        def __setitem__(self, key, value):
            with self.lock:
                self.cache[key] = value
                if self.maxsize is not None and len(self.cache) > self.maxsize:
                    self.cache.popitem(0)

        def info(self):
            """Report cache statistics"""
            with self.lock:
                return _CacheInfo(self.hits, self.misses,
                                  self.maxsize, len(self.cache))

I'm not sure where this class should go; it would be convenient to just stick
it in functools along with lru_cache(), but perhaps the collections package
would be more appropriate?

Cheers,
Nadeem


More information about the Python-Dev mailing list