Project P074
Cache simulator
One trace of requests through a small cache under LRU, FIFO, LFU and Belady's optimal rule: hits side by side, one rule step by step with every eviction, and hits as the cache grows - where FIFO can do worse with more room.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
One trace of requests through a small cache, under four rules for what to throw out when it is full. The hits are shown side by side, one rule step by step with every eviction, and the hits as the cache grows. It starts with the trace 1 2 3 4 1 2 5 1 2 3 4 5, where FIFO does worse with 4 places than with 3.
main.eml- the menu, reading traces and sizes, and the tablescaches.eml- the four rules, the simulation, and hits by cache size
How each part works:
- The four rules, as in the corpus case
cache-eviction-policy: - LRU throws out the key used longest ago; - FIFO throws out the key that came in first; - LFU throws out the key used least often since it came in, and of those the one used longest ago; - OPT throws out the key whose next request is furthest away, or that is never asked for again (Belady, 1966). It needs to know the future, so no real cache can follow it. But no rule can get more hits, which makes it the fair yardstick. - As the cache grows, LRU and OPT never lose a hit: what a smaller cache holds, a bigger one under the same rule holds too. FIFO has no such guarantee, and on the starting trace it gets 3 hits with 3 places and 2 with 4 - Belady's anomaly.
- None of the rules is best everywhere. On a loop slightly longer than the cache, LRU throws out exactly the key it needs next and hits nothing.
What is checked: menu choices 1 to 5; a cache of 1 to 8 places; the rule as LRU, FIFO, LFU or OPT; a trace of 1 to 40 names, each 1 to 6 letters or digits, separated by spaces. An empty answer cancels.
Sessions: sessions/basic.in gives: - the four rules with 3 places: OPT 5 hits, FIFO 3, LRU and LFU 2; - hits for sizes 1 to 6, with FIFO's anomaly at 4; - FIFO and OPT step by step with 3 places; - the trace A B C A B D A B C D E A with 2 places: no rule but OPT gets a hit.
sessions/bad-input.in gives: - menu choices 0 and x; - cache sizes 0, 9 and abc, then a cancel; - the rules lru and MRU, then a cancelled size; - traces with an 11-letter name, with a comma, and with 41 requests, then a cancel.
Built on the verified corpus case cache-eviction-policy (LRU, LFU and FIFO on one trace, against the optimal count that looks at the future).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Cache simulator ==
One trace of requests through a small cache: LRU, FIFO, LFU and Belady's optimal OPT.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 0
Pick a number from 1 to 5.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> x
Pick a number from 1 to 5.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 1
cache size (1 to 8)> 0
Type a whole number from 1 to 8.
cache size (1 to 8)> 9
Type a whole number from 1 to 8.
cache size (1 to 8)> abc
Type a whole number from 1 to 8.
cache size (1 to 8)>
Cancelled.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 2
rule (LRU, FIFO, LFU or OPT)> lru
Type LRU, FIFO, LFU or OPT.
rule (LRU, FIFO, LFU or OPT)> MRU
Type LRU, FIFO, LFU or OPT.
rule (LRU, FIFO, LFU or OPT)> LRU
cache size (1 to 8)>
Cancelled.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 4
requests, separated by spaces> A B toolongname
Type 1 to 40 names of letters or digits, up to 6 each.
requests, separated by spaces> A,B
Type 1 to 40 names of letters or digits, up to 6 each.
requests, separated by spaces> k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k
Type 1 to 40 names of letters or digits, up to 6 each.
requests, separated by spaces>
Cancelled.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 5
Bye.
What was typed (18 lines)
0
x
1
0
9
abc
2
lru
MRU
LRU
4
A B toolongname
A,B
k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k
5
basic
interpreter: byte-equal== Cache simulator ==
One trace of requests through a small cache: LRU, FIFO, LFU and Belady's optimal OPT.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 1
cache size (1 to 8)> 3
12 requests, cache of 3:
LRU 2 hits 16.7%
FIFO 3 hits 25.0%
LFU 2 hits 16.7%
OPT 5 hits 41.7% the most any rule can get
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 3
hits for cache sizes 1 to 6:
size 1 2 3 4 5 6
LRU 0 0 2 4 7 7
FIFO 0 0 3 2 7 7
FIFO gets fewer hits with 4 places than with 3 - Belady's anomaly.
LFU 0 0 2 4 7 7
OPT 0 3 5 6 7 7
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 2
rule (LRU, FIFO, LFU or OPT)> FIFO
cache size (1 to 8)> 3
time request result evicted cache after
1 1 miss 1
2 2 miss 1 2
3 3 miss 1 2 3
4 4 miss 1 2 3 4
5 1 miss 2 3 4 1
6 2 miss 3 4 1 2
7 5 miss 4 1 2 5
8 1 hit 1 2 5
9 2 hit 1 2 5
10 3 miss 1 2 5 3
11 4 miss 2 5 3 4
12 5 hit 5 3 4
FIFO: 3 hits out of 12.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 2
rule (LRU, FIFO, LFU or OPT)> OPT
cache size (1 to 8)> 3
time request result evicted cache after
1 1 miss 1
2 2 miss 1 2
3 3 miss 1 2 3
4 4 miss 3 1 2 4
5 1 hit 1 2 4
6 2 hit 1 2 4
7 5 miss 4 1 2 5
8 1 hit 1 2 5
9 2 hit 1 2 5
10 3 miss 1 2 5 3
11 4 miss 2 5 3 4
12 5 hit 5 3 4
OPT: 5 hits out of 12.
trace: 1 2 3 4 1 2 5 1 2 3 4 5
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 4
requests, separated by spaces> A B C A B D A B C D E A
A trace of 12 requests.
trace: A B C A B D A B C D E A
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 1
cache size (1 to 8)> 2
12 requests, cache of 2:
LRU 0 hits 0.0%
FIFO 0 hits 0.0%
LFU 0 hits 0.0%
OPT 3 hits 25.0% the most any rule can get
trace: A B C A B D A B C D E A
1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit
choice> 5
Bye.
What was typed (14 lines)
1
3
3
2
FIFO
3
2
OPT
3
4
A B C A B D A B C D E A
1
2
5
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P074 cache simulator: a trace of requests through a small cache under
# LRU, FIFO, LFU and Belady's optimal rule - hits side by side, one rule
# step by step, and hits as the cache grows, where FIFO can do worse with
# more room.
import caches
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def number(s):
if len(s) == 0 or len(s) > 2:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def pad(s, n):
while len(s) < n:
s + " " => s
return s
def lpad(s, n):
while len(s) < n:
" " + s => s
return s
def words(s):
[] => out
"" => w
for c in s + " ":
if c == " ":
if w != "":
out + [w] => out
"" => w
else:
w + c => w
return out
def good_key(w):
if len(w) == 0 or len(w) > 6:
return False
for c in w:
if not ((c >= "a" and c <= "z") or (c >= "A" and c <= "Z") or (c >= "0" and c <= "9")):
return False
return True
def joined(xs):
"" => s
for x in xs:
if s != "":
s + " " => s
s + x => s
return s
def percent(h, n):
# h / n as a percentage to one decimal, rounded half up.
(2000 * h + n) => a
2 * n => b
0 => q
while a >= b:
a - b => a
q + 1 => q
0 => whole
q => r
while r >= 10:
r - 10 => r
whole + 1 => whole
return str(whole) + "." + str(r) + "%"
def ask_size():
while True:
trim(input("cache size (1 to 8)> ")) => s
if s == "":
return -1
number(s) => n
if n >= 1 and n <= 8:
return n
"Type a whole number from 1 to 8." ^0
def ask_policy():
while True:
trim(input("rule (LRU, FIFO, LFU or OPT)> ")) => s
if s == "":
return ""
if s == "LRU" or s == "FIFO" or s == "LFU" or s == "OPT":
return s
"Type LRU, FIFO, LFU or OPT." ^0
def compare(trace):
ask_size() => size
if size == -1:
"Cancelled." ^0
return
(str(len(trace)) + " requests, cache of " + str(size) + ":") ^0
caches.run(trace, size, "OPT")[0] => best
for p in ["LRU", "FIFO", "LFU", "OPT"]:
caches.run(trace, size, p)[0] => h
"" => note
if p == "OPT":
" the most any rule can get" => note
elif h == best:
" as good as OPT here" => note
(" " + pad(p, 5) + lpad(str(h), 3) + " hits " + lpad(percent(h, len(trace)), 6) + note) ^0
def step_by_step(trace):
ask_policy() => p
if p == "":
"Cancelled." ^0
return
ask_size() => size
if size == -1:
"Cancelled." ^0
return
caches.run(trace, size, p) => r
" time request result evicted cache after" ^0
for t in [0:len(trace) - 1]:
r[1][t] => st
"miss" => res
if st[1]:
"hit" => res
(" " + lpad(str(t + 1), 4) + " " + pad(st[0], 7) + " " + pad(res, 6) + " " + pad(st[2], 7) + " " + joined(st[3])) ^0
(p + ": " + str(r[0]) + " hits out of " + str(len(trace)) + ".") ^0
def growing(trace):
"hits for cache sizes 1 to 6:" ^0
" size 1 2 3 4 5 6" ^0
for p in ["LRU", "FIFO", "LFU", "OPT"]:
caches.hits_by_size(trace, p, 6) => hs
"" => line
for h in hs:
line + lpad(str(h), 4) => line
(" " + pad(p, 5) + line) ^0
for k in [1:5]:
if hs[k] < hs[k - 1]:
(" " + p + " gets fewer hits with " + str(k + 1) + " places than with " + str(k) + " - Belady's anomaly.") ^0
def new_trace(trace):
while True:
trim(input("requests, separated by spaces> ")) => s
if s == "":
"Cancelled." ^0
return trace
words(s) => ws
True => ok
for w in ws:
if not good_key(w):
False => ok
if ok and len(ws) >= 1 and len(ws) <= 40:
("A trace of " + str(len(ws)) + " requests.") ^0
return ws
"Type 1 to 40 names of letters or digits, up to 6 each." ^0
["1", "2", "3", "4", "1", "2", "5", "1", "2", "3", "4", "5"] => trace
"== Cache simulator ==" ^0
"One trace of requests through a small cache: LRU, FIFO, LFU and Belady's optimal OPT." ^0
True => running
while running:
"" ^0
("trace: " + joined(trace)) ^0
"1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
compare(trace)
elif choice == "2":
step_by_step(trace)
elif choice == "3":
growing(trace)
elif choice == "4":
new_trace(trace) => trace
elif choice == "5":
False => running
else:
"Pick a number from 1 to 5." ^0
"Bye." ^0
Python projection (main.py)
import caches
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def number(s):
if len(s) == 0 or len(s) > 2:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def pad(s, n):
while len(s) < n:
s = s + " "
return s
def lpad(s, n):
while len(s) < n:
s = " " + s
return s
def words(s):
out = []
w = ""
for c in s + " ":
if c == " ":
if w != "":
out = out + [w]
w = ""
else:
w = w + c
return out
def good_key(w):
if len(w) == 0 or len(w) > 6:
return False
for c in w:
if not (c >= "a" and c <= "z" or c >= "A" and c <= "Z" or c >= "0" and c <= "9"):
return False
return True
def joined(xs):
s = ""
for x in xs:
if s != "":
s = s + " "
s = s + x
return s
def percent(h, n):
a = 2000 * h + n
b = 2 * n
q = 0
while a >= b:
a = a - b
q = q + 1
whole = 0
r = q
while r >= 10:
r = r - 10
whole = whole + 1
return str(whole) + "." + str(r) + "%"
def ask_size():
while True:
s = trim(input("cache size (1 to 8)> "))
if s == "":
return -1
n = number(s)
if n >= 1 and n <= 8:
return n
print("Type a whole number from 1 to 8.")
def ask_policy():
while True:
s = trim(input("rule (LRU, FIFO, LFU or OPT)> "))
if s == "":
return ""
if s == "LRU" or s == "FIFO" or s == "LFU" or s == "OPT":
return s
print("Type LRU, FIFO, LFU or OPT.")
def compare(trace):
size = ask_size()
if size == -1:
print("Cancelled.")
return
print(str(len(trace)) + " requests, cache of " + str(size) + ":")
best = caches.run(trace, size, "OPT")[0]
for p in ["LRU", "FIFO", "LFU", "OPT"]:
h = caches.run(trace, size, p)[0]
note = ""
if p == "OPT":
note = " the most any rule can get"
elif h == best:
note = " as good as OPT here"
print(" " + pad(p, 5) + lpad(str(h), 3) + " hits " + lpad(percent(h, len(trace)), 6) + note)
def step_by_step(trace):
p = ask_policy()
if p == "":
print("Cancelled.")
return
size = ask_size()
if size == -1:
print("Cancelled.")
return
r = caches.run(trace, size, p)
print(" time request result evicted cache after")
for t in range(0, len(trace)):
st = r[1][t]
res = "miss"
if st[1]:
res = "hit"
print(" " + lpad(str(t + 1), 4) + " " + pad(st[0], 7) + " " + pad(res, 6) + " " + pad(st[2], 7) + " " + joined(st[3]))
print(p + ": " + str(r[0]) + " hits out of " + str(len(trace)) + ".")
def growing(trace):
print("hits for cache sizes 1 to 6:")
print(" size 1 2 3 4 5 6")
for p in ["LRU", "FIFO", "LFU", "OPT"]:
hs = caches.hits_by_size(trace, p, 6)
line = ""
for h in hs:
line = line + lpad(str(h), 4)
print(" " + pad(p, 5) + line)
for k in range(1, 6):
if hs[k] < hs[k - 1]:
print(" " + p + " gets fewer hits with " + str(k + 1) + " places than with " + str(k) + " - Belady's anomaly.")
def new_trace(trace):
while True:
s = trim(input("requests, separated by spaces> "))
if s == "":
print("Cancelled.")
return trace
ws = words(s)
ok = True
for w in ws:
if not good_key(w):
ok = False
if ok and len(ws) >= 1 and len(ws) <= 40:
print("A trace of " + str(len(ws)) + " requests.")
return ws
print("Type 1 to 40 names of letters or digits, up to 6 each.")
trace = ["1", "2", "3", "4", "1", "2", "5", "1", "2", "3", "4", "5"]
print("== Cache simulator ==")
print("One trace of requests through a small cache: LRU, FIFO, LFU and Belady's optimal OPT.")
running = True
while running:
print("")
print("trace: " + joined(trace))
print("1) compare 2) step by step 3) as the cache grows 4) new trace 5) quit")
choice = trim(input("choice> "))
if choice == "1":
compare(trace)
elif choice == "2":
step_by_step(trace)
elif choice == "3":
growing(trace)
elif choice == "4":
trace = new_trace(trace)
elif choice == "5":
running = False
else:
print("Pick a number from 1 to 5.")
print("Bye.")
caches.eml
eml# P074 cache simulator - one trace of requests through a cache of a given
# size under four rules for what to throw out when it is full, as in the
# corpus case cache-eviction-policy:
# LRU the key used longest ago
# FIFO the key that came in first
# LFU the key used least often since it came in (ties: longest ago)
# OPT the key whose next use is furthest away, or never (Belady 1966) -
# it needs to know the future, so no real cache can do it, but
# nothing can do better, which makes it the fair yardstick.
def next_use(trace, key, t):
# The time key is next asked for after time t, or len(trace) if never.
t + 1 => k
while k < len(trace):
if trace[k] == key:
return k
k + 1 => k
return len(trace)
def victim(cache, policy, trace, t, last, came, uses):
# Which key in the cache to evict at time t.
cache[0] => best
for key in cache:
if policy == "LRU":
if last[key] < last[best]:
key => best
elif policy == "FIFO":
if came[key] < came[best]:
key => best
elif policy == "LFU":
if uses[key] < uses[best] or (uses[key] == uses[best] and last[key] < last[best]):
key => best
else:
if next_use(trace, key, t) > next_use(trace, best, t):
key => best
return best
def run(trace, size, policy):
# [hits, steps] where each step is [request, hit, evicted ("" if
# none), the cache after it, in the order keys came in].
[] => cache
{} => last
{} => came
{} => uses
0 => hits
[0] * len(trace) => steps
for t in [0:len(trace) - 1]:
trace[t] => key
"" => out
False => hit
for c in cache:
if c == key:
True => hit
if hit:
hits + 1 => hits
uses[key] + 1 => uses[key]
else:
if len(cache) == size:
victim(cache, policy, trace, t, last, came, uses) => out
[] => kept
for c in cache:
if c != out:
kept + [c] => kept
kept => cache
cache + [key] => cache
t => came[key]
1 => uses[key]
t => last[key]
[key, hit, out, cache] => steps[t]
return [hits, steps]
def hits_by_size(trace, policy, most):
# Hits for every cache size from 1 to most.
[0] * most => out
for s in [1:most]:
run(trace, s, policy)[0] => out[s - 1]
return out
Python projection (caches.py)
def next_use(trace, key, t):
k = t + 1
while k < len(trace):
if trace[k] == key:
return k
k = k + 1
return len(trace)
def victim(cache, policy, trace, t, last, came, uses):
best = cache[0]
for key in cache:
if policy == "LRU":
if last[key] < last[best]:
best = key
elif policy == "FIFO":
if came[key] < came[best]:
best = key
elif policy == "LFU":
if uses[key] < uses[best] or uses[key] == uses[best] and last[key] < last[best]:
best = key
elif next_use(trace, key, t) > next_use(trace, best, t):
best = key
return best
def run(trace, size, policy):
cache = []
last = {}
came = {}
uses = {}
hits = 0
steps = [0] * len(trace)
for t in range(0, len(trace)):
key = trace[t]
out = ""
hit = False
for c in cache:
if c == key:
hit = True
if hit:
hits = hits + 1
uses[key] = uses[key] + 1
else:
if len(cache) == size:
out = victim(cache, policy, trace, t, last, came, uses)
kept = []
for c in cache:
if c != out:
kept = kept + [c]
cache = kept
cache = cache + [key]
came[key] = t
uses[key] = 1
last[key] = t
steps[t] = [key, hit, out, cache]
return [hits, steps]
def hits_by_size(trace, policy, most):
out = [0] * most
for s in range(1, most+1):
out[s - 1] = run(trace, s, policy)[0]
return out