What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Marginal Returns: the Slope of the Capacity Curve and the Cost-Optimal Boundary”?
Answer: 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.
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.2094, 4187
| Daily cost, R = 3000, m = 1.0, k = 0.15 (illustrative units) | ||||
| C | LRU hit | recompute | storage | total |
| 0 | 0.0000 | 3000.0 | 0.0 | 3000.0 |
| 1046 | 0.3511 | 1946.8 | 156.9 | 2103.7 |
| 2093 | 0.4559 | 1632.3 | 313.9 | 1946.3 |
| 4187 | 0.5862 | 1241.5 | 628.0 | 1869.6 |
| 8374 | 0.7485 | 754.6 | 1256.1 | 2010.7 |
| 16748 | 0.9469 | 159.2 | 2512.2 | 2671.4 |
| optimum C* = 4187 slots, 0.2094 of the catalogue | ||||
| slot cost k = 0.075: C* = 11385 | ||||
| slot cost k = 0.3 | : C* = | 1521 |
Show the full program
# Chapter 4. p42: where the next slot stops paying for itself.
# Model: daily cost = R m (1 - H(C)) + k C, with R requests per day,
# m the cost of recomputing one chart on a miss and k the cost of
# keeping one cached result for one day, all in the same illustrative
# cost unit. The optimum satisfies R m dH/dC = k; since dH/dC falls as
# T grows, the root in T is found by bisection and C* is read as the
# occupancy there. R = 3000, m = 1, k = 0.15, Zipf a = 0.8 and
# N = 20000 keys are illustrative, not measurements.
import math
N, A = 20000, 0.8
R, M, K = 3000, 1.0, 0.15
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_hit(p, t):
return math.fsum(x * -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 slope(p, t):
num = math.fsum(x * x * math.exp(-x * t) for x in p)
den = math.fsum(x * math.exp(-x * t) for x in p)
return num / den
def best_t(p, target, tol=1e-9):
lo, hi = 0.0, 1.0
while slope(p, hi) > target:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if slope(p, mid) > target:
lo = mid
else:
hi = mid
return 0.5 * (lo + hi)
def cost(p, c, r, m, k):
t = che_t(p, c)
return r * m * (1.0 - che_hit(p, t)) + k * c, che_hit(p, t)
if __name__ == "__main__":
p = zipf(N, A)
t = best_t(p, K / (R * M))
cs = round(occupancy(p, t))
print("Daily cost, R = {}, m = {}, k = {} (illustrative units)"
.format(R, M, K))
print(" C LRU hit recompute storage total")
for c in (0, cs // 4, cs // 2, cs, 2 * cs, 4 * cs):
if c == 0:
tot, h = R * M, 0.0
else:
tot, h = cost(p, c, R, M, K)
print(" {:5d} {:.4f} {:8.1f} {:7.1f} {:7.1f}".format(
c, h, R * M * (1 - h), K * c, tot))
print("optimum C* = {} slots, {:.4f} of the catalogue".format(
cs, cs / N))
for k2 in (0.075, 0.3):
c2 = round(occupancy(p, best_t(p, k2 / (R * M))))
print("slot cost k = {:<5}: C* = {:5d}".format(k2, c2))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 4: Marginal Returns: the Slope of the Capacity Curve and the Cost-Optimal Boundary. 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 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
- Chapter 8 · Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache