What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache”?
Answer: Chapter 8 gives a read-only planning workflow for a toll booth's chart-result cache, the distilled Cache Hit Ratio Estimator and a pre-registered test, and flags for drift any capacity whose characteristic time reaches 9.58 days. Marked boxes separate published evidence, runnable Python calculations (22 programs), classical sources and the author's hypotheses.
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: 9.58
| Chart cache sheet: N | 50000, a = 0.9, R = 30000/day |
| C hit misses/day CPU-s/day memory MB T_C days | |
| 1250 | 0.4174 17477 3495 14.6 0.06 |
| 2500 | 0.5000 15001 3000 29.3 0.14 |
| 5000 | 0.5928 12215 2443 58.6 0.33 |
| 10000 | 0.6983 9052 1810 117.2 0.81 |
| 20000 | 0.8189 5433 1087 234.4 2.25 |
| 40000 | 0.9557 1330 266 468.8 9.58 |
| gain per doubling: | |
| 1250 | 2500: +0.0825 hit, 2475 fewer misses/day |
| 2500 | 5000: +0.0929 hit, 2786 fewer misses/day |
| 5000 | 10000: +0.1054 hit, 3163 fewer misses/day |
| 10000 | 20000: +0.1207 hit, 3620 fewer misses/day |
| 20000 | 40000: +0.1367 hit, 4102 fewer misses/day |
Show the full program
# Chapter 8. p81: a read-only capacity sheet for a chart-result cache.
# Model: the Che approximation turns four planning inputs into a table:
# distinct chart keys N, Zipf exponent a, requests per day R and the
# compute time per recomputed chart. Entry size converts slots into
# memory. Every input is illustrative (N = 50000, a = 0.9, R = 30000,
# 0.2 CPU-seconds per miss, 12 KB per entry); the sheet is advice to be
# read, not a setting written anywhere.
import math
N, A, R, CPU, KB = 50000, 0.9, 30000, 0.2, 12
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_hit(p, t):
return math.fsum(x * -math.expm1(-x * t) for x in p)
if __name__ == "__main__":
p = zipf(N, A)
print("Chart cache sheet: N = {}, a = {}, R = {}/day".format(N, A, R))
print(" C hit misses/day CPU-s/day memory MB T_C days")
rows = []
for c in (1250, 2500, 5000, 10000, 20000, 40000):
t = che_t(p, c)
h = che_hit(p, t)
rows.append((c, h))
print(" {:5d} {:.4f} {:7.0f} {:7.0f} {:7.1f} {:6.2f}"
.format(c, h, R * (1 - h), R * (1 - h) * CPU,
c * KB / 1024, t / R))
print(" gain per doubling:")
for (c0, h0), (c1, h1) in zip(rows, rows[1:]):
print(" {:5d} -> {:5d}: +{:.4f} hit, {:5.0f} fewer misses/day"
.format(c0, c1, h1 - h0, R * (h1 - h0)))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 8: Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache. 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 6 · Partitions and Tiers: the Same Slots, Arranged Differently
- Chapter 7 · Eastern and Western Classics: the Nine-Year Reserve of the Royal Regulations and Belady's Optimal Replacement