Drastische Performanceeinbuße bei Linked List mit Objects

[alzaimar]

Ich will eine MRU-Liste implementierren, das ist eine doppelt verkettete Liste. Ich dachte, ich mach das so;

Delphi-Quellcode:

Type
  TFoobarObject = Class
  Public
     pPrev, pNext : TFooBarObject; // Zeiger auf Vorgänger / Nachfolger
  ...
  End;
...

Var
  lHead, lTail : TFooBarObject;

Procedure Irgendwas;
Begin
  MyFooBar := TFooBar.Create;

// Diese vier Zeilen machen aus 10ms für 3000 x Irgendwas aufrufen 25000!!!!
{*}  MyFooBar.pNext := lHead.pNext;  // neues Objekt kommt an den Kopf der Liste
{*}  lHead.pNext.pPrev := MyFooBar;
{*}  lHead.pNext := MyFooBar;
{*}  MyFooBar.pPrev := lHead;
// Egal, ob das jetzt so stimmt (stimmt aber, glaube ich)
End;

Kann mir bitte bitte jemand erklären, wieso die kleinen Zeilen {*} die Anwendung um den Faktor 10.000 verlangsamen? Ich habe sie auskommentiert: 3000 Aufrufe = 0 oder 16ms (also echt wenig).

Mit den vier blöden Zeilen sind es 25.000 ms.



Ick zu blöd?

[cruiser]

MyFooBar sieht aus wie die Liate... die sollte nur pFirst, pLast und eventuell pCurrent kennen. Mehr braucht die auch gar nicht wissen.

Wenn du jetzt ein Objekt mit pPrev und pNext einhängen willst gehst du wie folgt vor:

Delphi-Quellcode:

var
  newItem, temp: TListItem; 
begin
  newItem := TListItem.Create; // neues Item erzeugen pPrev und pNext sind dann nil

  { ... Item mit Daten bestücken ... } 

  temp := Liste.pfirst; // Das erste Item aus der Liste greifen
  temp.pPref := newItem; // Diesem statt nil (Anfang) das neue Item als Vorgänger zuweisen
  newItem.pNext := temp; // Das alte erste Item ist jetzt der Nachfolger unseres neuen Items
  Liste.pFirst := newItem; // Zuguterletzt unser neues Item als erstes Item in der Liste setzen
end;

Dabei geh ich davon aus, dass beim newItem-erzeugen pPrev und pNext auf nil initialisiert werden.

[alzaimar]

Danke für Deinen Vorschlag, aber:
pPrev und pNext müssen nicht mit nil initialisiert werden, denn sie werden ja gesetzt. Und temp brauch ich auch nicht. Denn das funktioniert schon, so wie ich es mache. Nur eben unglaublich langsam...

TFooBar ist ein Element der Liste (Knoten). Daneben gibt es noch Head und Tail. Head zeigt auf das erste, Tail auf das letzte Element.

Eine MRU-Liste wird beim Caching verwendet: Sobald ein Element aus dem Cache verwendet wird, kommt es nach vorne. Neue Elemente, die geladen werden müssen, kommen auch nach vorne.

Wenn der Cache voll ist, schmeisst man vom 'Tail' ein paar Elemente weg, denn die sind naturgemäß längere Zeit nicht verwendet worden. Eine ziemlich geile MRU-Queue mit 0-Zeitaufwand... Ich hab das schon 1000x implementiert u.A. in einem SQL-Server, aber:

Wieso dauert das hier so lang? Selbst in der CPU-Ansicht sind es nur 12 MOV-Befehle.... ick versteh's nicht.

Ach: es ist egal, wie viele Zeilen auskommentiert werden: Ohne die 4 Zeilen sind es 10ms, ist auch nur eine nicht auskommentiert, dauert das 25 SEKUNDEN!

[alzaimar]

Delphi-Neustart hilft...

Danke trotzdem!

[cruiser]

Gut zu wissen, dass mein TObject-List Ersatz auf doppelt verlinkter Basis nich für die Katz ist Ich wollt mir so eben auch die Vergrösserung des Arrays mit rausoptimieren.

[alzaimar]

cruiser: Unterm Strich ist so eine Liste schneller als eine Linked List, vor allen Dingen, wenn Du in der Liste suchen willst. Eine MRU-Struktur interessiert sich nur für 'Vorne' und 'Hinten'. Eine Liste hingegen willst Du auch mal durchsuchen: Dann gibt es weitaus bessere Strukturen als die verkettete Liste. Für Dich als Performancefreak wäre die Skip List genau das Richtige: Sie ist auch verkettet, aber nicht nur mit dem nächsten Element, sondern auch mit den übernächsten, überübernächsten etc. Eine erstaunliche Struktur, die ein nahezu optimales Laufzeitverhalten (O(1) für alle Operationen) an den Tag legt. Ich hab hier irgendwo eine Implementierung gepostet (oder in der Codelibrary, oder im Delphi-Forum)...

Das Vergrößern kannst Du übrigens steuern, indem Du die Grow-Methode überschreibst. Sie ist aber schon ganz nett implementiert. Wirklich gute Ergebnisse erzielt man, wenn man die Listengröße einfach verdoppelt. Das passiert ja nicht so oft: Bis 2^32 Elemente drin sind, ganze 31 Mal...

Und wirklich Zeit fressen eh die Suchoperationen...

[cruiser]

Naja... was heisst Ersatz... wenn die Daten durchsucht und gehalten werden müssen ist ne LinkedList lahmer, stimmt. Nur ist so eine LinkedList bei vielen Änderungen an Anfang und Ende meiner Meinung nach fixer... Ich meinte eher, dass ich die Methoden möglichst equivalent gemacht hab. naja... noch konnt ich keine Testläufe machen Die SkipList sieht interessant aus, nur weiss ich nicht wie man das nutzen soll. Ich meine, wenn man nicht von vornherein einen Key hat. Aber wir werden OffTopic, glaub ich.