cache_miss_asy.h File Reference

Asymptotic (large-cache) miss ratio by a rank-threshold fixed point. More...

#include <algorithm>
#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for cache_miss_asy.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
T	line::cache::cache_miss_asy (const Matrix< T > &gamma, const std::vector< int > &m, int maxIter, const T &tolerance)
	Asymptotic (large-cache) miss ratio by a rank-threshold fixed point.
template<class T>
T	line::cache::cache_miss_asy (const Matrix< T > &gamma, const std::vector< int > &m)
	Reference defaults: 1000 sweeps at a 1e-8 sup-norm tolerance.

Detailed Description

Asymptotic (large-cache) miss ratio by a rank-threshold fixed point.

Templated port of jar/src/main/java/jline/api/cache/Cache_miss_asy.java. MATLAB has no counterpart, so the JAR is the reference.

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. Writing pi(k) for 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 is 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 sum_{l,k} gamma(l,k) pi(k) / sum_{l,k} gamma(l,k).

INDEX CONVENTION, AND IT IS THE REVERSE OF EVERY OTHER CACHE FUNCTION HERE. The reference reads n = gamma.getNumCols() and h = gamma.getNumRows(), so its gamma is (h x n), LIST-major, whereas cache_spm, cache_erec, cache_miss and the rest all take gamma as (n x h), ITEM-major. That is reproduced, because silently transposing would make the two conventions disagree about which of a non-square gamma's dimensions is the item count and return a plausible wrong ratio rather than an error. Callers holding an item-major gamma must transpose before calling.

The threshold is strict (>), so ties at the cutoff resolve as "in cache". With the ranking taken over the OTHER n-1 items and then compared against item k, an item exactly at the boundary is admitted; this reproduces the reference and matters only on gamma matrices with repeated entries.

A degenerate capacity (zero total, or any negative entry) returns 1, i.e. every request misses, which is the reference's early exit.

Arithmetic: EXACT-CAPABLE in its operations, but the answer is defined by a sup-norm tolerance and an iteration cap, so it is inexact by construction and gated on transcendental arithmetic like the other fixed-point cache routines (cache_xi_iter, cache_miss_fpi).

Definition in file cache_miss_asy.h.