Code-Kata: Cache-Klasse. Wer produziert den besten Code

[Dejan Vu]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310431)

So in der Art wäre auch mein Ansatz gewesen, bis ich realisierte, daß er gegen die Vorgabe verstößt (weshalb steht etwas weiter vorn im Thread).

Du irrst . Wahrscheinlichkeiten und Ausnahmen, d.h. konkrete Einzelbeispiele, widersprechen sich nicht.

Wenn in deinem Beispiel der Cache für alle 10 Elemente und 1000 (=10 x 100) Zugriffe einen Treffer erzielt hat, dann ist Quote 100%. Wenn nun ein 11. Element hinzukommt und dafür eines der vorherigen weicht, dann ändert sich zunächst einmal an der Wahrscheinlichkeit eines Treffers gar nichts. Erst die folgenden Zugriffe entscheiden dann, ob die gewählte Strategie gut ist, oder nicht. Und wenn nun nicht mehr die Elemente 1-10 sondern 2-11 benötigt werden, dann liegt die Quote wieder bei 100%.

[idefix2]

Uwe Raabe hat es richtig geschrieben. Es fehlt in deiner Vorgabe eine zeitliche Komponente, ohne die wird keine gute Performance herauskommen (und dein eigener Lösungsansatz ignoriert deine Vorgabe übrigens komplett, der implementiert NUR die zeitliche Komponente).
Das Problem dabei: Wenn ab irgendeinem Zeitpunkt ein anderes (ganz neues) Element als die bisher häufigsten öfter gebraucht wird, dauert es sehr lange, bis das Element im Cache gelassen wird. Zu Beginn ist die "Wahrscheinlichkeit" nahe 0, und das Element wird sehr oft hinausgeworfen (und verursacht dadurch viele cache misses), bis es aufgeholt hat und im Speicher bleiben darf. Deshalb gehört unbedingt auch der Zeitfaktor in irgendeiner Form ins Spiel, in der einfachsten Form z.B., dass ein Element, das neu in den Cache geholt wurde, bei den nächsten n (n deutlich kleiner als die Cachegrösse) Malen, die ein Element aus dem Cache fliegt, geschützt wird.

Elemente, die vor langer Zeit oft benötigt wurden, inzwischen aber längst nicht mehr, behalten nach deiner Vorgabe eine sehr hohe "Wahrscheinlichkeit". Auch dagegen gibt es ein einfaches Mittel:
Für den ganzen Cache wird eine Zugriffsnummer bei jedem Zugriff hochgezählt. Bei jedem Element, auf das zugegriffen wurde, wird zuzätzlich zur um 1 erhöhten Häufigkeit auch die Zugriffsnummer gespeichert. Dann ergibt die Zugriffsnummer des Cache minus Zugriffsnummer eines Elements sein Alter (= wie lange wurde das Element nicht gebraucht). Für die Berechnung, welches Element rausfliegt, wird dann nicht nur die Zugriffshäufigkeit hergenommen, sondern (Zugriffshäufigkeit*a-Alter*b), wobei man mit den Parametern a und b die Gewichtung der beiden Faktoren zueinander optimieren kann.

Und natürlich muss die Häufigkeit auch für die Elemente gespeichert bleiben, die schon aus dem Cache rausgeflogen sind.

[idefix2]

Zitat:

Zitat von Dejan Vu (Beitrag 1310453)

Zitat:

Zitat von Uwe Raabe (Beitrag 1310431)

So in der Art wäre auch mein Ansatz gewesen, bis ich realisierte, daß er gegen die Vorgabe verstößt (weshalb steht etwas weiter vorn im Thread).

Du irrst .

Uwe Raabe hat Recht. Deine Vorgabe verlangt, dass die Häufigkeit der Zugriffe berücksichtigt wird, in deinem Ansatz geht es nur darum, auf welches Element am längsten nicht zugegriffen worden ist, auch wenn davor die Zugriffe sehr häufig waren.

Zitat:

So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden

Eben nicht. Sie enthält vorne die Elemente, die vor kurzem abgefragt wurden. Was in der Tendenz öfter war, darüber speicherst du keinerlei Informationen.

[Daniel]

Es ist doch nur eine Spiel-Aufgabe. Wenn sich herausstellt, dass die Vorgaben unterschiedlich interpretiert werden können, dann legt sie doch einfach für Eure Lösung fest, das dürfte schneller gehen, als sich mit allen auf eine Interpretation zu einigen. Und eine starre Skala, auf der man die "absolut beste" Lösung wird bewerten können, dürfte so oder so schwierig werden.
Ich sehe den Variationen absolut gespannt entgegen.

[Dejan Vu]

Dann scheinen ja mindestens zwei sinnvolle Strategien zu existieren.

Für jede Strategie lassen sich ja Szenarien entwickeln, die den Cache alt aussehen lassen.

Die Zugriffsquote (d.h. Effizienz) ist ja auch abhängig von der Cache-Größe: Beim Beispiel von Uwe reicht es, die Cache-Größe auf 11 zu erhöhen und schon klappt alles wieder.

Ich finde den MRU-Ansatz deshalb sehr charmant, weil er so einfach ist und scheinbar auch sehr effizient: Er findet im SQL-Server Verwendung (zumindest in den älteren Versionen). Nachzulesen bei 'Inside SQL-Server 2000' von Ron Soukup und Kalen Delaney. In einer meiner NoSQL-Versuche war ein solcher Cache im Einsatz und hatte Hitraten von um die 97%. Mir hat das gereicht.

Andere Strategien dürften vielleicht noch effizienter sein, aber die Maxime beim SQL-Server lautet ja eh: RAM, RAM and more RAM (analog dem ultimativen Gegenmittel: Erhöhe die Cache-Größe, bis es passt)

Allen Caches gemein ist übrigens das Fehlen einer Glaskugel, um in die Zukunft zu schauen und dann zu entscheiden, welches Element fliegt.

Um die Strategien jedoch zu vergleichen benötigen wir deterministische Szenarien.
Wie wäre folgende:

Delphi-Quellcode:

N := 10000;
RangeSize := 100;

Cache := TCache.Create(SampleCacheSize); 

Randomize(123);

Range := N div RangeSize; // oder irgend eine andere Zahl
For i:=Range+1 to N-Range do 
  For j:=1 to RangeSize do begin
    Cache.Put(Random (i-Range, i+Range), nil);
    Cache.Get(Random (i-Range, i+Range), Dummy);
  end;

Ich fülle (Put) den Cache also mit einer zufälligen ID innerhalb eines bestimmten Bereiches und lese dann einen zufällig anderen Wert aus diesem Bereich. Nach einigen Versuchen bewege ich den Bereich um eins nach oben.

Eine andere Variante wäre dann z.B.

Delphi-Quellcode:

For i:=Range+1 to N-Range do 
  For j:=i-Range To i+Range-1
    Cache.Put(j, nil);
    Cache.Get(j, Dummy);
  end;

Achtung! Das sind nur Vorschläge. Wer es verbessern oder erweitern will: Nur Zu!

[Captnemo]

Das ist zwar nicht unbedingt mein Thema, aber ich hätte hier noch einen Vorschlag.

Nehmen wir an wir haben 100 Items und einen Cache von 10.
Item[45] wir 99 mal angesprochen, Item[54] wird 50 mal angesprochen. Danach werden 9 andere Items angesprochen. Jetzt müsste also Item[45] hinten rausfallen.
Danach wird aber wieder Item[45] angesprochen, muss es wieder geladen werden und Item[45] fliegt raus.
Die anderen 9 Items liegen nur rum, obwohl sie nur ein mal angesprochen wurde, und sorgen dafür, dass Item[45] und Item[54] trotz ihrer häufigen Verwendung aus dem Cache fliegen.

Ich würde mal versuchen, die Häufigkeit und die Historie eines Objects mit einzubeziehen.

Je Object im Cache kommt ein Zähler hinzu, der der bei Verwendung und Nichtverwendung dessen Wert nach oben oder nach unten verändert wird.
Wird ein Object angesprochen, so wird sein Wert z.B. auf 50 gesetzt. Wird er geladen, wird sein Wert z.B. auf 10 gesetzt. Wird bei eine Cacheanfrage ein Object nicht angesprochen, wird er z.B. um 1 verringert. Wird er bei einer weiteren Cacheanfrage auch nicht angesprochen, wird der Zähler z.B. um 2 veringert. (und möglicherweise so weiter).

Wird Platz benötigt, wird aus dem Cache das Element entfernt, welches den geringsten Wert hat. Wenn es mehrere mit gleichem geringstem Wert gibt, dann halt das älteste.

Auf diese Weise könnte nun also Item[45] und Item[54] trotz der neuen 9 Items im Cache bleiben, außer sie werden einige Zeit nicht benutzt. Die Werte, die gesetzt werden müssen natürlich der Gesamtgröße des Caches angepasst sein.

Ist nur mal so eine Idee. Also nicht steinigen, wenn's ne blöde Idee ist.

Jetzt kann es natürlich sein, dass der Verwaltungsoverhead für die Werte einen möglichen Performancegewinn wieder auffressen.

[Edit] Grad gesehen, dass Idefix2 fast das gleiche geschrieben hat [/Edit]

[Memnarch]

Zitat:

Zitat von idefix2 (Beitrag 1310460)

Zitat:

So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden

Eben nicht. Sie enthält vorne die Elemente, die vor kurzem abgefragt wurden. Was in der Tendenz öfter war, darüber speicherst du keinerlei Informationen.

Der unterschied: ich habe 5 elemente (A, B, C, D, E). 3 Elemente werden maximal gecached.

Bisherige anzahl an abfragungen/einträgen:

A = 10
B = 1
C = 1
---------<cachende>
D = 0
E = 0

Jetzt frage ich E, D und C an. A fällt aus dem cache raus. Bei Abfrageanzahl-Orientiertem Caching sehe das nach meiner Abfrage anders aus:

A = 10
B = 1
C = 2
D = 1
E = 1

was so ended:
A = 10
C = 2
D = 1
-----<cachende>
E = 0
B = 0

[Neutral General]

Ihr alten Theoretiker! :P
Bei nem Kata soll Code produziert werden über den man dann reden kann.
Haut mal in die Tasten und setzt eure Theorie in die Praxis um! ;)

[idefix2]

Zitat:

Zitat von Dejan Vu (Beitrag 1310464)

Für jede Strategie lassen sich ja Szenarien entwickeln, die den Cache alt aussehen lassen.

Natürlich. Im Optimalfall sollte eine Strategie an die typischen Szenarien der konkreten Anwendung angepaßt sein. Im Prinzip geht es um die zwei Kriterien "most recently used" und "most frequently used". Die Strategie, die ich vorgeschlagen habe, ermöglicht es, die beiden Kriterien anwendungsspezifisch auszubalancieren.

Nachdem wahrscheinlich meistens das erste der beiden Kriterien das wichtigere ist, ist Dein einfacherer Ansatz sicher nicht schlecht, bloss hast du im ersten Post als Vorgabe etwas ganz anderes geschrieben.

Vielleicht schaffe ich es übers Wochenende, etwas Code zu produzieren. Hab leider im Moment eine Menge um die Ohren, aber die Fragestellung ist ganz interessant.

Zitat:

Zitat von Neutral General (Beitrag 1310500)

Ihr alten Theoretiker! :P
Bei nem Kata soll Code produziert werden über den man dann reden kann.
Haut mal in die Tasten und setzt eure Theorie in die Praxis um! ;)

Fehler #1 bei sehr vielen Programmierern: Mit dem Codieren anfangen, bevor die Aufgabenstellung klar formuliert ist.

[Neutral General]

Zitat:

Zitat von idefix2 (Beitrag 1310543)

Zitat:

Zitat von Neutral General (Beitrag 1310500)

Ihr alten Theoretiker! :P
Bei nem Kata soll Code produziert werden über den man dann reden kann.
Haut mal in die Tasten und setzt eure Theorie in die Praxis um! ;)

Fehler #1 bei sehr vielen Programmierern: Mit dem Codieren anfangen, bevor die Aufgabenstellung klar formuliert ist.

Die Aufgabenstellung wurde klar formuliert. Es wurde ein Interface vorgeben mit Methoden die gefüllt werden müssen. Am Ende muss eine Cache-Klasse rauskommen der die im Ausgangspost formulierten Kriterien erfüllt.

Die meisten sind hier schon über mögliche Implementierungen am diskutieren wie verrückt.
Warum implementieren diese Leute nicht einfach mal ihre Ideen? Habe ich auch gemacht. Das Ergebnis mag nicht ideal sein, aber das ist ja gerade Sinn der Sache. Denn dann kann man darüber reden was man konkret besser machen könnte. Und warum die Implementierung von X (in gewissen Situationen) besser ist als die von Y.

Hier wird nur um den heißen Brei herumgeredet. Niemand wird daran gehindert sich bevor er loslegt ein paar Gedanken darüber zu machen. Wie viel Zeit jeder vorher zum Nachdenken und Planen seiner Idee verwendet ist ja Sache des Einzelnen.