What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Partitions and Tiers: the Same Slots, Arranged Differently”?
Answer: Then the Che column. The front-level hit ratios, 0.1931, 0.2613, 0.3450 and 0.4027, match a single cache of the same size exactly; this level is fine. The trouble lies at the back. The approximation for both levels together gives 0.4319, 0.4190, 0.4177 and 0.4309, systematically above the simulation, by about six points at the even split. The reason is that the front level's miss stream is not a stream of independent references. An object that has just missed the front is now in the front, so for a while its requests hit there and never reach the back. Requests reaching the back are thus spread out in time, with the requests for any one object pulled apart. Treating them as independent references, the Che approximation overstates the back level's chance to hit.
Scope of the numbers: Under Zipf requests the hit ratio of a least-recently-used (LRU) cache grows slowly with capacity: with illustrative parameters, a hundred-and-twenty-eight-fold increase in capacity raises the hit ratio only 6.80 times. Chapter 4 derives the optimal capacity from slope and cost, 4187 slots or 0.2094 of the catalogue under illustrative parameters, with a flat cost curve around the optimum.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.1931, 0.2613, 0.3450, 0.4027, 0.4177, 0.4190
| Two LRU levels with 2000 slots in all; one cache: 0.4483 | |||||
| C1 | C2 | Che L1 | Che L2 | Che all | sim all |
| 250 | 1750 | 0.1931 | 0.2388 | 0.4319 | 0.4277 |
| 500 | 1500 | 0.2613 | 0.1577 | 0.4190 | 0.3968 |
| 1000 | 1000 | 0.3450 | 0.0727 | 0.4177 | 0.3562 |
| 1500 | 500 | 0.4027 | 0.0281 | 0.4309 | 0.4048 |
Show the full program
# Chapter 6. p62: two LRU levels in tandem, the setting of Che (2002).
# Model: level 1 has C1 slots and sees all requests; its misses go to
# level 2 with C2 slots. Following Che, Tung and Wang, the miss stream
# of level 1 is treated as independent references with rates
# q_i = p_i (1 - h1_i); level 2 is solved by the same Che equation on
# q normalised. Overall hit = H1 + sum q_i h2_i. A single LRU of
# C1 + C2 slots is the yardstick. Seeded trace of 250000 Zipf requests
# (a = 0.8, N = 20000, illustrative), 50000 warm-up.
import math
import random
from collections import OrderedDict
N, A, L, WARM, TOTAL = 20000, 0.8, 250000, 50000, 2000
def zipf(n, a):
w = [1.0 / (i ** a) for i in range(1, n + 1)]
s = math.fsum(w)
return [x / s for x in w]
def occupancy(p, t):
return math.fsum(-math.expm1(-x * t) for x in p)
def che_t(p, c, tol=1e-9):
lo, hi = 0.0, 1.0
while occupancy(p, hi) < c:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if occupancy(p, mid) < c:
lo = mid
else:
hi = mid
return 0.5 * (lo + hi)
def che_two(p, c1, c2):
t1 = che_t(p, c1)
h1 = [-math.expm1(-x * t1) for x in p]
q = [x * (1.0 - h) for x, h in zip(p, h1)]
m = math.fsum(q)
qn = [x / m for x in q]
t2 = che_t(qn, c2)
l1 = math.fsum(x * h for x, h in zip(p, h1))
l2 = math.fsum(x * -math.expm1(-y * t2) for x, y in zip(q, qn))
return l1, l2
def sim_two(trace, c1, c2):
a, b = OrderedDict(), OrderedDict()
h1 = h2 = 0
for t, x in enumerate(trace):
if x in a:
a.move_to_end(x)
if t >= WARM:
h1 += 1
continue
a[x] = None
if len(a) > c1:
a.popitem(last=False)
if x in b:
b.move_to_end(x)
if t >= WARM:
h2 += 1
else:
b[x] = None
if len(b) > c2:
b.popitem(last=False)
n = len(trace) - WARM
return h1 / n, h2 / n
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
trace = rng.choices(range(N), weights=p, k=L)
t0 = che_t(p, TOTAL)
single = math.fsum(x * -math.expm1(-x * t0) for x in p)
print("Two LRU levels with {} slots in all; one cache: {:.4f}"
.format(TOTAL, single))
print(" C1 C2 Che L1 Che L2 Che all sim all")
for c1 in (250, 500, 1000, 1500):
c2 = TOTAL - c1
l1, l2 = che_two(p, c1, c2)
s1, s2 = sim_two(trace, c1, c2)
print(" {:4d} {:4d} {:.4f} {:.4f} {:.4f} {:.4f}".format(
c1, c2, l1, l2, l1 + l2, s1 + s2))Single source and citation
Fan, Y. (2026). Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts (Version 1.0.0), Chapter 6: Partitions and Tiers: the Same Slots, Arranged Differently. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-327 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026327,
author = {Fan, Yafu},
title = {Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Doubling Illusion: Hit-Ratio Curves under Zipf Requests
- Chapter 2 · The Characteristic Time: Solving the Che Approximation by Bisection, and How Accurate It Is
- Chapter 3 · Belady's Bound: Optimal Replacement, the Static Bound and the Capacity Price of LRU
- Chapter 4 · Marginal Returns: the Slope of the Capacity Curve and the Cost-Optimal Boundary
- Chapter 5 · Non-Stationary Requests: Popularity Drift, Frozen Lists and Cold Starts
- Chapter 7 · Eastern and Western Classics: the Nine-Year Reserve of the Royal Regulations and Belady's Optimal Replacement
- Chapter 8 · Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache