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

Greedy-Dual-Size-Frequency (GDSF) eviction policy. More...

#include <eviction_gdsf.h>

Classes
class	VictimIterator
	Iterator for iterating over cache items in the order they should be evicted. More...

Public Types
using	CacheItem = Item< Value >

Public Member Functions
void	clear ()
	Clears the policy.
void	set_cardinality (uint32_t cardinality)
	Set the cardinality of the policy. More...
void	on_insert (const Key &key, const CacheItem &item)
	Insertion event handler. More...
void	on_update (const Key &key, const CacheItem &old_item, const CacheItem &new_item)
	Update event handler. More...
void	on_cache_hit (const Key &key, const CacheItem &item)
	Cache hit event handler. More...
void	on_evict (const Key &key, const CacheItem &item)
	Eviction event handler. More...
VictimIterator	victim_begin () const
	Get an iterator to the first item that should be evicted. More...
VictimIterator	victim_end () const
	Get an end iterator. More...

Detailed Description

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

Greedy-Dual-Size-Frequency (GDSF) eviction policy.

Generally, GDSF tries to first evict the items that will be the least costly to reload, while taking into account access frequency. GDSF is implemented using a priority queue sorted by a coefficient computed for each item. Items are then evicted starting with the item with the smallest coefficient.

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.
Cost	A functor taking a a Key& and a const Item<Value>& returning the cost to load this item in cache.

Member Function Documentation

on_cache_hit()

template<class Key , class KeyHash , class Value , class Cost >

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

Cache hit event handler.

Updates the coefficient for this item and changes its position in the priority queue.

Parameters

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

on_evict()

template<class Key , class KeyHash , class Value , class Cost >

void cachemere::policy::EvictionGDSF< Key, KeyHash, Value, Cost >::on_evict	(	const Key &	key,
		const CacheItem &	item
	)

Eviction event handler.

Removes the item from the priority queue.

Parameters

key	The key that was evicted.
item	The item that was evicted.

on_insert()

template<class Key , class KeyHash , class Value , class Cost >

void cachemere::policy::EvictionGDSF< Key, KeyHash, Value, Cost >::on_insert	(	const Key &	key,
		const CacheItem &	item
	)

Insertion event handler.

Computes a coefficient for the item and inserts it in the priority queue.

Parameters

key	The key of the inserted item.
item	The item that has been inserted in cache.

on_update()

template<class Key , class KeyHash , class Value , class Cost >

void cachemere::policy::EvictionGDSF< Key, KeyHash, Value, Cost >::on_update	(	const Key &	key,
		const CacheItem &	old_item,
		const CacheItem &	new_item
	)

Update event handler.

Updates the coefficient for this item and changes its position in the priority queue.

Parameters

key	The key that has been updated in the cache.
old_item	The old value for this key.
new_item	The new value for this key.

set_cardinality()

template<class Key , class KeyHash , class Value , class Cost >

void cachemere::policy::EvictionGDSF< Key, KeyHash, Value, Cost >::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.

victim_begin()

template<class Key , class KeyHash , class Value , class Cost >

auto cachemere::policy::EvictionGDSF< Key, KeyHash, Value, Cost >::victim_begin

Get an iterator to the first item that should be evicted.

Returns

An item iterator.

victim_end()

template<class Key , class KeyHash , class Value , class Cost >

auto cachemere::policy::EvictionGDSF< Key, KeyHash, Value, Cost >::victim_end

Get an end iterator.

Returns

The end iterator.

---

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

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