cache_cost.h File Reference

Mean per-list storage cost of a cache with item sizes, and the screen for promotion paths that storage cost caps make unreachable. More...

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

Include dependency graph for cache_cost.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheBlockedPair
	One (item, list, blocking list) triple, all 0-based. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
std::vector< T >	line::cache::cache_cost (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k, const Matrix< T > &pij)
	Mean per-list storage cost of a cache with item sizes, and the screen for promotion paths that storage cost caps make unreachable.
template<class T>
std::vector< T >	line::cache::cache_cost (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k)
template<class T>
std::vector< CacheBlockedPair >	line::cache::cache_cost_pathcheck (const Matrix< T > &gamma, const std::vector< int > &sigma, const std::vector< int > &k, const std::vector< int > &parent)

Detailed Description

Mean per-list storage cost of a cache with item sizes, and the screen for promotion paths that storage cost caps make unreachable.

Templated port of matlab/src/api/cache/cache_cost.m and cache_cost_pathcheck.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_cost.java and Cache_cost_pathcheck.java.

K_j = sum_i sigma_i pi_ij is the expected storage cost of the items resident in list j at steady state (Casale-Gast, IEEE/ACM Trans. Networking 29(2), 2021, Sec. IX). Every operation is a field operation, so the exact instantiation returns K as a rational.

The path check exists because E(m,k) sums over every size-feasible state while under RR-C(m) an item only reaches list j by being promoted one list at a time from the miss list: a cap on an intermediate list can leave size-feasible states unreachable, and E(m,k) then normalizes over states the cache never visits. An EMPTY report is a necessary, not sufficient, condition for the two sets to agree – a list of capacity above one may still be unreachable when its cap admits no combination containing the item.

Definition in file cache_cost.h.