cache_t_lrum_map.h File Reference

Characteristic times of the LRU(m)-MAP TTL approximation. More...

#include <cstddef>
#include <vector>
#include "line/api/cache/cache_lrum_map_levelstats.h"
#include "line/api/mam/map_moment.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
#include "line/util/rootfind.h"

Include dependency graph for cache_t_lrum_map.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
std::vector< T >	line::cache::cache_t_lrum_map (const std::vector< mam::Map< T > > &items, const std::vector< T > &m, const T &tol, unsigned maxswp=200)
	Characteristic times of the LRU(m)-MAP TTL approximation.

Detailed Description

Characteristic times of the LRU(m)-MAP TTL approximation.

Templated port of matlab/src/api/cache/cache_t_lrum_map.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_t_lrum_map.java. The times T_1..T_h are fixed by equating the expected occupancy of each list to its capacity,

sum_k occ_l(item k; T) = m_l, l = 1..h,

with occ from cache_lrum_map_levelstats (Gast and Van Houdt, Performance Evaluation 2017, Section 3.1.2).

HOW THE SYSTEM IS SOLVED, and why it is not a multivariate optimizer: occ_l is strictly increasing in T_l (a longer timer keeps the item in list l longer), so each equation is a well-posed SCALAR root problem in its own unknown once the other times are held fixed. The system is therefore solved by Gauss-Seidel sweeps of bracketed scalar solves – the same structure cache_t_hlru.h already uses for h-LRU – with the bracket found by doubling and closed by bisection. The result is deterministic and needs no derivative, no line search and no trust region.

That is a real improvement on both references. MATLAB calls fsolve on log(T) from a fixed zero start, so it needs the Optimization Toolbox and stops on fsolve's default tolerances (the reference instance in the tests leaves a capacity residual of about 1e-10). The JAR does not solve the system at all: it hands the residual NORM to COBYLA, a derivative-free constrained optimizer, which turns h independent monotone equations into one nonconvex minimization – and COBYLA is stopped at rhoend = 1e-6, so its times carry a much larger error than either the MATLAB or this port.

ARITHMETIC: transcendental, through cache_lrum_map_levelstats.

Definition in file cache_t_lrum_map.h.