Methoden zur Speicherverwaltung in eigenen Datenstrukturen

[CSHW89]

Hallo,
ich würde gerne mal eine Umfrage (weiß allerdings grad nicht wie) bzw. Diskussion starten. Es geht darum, wie man am besten Elemente in einer eigenen Datenstruktur (z.b. Stack) speichert, und wie man damit umgeht, wenn sie gelöscht werden. Mich beschäftigt diese Frage z.Z. wieder, da ich schon sehr viele Ansätze gefunden hab, aber keiner so wirklich zufriedenstellend war. Das Problem ist halt, dass PB erstens kein OOP unterstützt (ich will jetzt keine Diskussion starten, warum denn nicht), und zweitens keinen Garbage Collector besitzt. Also muss man sich selbst um die Speicherverwaltung kümmern, klar! Aber wie? Hab in den Jahren nun vier mögliche Wege gefunden, die ich jetzt mal vorstellen will:

Zu jeder Methode gibt es übrigens hier ein Beispielcode:
http://cshw89.mevedia.de/StackMethoden.zip

=======================
Methode1:
- Einfügen (push) kann man nur Integer bzw. Pointer
- Beim Löschen aus dem Stack (pop) wird der eingefügte Wert ignoriert. Es wird also nichts freigegeben.

Vorteile
- Die eingefügten Werte können alles sein: Integer, Pointer von Strings, Speicheradressen ect...

Nachteile:
- Speicherleckgefahr!
- Falls es Pointerwerte sind, muss der Benutzer den Stack immer leeren, und dabei jeden Wert freigeben
- Falls komplexere Gebilde zum Stack hinzugefügt werden, muss darauf geachtet werden, dass auch weitere Verweise freigegeben werden

=======================
Methode2:
- Einfügen (push) kann man nur Speicheradressen
- Beim Löschen aus dem Stack (pop) wird der eingefügte Wert als Speicheradresse interpretiert und der Speicher freigegeben

Vorteile:
- Falls die Speicherstellen keine Verweise zu weiteren Speicheradressen besitzen, braucht sich der Benutzer um nichts zu kümmern

Nachteile:
- Speicherleckgefahr!
- Siehe Vorteil, falls nicht, muss darauf geachtet werden, und seperat freigegeben werden
- Im Stack können keine einfachen Werte wie "1" hinzugefügt werden. Dazu muss immer ein Speicher adressiert werden, indem dann "1" hineingeschrieben wird

=======================
Methode3:
- OOP Gedanke
- Erstelle ein Interface Object, das eine Funktion 'free' besitzt
- Jedes eingefügte Element muss einer Structure/Interface angehören, die/das von Object erbt. Jedes Element besitzt also eine free()-Methode
- Beim Löschen aus dem Stack (pop) wird diese Funktion free() aufgerufen

Vorteile:
- Keine Speicherleckgefahr
- Es können in einem Stack Elemente vieler verschiedener "Klassen" hinzugefügt werden

Nachteile:
- Für jeden primitiven Datentyp muss es eine "Wrapper-Klasse" geben (Im Beispiel: Int)
- Overhead: Falls der Benutzer ein Element einer eigenen Structure hinzufügen will, muss er dafür Structure, Interface, eine New-Methode, und eine Free-Methode schreiben.

=======================
Methode4:
- Structure / Interface und die Funktionen vom Stack werden nicht nur einmal definiert, sondern mit einem Macro für jeden Typ, für den der Benutzer ein Stack braucht

Vorteile:
- Jede Art von Daten können im Stack gespeichert werden
- Falls die Elemente keine Verweise zu weiteren Speicheradressen besitzen, braucht sich der Benutzer um nichts zu kümmern

Nachteile:
- Speicherleckgefahr!
- Siehe Vorteil, falls nicht, muss darauf geachtet werden, und seperat freigegeben werden
- Overhead im kompilierten Code
- Autovervollständigung in der IDE funktioniert nicht

=======================

Meine Frage nun, welche ist die beste?

Falls jemand Fragen zu einer Methode hat, stellt sie bitte. Falls jemand vielleicht sogar noch eine weitere Methode kennt, stellt sie bitte vor.
Ich bedanke mich übrigens bei jedem, der es bis hier hin geschaft hat

lg Kevin

[STARGÅTE]

Ich glaube eine perfekte Lösung gibt es nicht, da es immer auf die Situation ankommt.

Wenn ich wirklich nur ein Stack aus Integers habe, oder einer festen Datenlänge, nutze ich natürlich Methode1.
Dass heißt, es wird Platz für 1000 Elemente reserviert und mit jedem Push/Pop nur der Zeiger veränder an dem elesen/geschrieben wird. Dort ist dies die schnellste und einfachste Methode.

Für meine Verwaltung für Undo-/Redo-Funktionen (was ja auch n Art Stack ist) verwende ich hingegen Methode 3.
Das heißt, jedes Elemente besitzt seine eigene Freigabe-/Initiallisierungs-Prozedure. Dort ist diese Variante einfach die praktischste, weil es halt verschiedene Arten von Elementen gibt und man sich beim hinzufügen/entfernen keine weiteren gedanken machne muss.

Für wirklich schnelle Verarbeitung eignet sich nur Methode 1, da alle andere zu viel Zeit darin verschwenden sachen zu reservieren/freizugeben.
Man sollte also so lange es geht (man also eine feste Datenlänge hat) immer bei methode 1 bleiben.
Auch bei Strings kann man ja FixStrings nutzen.
Selbst wenn die Länge nicht bekannt ist, könnte man in als Header ein Counter einbauen, und einen Langen String in kleine zerlegen (mehrfach push) und beim lesen dann mehrfach pop.

Allgemein gilt: Man sollte möglichs viel von den Prozeduren selbst überwachen lassen (rekursion, verschachtelung usw.) sodass der Benutzer sich nicht mit dem gedanken quälen muss, was er genau noch alles machen muss.

[remi_meier]

[...]Das Problem ist halt, dass PB erstens kein OOP unterstützt (ich will jetzt keine Diskussion starten, warum denn nicht), und zweitens keinen Garbage Collector besitzt. Also muss man sich selbst um die Speicherverwaltung kümmern, klar![...]

Och, portier das doch kurz mal auf Windows, dann hast du
deinen GC :
http://www.purebasic.fr/english/viewtop ... ilit=boehm

Ansonsten:
Unter PB würde ich Methode 1 bevorzugen. Keine unnötigen
Allokationen.

Abstrakt kannst du dein Problem als Objekt-Ownership Problem
betrachten. Die Elemente, welche du in den Stack legst, sind
die Objekte. Anfangs, wenn du das Objekt erstellst, gehört
es dir (dir allein), da nur du die Referenz (Speicheradresse)
kennst. Gibst du es dem Stack hast du folgende Möglichkeiten:

• Gib ownership ab. Das Objekt gehört nun alleine dem Stack.
• Behalte ownership. Das Objekt gehört immer noch dir, der Stack kennt es aber.

Der dem das Objekt gehört, muss es natürlich auch freigeben,
falls nicht mehr benötigt.
Bei Variante 1 würde es Sinn ergeben, wenn der Stack auch
wieder sein ownership abgibt, wenn das Objekt aus dem Stack
entfernt wird. Also muss der Stack nie Free() aufrufen.
Bei Variante 2 gehört das Objekt nie dem Stack, also darf er
nie Free() ausführen.

Ein Gemisch aus beiden Varianten würde ich nicht anwenden.
Vorteil bei Variante 1 ist, dass mehrere Clients (Klassen) des
Stacks direkt owner des Objekts werden. Somit ist das
gemeinsame Verwenden des Stacks sinnvoll.
Bei Variante 2 würde ein anderer Client zwar das Objekt
kennen, es gehört ihm aber nicht. Der Client, welcher das
Objekt in den Stack gelegt hat, muss es auch wieder freigeben.

Welche Variante ich bevorzuge ist je nach Anwendungsfall
unterschiedlich. Aber in keiner muss der Stack das Objekt
verwalten.

Das mal so meine Sicht.

Cheers!
Remi

[CSHW89]

Erstmal danke für eure Antworten.
Ich hätte vielleicht auch noch erwähnen sollen, dass Stack hier nur ein Beispiel war. Was ich eigentlich machen will, ist, mehrer Includes schreiben für viele verschiedene Datenstrukturen, wie Bäume, Graphen, Automaten ect..., damit ich die dann einfach schon parat hab, wenn ich die mal in einem Projekt brauche.
Es ist halt schon oft passiert, dass ich solche Datenstrukturen erstmal implementieren musste, bevor ich mit meinem eigentlich Projekt anfangen konnte.
Das Problem dabei ist halt nur dieser Satz...

Ich glaube eine perfekte Lösung gibt es nicht, da es immer auf die Situation ankommt.

...der leider sowas von wahr ist.

Ich denke im Endeffekt läuft es auf diese beiden Möglichkeiten hinaus:

Methode1:
- Performance

Methode3:
- Sicherheit und Bequemlichkeit des Nutzers

... wobei ich ja schon zu Methode 3 tendiere (wenn da nicht dieser blöde Performane-Verlust wäre).
Hm, ich werd mir das nochmal durch den Kopf gehen lassen

Noch zu diesem Satz:

Welche Variante ich bevorzuge ist je nach Anwendungsfall
unterschiedlich. Aber in keiner muss der Stack das Objekt
verwalten.

Naja Grundgedanke ist sicherlich richtig, und bei einem Stack vielleicht noch vertretbar. Aber sobald die Datenstruktur kompilzierter wird, z.b. bei Graphen, haste Knoten und Kanten, bei einem meiner Projekte haben die Knoten nicht nur so einfache Namen wie "q0", sondert besitzen selbst noch Listen, dessen Elemente sind auch noch Speicheradressen einer anderen Struktur, die auch noch Verweise hat ect...
Das kann sehr schnell, sehr unübersichtlich werden. Und wenn sich dann der Benutzer der Klassen "Graph" darum kümmern muss, wenn er einen Graph nicht mehr braucht, find ich, ist das dann auch nicht mehr Sinn der Sache, meine Meinung.

lg kevin

[remi_meier]

[...]
Noch zu diesem Satz:

Welche Variante ich bevorzuge ist je nach Anwendungsfall
unterschiedlich. Aber in keiner muss der Stack das Objekt
verwalten.

Naja Grundgedanke ist sicherlich richtig, und bei einem Stack vielleicht noch vertretbar. Aber sobald die Datenstruktur kompilzierter wird, z.b. bei Graphen, haste Knoten und Kanten, bei einem meiner Projekte haben die Knoten nicht nur so einfache Namen wie "q0", sondert besitzen selbst noch Listen, dessen Elemente sind auch noch Speicheradressen einer anderen Struktur, die auch noch Verweise hat ect...
Das kann sehr schnell, sehr unübersichtlich werden. Und wenn sich dann der Benutzer der Klassen "Graph" darum kümmern muss, wenn er einen Graph nicht mehr braucht, find ich, ist das dann auch nicht mehr Sinn der Sache, meine Meinung.

Es gibt einen deutlichen Unterschied zwischen einem
Stack und einem Graphen. Der Stack ist ein Container,
wo man Objekte hinein legt um sie später wieder zu
holen, ein Graph ist meist eine Datenstruktur, welche
aus Objekten besteht (man legt nicht Objekte hinein
um sie wieder zu entnehmen). Die richtige Vorgehens-
weise bei einem Graphen ist deshalb meist, dass
der Graph das Ownership auf seine Objekte hat

Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.

In computer science, a container is a class, a data structure[1][2], or an abstract data type (ADT) whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules.

Finde diesen Unterschied eigentlich ziemlich deutlich

Edit: Oh, habe soeben eine Erklärung dazu für C++ gefunden:
http://drdobbs.com/cpp/184409895

[Danilo]

Sowas macht nur Sinn, wenn es generische Typen unterstützt. In PB hast Du aber echt
ein Problem, ohne Operator-Overloading und Templates. Da kannst Du nur rumpfuschen
um das einfachste Zeug zum laufen zu bekommen, statt richtige Programme zu schreiben.

Mit Stack als Macro kannst Du den Typ nehmen: Stack( l ) und Stack( POINT ) - das Macro
generiert Stach_Push_l und Stack_Pop_l usw. - aber bei anderen Sprachen (C++/C#) ist das
schon eingebaut. PB ist für fortgeschrittene Sachen einfach zurück geblieben.
Wenn Du Programme entwickeln möchtest, statt Dich mit so Kleinzeugs rumzuschlagen, hilft
wohl nur C++/C#/Java.

[CSHW89]

Sowas macht nur Sinn, wenn es generische Typen unterstützt. In PB hast Du aber echt
ein Problem, ohne Operator-Overloading und Templates. Da kannst Du nur rumpfuschen
um das einfachste Zeug zum laufen zu bekommen, statt richtige Programme zu schreiben.

Naja geht. Ich finde meine 3. Methode kommt da schon sehr nah dran. Ist halt nur ein bisschen mehr Aufwand, aber wenn es dann einmal steht. Was mir dann nur sorgen bereitet, ist, wie Stargate schon sagte, die Performance. Das ständige Allokieren und Freigeben kann schon viel Zeit einnehmen. Allerdings muss man das ja auch bei OOP-Sprachen wie C++ und Java machen. Also werd ich mich wohl dafür entscheiden.

Danke nochmal an alle für die Antowrten.

lg Kevin

[NicTheQuick]

Wenn man sein Programm wirklich auf Geschwindigkeit trimmen will für schnelle Algorithmen, die diese Datenstrukturen brauchen, muss man noch an ganz andere Sachen denken. Einzelne Objekte pro Datensatz sind da meistens Gift. Nur mal ein Beispiel: Die Daten für den Graphen und die Übergangsfunktion eines endlichen Automaten legt man am besten in einem eindimensionalen Array ab. Je nach Cachegröße der CPU können so schon direkt alle Übergangsmöglichkeiten mit einem Rutsch in den Cache kopiert und dort behalten werden, was unheimlich Geschwindigkeit mit sich bringt. Im Gegensatz dazu ist die schönere, aber weitaus langsamere Variante das Hantieren mit Knoten, Kanten und deren Übergangsparameter in einzelnen Objekten. So können bei etwas größeren Automaten nie alle Übergänge gleichzeitig in den Cache geladen werden.

Aber ich glaube ich drifte schon wieder zu weit vom eigentlichen Thema ab.
Dazu sei vielleicht noch gesagt, dass ich da Danilo durchaus Recht gebe. Die Sache mit den Makros würde wahrscheinlich sogar gehen, aber sehr hässlich werden.

[CSHW89]

Dazu sei vielleicht noch gesagt, dass ich da Danilo durchaus Recht gebe. Die Sache mit den Makros würde wahrscheinlich sogar gehen, aber sehr hässlich werden.

Siehe dazu meine 4. Methode bzw. das Beispiel. Sobald da aber die Datenstruktur komplizierter wird, sieht man, glaub ich, nix mehr .
lg Kevin

[remi_meier]

Wenn man sein Programm wirklich auf Geschwindigkeit trimmen will für schnelle Algorithmen, die diese Datenstrukturen brauchen, muss man noch an ganz andere Sachen denken. Einzelne Objekte pro Datensatz sind da meistens Gift. Nur mal ein Beispiel: Die Daten für den Graphen und die Übergangsfunktion eines endlichen Automaten legt man am besten in einem eindimensionalen Array ab. Je nach Cachegröße der CPU können so schon direkt alle Übergangsmöglichkeiten mit einem Rutsch in den Cache kopiert und dort behalten werden, was unheimlich Geschwindigkeit mit sich bringt. Im Gegensatz dazu ist die schönere, aber weitaus langsamere Variante das Hantieren mit Knoten, Kanten und deren Übergangsparameter in einzelnen Objekten. So können bei etwas größeren Automaten nie alle Übergänge gleichzeitig in den Cache geladen werden.

Das stimmt so garantiert, aber bevor man so low-level
Überlegungen anstellt und sein Programm total umkrempelt,
kann man sich auch einmal alternative "malloc"-Implementationen
anschauen.
Geht man davon aus, dass alle Knoten und Kanten zu Beginn
zusammen alloziert werden, werden die meisten Allocators
die Datensätze hintereinander anordnen. D. h. sie sind praktisch
in einem eindimensionalen Array mit etwas Overhead dazwischen.

Es gibt dann natürlich solche, die genau auf diesen Fall optimieren
und solche, welche z. B. auf Multi-Threading spezialisiert sind.
Da hat man eine ganz schöne Auswahl

Aber ihr wisst ja, immer zuerst profilen bevor man optimiert.

@CSHW89: Man kann vieles irgendwie implementieren, aber in
PB braucht man für gewisse Sachen einfach 10x so viel Code
wie in anderen Sprachen. Und man hat kaum Typensicherheit.