What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “The Characteristic Time: Solving the Che Approximation by Bisection, and How Accurate It Is”?
Answer: At all three capacities the Che value falls inside the interval. At two hundred and fifty slots the simulated mean is 0.1930, the interval runs from 0.1921 to 0.1940, and the approximation gives 0.1931. At one thousand the mean is 0.3448, the interval runs from 0.3428 to 0.3468, and the approximation gives 0.3450. At four thousand the mean is 0.5769, the interval runs from 0.5749 to 0.5789, and the approximation gives 0.5767. The standard deviation between batches lies between 0.0012 and 0.0024. Even under perfectly stationary requests, then, a hit ratio measured over a few tens of thousands of requests moves by a few thousandths; before comparing it with a forecast, that wobble must be acknowledged.
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.0012, 0.0024, 0.1921, 0.1930, 0.1931, 0.1940
| Batch means: 8 batches of 50000 requests | |||||
| C | mean | sd | 95% interval | Che | inside |
| 250 | 0.1930 | 0.0012 | [0.1921, 0.1940] | 0.1931 | yes |
| 1000 | 0.3448 | 0.0024 | [0.3428, 0.3468] | 0.3450 | yes |
| 4000 | 0.5769 | 0.0024 | [0.5749, 0.5789] | 0.5767 | yes |
Show the full program
# Chapter 2. p22: how sure is the agreement? Batch means on a long run.
# Model: one seeded trace of 450000 Zipf requests (a = 0.8, N = 20000,
# illustrative) runs through LRU. After 50000 warm-up requests the rest
# is cut into 8 batches of 50000; the batch hit ratios give a mean and
# a 95 % interval with Student t = 2.365 for 7 degrees of freedom.
# The Che value has no free parameter and is set against the interval.
import math
import random
import statistics
from collections import OrderedDict
N, A, WARM, B, NB = 20000, 0.8, 50000, 50000, 8
T7 = 2.365
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)
def lru_batches(trace, c, warm, b):
cache = OrderedDict()
counts = [0] * ((len(trace) - warm) // b)
for t, k in enumerate(trace):
if k in cache:
cache.move_to_end(k)
if t >= warm:
counts[(t - warm) // b] += 1
else:
cache[k] = None
if len(cache) > c:
cache.popitem(last=False)
return [x / b for x in counts]
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
trace = rng.choices(range(N), weights=p, k=WARM + B * NB)
print("Batch means: {} batches of {} requests".format(NB, B))
print(" C mean sd 95% interval Che inside")
for c in (250, 1000, 4000):
hs = lru_batches(trace, c, WARM, B)
m = math.fsum(hs) / len(hs)
sd = statistics.stdev(hs)
half = T7 * sd / math.sqrt(len(hs))
h = che_hit(p, che_t(p, c))
ok = "yes" if m - half <= h <= m + half else "no"
print(" {:5d} {:.4f} {:.4f} [{:.4f}, {:.4f}] {:.4f} {}"
.format(c, m, sd, m - half, m + half, h, ok))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 2: The Characteristic Time: Solving the Che Approximation by Bisection, and How Accurate It Is. 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 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
- Chapter 8 · Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache