What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “The Doubling Illusion: Hit-Ratio Curves under Zipf Requests”?

Answer: At the four capacities the simulated hit ratios are 0.1380, 0.2624, 0.4496 and 0.7374; the Che approximation gives 0.1373, 0.2613, 0.4483 and 0.7367. The gaps are -0.0007, -0.0010, -0.0013 and -0.0007, and the largest absolute gap is only 0.0013. The approximation has no parameter fitted to the simulation; it uses only the request probabilities and the capacity. For a capacity-planning problem this error is far below the error in estimating the request probabilities themselves; Chapter 8 shows that a slightly misestimated Zipf exponent alone costs an order of magnitude more.

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.0007, -0.0010, -0.0013, 0.0013, 0.1373, 0.1380

LRU simulation vs Che, 250000 scored requests
CsimulatedCheChe - sim
1250.13800.1373-0.0007
5000.26240.2613-0.0010
20000.44960.4483-0.0013
80000.73740.7367-0.0007
largest absolute gap = 0.0013
Show the full program
# Chapter 1. p13: a seeded LRU simulation against the Che prediction.
# Model: 300000 independent Zipf requests (a = 0.8, N = 20000 keys,
# illustrative) are replayed through a true LRU cache (OrderedDict);
# the first 50000 requests warm the cache and are not scored. The Che
# approximation is computed for the same p and C with no fitted
# parameter. Fixed seed 20261113, so every run prints the same table.
import math
import random
from collections import OrderedDict

N, A, L, WARM = 20000, 0.8, 300000, 50000


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_hit(trace, c, warm):
    cache = OrderedDict()
    hits = 0
    for t, k in enumerate(trace):
        if k in cache:
            cache.move_to_end(k)
            if t >= warm:
                hits += 1
        else:
            cache[k] = None
            if len(cache) > c:
                cache.popitem(last=False)
    return hits / (len(trace) - warm)


if __name__ == "__main__":
    p = zipf(N, A)
    rng = random.Random(20261113)
    trace = rng.choices(range(N), weights=p, k=L)
    print("LRU simulation vs Che, {} scored requests".format(L - WARM))
    print("      C   simulated    Che     Che - sim")
    worst = 0.0
    for c in (125, 500, 2000, 8000):
        s = lru_hit(trace, c, WARM)
        h = che_hit(p, che_t(p, c))
        worst = max(worst, abs(h - s))
        print("  {:5d}    {:.4f}    {:.4f}   {:+.4f}".format(c, s, h, h - s))
    print("largest absolute gap = {:.4f}".format(worst))

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 1: The Doubling Illusion: Hit-Ratio Curves under Zipf Requests. 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