cache_miss.h File Reference

Exact cache miss rates from the recursive normalizing constant. More...

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

Include dependency graph for cache_miss.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheMissResult< T >
	Return value of cache_miss, mirroring [M,MU,MI,pi0]. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheMissResult< T >	line::cache::cache_miss (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	Exact cache miss rates from the recursive normalizing constant.
template<class T>
CacheMissResult< T >	line::cache::cache_miss (const Matrix< T > &gamma, const std::vector< int > &m)
	Overload without request rates: only the global miss rate is defined.

Detailed Description

Exact cache miss rates from the recursive normalizing constant.

Templated port of matlab/src/api/cache/cache_miss.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_miss.java.

Two quantities are computed, both as ratios of cache_erec constants: M = E(gamma, m + e_1) / E(gamma, m), the global miss rate; and pi0(k) = E(gamma without item k, m) / E(gamma, m), the probability that item k is absent from the cache, from which the per-user rate MU(v) = sum_k lambda(v,k) pi0(k) and the per-item rate MI(k) = (sum_v lambda(v,k)) pi0(k) follow.

Pure field operations throughout, so the exact instantiation returns rates with no rounding.

DIVERGENCE, MATLAB vs JAR: MATLAB conditions on the absence of item k by deleting ROW k of gamma, gamma(setdiff(1:n,k),:) – gamma is item-by-list, so a row is an item. The JAR's Cache_miss deletes COLUMN k instead (it builds gammaWithoutK by iterating over gamma.getNumCols() and skipping j == k), which removes a cache LIST, not an item, and additionally reads the item count as lambda.getNumCols() while indexing gamma by it. The JAR's pi0/MU/MI are therefore wrong whenever h != n, and meaningless in general. This port follows MATLAB.

Definition in file cache_miss.h.