AlgoVerse

Caching policies (LRU, FIFO, furthest-in-future)

Three caches of the same size serve one request sequence and their misses are compared; furthest-in-future is optimal but has to know the future.

A cache is small and fast and holds only k items. A request for an item not in it is a miss: the item must be brought in, and if the cache is full, one item has to go. Which one?

Read the full explanation ↓
Input:
R 1×12 · k=3PDF export

A cache of 3 and 12 requests; misses: LRU 10, FIFO 9 and the optimum 7.

  1. def caching(R, k):
  2. # Three caches of size k serve the same requests: LRU, FIFO and furthest-in-future (the offline optimum).
  3. reqs = R[0]
  4. lru = [] # least recently used first
  5. fifo = [] # oldest first
  6. opt = []
  7. hits = [0, 0, 0]
  8. misses = [0, 0, 0]
  9. rows = [] # for the picture: each request and the three caches after it
  10. for t in range(len(reqs)):
  11. x = reqs[t]
  12. if x in lru:
  13. hits[0] = hits[0] + 1
  14. lru.remove(x)
  15. lru.append(x)
  16. else:
  17. misses[0] = misses[0] + 1
  18. if len(lru) == k:
  19. y = lru.pop(0)
  20. lru.append(x)
  21. if x in fifo:
  22. hits[1] = hits[1] + 1
  23. else:
  24. misses[1] = misses[1] + 1
  25. if len(fifo) == k:
  26. y = fifo.pop(0)
  27. fifo.append(x)
  28. if x in opt:
  29. hits[2] = hits[2] + 1
  30. else:
  31. misses[2] = misses[2] + 1
  32. if len(opt) == k:
  33. y = furthest(reqs, t, opt)
  34. opt.remove(y)
  35. opt.append(x)
  36. rows.append([x, list(lru), list(fifo), list(opt)])
  37. return misses
  40. def furthest(reqs, t, cache):
  41. # The cached item whose next request is furthest away (or never comes).
  42. best = cache[0]
  43. best_next = -1
  44. for y in cache:
  45. nxt = len(reqs)
  46. for s in range(len(reqs) - 1, t, -1):
  47. if reqs[s] == y:
  48. nxt = s
  49. if nxt > best_next:
  50. best = y
  51. best_next = nxt
  52. return best

Invariant: At every point, furthest-in-future has had no more misses than any other policy.

Start

x—
hits—
misses—

The table is still empty.

Local variables

k3

Orange = changed in this step

R list

[1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]

Call stack

  1. caching()line 1
Step 1 of 385
Black = served · Orange = key steplru_miss: 0/10 · fifo_miss: 0/9 · opt_miss: 0/7 · served: 0/12 · lru_evict: 0/7 · fifo_evict: 0/6 · opt_evict: 0/4 · opt_hit: 0/5 · lru_hit: 0/2 · fifo_hit: 0/3
    Explanation

    The problem

    A cache is small and fast and holds only k items. A request for an item not in it is a miss: the item must be brought in, and if the cache is full, one item has to go. Which one?

    • LRU: the item whose last use is longest ago.
    • FIFO: the item that came in first.
    • Furthest-in-future (Belady): the item whose next request comes latest.

    Why furthest-in-future is optimal

    An exchange argument (the greedy-algorithms chapter of CLRS) shows that any optimal schedule can be turned, step by step, into this greedy choice without adding misses. But the policy is offline: it has to know the future.

    Online policies

    LRU and FIFO do not know the future. Both are k-competitive: their misses are at most about k times the optimum's, and no deterministic online algorithm can do better (CLRS chapter 27).

    The input

    R is the requests and k the cache size.