<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P074-cache-simulator/ | updated: 2026-10-14 -->

# 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.

EML-P project `projects/cache-simulator` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/cache-simulator` runs it and `eml project verify projects/cache-simulator` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: cache-eviction-policy (https://efficientnewlanguage.org/cases/249-cache-eviction-policy/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
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
```

Screen:

```text
== 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.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
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
```

Screen:

```text
== 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.
```

## Modules

### main.eml

```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 of main.eml:

```python
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 of caches.eml:

```python
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
```

## README

# P074 - Cache simulator

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 tables
- `caches.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).