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
Cmeansd95% intervalCheinside
2500.19300.0012[0.1921, 0.1940]0.1931yes
10000.34480.0024[0.3428, 0.3468]0.3450yes
40000.57690.0024[0.5749, 0.5789]0.5767yes
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