Cache Algorithms
Cache performance analysis.
The cache module provides algorithms for analyzing cache systems with various
replacement policies (LRU, FIFO, RR, etc.) and item popularity distributions.
Key function categories:
Miss probability:
cache_miss(),cache_miss_fpi(),cache_miss_spm(),cache_mva_miss()Hit probability:
cache_prob_erec(),cache_prob_fpi(),cache_prob_spm()TTL caches:
cache_ttl_hlru(),cache_ttl_lrua(),cache_ttl_lrum()Mean-field methods:
cache_rrm_meanfield(),cache_rrm_meanfield_ode()Characteristic time:
cache_t_hlru(),cache_t_lrum()MVA-based analysis:
cache_mva(),cache_spm()
Cache Analysis Algorithms.
Native Python implementations for analyzing cache systems, including exact recursive methods, singular perturbation methods, importance sampling, TTL-based caches, and various approximation techniques.
- Key algorithms:
cache_erec: Exact recursive normalizing constant cache_prob_erec: Exact recursive state probabilities cache_spm: Singular perturbation method cache_spm_size: Ray (WKB) asymptotics of the cost-capped constant cache_miss: Miss rate computation cache_is: Importance sampling cache_ttl_*: TTL-based cache analysis cache_rrm_*: Random replacement model
- cache_lrum_map_levelstats(D0, D1, T)[source]
Level statistics of one item’s embedded (list, phase) chain under the LRU(m)-MAP TTL approximation (Gast and Van Houdt, PEVA 2017, eqs. 5-9).
- Parameters:
- Returns:
time-stationary level probabilities (h+1,), list occupancies (h,), request-weighted hit fractions (h,)
- Return type:
(prob, occ, hitfrac)
References
Original MATLAB: matlab/src/api/cache/cache_lrum_map_levelstats.m
- cache_t_lrum_map(D0c, D1c, m)[source]
Characteristic times for the LRU(m)-MAP TTL approximation.
- Parameters:
- Returns:
Characteristic times (h,)
- Return type:
References
Original MATLAB: matlab/src/api/cache/cache_t_lrum_map.m
- cache_ttl_lrum_map(D0c, D1c, m)[source]
Request-weighted hit/miss probabilities for LRU(m) with per-item MAP request streams (Gast and Van Houdt, PEVA 2017). Intended for items with genuinely distinct or correlated request processes (e.g. marked MAP arrivals); when items are i.i.d. marks of a common stream the request sequence is IRM and the Poisson-based TTL approximations already apply.
- Parameters:
- Returns:
(n,h+1) request-weighted probabilities (column 0 = miss) and (n,h+1) time-stationary level occupancy probabilities
- Return type:
(pij, pijtime)
References
Original MATLAB: matlab/src/api/cache/cache_ttl_lrum_map.m
- cache_erec(gamma, m, sigma=None, k=None)[source]
Compute the cache normalizing constant using exact recursive method.
With item sizes and per-list storage cost caps this evaluates the constrained normalizing constant E(m,k) of Casale-Gast (IEEE/ACM Trans. Networking 29(2), 2021), Sec. IX, from the recursion E(m,k) = E_i(m,k) + sum_j m_j gamma_ij E_i(m-1_j, k-sigma_i 1_j), with the extra boundary E(m,k)=0 whenever some residual cap is negative.
- Parameters:
gamma (ndarray) – Cache access factors matrix (n x h), where n is number of items and h is number of cache levels.
m (ndarray) – Cache capacity vector (1 x h or h,).
sigma (ndarray) – Optional item storage costs (sizes), positive integers (n,).
k (ndarray) – Optional per-list storage cost caps, non-negative integers (h,).
- Returns:
Normalizing constant E.
- Return type:
- cache_erec_aux(gamma, m, k)[source]
Auxiliary method for computing cache normalizing constant using exact recursive method.
This method performs the core computation recursively, adjusting the size of the input matrix.
- cache_prob_erec(gamma, m, sigma=None, k=None)[source]
Compute cache state probabilities using exact recursive method.
This method calculates the probabilities of the cache being in different states based on the cache access factors and capacity. With item sizes and per-list storage cost caps it evaluates pi_ij = m_j gamma_ij E_i(m-1_j, k-sigma_i 1_j) / E(m,k).
- Parameters:
- Returns:
Matrix (n x h+1) containing cache state probabilities. Column 0 is miss probability, columns 1..h are hit probabilities at each cache level.
- Return type:
- cache_cost(gamma, m, sigma, k=None, pij=None)[source]
Mean storage cost held by each cache list.
Evaluates K_j = sum_i sigma_i pi_ij, the expected storage cost of the items resident in list j at steady state, as defined in Casale-Gast (IEEE/ACM Trans. Networking 29(2), 2021), Sec. IX.
- Parameters:
- Returns:
Mean storage cost of each list (h,).
- Return type:
- cache_cost_pathcheck(gamma, sigma, k, parent)[source]
Detect promotion paths blocked by storage cost caps.
The constrained normalizing constant E(m,k) sums the product form over every size-feasible cache state, while under RR-C(m) an item only reaches list j by being promoted one list at a time along the path from the miss list. A cap on an intermediate list therefore makes size-feasible states unreachable and E(m,k) normalizes over states the cache never visits. An empty report is a necessary, not sufficient, condition for the two sets to agree.
- Parameters:
- Returns:
Array of blocked triples [item, list, blocking list], 0-based.
- Return type:
- cache_mva(gamma, m)[source]
Mean Value Analysis for cache systems.
Computes cache performance metrics using MVA approach.
- Parameters:
- Returns:
pi: Steady-state probabilities
pi0: Miss probabilities per item
pij: Hit probabilities per item per level (n x h)
x: Throughput vector
u: Utilization vector
E: Normalizing constant
- Return type:
Tuple of (pi, pi0, pij, x, u, E) containing
- cache_spm_size(gamma, m, sigma, k, costmode='atmost')[source]
Ray expansion of the cost-capped cache normalizing constant.
- Parameters:
gamma (
ndarray (n,h)) – Item popularity probabilities (access factors).m (
ndarray (h,)) – Cache list capacities, non-negative integers.sigma (
ndarray (n,)) – Item storage costs (sizes), positive integers.k (
ndarray (h,)) – Per-list storage cost caps, integers.costmode (
{'atmost', 'exact'}) –'atmost'(default) matchescache_erec;'exact'resolves the cost exactly atk.
- Returns:
- cache_xi_iter(gamma, m, tol=1e-12, max_iter=1000)[source]
Compute cache xi terms using iterative method from Gast-van Houdt.
This method calculates the xi values which are important for understanding the distribution of items in the cache. The algorithm assumes that the access factors are monotone with the list index.
- cache_spm(gamma, m)[source]
Approximate the normalizing constant using SPM method.
Computes the normalizing constant of the cache steady state distribution using the singular perturbation method (also known as ray integration).
- cache_prob_spm(gamma, m)[source]
Compute cache miss probabilities using singular perturbation method.
Uses the SPM (ray integration) method to compute miss probabilities for cache systems.
- cache_prob_fpi(gamma, m, tol=1e-8, max_iter=1000)[source]
Compute cache hit probabilities using fixed point iteration (FPI method).
Matches MATLAB cache_prob_fpi: Uses fixed point iteration to compute cache hit probability distribution.
- Parameters:
- Returns:
Column 0: miss probabilities
Columns 1:h: hit probabilities at each level
- Return type:
Matrix (n x h+1) where
- cache_miss(gamma, m, lambd=None, sigma=None, cap=None)[source]
Compute miss rates for a cache system using exact recursive method.
- Parameters:
gamma (ndarray) – Item popularity probabilities (n x h matrix)
m (ndarray) – Cache capacity vector (h,)
lambd (ndarray | None) – Optional arrival rates per user per item (u x n x h+1)
sigma (ndarray | None) – Optional item storage costs (sizes) (n,)
cap (ndarray | None) – Optional per-list storage cost caps (h,)
- Returns:
M: Global miss rate
MU: Per-user miss rate (u,) or None
MI: Per-item miss rate (n,) or None
pi0: Per-item miss probability (n,) or None
- Return type:
Tuple of (M, MU, MI, pi0) where
References
Original MATLAB: matlab/src/api/cache/cache_miss.m
- cache_xi_fp(gamma, m, xi_init=None, tol=1e-14, max_iter=10000)[source]
Fixed-point iteration for computing cache performance metrics.
Computes cache performance metrics including Lagrange multipliers, miss probabilities, and hit probabilities.
- Parameters:
- Returns:
xi: Converged Lagrange multipliers (h,)
pi0: Miss probability per item (n,)
pij: Hit probability per item per list (n x h)
it: Number of iterations
- Return type:
Tuple of (xi, pi0, pij, it) where
References
Original MATLAB: matlab/src/api/cache/cache_xi_fp.m
- cache_miss_fpi(gamma, m, lambd=None)[source]
Compute cache miss rates using fixed-point iteration method.
- Parameters:
- Returns:
M: Global miss rate
MU: Per-user miss rate or None
MI: Per-item miss rate or None
pi0: Per-item miss probability or None
- Return type:
Tuple of (M, MU, MI, pi0) where
References
Original MATLAB: matlab/src/api/cache/cache_miss_fpi.m
- cache_miss_spm(gamma, m, lambd=None)[source]
Compute cache miss rates using singular perturbation method.
- Parameters:
- Returns:
M: Global miss rate
MU: Per-user miss rate or None
MI: Per-item miss rate or None
pi0: Per-item miss probability or None
lE: Log of normalizing constant
- Return type:
Tuple of (M, MU, MI, pi0, lE) where
References
Original MATLAB: matlab/src/api/cache/cache_miss_spm.m
- cache_mva_miss(p, m, R)[source]
Compute cache miss rates using Mean Value Analysis.
- Parameters:
- Returns:
M: Global miss rate
Mk: Per-item miss rate (n,)
- Return type:
Tuple of (M, Mk) where
References
Original MATLAB: matlab/src/api/cache/cache_mva_miss.m
- cache_miss_asy(gamma, m, maxiter=1000, tol=1e-8)[source]
Asymptotic (large-cache) miss ratio by a rank-threshold fixed point.
The deterministic limit of a multi-list cache: as the item count grows, list l holds exactly the m[l] items of largest effective popularity, so an item’s membership becomes a THRESHOLD test rather than a probability. With pi[k] the miss probability of item k, the effective popularity of item j in list l is gamma[l,j]*(1-pi[j]) and the fixed point is
pi[k] = sum_l gamma[l,k] 1{item k outside the top m[l]} / sum_l gamma[l,k],
iterated to a sup-norm tolerance from the uniform start pi = 1/n. The returned scalar is the request-weighted miss ratio.
INDEX CONVENTION, AND IT IS THE REVERSE OF EVERY OTHER CACHE FUNCTION HERE. gamma is (h, n), LIST-major, whereas cache_spm, cache_erec and cache_miss all take gamma as (n, h), ITEM-major. Callers holding an item-major gamma must transpose. The threshold is strict, so an item exactly at the cutoff is admitted. A degenerate capacity (zero total, or any negative entry) returns 1.
- Parameters:
- Returns:
The request-weighted asymptotic miss ratio.
- Return type:
References
N. Gast, B. Van Houdt, “Transient and steady-state regime of a family of list-based cache replacement algorithms”, Queueing Syst. 83, 2016. jar/src/main/java/jline/api/cache/Cache_miss_asy.java
- cache_miss_rmf(gamma, m, lambd, tspan=None, x0init=None, accost=None, return_state=False)[source]
RMF (1/N-accurate) miss rates for RANDOM(m) caches.
Mirrors the cache_miss_fpi contract. gamma is accepted for interface compatibility (used for sizing only); the popularity is recovered from lambd, the (u, n, h+1) per-user per-item arrival rates.
- Parameters:
gamma – item access factors (unused beyond sizing).
m – cache capacity vector (h,).
lambd – arrival rates per user per item per list (u, n, >=1).
tspan – optional [t0, t1]. When given, also integrates the plain mean-field drift over the window and returns the transient trajectory (the same drift that _fixed_point drives to steady state). Omitting tspan preserves the steady-state-only contract.
x0init – optional initial occupancy (dim,) for the transient; defaults to the standard first-m-in-list initial state. Used to carry the cache mean occupancy across environment switches.
return_state – append the converged fixed point xss (dim,), the flat DDPP occupancy item-major over lists 0..h, as one extra trailing element. It is what resolves a hit BY LIST, which the aggregate miss rate cannot: hitByList(r,l) = sum_i popularity_r(i)*xss[i,l].
- Returns:
Tuple (M, MU, MI, pi0) when tspan is None, else (M, MU, MI, pi0, tout, pi0_t, MU_t, xtraj) with tout (nt,), pi0_t (n, nt) per-item list-0 occupancy, MU_t (u, nt) per-user miss rate, and xtraj (dim, nt) full DDPP occupancy trajectory. With return_state, xss is appended to whichever of the two is returned.
- cache_rmf_lna(x, p, m, n, h, dim)[source]
Stationary covariance of the RANDOM(m) occupancy under the LNA.
Twin of the MATLAB local rmf_lna_covariance: the solution of F’(x) W + W F’(x)’ + Q(x) = 0 with the same _jacobian and _noise_matrix the 1/N correction is built from, so mean and covariance linearise about the identical drift.
THE SUBSPACE IS THE POINT. The Jacobian is singular twice over, because the cache conserves two things: each item is in exactly one list (sum_k x[i,k] = 1) and each list holds exactly its capacity (sum_i x[i,k] = m[k]). Every jump is a SWAP, l(i,j,k) = (e_i - e_j) tensor (e_{k+1} - e_k), so the fluctuation lives on the tensor product of the zero-sum item space with the zero-sum list space: the double-centred subspace, of dimension (n-1)*h. Restricting to an orthonormal basis of it is exact, and it is what makes the covariance of a deterministic total come out as zero.
- Raises:
ValueError – the fixed point is not exponentially stable on that subspace, so there is no stationary covariance.
- cache_miss_sfifo_rmf(gamma, m, lambd, tspan=None, x0init=None, tmax=20000.0, accost=None)[source]
Position-resolved mean-field miss rates for strict FIFO(m) caches.
Mirrors the cache_miss_rmf / cache_miss_fpi contract. gamma is accepted for interface compatibility (used for sizing only); the popularity is recovered from lambd, the (u, n, h+1) per-user per-item arrival rates.
Returns (M, MU, MI, pi0) when tspan is None, else (M, MU, MI, pi0, tout, pi0_t, MU_t, xtraj) with tout (nt,), pi0_t (n, nt) per-item out-of-cache occupancy, MU_t (u, nt) per-user miss rate, and xtraj (n*S, nt) the full position-resolved occupancy trajectory.
- cache_miss_fifo_rmf(gamma, m, lambd, tspan=None, x0init=None, tmax=20000.0, accost=None)[source]
Position-resolved mean-field miss rates for FIFO(m) caches.
Mirrors the cache_miss_rmf / cache_miss_sfifo_rmf contract. gamma is accepted for interface parity (used for sizing only); the popularity is recovered from lambd, the (u, n, h+1) per-user per-item arrival rates.
Returns (M, MU, MI, pi0) when tspan is None, else (M, MU, MI, pi0, tout, pi0_t, MU_t, xtraj). The transient path is the intended use: at steady state FIFO(m) equals RANDOM(m) (Gast15 Thm 1), so prefer cache_miss_rmf when only the fixed point is needed.
- cache_is(gamma, m, samples=100000, sigma=None, k=None)[source]
Importance sampling estimation of cache normalizing constant.
Estimates the normalizing constant for cache models using Monte Carlo importance sampling.
- Parameters:
- Returns:
E: Normalizing constant estimate
lE: Log of normalizing constant
- Return type:
Tuple of (E, lE) where
References
Original MATLAB: matlab/src/api/cache/cache_is.m
- cache_prob_is(gamma, m, samples=100000, sigma=None, k=None)[source]
Importance sampling estimation of cache hit probabilities.
Estimates cache hit probability distribution using Monte Carlo importance sampling.
- Parameters:
- Returns:
prob[i, 0] = miss probability for item i prob[i, 1+j] = hit probability for item i at level j
- Return type:
Cache hit probability matrix (n x h+1)
References
Original MATLAB: matlab/src/api/cache/cache_prob_is.m
- cache_miss_is(gamma, m, lambd=None, samples=100000, sigma=None, k=None)[source]
Importance sampling estimation of cache miss rates.
Computes global, per-user, and per-item miss rates using Monte Carlo importance sampling.
- Parameters:
- Returns:
M: Global miss rate
MU: Per-user miss rate or None
MI: Per-item miss rate or None
pi0: Per-item miss probability or None
lE: Log of normalizing constant
- Return type:
Tuple of (M, MU, MI, pi0, lE) where
References
Original MATLAB: matlab/src/api/cache/cache_miss_is.m
- logmeanexp(x)[source]
Compute log(mean(exp(x))) in a numerically stable way.
Uses the log-sum-exp trick for numerical stability.
- cache_t_hlru(gamma, m)[source]
Characteristic time of each list of an h-LRU / LRU(m) cache.
Solves the TTL (characteristic-time) fixed point of the list-based h-LRU (LRU(m)) policy: sum_k pi_l(k;T) = m[l] for each list l, where the level probabilities follow the birth-death form pi_l ~ prod_{s<=l} (1-e_s)/e_s with e_s = exp(-gamma_k*T_s) (Gast and Van Houdt, SIGMETRICS 2015). Solved by per-list bisection with Gauss-Seidel sweeps.
- Parameters:
- Returns:
Characteristic time for each cache list (h,)
- Return type:
References
Original MATLAB: matlab/src/api/cache/cache_t_hlru.m
- cache_ttl_hlru(gamma, m)[source]
Steady-state list occupancy probabilities for an h-LRU / LRU(m) cache.
Characteristic-time (TTL) approximation of the list-based h-LRU policy: h LRU lists of capacities m[0..h-1], a miss inserts at the head of list 1, a hit in list l exchanges the item with the tail of list l+1 (Gast and Van Houdt, SIGMETRICS 2015). For h=1 this reduces exactly to the Che approximation for LRU.
- Parameters:
- Returns:
(n x h+1) probabilities; column 0 = not cached, column 1+l = in list l
- Return type:
References
Original MATLAB: matlab/src/api/cache/cache_ttl_hlru.m
- cache_ttl_lrua(lambd, R, m, seed=23000, ttl=None)[source]
Compute steady-state probabilities for TTL-LRU cache with arrival routing.
Uses fixed-point iteration with DTMC solving for cache systems with multiple users, items, and levels with routing.
- Parameters:
lambd (ndarray) – Arrival rates per user per item per list (u x n x h+1)
R (list) – Routing probability structure. Can be either: - 1D list: R[i] is the (h+1 x h+1) routing matrix for item i - 2D list: R[v][i] is the routing matrix for user v, item i
m (ndarray) – Cache capacity vector (h,)
seed (int) – Random seed for initialization (default: 23000)
ttl (ndarray | None) – Optional real TTL per cache level (h,). Caps the characteristic time at each level: items expire after ttl[l] time units even if the cache is not full. Units are in model time (request epochs when arrival rates sum to 1). Use np.inf for levels with no TTL. When TTL is binding, effective occupancy may be less than m[l].
- Returns:
Steady-state probability distribution (n x h+1)
- Return type:
References
Original MATLAB: matlab/src/api/cache/cache_ttl_lrua.m
- cache_rrm_meanfield_ode(t, x, lambd, m, n, h)[source]
ODE function for RRM mean-field cache dynamics.
Defines the differential equations for the Random Replacement Model mean-field cache dynamics.
- Parameters:
- Returns:
Time derivative of state vector
- Return type:
References
Original MATLAB: matlab/src/api/cache/cache_rrm_meanfield_ode.m
- cache_rrm_meanfield(lambd, m, t_end=10000.0, seed=23000)[source]
Solve RRM mean-field steady state using ODE integration.
Computes the steady-state probability distribution for a cache with random replacement policy using mean-field ODE dynamics.
- Parameters:
- Returns:
prob: Steady-state probability matrix (n x h+1)
missrate: Global miss rate (lambda * miss_prob)
missratio: Miss ratio (missrate / sum(lambda))
- Return type:
Tuple of (prob, missrate, missratio) where
References
Original MATLAB: matlab/src/api/cache/cache_rrm_meanfield.m
- cache_gamma_lp(lambd, R)[source]
Compute gamma parameters for cache models using linear programming approach.
Computes item popularity probabilities at each cache level based on arrival rates and routing probabilities.
- Parameters:
- Returns:
gamma: Item popularity probabilities at each level (n x h)
u: Number of users
n: Number of items
h: Number of cache levels
parent: Parent list of each list, 0-based with -1 for the lists rooted in the miss list (h,)
- Return type:
Tuple of (gamma, u, n, h, parent) where
References
Original MATLAB: matlab/src/api/cache/cache_gamma_lp.m
- cache_gamma(lambd, R)[source]
Access factors of a multi-list cache whose lists form a general graph.
Companion of cache_gamma_lp, which requires the access structure to be a tree and walks the unique parent relation. Here the structure is only required to be reachable: the path to list j is the BREADTH-FIRST shortest path in the access graph of item i, so a list with several parents is admissible and the first shortest path found in node order is the one taken. Along that path,
gamma[i,j] = (sum_v lambd[v,i,0]) prod_edges (a,b) sum_v lambd[v,i,a] R[v][i][a,b]
THREE DIVERGENCES FROM cache_gamma_lp, all of which change the number, so the two are not substitutes: the destination of column j is node j and not node j+1, so column 0 carries no edge factor at all; the leading factor is the aggregate miss-node request rate rather than one; and each edge factor reads lambd at the SOURCE node a alone rather than summing over every t <= a. Use cache_gamma_lp for the access factors a cache solver consumes.
The adjacency is read from user 0 only, so a model whose users route an item differently is analysed on the first user’s graph. An unreachable list gives gamma[i,j] = 0.
- Parameters:
- Returns:
Tuple of (gamma, u, n, h) with gamma of shape (n, h).
- Return type:
References
jar/src/main/java/jline/api/cache/Cache_gamma.java