What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Partitions and Tiers: the Same Slots, Arranged Differently”?

Answer: Then the Che column. The front-level hit ratios, 0.1931, 0.2613, 0.3450 and 0.4027, match a single cache of the same size exactly; this level is fine. The trouble lies at the back. The approximation for both levels together gives 0.4319, 0.4190, 0.4177 and 0.4309, systematically above the simulation, by about six points at the even split. The reason is that the front level's miss stream is not a stream of independent references. An object that has just missed the front is now in the front, so for a while its requests hit there and never reach the back. Requests reaching the back are thus spread out in time, with the requests for any one object pulled apart. Treating them as independent references, the Che approximation overstates the back level's chance to hit.

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.1931, 0.2613, 0.3450, 0.4027, 0.4177, 0.4190

Two LRU levels with 2000 slots in all; one cache: 0.4483
C1C2Che L1Che L2Che allsim all
25017500.19310.23880.43190.4277
50015000.26130.15770.41900.3968
100010000.34500.07270.41770.3562
15005000.40270.02810.43090.4048
Show the full program
# Chapter 6. p62: two LRU levels in tandem, the setting of Che (2002).
# Model: level 1 has C1 slots and sees all requests; its misses go to
# level 2 with C2 slots. Following Che, Tung and Wang, the miss stream
# of level 1 is treated as independent references with rates
# q_i = p_i (1 - h1_i); level 2 is solved by the same Che equation on
# q normalised. Overall hit = H1 + sum q_i h2_i. A single LRU of
# C1 + C2 slots is the yardstick. Seeded trace of 250000 Zipf requests
# (a = 0.8, N = 20000, illustrative), 50000 warm-up.
import math
import random
from collections import OrderedDict

N, A, L, WARM, TOTAL = 20000, 0.8, 250000, 50000, 2000


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_two(p, c1, c2):
    t1 = che_t(p, c1)
    h1 = [-math.expm1(-x * t1) for x in p]
    q = [x * (1.0 - h) for x, h in zip(p, h1)]
    m = math.fsum(q)
    qn = [x / m for x in q]
    t2 = che_t(qn, c2)
    l1 = math.fsum(x * h for x, h in zip(p, h1))
    l2 = math.fsum(x * -math.expm1(-y * t2) for x, y in zip(q, qn))
    return l1, l2


def sim_two(trace, c1, c2):
    a, b = OrderedDict(), OrderedDict()
    h1 = h2 = 0
    for t, x in enumerate(trace):
        if x in a:
            a.move_to_end(x)
            if t >= WARM:
                h1 += 1
            continue
        a[x] = None
        if len(a) > c1:
            a.popitem(last=False)
        if x in b:
            b.move_to_end(x)
            if t >= WARM:
                h2 += 1
        else:
            b[x] = None
            if len(b) > c2:
                b.popitem(last=False)
    n = len(trace) - WARM
    return h1 / n, h2 / n


if __name__ == "__main__":
    p = zipf(N, A)
    rng = random.Random(20261113)
    trace = rng.choices(range(N), weights=p, k=L)
    t0 = che_t(p, TOTAL)
    single = math.fsum(x * -math.expm1(-x * t0) for x in p)
    print("Two LRU levels with {} slots in all; one cache: {:.4f}"
          .format(TOTAL, single))
    print("    C1    C2   Che L1   Che L2   Che all   sim all")
    for c1 in (250, 500, 1000, 1500):
        c2 = TOTAL - c1
        l1, l2 = che_two(p, c1, c2)
        s1, s2 = sim_two(trace, c1, c2)
        print("  {:4d}  {:4d}   {:.4f}   {:.4f}    {:.4f}    {:.4f}".format(
            c1, c2, l1, l2, l1 + l2, s1 + s2))

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 6: Partitions and Tiers: the Same Slots, Arranged Differently. 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