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

[Dejan Vu]

Moin

Ausgehend von dieser Anregung möchte ich alle Programmierer auffordern, für folgende Problemstellung den aus ihrer Sicht bestmöglichen Code zu erstellen, und zwar unter den Gesichtspunkten: Lesbarkeit und Performance.

Ich benötige einen Cache, der Objekte verwaltet, die über einen eindeutigen Bezeichner (ID) identifiziert werden können. Der Cache soll maximal N Elemente im Speicher halten. Dabei soll die Wahrscheinlichkeit eines Treffers im Cache umso höher sein, je häufiger ich ein Element verwende.

Obwohl so eine Klasse nach Generics schreit, wollen wir darauf verzichten und als ID-Type einen Integer verwenden. Der Cache soll beliebige TObject-Referenzen verwalten.

Die Klasse (Interface) sieht so aus:

Delphi-Quellcode:

Type
  TCache = Class
  //... was auch immer 
  public
     Constructor Create (MaxSize : Integer);
     Function Contains (ID : Integer) : Boolean;
     Function Get (ID : Integer) : TObject;
     Procedure Put (ID : Integer; Item : TObject);
     Procedure Remove(ID : Integer);
     Property MaxSize : Integer Read GetSize;
     Property CurrentNumberOfElements : Integer Read GetCurrentNumberOfElements;
  end;

Als Verwendung kann man sich einen Lademechanismus vorstellen:

Delphi-Quellcode:

Procedure Load (ID : Integer; var item : TItem);
Begin
  If Cache.Contains (ID) then 
    item := Cache.Get (ID)
  else begin
    item := LoadFromExternalResource(ID);
    Cache.Put (ID, item);
  end
end;

Ich möchte naturgemäß die Anzahl der Aufrufe von 'LoadFromExternalResource' verringern, so gut es eben geht. Die ExternalResource ist mindestens 1000x langsamer als der Cache. Insofern wird kein Assembler benötigt.

So, bin gespannt, was dabei rauskommt.

[baumina]

Derjenige der gewinnt wird dann zum DP-Programmiergott gekrönt :stupid:

[Uwe Raabe]

Gibt es eine TestSuite, die die Korrektheit der Klasse an sich und die Einhaltung der Vorgaben überprüft?

Gerade bei der Forderung

Zitat:

Dabei soll die Wahrscheinlichkeit eines Treffers im Cache umso höher sein, je häufiger ich ein Element verwende.

sehe ich eine gewisse Problematik für die Implementation. Nehmen wir mal die maximale Anzahl der Elemente im Cache mit 10 an und jedes Element ist über 100x verwendet worden. Jetzt wird ein elftes Element "X" angefordert und kommt in den Cache (Put). Dafür muss eines der vorhandenen 10 Elemente (nennen wir es "Y") aber weichen. Nun haben wir den Fall, daß Element X im Cache ist, obwohl es nur einmal verwendet wurde, Element Y trotz seiner über 100 Verwendungen aber nicht. Das widerspricht eindeutig der Forderung, nach der Element X wegen der geringeren Verwendung gar nicht in den Cache gehört.

Man kann sich jetzt mindestens zwei Szenarien vorstellen:

1. Element Y wird nicht mehr gebraucht, X aber schon
2. Die Elemente X und Y werden gleichmäßig verwendet

Im Fall von 1 würde das Rauswerfen von Y und das Aufnehmen von X passen. Bei Fall 2 wird es wohl eine Art Ping-Pong zwischen X und Y geben, bei dem das eine Element das andere immer wieder rausschmeisst, solange die anderen Cache-Bewohner eine höhere Verwendungszahl aufweisen. Die obige Betrachtung kann analog auf die anderen Cache-Bewohner erweitert werden.

Die Forderung, daß die Treffer-Wahrscheinlichkeit mit der Häufigkeit der Verwendung (in der Vergangenheit) gekoppelt wird, kann also zu einer erheblichen Degradation des Cache führen. Hier fehlt irgendwie noch eine Zeitkomponente.

[TiGü]

Auch wenn ich weiß, dass nicht alle Anforderungen erfüllt sind, will ich doch einen ersten Versuch posten.
Denn in Sachen Lesbarkeit ist durch die Verwendung von System.Contnrs.TObjectList kaum was zu verbessern.
Zwar wäre ein Nachbau eines Dictionarys vielleicht zielführender, aber die anderen dürfen auch gerne ran. :-D

Delphi-Quellcode:

unit Code.Kata.Cache;

interface

uses
  System.SysUtils,
  System.Contnrs,
  System.Classes,
  System.Math;

type
  TCache = class
  strict private
    FObjectList : System.Contnrs.TObjectList;
  private
    function GetCurrentNumberOfElements : Integer;
    function GetSize : Integer;
  public
    constructor Create(MaxSize : Integer);
    function Contains(ID : Integer) : Boolean;
    function Get(ID : Integer) : TObject;
    procedure Put(ID : Integer; Item : TObject);
    procedure Remove(ID : Integer);
    property MaxSize : Integer read GetSize;
    property CurrentNumberOfElements : Integer read GetCurrentNumberOfElements;
  end;

implementation

{ TCache }

function TCache.Contains(ID : Integer) : Boolean;
begin
  Result := Get(ID) <> nil;
end;

constructor TCache.Create(MaxSize : Integer);
begin
  FObjectList := System.Contnrs.TObjectList.Create(True);
  FObjectList.Capacity := MaxSize;
end;

function TCache.Get(ID : Integer) : TObject;
begin
  Result := nil;
  if InRange(ID, 0, FObjectList.Count - 1) then
  begin
    Result := FObjectList.Items[ID];
  end;
end;

function TCache.GetCurrentNumberOfElements : Integer;
begin
  Result := FObjectList.Count;
end;

function TCache.GetSize : Integer;
begin
  Result := FObjectList.Capacity;
end;

procedure TCache.Put(ID : Integer; Item : TObject);
begin
  if ID <> -1 then
  begin
    FObjectList.Add(Item)
  end
  else
  begin
    FObjectList.Insert(ID, Item);
  end;
end;

procedure TCache.Remove(ID : Integer);
begin
  FObjectList.Delete(ID);
end;

end.

[Mavarik]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310274)

Die Forderung, daß die Treffer-Wahrscheinlichkeit mit der Häufigkeit der Verwendung (in der Vergangenheit) gekoppelt wird, kann also zu einer erheblichen Degradation des Cache führen. Hier fehlt irgendwie noch eine Zeitkomponente.

Der Cache mag ja ggf. "nur" 10 Elemente halten, aber die Statistik welche Elemente in den Cache kommen muss mehr Elemente kennen/können und diese auch historisch speichern...

[Uwe Raabe]

Zitat:

Zitat von Mavarik (Beitrag 1310277)

Zitat:

Zitat von Uwe Raabe (Beitrag 1310274)

Die Forderung, daß die Treffer-Wahrscheinlichkeit mit der Häufigkeit der Verwendung (in der Vergangenheit) gekoppelt wird, kann also zu einer erheblichen Degradation des Cache führen. Hier fehlt irgendwie noch eine Zeitkomponente.

Der Cache mag ja ggf. "nur" 10 Elemente halten, aber die Statistik welche Elemente in den Cache kommen muss mehr Elemente kennen/können und diese auch historisch speichern...

Ich wollte eigentlich darauf hinaus, daß man eher Wert auf die zuküftige Verwendung der Elemente abzielt, als auf die vergangene. Selbst mit der erweiterten Statistik brauche ich erst 100 Zugriffe bis das neue Element in den Cache kommt, wobei selbst nicht mehr benötigte Elemente noch zu lange im Cache bleiben. Um 10 Elemente mit Verwendung 100 aus dem Cache zu werfen bedarf es mindestens 10 anderer Elemente mit jeweils auch 100 Zugriffen. Das sind über 1000 Cache-Misses, die man eigentlich vermeiden möchte. Man rechne das mal mit realistischeren Cache-Größen und Cache-Hits hoch. Der Effekt verschlimmert sich noch mit einer längeren Verwendung des Cache.

Ich will hier jetzt auch keine Diskussion über Cache-Architekturen losbrechen, aber mit den vorhandenen Rahmenbedinungen ist eine Bewertung der vorgelegten Lösungen reine Geschmackssache. Deswegen meine Eingangsfrage nach der Testsuite, mit der eine objektive Beurteilung zumindest möglich wäre.

[Neutral General]

Hi,

Das ist mein Versuch:

Delphi-Quellcode:

type
  TCache = class
  private
    FMaxSize: Integer;
    FCacheDict: TDictionary<Integer, TObject>;
    FCacheIDs: TList<Integer>;
    procedure Renew(ID: Integer);
    procedure CleanCache;
    function GetCurrentNumberOfElements: Integer;
    function GetSize: Integer;
  public
    constructor Create (MaxSize : Integer);
    destructor Destroy; override;
    function Contains (ID : Integer) : Boolean;
    function Get (ID : Integer) : TObject;
    procedure Put (ID : Integer; Item : TObject);
    procedure Remove(ID : Integer);
    property MaxSize : Integer Read GetSize;
    property CurrentNumberOfElements : Integer Read GetCurrentNumberOfElements;
  end;

implementation

{ TCache }

procedure TCache.CleanCache;
var i: Integer;
begin
  for i := FCacheIDs.Count-1 downto FMaxSize do
  begin
    FCacheDict.Remove(FCacheIDs[i]);
    FCacheIDs.Delete(i);
  end;
end;

function TCache.Contains(ID: Integer): Boolean;
begin
  Result := FCacheDict.ContainsKey(ID);
end;

constructor TCache.Create(MaxSize: Integer);
begin
  inherited Create;
  FMaxSize := MaxSize;
  FCacheDict := TDictionary<Integer, TObject>.Create;
  FCacheIDs := TList<Integer>.Create;
end;

destructor TCache.Destroy;
begin
  FreeAndNil(FCacheDict);
  FreeAndNil(FCacheIDs);
  inherited;
end;

function TCache.Get(ID: Integer): TObject;
begin
  if Contains(ID) then
  begin
    Result := FCacheDict[ID];
    Renew(ID);
  end
  else
    raise EListError.CreateFmt('Das Element mit der ID %d ist nicht im Cache enthalten!', [ID]);
end;

function TCache.GetCurrentNumberOfElements: Integer;
begin
  Result := FCacheDict.Count;
end;

function TCache.GetSize: Integer;
begin
  Result := FMaxSize;
end;

procedure TCache.Put(ID: Integer; Item: TObject);
begin
  if not Contains(ID) then
  begin
    FCacheIDs.Insert(0, ID);
    FCacheDict.Add(ID, Item);
    CleanCache();
  end
  else
    Renew(ID); // Evtl eher ne Exception? Ist Geschmackssache denke ich.
end;

procedure TCache.Remove(ID: Integer);
begin
  FCacheIDs.Remove(ID);
  FCacheDict.Remove(ID);
end;

procedure TCache.Renew(ID: Integer);
var OldIndex: Integer;
begin
  OldIndex := FCacheIDs.IndexOf(ID);
  if OldIndex <> -1 then
    FCacheIDs.Move(OldIndex, 0);
end;

[Uwe Raabe]

Zitat:

Zitat von TiGü (Beitrag 1310276)

Auch wenn ich weiß, dass nicht alle Anforderungen erfüllt sind, will ich doch einen ersten Versuch posten.

Dein Ansatz hat aber ein paar klitzekleine Denkfehler:

- Die Capacity der Liste wir automatisch erhöht, wenn der Count sie überschreitet. Damit wächst deine Liste über den anfänglichen MaxSize-Wert hinaus.

- Die ID muss nicht zwingen mit dem Index in der Liste identisch sein. Der ändert sich nämlich beim Löschen eines Elements in der Mitte für alle folgenden Elemente. Diese wären dann nicht mehr über ihre ursprüngliche ID erreichbar. Man bekommt dann also entweder das falsche Element oder legt ein Element nochmal im Cache ab, obwohl es schon da ist.

Das ist eben der Unterschied zwischen einer Liste und einem Dictionary.

[Der schöne Günther]

Was seid ihr alle so schnell? Ich hätte immer häppchenweise was daran gemacht und wäre frühestens zum Wochenende fertig :o

[Mavarik]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310278)

Ich will hier jetzt auch keine Diskussion über Cache-Architekturen losbrechen, aber mit den vorhandenen Rahmenbedinungen ist eine Bewertung der vorgelegten Lösungen reine Geschmackssache. Deswegen meine Eingangsfrage nach der Testsuite, mit der eine objektive Beurteilung zumindest möglich wäre.

Obwohl das ein Interessantes Thema ist...

Eine Testsuite wäre Cool... Um Cache-Treffer und Performance zu ermitteln...

[Mavarik]

Zitat:

Zitat von Der schöne Günther (Beitrag 1310282)

Was seid ihr alle so schnell? Ich hätte immer häppchenweise was daran gemacht und wäre frühestens zum Wochenende fertig :o

Zu schnell... Auf jeden Fall...

Darf das Vorgabe Objekt auch umgestellt werden? Es ist für mich vom System schon falsch...
Wer will schon ein Cache den er "per Hand" ansprechen muss...

Der Cache sollte so funktionieren, dass er bei Ansprache eines Objectes automatisch arbeiten kann...

[TiGü]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310281)

Zitat:

Zitat von TiGü (Beitrag 1310276)

Auch wenn ich weiß, dass nicht alle Anforderungen erfüllt sind, will ich doch einen ersten Versuch posten.

Dein Ansatz hat aber ein paar klitzekleine Denkfehler:

Logo, so wirklich gelöst ist das natürlich nicht.

Am einfachsten würde ich das so lösen: Die Systems.Generics.Collections.TDictionary-Klasse nehmen, kopieren und alles Generische entfernen, damit es mit Delphi 7 kompilierbar wird.
An den Stellen (z. B. Add), wo auf den FGrowThreshold geprüft wird, zusätzlich die MaxSize mit ins Spiel bringen.

Fragen:
Was soll passieren, wenn die MaxSize erreicht wird und man weitere Elemente hinzufügt? Solls eine Exception geben?
Was soll passieren, wenn ich das selbe (!) Objekt unter verschiedenen Schlüsseln hinzufüge?
Welches Element soll eigentlich zurückgeben werden, wenn ich hinter einen Schlüssel 2..N Elemente gespeichert habe?

Ich verlange auch einen Testfall!

[Uwe Raabe]

Zitat:

Zitat von TiGü (Beitrag 1310288)

damit es mit Delphi 7 kompilierbar wird.

Ist das etwa eine Vorgabe? :shock:

[TiGü]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310290)

Zitat:

Zitat von TiGü (Beitrag 1310288)

damit es mit Delphi 7 kompilierbar wird.

Ist das etwa eine Vorgabe? :shock:

Habe ich wegen folgenden Satz und dem Profil von Dejan Vu mal angenommen:

Zitat:

Zitat von Dejan Vu (Beitrag 1310261)

Obwohl so eine Klasse nach Generics schreit, wollen wir darauf verzichten und als ID-Type einen Integer verwenden. Der Cache soll beliebige TObject-Referenzen verwalten.

[TRomano]

In der Praxis würde ich auch ein TDictionary nehmen und die Größe halt im Code auf MaxSize begrenzen. Ich würde auch nebenbei eine Statistik mit den den Aufrufen (Hits) führen und nur bei Überschreitung von MaxSize das Element mit den wenigsten Hits löschen, um das neue einzufügen. Ist aber vielleicht am Thema vorbei ...

[BUG]

Zitat:

Zitat von TRomano (Beitrag 1310294)

Ich würde auch nebenbei eine Statistik mit den den Aufrufen (Hits) führen und nur bei Überschreitung von MaxSize das Element mit den wenigsten Hits löschen, um das neue einzufügen. Ist aber vielleicht am Thema vorbei ...

Das ist eben die Frage: Geht es hier nur um die saubere Umsetzung von Cache-Verdrängungsstrategien oder auch um deren Auswahl. Für das zweite gibt es Unmengen an wissenschaftlicher Literatur. Afaik geht das aber an der Zielstellung von so einem Kata vorbei :gruebel:
Vielleicht sollte man eine Strategie vorgeben.

[Stevie]

[OT] Fiel mir grad so ein, als ich das hier las: http://martinfowler.com/bliki/TwoHardThings.html [/OT]

[Dejan Vu]

Wo hast Du das denn schon wieder her :lol:

Ich hatte meinen Ansatz mit der MRU-Strategie ('Most Recently Used') umgesetzt, so wie sie im SQL-Server zum Einsatz kommt. Sie ist verblüffend einfach.

In einer Dictionary werden die gecachten Objekte vorgehalten. Zusätzlich sind sie in einer verketteten Liste verbunden. Wird der Cache zu voll, werden die Items, die am Ende der Liste sind, entfernt (aus der Liste und dem Dictionary).

Wenn ein Item eingefügt wird, kommt es an den Anfang der Liste. Ebenso, wenn ein Item abgefragt wird.
So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden und hinten sind eher die Elemente, die schon länger keine Sau mehr interessieren. Und das sind dann genau die, die verschwinden.

Das kann man dann alles wunderbar testen.

Bezüglich der 'Vorgaben'... Ich habe einfach mal angefangen. Und der kleinste Nenner wäre etwas ohne Generics. Ich denke, eine entsprechende Implementierung ist davon unabhängig, aber sinnvoller wäre natürlich eine, die wirklich wiederverwendbar wäre, und das geht nun mal nur mit Generics.

Bezüglich der Testsuite... Das wäre wirklich optimal, aber ich hab keine ;-(

Ich poste später vielleicht meinen Ansatz. Nur sitze ich bei 36°C und da denkt man nicht direkt daran, alten Code rauszukramen und zu reinigen.

[idefix2]

Zitat:

Zitat von Mavarik (Beitrag 1310284)

Zu schnell... Auf jeden Fall...

Darf das Vorgabe Objekt auch umgestellt werden? Es ist für mich vom System schon falsch...
Wer will schon ein Cache den er "per Hand" ansprechen muss...

Der Cache sollte so funktionieren, dass er bei Ansprache eines Objectes automatisch arbeiten kann...

Ja, das sehe ich auch so.
Beim Zugriff auf ein Element, das nicht im Cache ist, sollte das Nachladen meines Erachtens durch die Klasse selbst erledigt werden - z.B. durch eine Callback-Routine, die beim Create übergeben wird.

[Uwe Raabe]

Zitat:

Zitat von Dejan Vu (Beitrag 1310417)

Wenn ein Item eingefügt wird, kommt es an den Anfang der Liste. Ebenso, wenn ein Item abgefragt wird.
So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden und hinten sind eher die Elemente, die schon länger keine Sau mehr interessieren. Und das sind dann genau die, die verschwinden.

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). Schreib doch die Vorgabe einfach um:

Zitat:

Der Cache soll die maximal N zuletzt verwendeten Elemente im Speicher halten.

Der Satz mit Wahrscheinlichkeit und häufiger kann dann entfallen. Damit ist die Cache-Strategie klar definiert und es kommt nur noch auf die Implementierung an.

[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.

[Namenloser]

Ich geb mal meinen Senf dazu. Bin jetzt nicht wirklich glücklich über den ganzen Boilerplate-Code, aber ich kann ja auch nichts dafür, dass es keine gescheite Standardlib gibt (oder hat Delphi inzwischen eine verkettete Liste? Habe nichts gefunden).

Habe den Code nicht getestet, da ich kein Delphi mehr habe, also habe ich bestimmt irgendwo was übersehen. Aber es geht ja eher um den Ansatz, denke ich.

Ein paar Worte zu meinen Designentscheidungen:
- Ich habe es jetzt mal so interpretiert, dass es ein einfacher MRU-Cache sein soll.
- Ich prüfe nicht explizit ob die Aufrufe gültig sind (z.B. ob bei Get der Key auch wirklich existiert) und werfe daher auch keine Exceptions. Denn offensichtlich ist die Schnittstelle so angelegt, dass der Benutzer vorher selbst mit Contain prüfen soll, ob der Key existiert. Wenn die Klasse selber es dann noch mal prüfen würde, würde doppelt geprüft. Deswegen habe ich die Prüfungen nur als nur Assertions drin. Die ganze Schnittstelle ist meiner Meinung nach nicht optimal (die von TDictionary übrigens auch nicht), aber war ja so vorgegeben, also muss man das beste daraus machen.
- Edit: Achso, und falls sich jemand wundert: Ich verwende grundsätzlich (fast) nie private sondern immer protected (bis auf sehr wenige Ausnahmen, bei denen es wirklich gute Gründe gibt, die dagegen sprechen). Könnt ihr meinetwegen schlecht finden, ist mir aber egal :stupid:

Delphi-Quellcode:

  { TLinkedListItem }

  TLinkedListItem<T> = class
  protected
    FValue: T;
    FPrev: TLinkedListItem<T>;
    FNext: TLinkedListItem<T>;
  public
    constructor Create;
    constructor Create(Value: T);
    property Value: T read FValue write FValue;
    property Next: TLinkedListItem<T> read FNext;
    property Prev: TLinkedListItem<T> read FPrev;
  end;

  { TLinkedList }

  TLinkedList<T> = class
  protected
    FSentinel: TLinkedListItem<T>;
    function GetFirst: TLinkedListItem<T>;
    function GetLast: TLinkedListItem<T>;
  public
    constructor Create;
    destructor Destroy; override;
    procedure InsertBefore(Item: TLinkedListItem<T>; Successor: TLinkedListItem<T>);
    function Extract(Item: TLinkedListItem<T>): TLinkedListItem<T>;
    property First: TLinkedListItem<T> read GetFirst;
    property Last: TLinkedListItem<T> read GetLast;
  end;

  { TCache }

  TCache = class
  protected type
    TKeyValuePair = record
      Key: Integer;
      Value: TObject;
    end;

    TCacheItem = TLinkedListItem<TKeyValuePair>;
    TCacheItemList = TLinkedList<TKeyValuePair>;
  protected
    FMaxSize: Integer;
    FMRU: TCacheItemList;
    FMap: TDictionary<Integer, TCacheItem>;

    function GetCurrentNumberOfElements: Integer;
    function GetSize: Integer;

    function MakePair(Key: Integer; Value: TObject): TKeyValuePair;

    procedure Bump(Item: TCacheItem);
    procedure Evict(Item: TCacheItem);
  public
    constructor Create(MaxSize: Integer);
    destructor Destroy; override;
    function Contains(ID: Integer): Boolean;
    function Get(ID: Integer): TObject;
    procedure Put(ID: Integer; Item: TObject);
    procedure Remove(ID: Integer);
    property MaxSize: Integer Read FMaxSize;
    property CurrentNumberOfElements : Integer Read GetCurrentNumberOfElements;
  end;

implementation

{ TLinkedListItem }

constructor TLinkedListItem<T>.Create;
begin
  FNext := Self;
  FPrev := Self;
end;

constructor TLinkedListItem<T>.Create(Value: T);
begin
  Create;
  Self.Value := Value;
end;

{ TLinkedList }

constructor TLinkedList<T>.Create;
begin
  FSentinel := TLinkedListItem<T>.Create;
end;

destructor TLinkedList<T>.Destroy; override;
begin
  FSentinel.Free;
end;

function TLinkedList<T>.GetFirst: TLinkedListItem<T>;
begin
  Result := FSentinel.Next;
end;

function TLinkedList<T>.GetLast: TLinkedListItem<T>;
begin
  Result := FSentinel.Prev;
end;

procedure TLinkedList<T>.InsertBefore(Item: TLinkedListItem<T>;
  Successor: TLinkedListItem<T>);
begin
  Extract(Successor);
  Item.Next := Successor;
  Item.Prev := Successor.Prev;
  Item.Next.Prev := Item;
  Item.Prev.Next := Item;
end;

function TLinkedList<T>.Extract(Item: TLinkedListItem<T>): TLinkedListItem<T>;
begin
  Item.Prev.Next := Item.Next;
  Item.Next.Prev := Item.Prev;
  Item.Prev := Item;
  Item.Next := Item;
  Result := Item;
end;

{ TCache }

constructor TCache.Create(MaxSize: Integer);
begin
  FMaxSize := MaxSize;
  FMap := TDictionary<Integer, TCacheItem>.Create;
  FMRU := TCacheItemList.Create;
end;

destructor TCache.Destroy; override;
begin
  while (NumberCurrentNumberOfElements > 0) do
    Evict(FMRU.First);
  FMRU.Free;
  FMap.Free;
end;

function TCache.GetCurrentNumberOfElements: Integer;
begin
  Result := FMap.Count;
end;

function TCache.MakePair(Key: Integer; Value: TObject): TKeyValuePair;
begin
  Result.Key := Key;
  Result.Value := Value;
end;

procedure TCache.Bump(Item: TCacheItem);
begin
  FMRU.InsertBefore(CacheItem, FMRU.First);
end;

procedure TCache.Evict(Item: TCacheItem);
begin
  FMap.Remove(CacheItem.Value.Key);
  FMRU.Extract(CacheItem);

  CacheItem.Value.Value.Free;
  CacheItem.Free;
end;

function TCache.Contains(ID: Integer): Boolean;
begin
  Result := FMap.ContainsKey(ID);
end;

function TCache.Get(ID: Integer): TObject;
var
  CacheItem: TCacheItem;
begin
  Assert(Contains(ID));

  CacheItem := FMap[ID];
  Bump(CacheItem);
  Result := CacheItem.Value.Value;
end;

procedure TCache.Put(ID: Integer; Item: TObject);
var
  CacheItem: TCacheItem;
begin
  Assert(not Contains(ID));

  if GetCurrentNumberOfElements >= FMaxSize then
    Evict(FMRU.Last);

  CacheItem := TCacheItem.Create(MakePair(ID, Item));
  FMap[ID] := CacheItem;
  Bump(CacheItem);
end;

procedure TCache.Remove(ID: Integer);
begin
  Assert(Contains(ID));
  Evict(FMap[ID]);
end;

[idefix2]

Hier mein erster Versuch.

Das Interface der Klasse habe ich bewusst etwas anders gestaltet als in der Vorgabe: Die Klasse kümmert sich sowohl umd das Nachladen von Objekten aus dem externen Speicher als auch um das externe Speichern veränderter Daten.
Dazu müssen ihr beim Create zwei Routinen übergeben werden, die das Laden und Speichern der Daten erledigen. Das Programm, das den Cache dann verwendet, holt alle Daten aus der Cache Klasse und schreibt Veränderungen auch nur in die Cache Klasse.

Für die aktuellen Cacheelemente sollte wohl zusätzlich noch eine nach dem "Hinauswurfkriterium" sortierte Liste verwaltet werden (oder sogar statt des TDictionary, aber dadurch würde das Auffinden der im Cache vorhandenen Elemente wieder langsamer), damit man nicht alle Elemente durchgehen muss, wenn ein Element aus dem Cache zu entfernen ist, um herauszufinden, welches weggehört. Eine einfache verkettete Liste, wie sie namenloser in seinem Algorithmus verwendet, bringt nicht viel, weil man dann die verkettete Liste trotzdem immer durchgehen muss, um das an Stelle des hinausgeworfenen Elements hinzukommende neue Element an der richtigen Stelle einzufügen, das ist nämlich auch nicht unbedingt am Ende der Liste.

Die gespeicherte Zugriffshäufigkeit eine Elements wird beim Entfernen des Elements aus dem Cache halbiert, damit sich uralte hohe Zugriffshäufigkeiten weniger stark auswirken.

Delphi-Quellcode:

unit CacheUnit;

interface

uses Generics.Collections;

Type
  // Callback zum Laden eines externen Objekts, wenn es noch nicht im Cache ist
  TLoadFunction = function (key: integer): TObject;
  // Callback zum externen Speichern eines Objekts
  TSaveFunction = procedure (key: integer; Obj: TObject);

  TCache = Class
  type
     TItem = record
        LastAccess: integer;
        AccessCount: integer;
        end;
  private
     FCurrentSize: Integer;
     FCache: array of TObject;
     FWeightTime: integer;
     FWeightFrequency: integer;
     FLoadObject: TLoadfunction;
     FSaveObject: TSavefunction;
     FCurrentAccess: integer;
     FAllItems: TDictionary<integer,TItem>;      // enthält Nutzungsdaten der Elemente
     FCachedItems: TDictionary<integer,integer>; // Enthält Index der Elemente im Cache

     FHitCount: integer;
     FReadCount: integer;

     function GetMaxSize: integer;
     function FindPlaceInCache: integer;
     procedure RegisterAccess(ID: integer);
     function GetHitPercentage: integer;

  public
     Constructor Create (MaxSize : Integer; WeightTime, WeightFrequency: integer;
          LoadObject: TLoadfunction; SaveObject: TSaveFunction);
     Destructor Destroy;
     Function Get (ID : Integer) : TObject;
     Procedure Put (ID : Integer; Obj : TObject);
     Property MaxSize : Integer Read GetMaxSize;
     Property CurrentNumberOfElements : Integer Read FCurrentSize;
     Property HitPercentage: integer Read GetHitPercentage;
  end;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
implementation
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////


constructor TCache.Create(MaxSize: Integer; WeightTime, WeightFrequency: integer;
     LoadObject: TLoadFunction; SaveObject: TSaveFunction);
begin
  inherited create;
  SetLength(FCache,MaxSize);
  FLoadObject := LoadObject;
  FSaveObject := SaveObject;
  FAllItems := TDictionary<integer,TItem>.Create;
  FCachedItems := TDictionary<integer,integer>.Create;
  FWeightTime:= WeightTime;
  FWeightFrequency:= WeightFrequency;
end;

destructor TCache.destroy;
begin
  FCachedItems.free;
  FAllItems.free;
  inherited;
end;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
// TCache.GetMaxSize und GetHitPercentage
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

function TCache.GetMaxSize: integer;
begin
Result:=Length(FCache);
end;

function TCache.GetHitPercentage: integer;
begin
if FReadCount=0
then Result:=0
else Result:=FHitCount * 100 div FReadCount;
end;


////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
// Platz im Cache finden und nötigenfalls freimachen
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

function TCache.FindPlaceInCache: integer;
var
  Key, KeyToRemove: integer;
  Worst,Kriterium: integer;
  Item: TItem;
begin
if FCurrentSize<Length(FCache) // noch Platz im Cache
then begin 
     result:=FCurrentSize; 
     inc(FCurrentSize); 
     exit 
     end;

Worst:=FCurrentAccess*FWeightFrequency;
for Key in FCachedItems.Keys do
    begin
    with FAllItems[Key] do
         Kriterium:=AccessCount*FWeightFrequency-(FCurrentAccess-LastAccess)*FWeightTime;
    if Kriterium<Worst
    then begin Worst:=Kriterium;
         KeyToRemove:=key;
         Result:=FCachedItems[key];
         end;
    end;

FCachedItems.Remove(KeytoRemove);
Item:=FAllItems[KeyToRemove];
Item.AccessCount:=Item.AccessCount div 2;
FAllItems.AddOrSetValue(KeyToRemove,Item);
end;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
// TCache.Get und Put
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

procedure TCache.RegisterAccess(ID: integer);
var
  item: TItem;
begin
  inc(FCurrentAccess);
  if FAllItems.ContainsKey(ID)
  then begin item:=FAllItems[ID]; inc(Item.AccessCount) end
  else item.Accesscount:=1;
  item.LastAccess:=FCurrentAccess;
  FAllItems.AddOrSetValue(ID,Item);
end;

function TCache.Get(ID: Integer): TObject;
var
  idx: integer;
begin
  inc(FReadCount);
  if FCachedItems.TryGetValue(ID, idx)
  then inc(FHitCount)
  else begin
       idx:=FindPlaceInCache;
       FCache[idx]:=FLoadObject(ID);
       FCachedItems.Add(ID,idx);
       end;
  RegisterAccess(ID);
  Result:=FCache[idx];
end;


procedure TCache.Put(ID: Integer; Obj: TObject);
var
  idx: integer;
begin
  FSaveObject(ID, Obj);
  inc(FCurrentAccess);
  if not FCachedItems.TryGetValue(ID, idx)
  then begin
       idx:=FindPlaceInCache;
       FCachedItems.Add(ID,idx)
       end;
  FCache[idx]:=Obj;
  RegisterAccess(ID);
end;

end.

[Namenloser]

Zitat:

Zitat von idefix2 (Beitrag 1310562)

Für die aktuellen Cacheelemente sollte wohl zusätzlich noch eine nach dem "Hinauswurfkriterium" sortierte Liste verwaltet werden (oder sogar statt des TDictionary, aber dadurch würde das Auffinden der im Cache vorhandenen Elemente wieder langsamer), damit man nicht alle Elemente durchgehen muss, wenn ein Element aus dem Cache zu entfernen ist, um herauszufinden, welches weggehört. Eine einfache verkettete Liste, wie sie namenloser in seinem Algorithmus verwendet, bringt nicht viel, weil man dann die verkettete Liste trotzdem immer durchgehen muss, um das an Stelle des hinausgeworfenen Elements hinzukommende neue Element an der richtigen Stelle einzufügen, das ist nämlich auch nicht unbedingt am Ende der Liste.

Hö? Da wird nichts durchgegangen. Es gibt einen Pointer auf das erste und auf das letzte Element. Einfügen und Löschen passiert in O(1).

[idefix2]

Ich spreche von meinem Algorithmus.
Du hast einen einfachen MRU (laut inzwischen modifizierter Vorgabe, im Eingangspost war etwas anderes verlangt) implementiert, da braucht man das natürlich nicht.

[Dejan Vu]

Zitat:

Zitat von idefix2 (Beitrag 1310562)

Das Interface der Klasse habe ich bewusst etwas anders gestaltet als in der Vorgabe

Wieso hältst Du dich nicht an die Vorgabe? Wieso soll sich ein Cache um das Schreiben kümmern? Wieso soll er Statistiken pflegen?

Durchgefallen. ;-)

Im Ernst: Sollen wir für deine Sonderklasse extra eigene Test- und Prüfroutinen schreiben?
:gruebel:

Schreib Deine doch bitte um, dann kann man die mit den MRU-Ansätzen vergleichen. Dein Algorithmus ist wirklich sehr interessant.

Ein Tipp bezüglich der

Delphi-Quellcode:

function TCache.FindPlaceInCache: integer;

: Du rennst mit einer For-Schleife durch die Liste? Das ist jetzt aber nicht so sonderlich performant, denn ein Cache verwaltet i.a. Millionen von Elementen.
Diese Routine wird bei jedem Cache-Aufruf einmal komplett durch alle Elemente laufen. Das kannst Du mit einer Priority-Queue (bzw. einem Baum) viel effizienter Lösen. Der wird bei jedem Zugriff sortiert bzw. mit wenigen Handgriffen angepasst, sodass dein 'worst element' immer automatisch 'oben' ist. Aber die Implementierung ist natürlich ungemein komplexer.

Zitat:

Zitat von Namenloser (Beitrag 1310550)

Ein paar Worte zu meinen Designentscheidungen:
- Ich prüfe nicht explizit ob die Aufrufe gültig sind (z.B. ob bei Get der Key auch wirklich existiert) und werfe daher auch keine Exceptions. Denn offensichtlich ist die Schnittstelle so angelegt, dass der Benutzer vorher selbst mit Contain prüfen soll, ob der Key existiert....

Gut gesehen.

Zitat:

...Die ganze Schnittstelle ist meiner Meinung nach nicht optimal...

Gegenvorschlag?

Zitat:

Ich verwende grundsätzlich (fast) nie private sondern immer protected (bis auf sehr wenige Ausnahmen, bei denen es wirklich gute Gründe gibt, die dagegen sprechen).

Welche Gründe sprechen gegen private Felder? Properties sehe ich ein, aber Felder sollten so strict private sein, wie es nur geht.
Ich deklariere Felder immer privat (außer bei DTO) aber den Zugriff per Property als protected. Vermutlich ist das das Gleiche, aber mit mehr Tipparbeit verbunden.

Das 'MakePair' würde ich dem TKeyValuePair als Create spendieren. Gehört -finde ich- dorthin.

Delphi-Quellcode:

// function TCache.MakePair(Key: Integer; Value: TObject): TKeyValuePair;
// begin
//   Result.Key := Key;
//   Result.Value := Value;
// end;

constructor TKeyValuePair.Create(aKey: Integer; aValue: TObject)
begin
  Self.Key := aKey;
  Self.Value := aValue;
end;

Das Freigeben des Cache-Items gehört (finde ich) in den Destruktor des TCacheItem.... Aber wieso gibst Du dort auch das 'Value' frei? Das ist doch das zu cachende Objekt? Damit hat doch der Cache nix am Hut. Oder hab ich mich verlesen?

Delphi-Quellcode:

procedure TCache.Evict(Item: TCacheItem);
begin
  ...
  CacheItem.Value.Value.Free; // <<<--- Mööp, ich glaube, da ist ein Value. zu viel
  CacheItem.Free;
end;

Hier würde ich zwei zusätzliche kleine Methoden draus machen (Lesbarkeit, Clean Code).

Delphi-Quellcode:

// procedure TCache.Put(ID: Integer; Item: TObject);
// var
//   CacheItem: TCacheItem;
// begin
//   Assert(not Contains(ID));
// 
//   if GetCurrentNumberOfElements >= FMaxSize then
//     Evict(FMRU.Last);
// 
//   CacheItem := TCacheItem.Create(MakePair(ID, Item));
//   FMap[ID] := CacheItem;
//   Bump(CacheItem);
// end;

procedure TCache.RemoveLeastUsedElementFromCache;
begin
  if GetCurrentNumberOfElements >= FMaxSize then
    Evict(FMRU.Last);
end;

procedure TCache.AddItemToCache(ID: Integer; Item: TObject);
var
  CacheItem: TCacheItem;

begin
  CacheItem := TCacheItem.Create(MakePair(ID, Item));
  FMap[ID] := CacheItem;
  Bump(CacheItem);
end;

procedure TCache.Put(ID: Integer; Item: TObject);
begin
  Assert(not Contains(ID));

  RemoveLeastUsedElementFromCache;
  AddItemToCache(ID, Item); 
end;

'Bump' und 'Evict' sind für mich ungewöhnliche Begriffe. Ich würde zumindest 'Bump' anders benennen. Aber vermutlich ist das bei Dir/euch Standard. Dann müsste ich mich anpassen :stupid:

Deckt sich ziemlich mit meiner Implementierung, nur das ich keine Generics habe und die MRU selbst implementieren muss.

PS: Es gibt keine Vorgabe, das eine MRU verwendet werden soll! ICH hätte das so gelöst. Wie ihr das macht, ist mir schnuppe (im Gegenteil: Sehr interessant)

[Namenloser]

Zitat:

Zitat von idefix2 (Beitrag 1310568)

Ich spreche von meinem Algorithmus.
Du hast einen einfachen MRU (laut inzwischen modifizierter Vorgabe, im Eingangspost war etwas anderes verlangt) implementiert, da braucht man das natürlich nicht.

Achso, war wohl noch zu früh.

Aber wenn ich so drüber nachdenke, müsste sich der Ansatz mit der verketteten Liste auch für beliebige Sortierungen erweitern lassen. Denn das schöne ist ja, wenn wir das Element gecached haben, kennen wir automatisch die Position bzw. das Glied in der Liste. Dann müssen wir nach dem Updaten des Scores also nur schauen ob das „linke“ (vorherige) Element einen schlechteren Score hat und solange das geupdatete Element nach links verschieben, bis die Sortierung wieder stimmt (wie bei Insertion-Sort). Ist im Worst-Case zwar auch O(n), aber im Best-Case O(1). Es wird auf jeden Fall schneller sein als jedes mal alle Keys zu durchlaufen wie aktuell bei dir.

Zitat:

Zitat von Dejan Vu

Gegenvorschlag?

Delphi-Quellcode:

TCache = Class;

TCacheHandle = class
protected
  FParent: TCache;
  { ... }
public
  property IsNull: Boolean;
  property ID: Integer;
  property Value: TObject;
  procedure Put(Value: TObject);
  procedure Remove;
end;

TCache = class
protected
{ ... }
public
  function GetHandle(ID: Integer): TCacheHandle;
  // Sonst keine öffentlichen Methoden
end;

Zitat:

Zitat von Dejan Vu

Welche Gründe sprechen gegen private Felder? Properties sehe ich ein, aber Felder sollten so strict private sein, wie es nur geht.

Ja, da hast du recht, es wäre sauberer, die Felder private zu machen und über eine protected property Zugriff darauf zu gewähren. Bin aber meistens zu faul dazu und es bläht mir den Code zu sehr auf.

Ich habe bei private einfach die Erfahrung gemacht, dass man oft im Laufe der Zeit mehr und mehr Dinge doch noch protected macht, weil sich Nutzungsmöglichkeiten ergeben, die man am Anfang nicht vorhergesehen hat. Auch bei der VCL/RTL habe ich mich schon oft aufgeregt, dass Sachen sinnloserweise private waren und ich dann deshalb Code kopieren musste (Gruß an himitsu an dieser Stelle). Deswegen habe ich mir einfach angewöhnt: Im Zweifel für protected. Weil man sich da seltener was verbaut. Protected heißt bei mir daher aber auch immer ein bisschen „Use at your own risk“. Also bloß, weil man auf protected Felder zugreifen kann, heißt es nicht, dass man es unbedingt sollte. Da muss man eben Vernunft walten lassen. In Python gibt es übrigens gar kein private. Dort gibt es nur die Konvention, dass Variablen, die mit einem _ beginnen, tabu sind. Es wird sich eben darauf verlassen, dass der Programmierer sich daran hält, aber wer sich unbedingt in den Fuß schießen will, kann es tun. So ähnlich halte ich es auch.

Zitat:

Zitat von Dejan Vu

Das 'MakePair' würde ich dem TKeyValuePair als Create spendieren. Gehört -finde ich- dorthin.

Habe ich auch schon oft so gemacht, als static class function. Aber damals gab es noch keine echten Konstruktoren von records, und das hat sich in neueren Delphi-Versionen ja glaube ich geändert. Ich wollte da lieber nichts verwenden, was ich nicht kenne.

Zitat:

Zitat von Dejan Vu

Aber wieso gibst Du dort auch das 'Value' frei? Das ist doch das zu cachende Objekt? Damit hat doch der Cache nix am Hut. Oder hab ich mich verlesen?

Habe das so gemacht, weil TCache keinen OnRemove-Handler hat.

Zitat:

Zitat von Dejan Vu

'Bump' und 'Evict' sind für mich ungewöhnliche Begriffe. Ich würde zumindest 'Bump' anders benennen.

Also Evict ist glaube ich schon ein Standardbegriff, Bump vielleicht eher nicht. Habe da irgendwie an Internetforen gedacht.

Aber wie heißt es so schön: „There are only two hard things in Computer Science: cache invalidation and naming things.“
Passt ja auch sonst zu diesem Thread. ;)

[idefix2]

Zitat:

Zitat von Dejan Vu (Beitrag 1310569)

Zitat:

Zitat von idefix2 (Beitrag 1310562)

Das Interface der Klasse habe ich bewusst etwas anders gestaltet als in der Vorgabe

Wieso hältst Du dich nicht an die Vorgabe? Wieso soll sich ein Cache um das Schreiben kümmern? Wieso soll er Statistiken pflegen?

Wenn die Cache-Klasse auch das Schreiben besorgt, muss die Anwendung zu speichernde Daten nur an einer Stelle "abgeben", sonst muss sie die Daten sowohl in den Cache schreiben als auch selbst auf das externe Medium speichern.
Mir erscheint eine Klasse, die transparent den Zugriff auf die Daten organisiert und dabei die Daten cached, wesentlich zweckmässiger als eine reine Cache-Klasse, in der man erst nachschauen muss, ob die Daten dort sind, und sich andernfalls die Daten von draussen zu besorgen. Und wenn man das macht, dann muss die Cache-Klasse die Statistik über Hits und Misses natürlich selbst führen, das Programm draussen bekommt davon nichts mit (und braucht davon auch nichts mitzubekommen)

Natürlich wird man sich für eine reine Cache-Klasse in einer Anwendung einen Wrapper Schreiben, der das erledigt, aber so erscheint es mir wesentlich eleganter. Das Schreiben könnte in dieser Klasse auch leicht in einen separaten Thread ausgelagert und gequeued werden, wobei Elemente im Cache geschützt bleiben und nicht hinausgeworfen werden dürfen, bis sie wirklich auf das externe Medium geschrieben sind. Wenn du das Schreiben ausserhalb des Caches erledigst, wird es mit einem separaten Thread wesentlich komplizierter, denn es könnte dir passieren, dass ein Element aus dem Cache gelöscht wird und dann wieder angefordert wird, während das Schreiben auf das externe Medium noch in der Warteschlange des anderen Threads steckt.

Zitat:

Zitat von Dejan Vu (Beitrag 1310569)

Im Ernst: Sollen wir für deine Sonderklasse extra eigene Test- und Prüfroutinen schreiben?
:gruebel:

Schreib Deine doch bitte um, dann kann man die mit den MRU-Ansätzen vergleichen. Dein Algorithmus ist wirklich sehr interessant.

Das ist allerdings hier ein schlagendes Argument, an das ich nicht gedacht habe.
Ich werde schauen wann ich dazukomme, auch wenn ich den Ansatz prinzipiell für schlechter halte.

Zitat:

Zitat von Dejan Vu (Beitrag 1310569)

Ein Tipp bezüglich der

Delphi-Quellcode:

function TCache.FindPlaceInCache: integer;

: Du rennst mit einer For-Schleife durch die Liste? Das ist jetzt aber nicht so sonderlich performant, denn ein Cache verwaltet i.a. Millionen von Elementen.
Diese Routine wird bei jedem Cache-Aufruf einmal komplett durch alle Elemente laufen. Das kannst Du mit einer Priority-Queue (bzw. einem Baum) viel effizienter Lösen. Der wird bei jedem Zugriff sortiert bzw. mit wenigen Handgriffen angepasst, sodass dein 'worst element' immer automatisch 'oben' ist. Aber die Implementierung ist natürlich ungemein komplexer.

Schon klar. Ich habe ja geschrieben:

Zitat:

Für die aktuellen Cacheelemente sollte wohl zusätzlich noch eine nach dem "Hinauswurfkriterium" sortierte Liste verwaltet werden (oder sogar statt des TDictionary, aber dadurch würde das Auffinden der im Cache vorhandenen Elemente wieder langsamer), damit man nicht alle Elemente durchgehen muss, wenn ein Element aus dem Cache zu entfernen ist, um herauszufinden, welches weggehört. Eine einfache verkettete Liste, wie sie namenloser in seinem Algorithmus verwendet, bringt nicht viel, weil man dann die verkettete Liste trotzdem immer durchgehen muss, um das an Stelle des hinausgeworfenen Elements hinzukommende neue Element an der richtigen Stelle einzufügen, das ist nämlich auch nicht unbedingt am Ende der Liste.

Gestern Nacht war es mir schon zu spät, da hatte ich keine Lust mehr, das auch noch zu machen. So schlimm, wie du schreibst, ist es nicht, weil die Routine nicht bei jedem Cachezugriff aufgerufen wird, sondern nur bei Cache Misses, wenn der Cache voll ist. Und Millionen von Elementen sind es wohl auch nicht, es werden ja nur die aktuell im Cache befindlichen Elemente durchgegangen. Andererseits stimmt das, was ich geschrieben habe, auch nicht ganz, eine einfache verkette Liste würde trotzdem eine deutliche Verbesserung bringen, weil neue Elemente zwar nicht immer ganz ans Ende kommen, aber tendenziell doch eher im hinteren (hintersten) Teil der Liste landen werden, vor allem, wenn die MRU-Gewichtung grösser ist als die Häufigkeits-Gewichtung, was sie wahrscheinlich in den meisten Anwendungsfällen sein sollte.

Jetzt muss ich weg, vielleich komme ich übers WE noch dazu, da weiter zu machen.