Geschwindigkeitsunterschiede bei Objekten/Pointern?

[Tiefflieger]

Angenommen, ich möchte einen sehr großen (nur begrenzt durch die Leistungsfähigkeit des Computers) Baum erstellen bzw mit demselben Sachen auswerten:
Ist der Geschwindigkeits-/Speicherplatzunterschied zwischen der Implementation mit reinen Zeigern und der Implementation als Klasse bei einigen 100.000 Baumknoten sehr groß?

Hier ist ein Beispiel, wie ich das meine:

Delphi-Quellcode:

//Implementation mit reinen Zeigern
type PBaum = ^TBaum
     TBaum = record
               info         : TInfo;
               links,rechts : PBaum;
             end;

//Implementation als Klasse
type CBaum = class
               info         : TInfo;
               links,rechts : CBaum;
               function bli : Tbla;
               procedure blubb;
            end;

Oder gibt sich das nicht viel, da Objekte auch nur Zeiger auf etwas sind?

[jbg]

Deine Wortwahl ist nicht passend. Entweder schreibst du Zeiger und Referenzen, was aber im Endeffekt wieder dasselbe ist, also keinen Geschwindigkeitsunterschied hat. Oder du schreibst Records und Klassen, wobei dadurch, dass Klassen mehr overhead haben die Records klar die Nase vorne haben, wenn auch nicht all zu weit.

[choose]

Exemplare von Klassen (=Objekte) halten neben den Exemplarvariablen noch eine "Referenz auf die Klasse", mit deren Hilfe Konstrukte der Art

Delphi-Quellcode:

if myObject is TMyClass then

und Polymorphie iA möglich werden.
Der hierfür benötigte Speicher ist die Größe einer Referenz selbst (zZt 4 Bytes). Darüber hinaus sind Klassen iA für "optimierten Zugriff" ausgerichtet. Diese Optimierung des Compilers hat bei der aktuellen Implementierung zB zur Folge, dass zwei Bytes tatsächlich 8 Bytes "belegen". Bei Records hingegen kann dieses Verhalten explizit mit packed vermieden werden, um Speicher auf Kosten der Performance zu sparen.

Der Zugriff auf Exemplarvariablen ist identisch mit dem Zugriff bei Records, allerdings sollten bei Objekten die Exemplarvariablen im Sinne der OOP generell verborgen sein (Geheimnisprinzip).
Delphi bietet hier das Konzept der Eigenschaften (Properties), bei der zwar Setter-Methoden zur Zusicherung von Invarianten, zum Lesen jedoch ein direkter Zugriff auf eine verborgene (private) Exemplarvariable angegeben werden kann. Übersetzt wird dieses Konstrukut beim Lesen dann wieder wie der "optimale Zugriff".
Lediglich beim Erzeugen und Freigeben von Exemplaren ist die Lösung mit Objekten etwas träger, bietet im Gegenzug aber die vielen Möglichkeiten der OOP :)

[negaH]

Werden in Klassen nur statische Methoden benutzt so gibt es in fakt keinerlei Performance Unterschiede zu normalen dynamischen Records. Ich empfehle dir also aus Sicht der Übersichtlichkeit Klassen zu benutzen.

Allerdings, werden sehr große Bäume benutzt, so gibt es andere Methoden sie um ein mehrfaches zu beschleunigen.
1. Methode sind Records die ohne Zeigeroperationen auskommen. Dabei wird ein Array of Record benutzt. Man prealloziert eine Array mit zB. 1024 Elementen. Somit wird nur bei jeder 1024'ten Node ein großer Speicher alloziert, statt 1024 mal viel kleine Speicher zu allozieren.
2. Methode ist es in deinem TNode Object die methoden .NewInstance und .FreeInstance zu überschreiben. Beide Methoden greifen nun nicht auf den Borland Speicher manager direkt zu, sondern auf ein Array of TMyObjectRecord.

Beide Methoden versuchen den langsammen Speicher Manager zu umgehen, und Chunkweise ganze Objecte auf einmal zu allozieren. Freigegeben Objecte/Records werden auch nicht mehr zum MM durchgereicht, sondern in einem schenllen Pool verlinkter Objecte/Records verwaltet. D.h. eine Neuallokation solcher Objecte/Records ist extrem schnell.
Insgesamt ist der Performanceboost weit größer 10%, meistens aber 2-3 mal schneller als der Borland MM.

Gruß Hagen

[choose]

Zitat:

Zitat von negaH

Insgesamt ist der Performanceboost weit größer 10%, meistens aber 2-3 mal schneller als der Borland MM.

Hallo Hagen,

über den Einsatz eines Nodemanagers, der auch recyceln kann, habe ich im Zusammenhang mit Delphi das erste Mal in "The Tomes of Delphi, Aglorithms and Data Structures", Julian Bucknall gelesen. Obwohl ich eine ähnliche Technik bereits erfolgreich bei Tupel-Mengen verwendet habe, war meine Entscheidungsgrundlage nicht wirklich... metrisch fundiert.

Zwar ist in meinem aktuellen Projekt nicht das Speicherhandling sondern die Referenzzählung der Flaschenhals, mich würde trotzdem interessieren, ob Du konkrete Erfahrungswerte für den Einsatz eines Nodemanagers für die Objekterstellung anbieten kannst: Für welche Exemplargrößes lohnt sich der Einsatz? Wie groß ist der tatsächliche Zeitgewinn bei welchen Mengen von Exemplaren? Was gewinnt man bei eine Initialisierung direkt in NewInstance? Wie groß sollten die Chunks gewählt sein? Gibt es elegante Lösung für Polymorhpie, also unterschiedliche Exemplargrößen? etc.

[negaH]

Zitat:

ob Du konkrete Erfahrungswerte für den Einsatz eines Nodemanagers für die Objekterstellung anbieten kannst:

Ja, aber aus ganz anderen Gründen. Ich benötigte einen Pool von gleichgroßen Records die aber per Reference Counting, sprich Interfaces, arbeiteten. Dadurch wurde mit Hilfe der integrierten Fähigkeiten des Delphi Compilers, ein automatisches Garbarge Collection und "Copy on Write Demand" realisiert. In diesem speziellen Fall wurden ALLE Operationen auf diesen "forged Interfaces" ca. 10% beschleunigt. Allerdings in der Gesamtperformance spielte der Speichermanager von vornherein eine unwichtigere Rolle. D.h. diese 10% müssen viel höher bewertet werden als die Zahl 10 dies suggeriert ! Nur ca. 0.01% von allen Operationen sind Aufrufe zum Speichermanagement. Somit sind die 10% viel mehr als von mir tatsächlich erwartet.

Zitat:

Für welche Exemplargrößes lohnt sich der Einsatz?

Am einfachsten und effizientesten sind Records mit fester Größe. D.h. der MM Ersatz verwaltet nur Objecte/Records die eine gleichbleibende Speichergröße besitzen.
Für variable Speichergrößen, würde ich beim Borland MM bleiben, denn dieser MM ist eigentlich schon enorm optimiert und einer der schnellsten überhaupt.

Zitat:

Wie groß ist der tatsächliche Zeitgewinn bei welchen Mengen von Exemplaren?

Dioes hängt hauptsächlich von der Größe und der Häüfigkeit der Records ab. Um so häufiger Alloziert/Dealloziert wird um so größer ist der Zeitgewinn. In meiner Library hatte ich ca. 2 Mio solcher De-/Alloziereungen pro Berechnung. Durch den Pool wurden die tatsächlichen Aufrufe zum Borland MM auf ca. 10.000 reduziert. D.h. nur 0.005 Prozent der Speicheranforderungen. Da der Pool selber Threadbezogen arbeitet, d.h. jeder Thread hat seinen eigenen Pool, entfällt das Locking per RTL-CS. Alleine dies würde im Borland MM 2 Mio mal erfolgen.

Zitat:

Was gewinnt man bei eine Initialisierung direkt in NewInstance?

Arbeitet man mit Klassen so bleibt einem garnichts anderes übrig als .NewInstance zu überschreiben. Nur innerhalb von .NewInstance kann für eine spezielle Klasse deren Allokation geändert werden. Im gleichem Maße muß man demzufolge auf .FreeInstance überschreiben.

Zitat:

Wie groß sollten die Chunks gewählt sein?

Abhänig vom Datenaufkommen. Am besten ist es wenn der Pool nicht linear wächst. Statt also immer 1024 Objecte per Chunk zu allozieren, könnte man auch den Pool um 16,32,64,128,256... usw. Objecte vergrößeren. Damit würde der Pool sich nichtlinear anpassen. Man sollte den Pool konfigurierbar halten. D.h. die Zuwachsraten und nach welcher Methode sollten einstellbar sein.

Zitat:

Gibt es elegante Lösung für Polymorhpie, also unterschiedliche Exemplargrößen?

Jo, den integrierten Speichermanager :-) Meiner Meinung nach lohnen eigene Pools nur wenn man wirklich das letzte Quentchen rausholen muß UND alle anderen Optimierungsoptionen schon ausgschöpft hat. In meiner Library war dies ein bischen anders. Meine Anforderungen entstanden hauptsächlich aus dem Ziel per "Interfaces" das autm. Reference Counting + Garbarge Collection + Copy on Write Demand + Autoallokation umzusetzen. Da von vornherein feststand das die Recordgrößen fixiert sind war es sinnvoll all diese Features über einen Speicher-Pool zu erledigen, der zudem noch threadsicher sein sollte.

Gruß Hagen

[negaH]

Ach eines noch. Der Performancegewinn wurde aber wahrscheinlich aus einem ganz anderen Grund erreicht. Angenommen man hat viele Speicherkopieroperationen von einer Node in die andere (bei mir sind es Large Integer). Dann ist es wichtig zu wissen wie und warum die internen CPU Caches arbeiten. Die Caches arbeiten immer dann optimial wenn 1. die Speicherbereich an 64 Byte Grenzen ausgereichtet sind und 2. die Speichergrenzen der beiden Nodes/Large Integer nicht in der selben Page liegen. Besonders Punkt 2. ist enorm wichtig. Da mein Pool als FIFO arbeitet rotieren sozusagen die allozierten Speicher im Pool. Dadurch passiert es das der Pool succesive Speicherbereich auch meistens succesive im Cache halten kann. Von der Wahrscheinlichkeit her gesehen ist es also so das dieser Pool Objecte zur Verfügung stellt die in unterschiedlichen Cache-Pages liegen. Eine Speicherkopieroperation zwischen zwei solcher unabhäniger Cachelines ist dann sehr viel scheller und verhindert Cachmisses der CPU. Eineinzigster solcher Cachemiss kann ca. 200 Taktzyklen beanspruchen.

Wird beim Borland MM wiederholt ein Object mit gleicher Speichergröße alloziert und dealloziert so wird immer wieder der selbe Speicherbereich benutzt. Dies erscheint auf den ersten Blick als Cache-freundlich, ist es aber nicht. Da durch den anderen Inhalt des neuallozierten Objects ein Cache-refresh auf gleicher Cacheline nötig wird. Eine Cacheline ist aber meistens größer als 512 Bytes. Somit muß die CPU ganze 512 Bytes auffrischen und nachladen. Der Algorithmus heutger Cahces ist aber darauf optimiert das zufällige Speicheradressen nachgeladen und aufgefrischt werden müssen. Eben auf denn meist praktischen Gebrauch in einem PM OS. D.h. der Cache arbeitet relativ ineffizient wenn man sehr geordnete Speicherzugriffe durchführt. Deshalb gibt es ja auch im MMX/SSE Bereich Befehle die für's Audio/Video Streaming den Cache umgehen können. Bei solchen Operationen ist nämlich der Cache eine Bremse. Ähnliches passiert nun wenn man sehr viele wiederholte gleichgroße Speicherchunks alloziert und dealloziert.

Gruß Hagen

[Tiefflieger]

wow, viele neue infos und wörter (chunk etc), von denen ich noch nie etwas gehört habe ;)
wie alloziere ich denn ein objekt in meinem dynamischen array? über so etwas in der art von

Delphi-Quellcode:

procedure CBaum.NewInstance(info:TInfo);
begin
  self := CBaumArray.Add(info);
end;

function CBaumArray.Add(info:TInfo):CBaum;
begin
  if AnzKnoten = MaxAnzKnoten then 
    ;//Arraylänge verdoppeln
  
  knotenarray[AnzKnoten + 1].create(info);
  result := knotenarray[AnzKnoten + 1];
  
  inc(AnzKnoten);
end;

?

Ist das nicht unsauber, da CBaumarray CBaum kennen muß und umgekehrt? vor allem, wenn ich die beide in zwei verschiedene units packe gibts doch kreuzverweise...?

[choose]

Zitat:

Zitat von Hagen

Zitat:

ob Du konkrete Erfahrungswerte für den Einsatz eines Nodemanagers für die Objekterstellung anbieten kannst:

Ja [...]. Ich benötigte einen Pool von gleichgroßen Records die aber per Reference Counting, sprich Interfaces, arbeiteten. Dadurch wurde mit Hilfe der integrierten Fähigkeiten des Delphi Compilers, ein automatisches Garbarge Collection und "Copy on Write Demand" realisiert. [...] Somit sind die 10% viel mehr als von mir tatsächlich erwartet.

Das kommt dem, was ich zZt noch mit dem Borland Memory Manager (BMM) realisiere, ziemlich nahe: Lediglich mit dem Unterschied, dass meine "forgotten Interfaces" als gecachte Werte erst bei Bedarf als "freie Nodes" gekennzeichnet werden, weil sie in den meisten Fällen ohnehin kurze Zeit später erneut "erbaut" werden würden...

Zitat:

Zitat von Hagen

Zitat:

Für welche Exemplargrößes lohnt sich der Einsatz?

Am einfachsten und effizientesten sind Records mit fester Größe. [...] Für variable Speichergrößen, würde ich beim Borland MM bleiben, denn dieser MM ist eigentlich schon enorm optimiert und einer der schnellsten überhaupt.

Diese Antwort deckt sich mit Deiner Äußerung zur Polymorphie. Danke.

Zitat:

Zitat von Hagen

Zitat:

Wie groß ist der tatsächliche Zeitgewinn bei welchen Mengen von Exemplaren?

Dioes hängt hauptsächlich von der Größe und der Häüfigkeit der Records ab. [...] In meiner Library hatte ich ca. 2 Mio solcher De-/Alloziereungen pro Berechnung. Durch den Pool wurden die tatsächlichen Aufrufe zum Borland MM auf ca. 10.000 reduziert. [...] Da der Pool selber Threadbezogen arbeitet, [...] entfällt das Locking per RTL-CS.

Gerade das Veremeiden des Lockings klingt interessant...

Zitat:

Zitat von Hagen

Zitat:

Was gewinnt man bei eine Initialisierung direkt in NewInstance?

Arbeitet man mit Klassen so bleibt einem garnichts anderes übrig als .NewInstance zu überschreiben.

Das ist mir schon klar, Hagen, ich meinte aber eher Vorbelegung von Exemplarvariablen, Referenzzählern direkt in NewInstance anstatt diese Belegung in InitInstance bzw. im Konstruktor vorzunehmen. Hier könnten neue Nodes mithilfe eines "Node-Templates" mit rep movsd relativ performant erzeugt werden...?

Zitat:

Zitat von Hagen

Ach eines noch. Der Performancegewinn wurde aber wahrscheinlich aus einem ganz anderen Grund erreicht. [...] Da mein Pool als FIFO arbeitet rotieren sozusagen die allozierten Speicher im Pool. Dadurch passiert es das der Pool succesive Speicherbereich auch meistens succesive im Cache halten kann. [...] Eine Speicherkopieroperation zwischen zwei solcher unabhäniger Cachelines ist dann sehr viel scheller und verhindert Cachmisses der CPU. Eineinzigster solcher Cachemiss kann ca. 200 Taktzyklen beanspruchen.

Interessanter Aspekt.

Danke Hagen, für Deine ausführliche Darstellung!

[choose]

Hallo Tiefflieger,

Deine Implementierung von NewInstance stützt sich nach meinem Eindruck wieder auf einen Konstruktor (und der eigentlichen Aufruf verstehe ich nicht ganz!) und damit auf die ursprüngliche Implementierung?

Zitat:

Delphi-Quellcode:

knotenarray[AnzKnoten + 1].create(info);
result := knotenarray[AnzKnoten + 1];

Der diskutierte Ansatz hingegen besteht darin, die Borland-Implementierung

Delphi-Quellcode:

class function TObject.NewInstance: TObject;
begin
  Result := InitInstance(_GetMem(InstanceSize));
end;

so zu ersetzten, dass der Aufruf von GetMem, also die Verwendung des Borland Memory Managers (BMM) entfällt. Die Funktion GetMem gibt einen Pointer auf einen Speicherbereich der Größe des Exemplars zurück. Und eben dieser Pointer könnte innhalb einer selbstgewählten Struktur (zb einem Array) effizienter ermittelt werden, zB so

Delphi-Quellcode:

  Result:= InitInstance(@MyClassArray[GetIndexOfNextFreeNode()]);

Weil dieses Vorgehen an sich aber wiederkehrend ist, könnte man es generisch in einen sog. Nodemanager implementieren, der dann den BMM bei der Erzeugung von Exemplaren einer konkreten Klasse vollständig ersetzt...