3
\$\begingroup\$

I wrote this code, in order to implement a cache decorator which handles least accessed eviction.

The role of this decorator is to memoize decorated functions calls with args and kwargs and return the previously computed value if still in cache.

Warning, this handles only serializable args and kwargs, for the sake of simplicity.

Please review it and tell me if this makes sense.

The code:

import json
import hashlib
from collections import OrderedDict


class EvictionCache(OrderedDict):

    def __init__(self, *args, **kwargs):
        max_size = kwargs.pop('max_size', None)
        super(EvictionCache, self).__init__(*args, **kwargs)
        self._max_size = max_size

    @property
    def full(self):
        return len(self) >= self._max_size

    def set(self, hash, value):
        if self.full:
            self.evict()
        super(EvictionCache, self).__setitem__(hash, value)

    def get(self, hash):
        value = super(EvictionCache, self).pop(hash, None)
        if value:
            super(EvictionCache, self).__setitem__(hash, value)
        return value

    def evict(self):
        print 'evicting oldest cached item'
        super(EvictionCache, self).popitem(last=False)


def cache(max_size=None):

    def make_md5(args, kwargs):
        data = dict(args=args, kwargs=kwargs)
        md5 = hashlib.md5(json.dumps(data, sort_keys=True)).hexdigest()
        return md5

    def wrapper(f):
        # make this cache belong to the decorated function to prevent the cache
        # to be shared between different decorated functions
        f._cache = EvictionCache(max_size=max_size)

        def inner(*args, **kwargs):
            md5 = make_md5(args, kwargs)
            res = f._cache.get(md5)
            if res:
                print 'from cache'
                return res

            res = f(*args, **kwargs)
            print 'to cache'
            f._cache.set(md5, res)

            return res

        return inner
    return wrapper


@cache(max_size=2)
def func(x):
    return x * 2


if __name__ == '__main__':

    print func(1)
    print func(2)
    print func(2)
    print func(1)
    print func(2)
    print func(3)
    print func(4)
    print func(5)

output

to cache
2
to cache
4
from cache
4
from cache
2
from cache
4
to cache
evicting oldest cached item
6
to cache
evicting oldest cached item
8
to cache
evicting oldest cached item
10
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

I don't really feel subclassing a built-in data structure and defining your custom get() and set() methods is a good idea. One of the downsides of the current implementation is that if I would do self.cache[key] = value - this will not go through the cache's set() method and, hence, will not go through the "eviction" check at all. If you are subclassing a dictionary or an ordered dictionary, properly define the __getitem__() and __setitem__() magic methods instead of writing your custom get() and set() on top of it.

Also check this implementation that has a simpler wrapper, but uses a "proxy" "cached function" helper class.

And, here is the source code of the Python's functools.lru_cache for the reference.

Some other minor notes:

  • use print() as a function for Python-3.x compatibility
\$\endgroup\$
4
  • \$\begingroup\$ Thanks, I agree with your points, but, in my defense, this subclass is only meant to be used by the decorator and only this way. I had initially defined custom getitem and setitem but refactored them to get / set, to match most existing caches implementations. I'll definitely have a look at what you shared. Thanks again! \$\endgroup\$
    – DevLounge
    Commented Mar 16, 2017 at 19:06
  • \$\begingroup\$ @Apero sure, you have valid reasons. I'd then may be would not subclass OrderedDict and have an ordered dict as an internal attribute of a regular EvictionCache class inherited from object. Would probably be a bit cleaner. You've probably noticed I've tried to come up with something cleaner for the "cached function" part, but decided to remove it from the answer - was not sure if my version was better. I'm also not sure about the need to use md5 and json dump..probably having repr((args, kwargs)) as a key would be good enough, what do you think?..Thanks. \$\endgroup\$
    – alecxe
    Commented Mar 16, 2017 at 19:10
  • \$\begingroup\$ Damn it, I didn't even know functools had and lru cache implementation. I just started coding my own. Also, yes, the internal attribute instead of sublcassing would be cleaner. Great review! \$\endgroup\$
    – DevLounge
    Commented Mar 16, 2017 at 19:13
  • \$\begingroup\$ The boltons distribution's cacheutils module also had an LRU class, along with several decorators for caching, in case the funcutils implementation doesn't do everything you want. \$\endgroup\$
    – Wil Cooley
    Commented Mar 18, 2017 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.