Note: This article is a stub. A more detailed analysis of different simple cache implementations will be published later. See the notes below for a rough summary.
The following is a simple cache implementation, which is suitable for relatively small caches (up to a few hundred items), and where it’s relatively costly to create or reload objects after a cache miss (e.g. a few milliseconds or more per object).
Simple cache implementation
class Cache:
def __init__(self, maxsize=100):
self.cache = {}
self.order = [] # least recently used first
self.maxsize = maxsize
def get(self, key):
item = self.cache[key] # KeyError if not present
self.order.remove(key)
self.order.append(key)
return item
def set(self, key, value):
if self.cache.has_key(key):
self.order.remove(key)
elif len(self.cache) >= self.maxsize:
# discard least recently used item
del self.cache[self.order.pop(0)]
self.cache[key] = value
self.order.append(key)
def size(self):
return len(self.cache)
Usage:
cache = Cache(100)
try:
item = cache.get(key)
except KeyError:
item = item_factory()
cache.set(key, item)
Note that this implementation uses an ordinary list to keep track of the access order, in order to be able to discard the least recently used items when the cache fills up. The list type isn’t really optimized for this purpose, but this approach is surprisingly efficient for smaller caches, especially when the cache accesses follow an 80/20 pattern.
Notes:
(100k accesses, 100 slots, 500 items, 10 ms object creation, 1k per object, integer keys) baseline: speed=1000s (0+1000) memory=0k memoization: speed=5.22s (0.22+5.00) memory=500k keep last: speed=989.86s (0.72+989.14) memory=1k clear all: speed=532.51s (0.55+531.96) memory=100k clear pop: speed=706.51s (0.76+705.75) memory=100k clear random: speed=400.61s (0.80+399.81) memory=100k clear lru: speed=317.05s (0.78+316.27) memory=100k alternative implementations: carlson: speed=320.22s (1.35+318.87) memory=100k http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/252524 prodromou: speed=343.61s (17.88+325.73) memory=100k http://freshmeat.net/projects/lrucache/ the carlson implementation uses a manually maintained double- linked list, which is O(1), but is slower than a list for small caches. the prodromou implementation uses a sorted heap of cache items, which turns out to be a lot slower.