Some answers are expensive to work out and are asked for again and again: the page a visitor has just looked at, the price of a journey somebody priced a minute ago, the result of a long calculation. A cache keeps recent answers so that the work is not done twice. Keeping them is the easy half. A cache has only so much room, and the interesting half is deciding what to throw away. This module builds a cache that forgets the right thing, and then measures how much work it saves.
Before this, you can: look things up in a dictionary and say what a missing key does; use a list as a stack and a deque as a queue; hand a function to another function, and count the work a loop does.
By the end you will be able to put a cache in front of a slow function, give it a limit, forget the oldest arrival, forget what has gone longest unused, keep keys in order of use, use a dictionary that remembers order, and measure a cache by its hit rate.
Before you read on, decide what this prints:
count = {"calls": 0}
def slow_square(n):
count["calls"] = count["calls"] + 1
return n * n
answers = {}
for n in [4, 7, 4, 4, 9, 7]:
if n not in answers:
answers[n] = slow_square(n)
print(count["calls"], len(answers))
3 3Six requests, and the slow function ran three times: once for each different number. The other three requests were answered from the dictionary. (The dictionary count is there only to count the calls. A function can change a dictionary it can see, as you learned in Build a Game.)
That dictionary is a cache. Every request goes to it first. If the key is there, the answer comes straight back: a hit. If it is not, the slow work is done, the answer is stored, and it is handed back: a miss.
def lookup(answers, n):
if n in answers:
return "hit"
answers[n] = n * n
return "miss"
answers = {}
print([lookup(answers, n) for n in [4, 7, 4, 4, 9, 7]])
['miss', 'miss', 'hit', 'hit', 'miss', 'hit']The first time any key is asked for is always a miss: there is nothing to remember yet. A cache earns its keep on the requests that repeat.
A cache is only right while the answer for a key does not change. The square of 4 is always 16. The price of a ticket may not be the same tomorrow, and a cache that goes on handing out yesterday's price is worse than no cache. That problem has a name, a stale entry, and one of the assignments is about it.
The dictionary above never forgets. Ask it for a million different numbers and it holds a million answers. A real cache has a capacity: a number of entries it may hold. When it is full and a new key arrives, something already there has to go. Removing an entry to make room is called eviction.
Which entry? The best one to evict is the one that will not be asked for again for the longest time. Nobody knows which that is. So a cache follows a rule that guesses, from what has happened so far, and different rules guess differently. The two that follow are the ones worth knowing first.
The simplest rule: evict whatever has been in the cache longest. The first in is the first out, which is a queue. Keep a deque of keys in the order they arrived.
from collections import deque
def fifo_put(cache, order, capacity, key, value):
if key in cache:
cache[key] = value
return
if len(cache) == capacity:
oldest = order.popleft()
del cache[oldest]
cache[key] = value
order.append(key)
cache = {}
order = deque()
for key in ["a", "b", "c", "a", "d"]:
fifo_put(cache, order, 3, key, key.upper())
print(key, list(order))
a ['a']
b ['a', 'b']
c ['a', 'b', 'c']
a ['a', 'b', 'c']
d ['b', 'c', 'd']del cache[oldest] removes a key and its value from a dictionary.
Look at the last two lines. a was stored again, so it was plainly still wanted. Then d arrived, the cache was full, and the rule evicted a, because a had arrived first. The rule looks only at when a key arrived. It takes no notice of whether the key has been used since.
A better guess: what was used a moment ago will probably be used again soon, and what has not been touched for a long time probably will not. So evict the key that has gone longest without being used. This rule is called least recently used.
Take the same requests, with room for three, and keep the keys in order of last use, the longest unused on the left:
| Request | Keys, longest unused first | What happened |
|---|---|---|
| a | a | stored |
| b | a b | stored |
| c | a b c | stored |
| a | b c a | used again: a moves to the right-hand end |
| d | c a d | full: b, the longest unused, is evicted |
Under the first rule the fourth request changed nothing and a was evicted. Here it moved a to the safe end, and b went instead.
Being used means more than being stored. A request that reads a key uses it too. Every hit moves its key to the recently-used end. That is the difference between the two rules, and it is the thing that is easiest to forget when writing one.
The cache needs two things: the answers, and the order of use. A dictionary holds the answers. For the order, start with what you know, a list of keys with the longest unused at position 0 and the most recently used at the end.
Two operations on that list do everything. When a key is used, take it out from wherever it is and put it at the end:
order = ["a", "b", "c"]
order.remove("a")
order.append("a")
print(order)
['b', 'c', 'a']When room is needed, the key to evict is at position 0:
order = ["b", "c", "a"]
evicted = order.pop(0)
print(evicted, order)
b ['c', 'a']With those two moves and a dictionary you can write the whole cache, and the lab asks you to.
It will work, and it has a cost you have met before. order.remove("a") first has to search the list for the key, from position 0 until it finds it, and then shift every key after it down one place to close the gap. A key near the front is found quickly and makes nearly the whole list shift. A key at the end is found only after the whole list has been searched, and shifts nothing. Either way one hit can cost as many steps as the cache has entries. order.pop(0) shifts every remaining key. For a cache of ten entries nobody will notice. For a cache of a hundred thousand, a hit can mean a hundred thousand steps of searching and shifting, and the cache that was meant to save work is doing a great deal of its own.
What is wanted is one structure that finds a key at once, as a dictionary does, and also keeps the keys in an order that can be changed cheaply. Python has it: OrderedDict.
from collections import OrderedDict
entries = OrderedDict()
entries["a"] = 1
entries["b"] = 2
entries["c"] = 3
entries.move_to_end("a")
print(list(entries))
['b', 'c', 'a']It is a dictionary: entries["a"], in, len and del all work. It also remembers the order of its keys. move_to_end(key) moves a key to the end without searching for it, and popitem(last=False) removes the first key and hands back the key and its value as a pair:
key, value = entries.popitem(last=False)
print(key, value, list(entries))
b 2 ['c', 'a']Giving an existing key a new value changes the value and leaves the key where it is in the order:
entries["c"] = 30
print(list(entries))
['c', 'a']So storing to a key that is already there is not, by itself, counted as a use. If your cache says it should be, your code has to move the key.
Why not reach for OrderedDict first? Because now you know what it is doing for you. It keeps exactly the order you kept in the list, and does the two moves without the shuffling. A tool is easier to use well when you have built the slow version of it once.
A cache is judged by one number: of all the requests, what fraction were hits? That is its hit rate.
def fifo_hit_rate(requests, capacity):
cache = {}
order = deque()
hits = 0
for key in requests:
if key in cache:
hits = hits + 1
else:
fifo_put(cache, order, capacity, key, True)
return hits / len(requests)
requests = ["a", "b", "a", "c", "a", "b", "d", "a"]
print(fifo_hit_rate(requests, 2), fifo_hit_rate(requests, 3))
0.125 0.375With room for two, one request in eight is a hit. With room for three, three in eight. More room usually helps, and the rule matters as much as the room: in this sequence a is asked for four times, and a rule that noticed would not let it go. The lab measures the second rule on the same requests.
The hit rate depends on the requests as much as on the cache. Requests that never repeat give a hit rate of 0 whatever you build. Requests that keep returning to a few favourites, as people do, reward a cache that holds on to the favourites. Before choosing a rule or a size, measure both on requests like the ones you expect.
You will trace hits and misses, watch the first rule evict a key that was just used, and work the second rule by hand. You will write a least-recently-used cache with a dictionary and a list, count what the list costs, and rewrite the cache on an OrderedDict. Then you will measure the two rules against each other and draw the result. Four assignments follow: a list of recent searches, a cache whose entries go stale, a cache with two mistakes to find, and a way to put your cache in front of any function.