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

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

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

[Uwe Raabe]

Zitat von TiGü:

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

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