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

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

[Mavarik]

Zitat von Uwe Raabe:

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 von Mavarik:

Zitat von Uwe Raabe:

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;

[Dejan Vu]

Zitat von idefix2:

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?


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 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 von Namenloser:

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

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)

[idefix2]

Zitat von Dejan Vu:

Zitat von idefix2:

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 von Dejan Vu:

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


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 von Dejan Vu:

Ein Tipp bezüglich der 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.

[Mavarik]

Zitat von Uwe Raabe:

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