PLearn 0.1
|
Class description: More...
#include <BoundedMemoryCache.h>
Public Types | |
typedef int * | pointer |
Public Member Functions | |
BoundedMemoryCache (int max_memory_=0) | |
void | clear () |
const ValueType * | operator() (const KeyType &key) const |
Try to get value associataed with key. | |
ValueType * | operator() (const KeyType &key) |
void | set (const KeyType &key, const ValueType &value) |
Associate value to key. | |
bool | isCached (const KeyType &key) const |
Check if this key is in cache. This does not change the access priority of the key. | |
int | nElements () const |
int | currentMemory () const |
int | maxMemory () const |
void | setMaxMemory (int new_max_memory) |
float | successRate () |
virtual | ~BoundedMemoryCache () |
void | verifyInvariants () |
Public Attributes | |
DoublyLinkedList< KeyType > * | doubly_linked_list |
int | n_successful_hits |
int | n_failures |
map< KeyType, pair< ValueType, DoublyLinkedListElement < KeyType > * > > | elements |
Protected Member Functions | |
virtual void | removeExcess () |
remove last element until current_memory <= max_memory; | |
virtual void | removeAll () |
remove all elements | |
Protected Attributes | |
int | n_elements |
int | max_memory |
int | current_memory |
Class description:
Similar semantically to a map<KeyType,ValueType>, except that a maximum memory usage can be set, and less frequently and less recently accessed elements that make memory usage go above that limit are dropped. The heuristic for giving more priority to more recently accessed stuff is the 'move-to-front' heuristic. When an entry is read or set it is moved to the front of a list. When the allowed memory has been overrun the last element of the list is dropped. The list is implemented with the new class plearn/base/DoublyLinkedList, a doubly-linked list with removeLast() and moveToFront() methods.
Definition at line 72 of file BoundedMemoryCache.h.
typedef int* PLearn::BoundedMemoryCache< KeyType, ValueType >::pointer |
Definition at line 140 of file BoundedMemoryCache.h.
PLearn::BoundedMemoryCache< KeyType, ValueType >::BoundedMemoryCache | ( | int | max_memory_ = 0 | ) | [inline] |
Definition at line 85 of file BoundedMemoryCache.h.
: n_elements(0), max_memory(max_memory_), current_memory(0), doubly_linked_list(new DoublyLinkedList<KeyType>), n_successful_hits(0), n_failures(0) {}
virtual PLearn::BoundedMemoryCache< KeyType, ValueType >::~BoundedMemoryCache | ( | ) | [inline, virtual] |
Definition at line 189 of file BoundedMemoryCache.h.
References PLearn::clear().
{ clear(); }
void PLearn::BoundedMemoryCache< KeyType, ValueType >::clear | ( | ) | [inline] |
Reimplemented in PLearn::Cache< KeyType, ValueType >.
Definition at line 90 of file BoundedMemoryCache.h.
References PLERROR.
{ /* int mm = max_memory; max_memory = 0; removeExcess(); // this is mostly useful when removeExcess is redefined, e.g. in sub-class Cache max_memory = mm; elements.clear(); */ removeAll(); // this is mostly useful when removeAll is redefined, e.g. in sub-class Cache if (elements.size() != 0) PLERROR("Weird"); }
int PLearn::BoundedMemoryCache< KeyType, ValueType >::currentMemory | ( | ) | const [inline] |
Definition at line 180 of file BoundedMemoryCache.h.
{ return current_memory; }
bool PLearn::BoundedMemoryCache< KeyType, ValueType >::isCached | ( | const KeyType & | key | ) | const [inline] |
Check if this key is in cache. This does not change the access priority of the key.
Reimplemented in PLearn::Cache< KeyType, ValueType >.
Definition at line 178 of file BoundedMemoryCache.h.
int PLearn::BoundedMemoryCache< KeyType, ValueType >::maxMemory | ( | ) | const [inline] |
Definition at line 181 of file BoundedMemoryCache.h.
{ return max_memory; }
int PLearn::BoundedMemoryCache< KeyType, ValueType >::nElements | ( | ) | const [inline] |
Definition at line 179 of file BoundedMemoryCache.h.
{ return n_elements; }
const ValueType* PLearn::BoundedMemoryCache< KeyType, ValueType >::operator() | ( | const KeyType & | key | ) | const [inline] |
Try to get value associataed with key.
If not in cache return 0, else return pointer to value. Recently accessed keys (with set or operator()) are less likely to be removed.
Reimplemented in PLearn::Cache< KeyType, ValueType >.
Definition at line 105 of file BoundedMemoryCache.h.
References PLearn::dbg, and PLERROR.
{ typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::const_iterator it = elements.find(key); if (it==elements.end()) { n_failures++; return 0; } n_successful_hits++; doubly_linked_list->moveToFront(it->second.second); #ifdef BOUNDCHECK if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); if (dbg) verifyInvariants(); #endif return &(it->second.first); }
ValueType* PLearn::BoundedMemoryCache< KeyType, ValueType >::operator() | ( | const KeyType & | key | ) | [inline] |
Reimplemented in PLearn::Cache< KeyType, ValueType >.
Definition at line 122 of file BoundedMemoryCache.h.
References PLearn::dbg, and PLERROR.
{ typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key); if (it==elements.end()) { n_failures++; return 0; } n_successful_hits++; doubly_linked_list->moveToFront(it->second.second); #ifdef BOUNDCHECK if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); if (dbg) verifyInvariants(); #endif return &(it->second.first); }
virtual void PLearn::BoundedMemoryCache< KeyType, ValueType >::removeAll | ( | ) | [inline, protected, virtual] |
remove all elements
Reimplemented in PLearn::Cache< KeyType, ValueType >.
Definition at line 237 of file BoundedMemoryCache.h.
References PLearn::dbg, and PLERROR.
{ while (n_elements) { KeyType& key = doubly_linked_list->last->entry; // current_memory -= sizeInBytes(elements[key]); elements[key].second=0; elements.erase(key); doubly_linked_list->removeLast(); n_elements--; #ifdef BOUNDCHECK if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); if (dbg) verifyInvariants(); #endif } current_memory = 0; }
virtual void PLearn::BoundedMemoryCache< KeyType, ValueType >::removeExcess | ( | ) | [inline, protected, virtual] |
remove last element until current_memory <= max_memory;
Reimplemented in PLearn::Cache< KeyType, ValueType >.
Definition at line 218 of file BoundedMemoryCache.h.
References PLearn::dbg, PLERROR, and PLearn::sizeInBytes().
{ while (current_memory > max_memory) { KeyType& key = doubly_linked_list->last->entry; current_memory -= sizeInBytes(elements[key]); elements[key].second=0; elements.erase(key); doubly_linked_list->removeLast(); n_elements--; #ifdef BOUNDCHECK if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); if (dbg) verifyInvariants(); #endif } }
void PLearn::BoundedMemoryCache< KeyType, ValueType >::set | ( | const KeyType & | key, |
const ValueType & | value | ||
) | [inline] |
Associate value to key.
Recently accessed keys (with set or operator()) are less likely to be removed.
Definition at line 144 of file BoundedMemoryCache.h.
References PLearn::dbg, PLERROR, and PLearn::sizeInBytes().
{ typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key); if (it==elements.end()) { // first time set DoublyLinkedListElement<KeyType>* p=doubly_linked_list->pushOnTop(key); #ifdef BOUNDCHECK if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); #endif pair<ValueType,DoublyLinkedListElement<KeyType>*> el(value,p); elements[key] = el; current_memory += sizeInBytes(el); n_elements++; #ifdef BOUNDCHECK if (dbg) verifyInvariants(); #endif } else { // already there, move it to front of list and update the value ValueType& v = elements[key].first; current_memory += sizeInBytes(value) - sizeInBytes(v); doubly_linked_list->moveToFront(it->second.second); #ifdef BOUNDCHECK if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); #endif v = value; #ifdef BOUNDCHECK if (dbg) verifyInvariants(); #endif } removeExcess(); }
void PLearn::BoundedMemoryCache< KeyType, ValueType >::setMaxMemory | ( | int | new_max_memory | ) | [inline] |
Definition at line 182 of file BoundedMemoryCache.h.
{ max_memory=new_max_memory; removeExcess(); }
float PLearn::BoundedMemoryCache< KeyType, ValueType >::successRate | ( | ) | [inline] |
Definition at line 187 of file BoundedMemoryCache.h.
{ return float(n_successful_hits)/(n_successful_hits + n_failures); }
void PLearn::BoundedMemoryCache< KeyType, ValueType >::verifyInvariants | ( | ) | [inline] |
Definition at line 192 of file BoundedMemoryCache.h.
References PLearn::DoublyLinkedListElement< T >::entry, PLearn::DoublyLinkedListElement< T >::next, PLERROR, and PLearn::DoublyLinkedListElement< T >::previous.
{ if (!doubly_linked_list->last || doubly_linked_list->last->next) PLERROR("something wrong with last element of doubly linked list!"); if (max_memory - current_memory>500) return; typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.begin(); for (;it!=elements.end();++it) { DoublyLinkedListElement<KeyType>* p = it->second.second; if (!p) PLERROR("BoundedMemoryCache::verifyInvariants(): null linked list pointer!"); DoublyLinkedListElement<KeyType>* next = p->next; DoublyLinkedListElement<KeyType>* previous = p->previous; if (previous && previous->next != p) PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (previous->next != element)\n"); if (next && next->previous != p) PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (next->previous != element)\n"); typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator pi = elements.find(p->entry); if (pi->second.second!=p) PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent pointers between map and list\n"); if (pi->first!=p->entry) PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent keys between map and list\n"); } }
int PLearn::BoundedMemoryCache< KeyType, ValueType >::current_memory [protected] |
The current memory used to store the elements
Definition at line 77 of file BoundedMemoryCache.h.
DoublyLinkedList<KeyType>* PLearn::BoundedMemoryCache< KeyType, ValueType >::doubly_linked_list |
Definition at line 79 of file BoundedMemoryCache.h.
map<KeyType, pair<ValueType,DoublyLinkedListElement<KeyType>*> > PLearn::BoundedMemoryCache< KeyType, ValueType >::elements |
the indexed elements. Each entry has (value, pointer into doubly_linked_list)
Definition at line 83 of file BoundedMemoryCache.h.
int PLearn::BoundedMemoryCache< KeyType, ValueType >::max_memory [protected] |
The maximum memory used to store the elements
Definition at line 76 of file BoundedMemoryCache.h.
int PLearn::BoundedMemoryCache< KeyType, ValueType >::n_elements [protected] |
The actual number of elements stored in memory
Definition at line 75 of file BoundedMemoryCache.h.
int PLearn::BoundedMemoryCache< KeyType, ValueType >::n_failures [mutable] |
Number of times operator() was called and entry not found
Definition at line 81 of file BoundedMemoryCache.h.
int PLearn::BoundedMemoryCache< KeyType, ValueType >::n_successful_hits [mutable] |
Number of times operator() was called successfully
Definition at line 80 of file BoundedMemoryCache.h.