cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value > Class Template Reference

Tiny Least Frequently Used (TinyLFU) insertion policy. More...

#include <insertion_tinylfu.h>

Public Types
using	CacheItem = cachemere::Item< Value >

Public Member Functions
void	clear ()
	Clears the policy.
void	on_cache_hit (const Key &key, const CacheItem &item)
	Cache hit event handler. More...
template<typename KeyType >
void	on_cache_miss (const KeyType &key)
	Cache miss event handler. More...
void	set_cardinality (uint32_t cardinality)
	Set the cardinality of the policy. More...
bool	should_add (const Key &key)
	Determines whether a given key should be inserted into the cache. More...
bool	should_replace (const Key &victim, const Key &candidate)
	Determines whether a given victim should be replaced by a given candidate. More...

Detailed Description

template<typename Key, typename KeyHash, typename Value>
class cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value >

Tiny Least Frequently Used (TinyLFU) insertion policy.

TinyLFU is a state-of-the-art insertion policy that helps determine whether a given item should be inserted and/or kept in cache while using a constant amount of memory. The policy uses a combination of frequency sketches to keep track of items that have yet to be inserted in the cache, and uses those sketches to decide which items should me prioritized.

Template Parameters

Key	The type of the keys used to identify items in the cache.
KeyHash	The type of the hasher used to hash item keys.
Value	The type of the values stored in the cache.

Member Function Documentation

on_cache_hit()

template<class Key , class KeyHash , class Value >

void cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value >::on_cache_hit	(	const Key &	key,
		const CacheItem &	item
	)

Cache hit event handler.

Updates the internal frequency sketches for the given item.

Parameters

key	The key that has been hit.
item	The item that has been hit.

on_cache_miss()

template<class Key , class KeyHash , class Value >

template<class KeyType >

void cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value >::on_cache_miss

(

const KeyType &

key

)

Cache miss event handler.

Updates the internal frequency sketches for the given key.

Parameters

key	The key that was missed.

set_cardinality()

template<class Key , class KeyHash , class Value >

void cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value >::set_cardinality

(

uint32_t

cardinality

)

Set the cardinality of the policy.

The set cardinality should be a decent approximation of the cardinality of the set of keys that might be inserted in the cache. Getting an accurate estimate is very important, because an underestimation will severely decrease the accuracy of the policy, while an overestimation will use too much memory.

Parameters

cardinality

The expected cardinality of the set of items.

should_add()

template<class Key , class KeyHash , class Value >

bool cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value >::should_add

(

const Key &

key

)

Determines whether a given key should be inserted into the cache.

TinyLFU always accepts insertions of items if there is room for them in the cache.

Parameters

key	The key of the insertion candidate.

should_replace()

template<class Key , class KeyHash , class Value >

bool cachemere::policy::InsertionTinyLFU< Key, KeyHash, Value >::should_replace	(	const Key &	victim,
		const Key &	candidate
	)

Determines whether a given victim should be replaced by a given candidate.

TinyLFU will use its internal sketches to build a frequency estimation for both keys. It will return true only if it estimates that the candidate key is accessed more frequently than the victim key.

Parameters

victim	The key of the victim the candidate will be compared to.
candidate	The replacement candidate.

---

The documentation for this class was generated from the following files:

• include/cachemere/policy/insertion_tinylfu.h
• include/cachemere/policy/insertion_tinylfu.hpp