How to apply a maximum cache size to memoize?

Question

I'm using this memoize decorator on a class and it is very effective. Now I'm ready to trade some of that speed for control over memory consumption. Ideally I'd be able to set a maximum; (eg: 2GB) but I guess I can trial and error a lot and settle for a maximum number of objects in the cache.

Anyone know of some ready-made code to do this? I guess I'd toss out the oldest in the cache to add the newest.

Or is there a more sensible way to do this?

Here's the routine I'm currently using:

def memoize(obj):
    """A decorator to cache advice objects using the advice key"""
    cache = obj.cache = {}

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        key = args[0]
        if key not in cache:
            cache[key] = obj(*args, **kwargs)
        return cache[key]

    return memoizer

Seems sensible to give the max as an arg to the decorator like:

@memoize(max=2000)
class Foo(object):
   ...

If your objects have different size, then it could be hard to estimate memory space consumed by your cache. If you cannot expect that object used last will be likely to be reused then the best strategy could be keeping first xxx objects in memory — Yevgen Yampolskiy, Sep 20 '12 at 03:29

score 8 · Accepted Answer · answered Sep 20 '12 at 04:25

If you're using Python 3.2, there's already a good caching decorator in the standard library:

import functools

@functools.lru_cache(maxsize=1000)
def fun(...):

Otherwise, I'd just have a look at the implementation of lru_cache. It's a good pure-Python general-purpose memoizer with LRU semantics (like the FIFO semantics you're using, but a bit more sophisticated) for better cache performance.

score 1 · Answer 2 · answered Sep 20 '12 at 03:20

If it were me I'd probably do something like this:

from collections import deque

def memoize(obj, maxlen = None):
    """A decorator to cache advice objects using the advice key"""
    cache = obj.cache = {}
    deck = obj.deck = deque([], maxlen = maxlen)

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        key = args[0]
        if key not in cache:
            if len(deck) == deck.maxlen:
              del cache[deck.popleft()[0]]
            temp = obj(*args, **kwargs)
            cache[key] = temp
            deck.append((key, temp))
        return cache[key]

    return memoizer

That ought to be close, but I wrote it in the editor here, not in a prompt. It may require some refinement.

How to apply a maximum cache size to memoize?

2 Answers2