Least frequently used cache

hi,

welche datenstruktur eignet sich am besten um einen LFU cache zu implementieren?

LG

Skym0sh0

Priority Queue?

Jester

doppelt verkettete liste?

oder (binärer) suchbaum mit doppelt verketteter liste auf den Elementen?

priority queue sortiert nach frequency und hashtable mit iterator auf pq element um einen entry zu finden?

boost::heap::priority_queue<entry, boost::heap::compare<MyClassCompare> > pq;
unordered_map<int, decltype(pq.begin())> ht;

volkard

coder1 schrieb:

priority queue sortiert nach frequency und hashtable mit iterator auf pq element um einen entry zu finden?
boost::heap::priority_queue<entry, boost::heap::compare<MyClassCompare> > pq;
unordered_map<int, decltype(pq.begin())> ht;

Damit bildest Du eine PtrPriorityQueue nach?

ja, boost::priority_queue scheint einen iterator zu providen.

die hashtable soll den lookup schneller machen, dann muss ich nicht durch alle elemente in der priority queue iterieren...

wenn der cache voll ist, dann wird das letzte element in der priority queue mit der kleinesten frequenz geloescht.

die frequenz berechnet sich wie folgt: es gibt einen globaler counter C, welcher alle zugriffe zaehlt. dann hat jedes objekt einen eignen counter start(o), welcher den startwert des globalen counters C uebernimmt, wenn ein neues element erstellt wird. jeder zugriff inkremmentiert einen weiteren localen counter uses(o).
die frequenz ergibt sich wie folgt: frequency = uses(o) / (C - start(o))

any feedback volkard?

Vergleiche mal die Performance deines Ansatzes mit vector + min_element. Da kann es durchaus Überraschungen geben, insbesondere bei kleinen Elementen.

um das min in einem vector zu finden brauch ich ja O(n) in worst case...warum soll das besser sein?

cooky451

Weil O(..) alle Konstanten verschluckt, Konstanten sind aber durchaus nicht irrelevant.

coder1 schrieb:

um das min in einem vector zu finden brauch ich ja O(n) in worst case...warum soll das besser sein?

Ich stelle mir vor, dass du einen Usecounter pro Element hast (n Elemente), den du sehr häufig (k mal) aktualisieren musst, bevor der Usecounter für LFU aussagekräftig wird. Eine Aktualisierung bei vector wäre nur ein Arrayzugriff + increment in k*O(1) während es bei der Priority Queue ein delete + insert in k*O(log n) wäre. Wahrscheinlich ist k ~ 10*n oder k~100*n. Damit käme der vector auf k*O(1) + n = O(n) gegen Priority Queue k*O(log n) = O(n log n).
Hinzu kommen die Konstanten von cooky. Insbesondere wenn die Daten nicht in den Cache passen (des Rechners, nicht dessen was du implementierst) können sequentielle Zugriffe um Faktor 10-100 schneller sein.
Herb Sutter: Modern C++: What You Need to Know (Wesentlicher Inhalt um Minute 40, Stream kaputt, Download geht) oder Kurzform von Bjarne Stroustrup mit unsichtbarem Graphen (weniger eindrucksvoll): Präsentationen, die um sequenzielle Zugriffe = vector vs Random Zugriffe = list gehen und warum vector so viel schneller ist. Ich war daran interessiert ob das hier auch so ist, zumal vector + min_element trivial zu implementieren sein sollte. Wenn deine Elemente nur ein int oder size_t für den Usecount sind sollte vector viel schneller sein. Wenn ein Element aus int Usecount + char[4096] Daten besteht wird es vector ziemlich wahrscheinlich nicht bringen.

Meine Loesung, die ich hier im Einsatz habe nutzt i.W. std::unordered_map fuer die Daten und eine std::list fuer die Zugriffshaeufigkeiten

unordered_map<KEY, pair<VALUE, typename EVICTION_STRATEGY::iteratorType>> cache;

ist Teil der eigentlichen Cache-Klasse

typedef list<pair<KEY, frequencyType>> SCORINGCONTAINER;
typedef typename SCORINGCONTAINER::iterator iteratorType;

ist Teil der Klasse fuer die LFU Eviction Stratgie

Damit geht das Update der Haeufigkeit beim CacheHit schnell (inkrementieren des Zaehlers frequencyType ), allerdings ist das Verdraengen aus dem Cache langsam, weil erst mit min_element das kleinste Element gesucht und dann aus der liste und dem cache entfernt wird.

volkard

coder1 schrieb:

any feedback volkard?

Ach, ich habe das Cachen ganz übersehen.

Jo, dann kannste Hashtable fürs Cachen und Heap für LFU benutzen. Der Heap dürfte nicht dauernd seinen Speicher durchwalken, wenn die Frequenzen einigermaßen nichtgleichverteilt sind.

Wie Jester vorschlägt (binärer) suchbaum (für Cache) mit doppelt verketteter liste (für LFU) auf den Elementen scheint mir genial für LRU.

Deine Rechnung für LFU würde ich wohl nur machen, wenn's der Auftraggeber explizit so wünscht. Sonst hänge ich gern Gedanken nach wie "Jedes Element hat einen Usecounter. Sobald ein Usercounter ein bestimmtes Limit erreicht, werden alle Usecounters durch 2 geteilt.".

Davon ausgehend, dass dein Cache nicht wesentlich dynamisch wächst oder schrumpft bietet sich ein Array an. Ansonsten bei vector bleiben.

const size_t cachesize = ...;
array<key_t, cachesize> keys;
array<counter_t, cachesize> counter;
array<data_t, cachesize> data;

void update(key_t key){ //braucht man häufig, O(log(n))
    //mit einer hashmap schafft man es vielleicht auf O(1)
    counter[lower_bound(cbegin(keys), cend(keys), key) - cbegin(keys)]++;
}

void replaceLFU(data_t &d, key_t key){ //braucht man selten, O(n);
    size_t removepos = min_element(cbegin(counter), cend(counter)) - cbegin(counter);
    size_t insertpos = lower_bound(cbegin(keys), cend(keys), key) - cbegin(keys);
    if (removepos < insertpos){
        copy(begin(counter) + removepos + 1, begin(counter) + insertpos, begin(counter) + removepos);
        copy(begin(data) + removepos + 1, begin(data) + insertpos, begin(data) + removepos);
        copy(begin(keys) + removepos + 1, begin(keys) + insertpos, begin(keys) + removepos);
        *(begin(counter) + insertpos - 1) = 0;
        *(begin(data) + insertpos - 1) = d;
        *(begin(keys) + insertpos - 1) = key;
    }
    else{ //gleiche nochmal mit copy_back oder andersrum
    }
}

Man kann sich noch überlegen, ob data tatsächlich Daten oder Zeiger enthalten soll. Auf jeden Fall sollte lower_bound schneller als eine map sein und der vector wird deutlich schneller als list sein.

Jester

volkard schrieb:

Wie Jester vorschlägt (binärer) suchbaum (für Cache) mit doppelt verketteter liste (für LFU) auf den Elementen scheint mir genial für LRU.

Was daran liegt, dass ich versehentlich "recently" statt "frequently" gelesen habe.

In dem Fall scheint mir der allererste vorschlag doch ganz gut: eine priority queue bzw. Ein heap. Da bei jedem zugriff sich dief requenz nur um 1 erhöht solte das update da schnell sein.

class LFU_Cache {
private:
typedef boost::heap::priority_queue<entry, boost::heap::compare<Comparison>> MyPriQue;
  MyPriQue pq;
  unordered_map<int, decltype(pq.begin())> ht;

public:
  void insert(int key, int value);

};

void LFU_Cache::insert(int key, int value) {  
  auto it = ht.find(key);

  if (it != ht.end()) {
    it->second->local_counter -= 10000; // <--- error: read-only variable is not assignable ... warum funkt das nicht?
    pq.pop();
    ht.erase(it);
  }

  pq.push(entry(key, value, LFU_Cache::global_counter));
  ht.insert(make_pair(key, pq.begin()));
}

die klass entry:

typedef struct entry {
	int key;
	int value;
	int local_counter;
 	int global_counter_start;
	entry(int key_, int value_, int global_counter_start_): key(key_), 
	                                                        value(value_),  
	                                                        local_counter(0), 
	                                                        global_counter_start(global_counter_start_) {}
}entry;

Dsa (Zeit)kritische ist ja nicht das Einfuegen oder lesen im Cache, sondern das Verdrängen eines Elementes aus dem Cache (nebst Anpassung der Verwaltungsstrukturen). Da laeuft es bei LFU auf irgendwas mit std::min_element oder einer entsprechend sortierenden Datenstruktur hinaus