Effektivität von Records und Objekten

[Gargamel]

Hi

Ich möchte eine Reihe von Gegenständen in einem dynamischen Array verwalten. Jeder Gegenstand (Anzahl ca. 300-500) hat etwa 40 Eigenchaften. Jetzt frage ich mich, was hinsichtlich Performance und Speicherverbrauch effektiver ist. Ein dyn. Array mit Objekten (inkl. Konstruktoren/Destruktoren/Methoden) oder halt ein dyn. Array mit Records.

Danke

[Klaus01]

Hallo,

zur Effekttivität und Speicherverbrauch kann ich nichts sagen.

Aber zur Verwaltung von Objecten würde ich eine TObjectList nehmen
und für Records eine TList oder TThreadList.

added:

Ansonsten sind halt die Zugriffsmöglichkeiten verschieden.
Bei Objecten kannst Du Get und Set (Properties) arbeiten.
Die Eigenschaften kannst Du zentral (wartbarer) in einem Object /einer Klasse verwalten.

Bei Records kannst Du direkt auf die Daten zugreifen (rec1.data).
Hast aber als Nachteil eine Handvoll von Routinen die diese Daten verarbeiten
im ganzen Programm verstreut.
Ändert sich etwas im Record musst Du die zugehörige Routine suchen und es auch dort ändern.

Grüße
Klaus

[Furtbichler]

Ein "Array of Record" ist das schnellste und kleinste. Ob es Spaß macht, damit zu arbeiten, sei mal dahingestellt.

300-400 Datensätze mit je 40 Eigenschaften ist nun nicht gerade viel, und da würde ich auf jeden Fall zu OOP raten.

[BUG]

Du solltest daran denken, das bei einem dynamischen Array beim Vergrößern im Zweifelsfall alle bisherigen Elemente kopiert werden müssen.
Im Extremfall ist ein Record schneller (mindesten eine Indirektion weniger) als ein Objekt, aber bis du das merkst, fallen dir vermutlich andere Sachen auf die Füße (siehe dyn. Array).

Wenn du etwas mehr Informationen gibst, wie du mit Daten arbeiten willst (wahlfrei vs. hintereinanderweg, usw.), könnte man dir vmtl. besser helfen.

[himitsu]

Zitat:

Zitat von BUG (Beitrag 1143544)

Du solltest daran denken, das bei einem dynamischen Array beim Vergrößern im Zweifelsfall alle bisherigen Elemente kopiert werden müssen.

In neueren "Delphis" ist FastMM schon an Board, das Optimiert dabei schon etwas.

Statt einem dynamischen Array bietet sich auch eine generische TList an, welche zwar wieder etwas "langsamer" ist, aber dafür noch ein paar nette Extras bietet.


Ich verwende Arrays vorallem dann, wenn ich mich nicht im die Erstellung/Speicherverwaltung der enthaltenen "Objekte" kümmern will.

Wenn man die Liste öfters verändert und vorallem mitten Drin, bzw. am Anfang Records einfügt oder löscht, dann wird dieser Vorgang immer langsamer, je größer die Records werden > mehr Daten.
Bei Objekten sind es dagegen immer nur SizeOf(TObjekt) Bytes pro zu verschiebendem Eintrag.




PS: Bei einem Array of Record, bzw. bei einer TList<Record>, liegen alle Record-Daten zusammen in einem Speicherbereich.
Bei einer Objektliste liegen diese Daten/Objekte überall verstreut im RAM und verbrauchen zusätzlichen Verwaltungsoverhead im Speichermanager.

[BUG]

Zitat:

Zitat von himitsu (Beitrag 1143564)

In neueren "Delphis" ist FastMM schon an Board, das Optimiert dabei schon etwas.

Aber auch FastMM wird nicht zB. ein halbes Kilobyte reservieren (~40*100), weil ein dynamisches Array noch 100 Einträge wachsen könnte.

[himitsu]

Nee, aber dank Möglichkeiten, wie z.B. Inplace-Realocation, kann er das oftmals auch so vergrößern, ohne es jedesmal verschieben zu müssen.

Bei der TList<> kann man den Speicher auch gleich direkt Vorbestellen, genauso wie man bei einem Array die gesamte Größe, schon vor dem Befüllen, festlegen könnte.

[Gargamel]

Hi

Ja, ich gebe gerne mehr Informationen. Also:

Der Begriff "Gegenstand" war von mir eingangs etwas unglücklich gewählt. Es geht darum, eine, wenn auch recht simple, KI zu programmieren.
Jegliche KI-Routinen finden in einer DLL statt, die 3D-Engine liegt in C++ vor.

Innerhalb der Engine gibt es zwei Aufrufe:

AI_registerObject(objID);
AI_removeObject(objID);

Der Parameter objID ist die interne ID eines Objektes innerhalb der 3D-Engine.

Jegliche zu verwaltende KI-Objekte befinden sich in einem dyn. Array. Die KI-Routinen selbst greifen ausschließlich auf dieses Array zu und berechnen halt diversen Kram. Werden jetzt allerdings Objekte mit AI_removeObject(...) entfernt und neue hinzugefügt, wird das Array nicht nur ständig größer, sondern es verbleiben auch Lücken. Um das zu vermeiden, gibt es ein zweites dyn. Array. Wird ein KI-Objekt mit AI_removeObject(...) entfernt, wird die Indexnummer im ersten Array in dem zweiten Array gespeichert. Pro AI_removeObject(...) wird demnach das zweite Array um einen Eintrag erweitert. Wird AI_registerObject(...) aufgerufen, wird erst im zweiten Array nachgesehen, ob es leere Elemente im ersten Array gibt. Wenn ja, bildet die gespeicherte Indexnummer des letzten Elements im zweiten Array den Index im ersten Array und das letzte Element wird im zweiten Array wieder gelöscht. Auf diese Weise halte ich das erste Array so klein und lückenlos wie möglich.

Der Quellcode dazu besteht bereits. Konkrete Geschwindigkeitsberechnungen habe ich nicht vorgenommen, aber gefühlt lief das alles, auch bei großen Listen, sehr flink.

Die Kommunikation zwischen 3D-Engine und DLL erfolgt über drei Funktionen. Neben AI_registerObject(...) und AI_removeObject(...) gibt es noch eine Funktion, die das berechnete Ergebnis der KI an die Engine übergibt.

Jetzt hat es mich halt interessiert, ob die Verwaltung und interne Berechnung der KI-Objekte über Records oder komplett objektorientiert effektiver ist. Der reine Programmieraufwand ist für mich nicht kriegsentscheidend. Mir kommt es auf die reine Performance und den Speicherverbrauch an.
In diesem Zusammenhang wäre auch interessant, inwieweit Exception-Handling sowohl Performance als auch Speicherverbrauch negativ beeinflusst.

Die KI selbst läuft vollkommen unabhängig von der 3D-Engine auf einem separaten CPU-Kern via Multithreading. Denn es wäre für die Framerate tödlich, jegliche KI-Berechnungen pro Frame auszuführen.

Ich hoffe, daß ihr jetzt alle nötigen Informationen habt, um mir Hinweise zu geben.

Nochmals Danke.

[s.h.a.r.k]

Allein aufgrund der Handlichkeit und leichten Erweiterbarkeit bei OOP würde ich zu (generischen) Listen (-> TList/TObjectList/TDictionary) in Verbindung mit Objekten tendieren. Oder man muss sich halt alle Methoden selbst basteln und ich weiß nicht, ob das wirkich so geschickt ist. Ich habe zwar so ziemlich alle Array-Methoden von PHP mal nach Delphi portiert, aber mir ist da die OOP-Struktur doch wesentlich lieber.

Wichtig ist hier auch vor allem die Lesbarkeit, wie ich finde, nicht unbedingt die Performance. Allerdings kann man z.B. durch ein TDictionary sehr viel Performance herausholen, in so fern es die korrekte Datenstruktur ist. Alternativ kann man sich ja auch andere Datenstrukturen aufbauen, wie z.B. eine Heap-Struktur.

Der zusätzliche Speicher für eine solche Liste sollte imho fast vernachlässigt werden. Davon sollte heutzutage nun fast mehr als genug vorhanden sein :)

[BUG]

Auch eine Idee wäre, wenn deine IDs in Wirklichkeit auf Integer gecastete Zeiger/Objektreferenzen wären. Die Objekte könntest du in einer Liste verwalten (wenn du sie mal so durchlaufen musst), greifst aber sonst immer über die Referenz auf sie zu. Das sollte auch schnell gehen.

Der AI-Engine erzählst einfach du nicht, dass die IDs in Wirklichkeit Zeiger sind.

[Iwo Asnet]

Also bei dem Verwaltungskram verwende OOP. Die paar Nanosekunden, die man vielleicht (wenn überhaupt) einspart, lohnen nicht den Mehraufwand.

Programmierer und strukturiere sauber, dann wird es auch schnell (genug). Wenn Du nicht völlig bekloppt programmiert hast, dann kannst Du zum Schluss noch an den kernigen Stellen etwas rausholen.

Nach meinen bescheidenen Kenntnissen produziert eine Klasse beim Instantiieren und bei virtuellen Methodenaufrufen etwas Overhead, aber ansonsten verhält es sich (vom Zeitverhalten her) wie ein Zeiger auf ein Record.

Wenn du mit 'Handles' arbeiten willst, dann würde ich eine Dictionary nehmen. Wenn ein Objekt eingetragen wird, erzeugst Du eine ID und das ist das Handle. Das ist sicherer als ein Index oder eine als 'Handle' gecastete Adresse.

Wenn du auf ein Objekt zugreifen willst, suchst Du in der Dictionary nach dem Handle, das geht sauschnell und produziert nur ein paar CPU-Zyklen overhead. Wird es nicht gefunden, kannst Du sehr sauber reagieren. Bei als Handle verkleideten Indizes oder Instanzzeigern kann man schnell richtig viel versaubeuteln ohne zu merken, was Sache ist.

Was das Exceptionhandling anbelangt ist nur das Auftreten einer Exception selbst performancetechnisch zu vermeiden. Das TRY an sich ist eigentlich nicht spürbar.

Also solltest Du mit TRY-EXCEPT arbeiten und ansonsten Exceptions vermeiden. Leider geht das oft zu Lasten der Lesbarkeit.

Ich würde mich übrigens an deiner Stelle hüten, nur auf Performance zu gehen, denn Lesbarkeit und vor allen Dingen "Robustheit" geht irgendwie vor, finde ich.

[Gargamel]

Zitat:

Wenn du mit 'Handles' arbeiten willst, dann würde ich eine Dictionary nehmen. Wenn ein Objekt eingetragen wird, erzeugst Du eine ID und das ist das Handle. Das ist sicherer als ein Index oder eine als 'Handle' gecastete Adresse.

Wenn du auf ein Objekt zugreifen willst, suchst Du in der Dictionary nach dem Handle, das geht sauschnell und produziert nur ein paar CPU-Zyklen overhead. Wird es nicht gefunden, kannst Du sehr sauber reagieren. Bei als Handle verkleideten Indizes oder Instanzzeigern kann man schnell richtig viel versaubeuteln ohne zu merken, was Sache ist.

Das habe ich leider garnicht verstanden.

Edit: Nur um Missverständnissen vorzubeugen. Die Objekt-ID, die durch AI_registerObject(...) und AI_removeObject(...) übergeben wird, ist eine von der 3D-Engine zugewiesene ID. Daran kann ich nichts ändern. Diese ID hat nichts mit dem Index in der KI-Liste zu tun.

[Iwo Asnet]

Alles klar, in den vorigen Posts kamen Ideen auf, Referenzen als Handles zu definieren. Wenn die 3D-Engines bzw. der Anwender der "KI" die IDs selbst vergibt, umso besser. Dann sind es für dich nur anonyme Identifikatoren. Hauptsache eindeutig.

Hier ist es mit Sicherheit am schnellsten, mit einer Dictionary zu arbeiten. Diese verwaltet in einer Art Liste die Objekte und rückt sie (sehr schnell) unter Angabe der ID wieder heraus.

[Gargamel]

Was ich bis jetzt bei all den Posts herauslesen konnte, nehmen sich Records und ein objektorientierter Ansatz nicht viel. Weder bezüglich Performance, noch Speicherverbrauch. Wobei OOP wegen Übersichtlichkeit und der schnelleren Erweiterbarkeit vorzuziehen ist.

@Iwo Asnet:

Mit Dictionary sind TList bzw. TObjectList gemeint? Wenn ja, wäre deren Vorteil einzig der, daß ich kein zweites dyn. Array brauche, um das erste dyn. Array nicht größer als nötig werden zu lassen. (wegen Löschung einzelner Elemente)

Zitat:

Diese verwaltet in einer Art Liste die Objekte und rückt sie (sehr schnell) unter Angabe der ID wieder heraus.

Aber was genau ist mit ...unter Angabe der ID... gemeint?

[Furtbichler]

Nee, eine Dictionary ist eine 'Liste' (eigentlich egal, was es genau ist), wo Du unter Angabe eines Schlüssels Daten ablegen kannst. So z.B.

Delphi-Quellcode:

MyDictionary.Add(ID, Data);
...
// später
...
MyData := MyDictionary[ID];
//

[Gargamel]

Ich kann die Klasse TDictionary bei mir nicht verwenden. (ich nutze Delphi Turbo Explorer)
Die Unit Contnrs beinhaltet die Klasse leider nicht.

[Klaus01]

.. vielleicht könntest Du dir mal anstelle dessen die THashmap anschauen.

Grüße
Klaus