Deterministische (sequentielle) Speicherverwaltung

[Bergmon]

Hallo liebes Forum,

ich weiß nicht in wie weit Speicherverwaltung in C++ noch eine große Rolle spielt, gibt es mittlerweile ja zahlreiche Smart-Pointer Implementierungen sogar im C++-Standard durch boost.
Ich bin neulich auf eine Smart-Pointer Implementierung aus einem (älteren, nicht zu alt:), SuperSmartPointer nennen sie die Klasse) Buch gestoßen, welche auf einer globalen Referenzenzählung eines Types beruht. Ich habe dann die Referenzzählung von der eigentlichen Zeiger-Klasse entkoppelt und kann dadurch die Referenzen geerbter Klassen unter einer gemeinsamen Basissklasse zählen lassen und besitze dennoch die vollen Typ-Informationen im Zeiger. Leider jedoch nicht mehr in der Referenzimplementierung. Außerdem wird durch eine weitere kleine Modifikation in der Zeigerklasse zwischen statischen und dynamischen Variablen nicht direkt unterschieden (sie werden auch gezählt), was eine flexible Anwendung ermöglicht.
Ich dachte ich poste einfach Mal den Code, falls es jemanden anderen auch interessiert. Zyklische Abhängigkeiten und Parallelverarbeitung wird nicht unterstützt. Funktioniert in meiner bisherigen Anwendung wunderbar, so dass kein einziges manuelles delete mehr benutzt wird.

Also lange Rede kurzer Sinn, hier der Code:

(i) Die Referenzzähler-Implementierung:

Code: Alles auswählen

///// ref ///////////////////////////////////////////////////////////////////////////////
template <typename T>
class ref
{
    protected:
    static std::map<T*, unsigned int> rfrnc;

    inline void init(T *);
    inline void init(T &);
    inline void finalize(T *);

    public:
        static  std::map<T*, unsigned int> reference();
};

template <typename T> std::map<T*, unsigned int> ref<T>::rfrnc;

template<typename T>
void ref<T>::init(T *p)
{
    if (rfrnc.find(p) == rfrnc.end())
        rfrnc[p] = 1;
    else
        rfrnc[p]++;
}

template<typename T>
void ref<T>::init(T &p)
{
    if (rfrnc.find(&p) == rfrnc.end())
        rfrnc[&p] = 2;
    else
        rfrnc[&p]++;
}

template<typename T>
void ref<T>::finalize(T *p)
{
    if(rfrnc.find(p) == rfrnc.end())
    {
        std::cerr << "ERROR: Missing entry in map!" << std::endl;
        return;
    }
    unsigned int &r = rfrnc[p];
    if(--r == 0)
    {
        rfrnc.erase(p);
        delete p;
    }
}


template <typename T>
std::map<T*, unsigned int> ref<T>::reference()
{
    return rfrnc;
}

Das eigentliche Zeiger-Template

Code: Alles auswählen

///// ptr ///////////////////////////////////////////////////////////////////////////////
template <typename T, typename I = T>
class ptr : public ref<I>
{
    T *p;

    public:
    ptr(T *);
    ptr(const ptr<T, I> &);
    ptr(T &);

    ~ptr();

    ptr<T, I>& operator =(const ptr<T, I> &rhs);

    const T& operator *() const;
    const T* operator ->() const;
    T& operator *();
    T* operator ->();

    operator void*() const { return p; }
};

template <typename T, typename I>
ptr<T, I>::ptr(T* p0)
{
    init(p = p0);
}

template <typename T, typename I>
ptr<T, I>::ptr(T &p0)
{
    p = &p0;
    init(p0);
}

template <typename T, typename I>
ptr<T, I>::ptr(const ptr<T, I> &p0)
{
    init(p = p0.p);
}

template <typename T, typename I>
ptr<T, I>::~ptr()
{
    finalize(p);
}

template <typename T, typename I>
ptr<T, I>& ptr<T, I>::operator =(const ptr<T, I> &rhs)
{
    if (this == &rhs)
        return (*this);

    finalize(p);
    init(p = rhs.p);

    return (*this);
}

template <typename T, typename I>
const T* ptr<T, I>::operator->() const
{
    return (p);
}

template <typename T, typename I>
const T& ptr<T, I>::operator*() const
{
    return (*p);
}

template <typename T, typename I>
T* ptr<T, I>::operator->()
{
    return (p);
}

template <typename T, typename I>
T& ptr<T, I>::operator*()
{
    return (*p);
}

Anwendung ganz normal:
(i) ptr<Type> p = ... (Referenz, Zeiger oder ptr<Type>)
(ii) ptr<Type, BaseType> p = ... (Referenz, Zeiger oder ptr<Type, BaseType>)

Funktioniert auch in stl-containern, z.B std::list<ptr<Type>> list. Allerdings habe ich das nur für die Liste bisher getestet.

Viele Grüße
Bergmon

p.s.: Werden keine Tabulatoren in der Formatierung unterstützt, oder ist es mein Fehler?

[CodingCat]

Aus irgendeinem Grund schmeißt das Code-Plugin die Formatierung weg, wenn keine explizite Sprachangabe gemacht wird. Für C++ geht das mit

Code: Alles auswählen

[/cn], ich habs dir mal in deinen Beitrag editiert, damit ich es besser lesen kann. ;-)

Leider ist diese Art der globalen Referenzzählung wohl mit das Grauenvollste, was man tun kann. Es ist traurig, dass es immer noch derart verbreitet ist, anstelle von durchdachtem Software-Entwurf zusätzliche Informationen einfach per Map hinzuzudichten. Dass das ganze nicht Thread-sicher ist, hast du selbst schon genannt. Das ist jedoch bei weitem nicht das Problematischste:

[list][*]Eine Map ist eine unglaublich unkompakte Datenstruktur. Intern steht hinter der Map eine Baumstruktur. Diese hält neben deinen Schlüsseln und Werten auch noch Ordnungsknoten. Das Ganze liegt bei Benutzung über einen längeren Zeitraum mit ziemlicher Sicherheit [i]nicht[/i] kontinuierlich im Speicher. Für jeden Smart Pointer, den du konstruierst oder zerstörst, musst du also mit Cache-Misses und somit Verzögerungen rechnen.[/list]
[list][*]Maps haben logarithmischen Suchaufwand. Liegen die Knoten des internen Suchbaums also nicht-kontinuierlich im Speicher, so musst du gleich mit einer ganzen Reihe von Cache-Misses rechnen. Generell ist es unsinnig, bei jeder Smart-Pointer-Konstruktion und -Destruktion eine Suche in entferntem Speicher durchzuführen.[/list]
[list][*]Zu allem Überfluss suchst du immer gleich zweimal: Einmal mit [cn]find()[/cn] und gleich nochmal mit [cn]operator [][/cn][/list]
[list][*]Deine Refernzenklasse hat uneinheitliche Semantik. Warum sollte eine Referenz anders gezählt werden als ein Zeiger?[/list]
[list][*]Deine Smart-Pointer-Klasse erzwingt [cn]const[/cn]-Transitivität, also Besitzsemantik. Diese will man in der Regel bei [i]geteilten[/i], [i]referenzgezählten[/i] Objekten jedoch gerade nicht.[/list]
[list][*]Deine Referenzenklasse ist nicht 100% Exception-sicher. Auch wenn es unwahrscheinlich ist, dass beim Einfügen in die Map Ausnahmen fliegen, ist es doch in diesem grundlegenden Rahmen unschön.[/list]

[cn]shared_ptr[/cn] ist inzwischen nicht mehr Boost-exklusiv, sondern findet sich ganz offiziell im C++11-Standard. Die Implementierung der jeweiligen Standard-Bibliothek ist mit ziemlicher Sicherheit ziemlich optimal, was die transparente externe Verwaltung von Referenzzählern (ohne Suche!) angeht. Mit [cn]weak_ptr[/cn] wird obendrein das Auflösen zyklischer Abhängigkeiten unterstützt. Thread-sicher ist das Ganze auch.

Will man nicht die ganze Zeit [cn]shared_ptr[/cn] rumreichen, so bietet es sich immer noch mehr an, den Referenzzähler per Basisklasse direkt in die referenzgezählten Objekte zu legen, auch damit entfallen jegliche Suchen sowie Zugriffe auf entfernte Speicherbereiche. (Mit [cn]enable_shared_from_this[/cn] ebenfalls vom Standard unterstützt.)

Wieso bietest du ausgerechnet einen Void-Cast an?

[Bergmon]

Vielen Danke für die ausführliche Kritik :)

Ein Großteil deiner Kritik richtet sich nun zunächst auf die schlechte Implementierung des Referenzzählers. Diese kann man zum Glück ändern und wollte ich auch als eigenen Template-Parameter angeben (habe aber hier eine funktionierende Implementierung gewählt). Ich persönlich finde sie auch nicht so schön doch stammt sie aus dem Buch-Beispiel (deswegen auch der void-cast, hatte ich noch gar nicht richtig gesehen:)). Mir ging es persönlich um die Möglichkeit, bei einer zentralen Speicherverwaltung auch mit abgeleiteten Klassen umgehen zu können, da sie sonst eventuell in mehreren Listen auftauchen und die Referenzzählung viel schwieriger wird.
Der Unterschied zwischen Referenz- und Zeiger-Konstruktur: Das war ein Hack von mir um die bestehende Implementierung sowohl für Heap-, als auch Stack-Addressen zuerweitern.

Grundsätzlich gibt es zwei disjunkte Prinzipien der Verwaltung: Zentral und Dezentral. Welches im Allgemeinen besser ist, mag ich nicht beurteilen. Ich denke im Allgemeinen nimmt man eine Mischung von beiden und das Verhältnis hängt von der lokalen Aufgabe ab. Bei der Speicherverwaltung fände ich ein dezentrales System an sich "intelligenter", weil man weniger globale Abhängikeiten hat und das ganze immer den kürzesten Weg nimmt. Finde ich persönlich ziemlich schwierig umzusetzen. In wie weit da shared_ptr weiterhilft, werde ich mir anschauen, danke für den Hinweis. Das einfachste wäre wohl wieder zu einer lokalen Referenzzählung überzugehen, allerdings hat man dann keinen Überblick mehr auf die allokierten Objekte, ein Effekt einer dezentralen Verwaltung?

Könntest du mir den Punkt mit der Besitzsemantik etwas genauer erklären?

Viele Grüße
Bergmon

[CodingCat]

Ein Großteil deiner Kritik richtet sich nun zunächst auf die schlechte Implementierung des Referenzzählers.

Das UND die zentrale Verwaltung, die permanenten Zugriff auf entfernten Speicher notwendig macht, unabhängig von der Güte der Implementierung.

Mir ging es persönlich um die Möglichkeit, bei einer zentralen Speicherverwaltung auch mit abgeleiteten Klassen umgehen zu können, da sie sonst eventuell in mehreren Listen auftauchen und die Referenzzählung viel schwieriger wird.

Du hast das Problem zwar umgangen, aber nicht wirklich beseitigt. Wenn du Zeiger von Base und Derived hast, werden diese getrennt verwaltet, und sobald einer der beiden nicht mehr existiert, das Objekt fälschlicherweise vorzeitig zerstört. Damit das nicht passiert, verlangst du vom Benutzer, dass er immer die richtige Basisklasse angibt. Eventuell hat Derived mehrere Basisklassen, steckt in einer Hierarchie. Wie sorgst du dafür, dass alle Benutzer sich auf eine Basisklasse einigen? Wie sorgst du dafür, dass die Basisklasse nicht vergessen wird?

Der Unterschied zwischen Referenz- und Zeiger-Konstruktur: Das war ein Hack von mir um die bestehende Implementierung sowohl für Heap-, als auch Stack-Addressen zuerweitern.

Ja, das war mir durchaus klar, aber es ist eben ein Hack, und Hacks haben in dieser Programmebene ganz sicher nichts zu suchen. ;)

Grundsätzlich gibt es zwei disjunkte Prinzipien der Verwaltung: Zentral und Dezentral. Welches im Allgemeinen besser ist, mag ich nicht beurteilen. Ich denke im Allgemeinen nimmt man eine Mischung von beiden und das Verhältnis hängt von der lokalen Aufgabe ab. Bei der Speicherverwaltung fände ich ein dezentrales System an sich "intelligenter", weil man weniger globale Abhängikeiten hat und das ganze immer den kürzesten Weg nimmt. Finde ich persönlich ziemlich schwierig umzusetzen.

Speicherverwaltung wird meist an irgendeiner Stelle zentral. In deinem Fall ist es aber nicht die Speicherverwaltung, sondern die Referenzverwaltung. Du musst damit rechnen, dass Leute andauernd Smart Pointers konstruieren, eventuell benutzen sie Smart Pointers IMMER an Stelle von Zeigern. Auch wenn ich persönlich kein Fan davon bin, ist das beispielsweise bei shared_ptr der Standardmodus. Somit fügst du potenziell an Stelle einer jeden Zeigerdefinition implizit eine binäre Suche in entferntem Speicher ein.

In wie weit da shared_ptr weiterhilft, werde ich mir anschauen, danke für den Hinweis. Das einfachste wäre wohl wieder zu einer lokalen Referenzzählung überzugehen, allerdings hat man dann keinen Überblick mehr auf die allokierten Objekte, ein Effekt einer dezentralen Verwaltung?

shared_ptr erzeugt bei (Erst-)Konstruktion mit einem rohen Zeiger einen zugehörigen Referenzzähler auf dem Heap. Ab diesem Zeitpunkt werden anstatt roher Zeiger nur noch shared_ptr-Objekte rumgereicht, bei Kopie eines shared_ptr (auch bei impliziten/expliziten Up-/Down-Casts) wird dieser interne Referenzzähler automatisch weitergegeben. Mit dem letzten shared_ptr (bzw. weak_ptr) verschwindet nicht nur das verwaltete Objekt, sondern auch sein Referenzzähler.

Da ich kein Freund von permanenter Referenzzählung durch permanente Kopie von shared_ptr-Instanzen bin, bevorzuge ich die Variante mit der referenzgezählten Basisklasse, die das Rumreichen roher Zeiger erlaubt. Nur im Fall echter langfristiger Teilung wird ein Smart Pointer erzeugt, der eine Referenz auf das entsprechende Objekt verwaltet.

Könntest du mir den Punkt mit der Besitzsemantik etwas genauer erklären?

Wenn du aus der Konstanz eines Zeigers auf die Konstanz des durch den Zeiger referenzierten Objektes schließt, bedeutet das, dass das referenzierte Objekt dem referenzierenden Objekt untergeordnet ist: Das untergeordnete Objekt ist const, weil eine logische Veränderung des untergeordneten Objektes eine logische Veränderung des übergeordneten Objektes implizieren würde.

[Bergmon]

Eventuell hat Derived mehrere Basisklassen, steckt in einer Hierarchie. Wie sorgst du dafür, dass alle Benutzer sich auf eine Basisklasse einigen?

Guter Punkt. Ich hatte das bis eben noch gar nicht auf dem Schirm, weil ich im Moment nur an einfache Bäume gedachte habe. Aber schon bei Multitrees wird es für manche Klassen nicht mehr funktionieren.

Somit fügst du potenziell an Stelle einer jeden Zeigerdefinition implizit eine binäre Suche in entferntem Speicher ein.

Ich will mich noch nicht von dem zentralen Aspekt von vornherein komplett trennen. Auf die schnelle viel mir eventuell eine Verbesserung ein. Was wäre, wenn die Referenz lokal gezählt wird und zusätzlich bei der Erzeugung eines neuen Zeigers eine Referenz auf den Referenzzähler global gespeichert wird? Dann wäre bei einer Kopie des Zeigers nur der interne Aufwand nötig und man hat global trotzdem diese Information zugänglich. Beim Löschen wäre allerdings dann der Aufwand nötig die überflüssige Referenz aus der globalen Liste zu schmeißen bzw. man würde es nicht deterministisch gestalten und ab und zu einen Thread starten, der die globale Liste durchsucht und verwaiste Einträge löscht?

Nur im Fall echter langfristiger Teilung wird ein Smart Pointer erzeugt, der eine Referenz auf das entsprechende Objekt verwaltet.

Da kommt mir die Frage auf, wie du hier eine Grenze ziehst? Das einzige was mir einfällt ist der Fall, wenn der Zeiger den Scope nicht verlässt. Smart-Pointer sind dann wohl überflüssig. Doch wenn dies nicht der Fall ist, woher weißt du auf welcher Zeitskala die Umgebung operiert? Lässt du das die Umgebung entscheiden, in dem Sinne, dass du mehrere Rückgabezeigertypen anbietest?

[dot]

Was für Vorteile bringt dir die globale Referenzzählung? Wieso muss sie unbedingt global sein? Wieso brauchst du überhaupt die Referenzzählung?
Mir fallen im Moment nur gravierende Nachteile ein. Allem voran eben, dass es global ist, was jeglichen Einsatz im Kontext mit Multithreading unter anderem schonmal unglaublich ineffizient macht. Die Implementierung über die map machts dann natürlich nicht besser...

[CodingCat]

Ich will mich noch nicht von dem zentralen Aspekt von vornherein komplett trennen.

Wieso nicht? Du hast externe, globale Abhängigkeiten, musst extern Konsistenz aufrecht erhalten, und durch globale Locks für Thread-Sicherheit sorgen. Was gewinnst du durch die Zentralität?

Auf die schnelle viel mir eventuell eine Verbesserung ein. Was wäre, wenn die Referenz lokal gezählt wird und zusätzlich bei der Erzeugung eines neuen Zeigers eine Referenz auf den Referenzzähler global gespeichert wird? Dann wäre bei einer Kopie des Zeigers nur der interne Aufwand nötig und man hat global trotzdem diese Information zugänglich. Beim Löschen wäre allerdings dann der Aufwand nötig die überflüssige Referenz aus der globalen Liste zu schmeißen bzw. man würde es nicht deterministisch gestalten und ab und zu einen Thread starten, der die globale Liste durchsucht und verwaiste Einträge löscht?

Klar wäre das eine Verbesserung der Laufzeit, aber damit erhöhst du die Komplexität nur noch weiter durch zusätzliche Ausführungspfade und Konsistenzbedingungen. Warum dann nicht gleich ganz dezentral, mit einer einzigen einheitlichen Programmlogik?

Da kommt mir die Frage auf, wie du hier eine Grenze ziehst? Das einzige was mir einfällt ist der Fall, wenn der Zeiger den Scope nicht verlässt. Smart-Pointer sind dann wohl überflüssig. Doch wenn dies nicht der Fall ist, woher weißt du auf welcher Zeitskala die Umgebung operiert? Lässt du das die Umgebung entscheiden, in dem Sinne, dass du mehrere Rückgabezeigertypen anbietest?

Ich muss überhaupt keine Grenze ziehen. Alles, was du per Parameter in eine Funktion reingereicht bekommst, lebt automatisch immer mindestens bis zum Ende dieser Funktion. Innerhalb von Funktionen muss ich folglich nie die Referenzen gegebener Ressourcen zählen, bei der Argumentübergabe auch nicht. Es gibt nur zwei Fälle, in denen Referenzzählung wichtig ist:

• Beim Erzeugen neuer Ressourcen innerhalb der erzeugenden Funktion (Ausnahmesicherheit!) sowie bei der Rückgabe der Ressource: In diesem Fall gebe ich tatsächlich immer Smart Pointers zurück, weil sonst das erzeugte Objekt natürlich gleich wieder sterben würde.

• Beim Speichern von Zeigern auf Ressourcen in einem nicht-lokalen Kontext, beispielsweise Speicherung in Attributen von Klassen: Nachdem die speicherende Funktion verlassen wurde, könnte die Ressource außerhalb der Funktion jederzeit freigegeben werden, somit muss jeder, der über den Ausführungszeitraum einer Funktion hinaus Zeiger auf Ressourcen speichert, selbst dafür sorgen, dass diese Ressource nicht zerstört wird.

[Bergmon]

Warum dann nicht gleich ganz dezentral, mit einer einzigen einheitlichen Programmlogik?

Naja, die Antwort ist folgende: Ich mache mir Gedanken auch über die zentrale Verwaltung, weil das Prinzip existiert. Allein das zwingt einen aus Gründen der Vollständigkeit daraüber nachzudenken. Wenn ein Prinzip von vornherein ausgeschlossen wird, kann das zu Problemen führen, die ich zuvermeiden suche. Wenn man beide Prinzipien verreinigt, ist man am Ende flexibler in der Programmentwicklung, einfach weil man sich aus funktionaler Sicht keine Gedanken machen muss über zentral oder dezentral.

Was für Vorteile bringt dir die globale Referenzzählung? Wieso muss sie unbedingt global sein?

Ein Vorteil der zentralen Verwaltung ist, wie ich finde, dass man einfach auf den aktuellen Zustand des Programms schauen kann. Man sieht die Klassen, die allokiert sind und kann sogar typsicher Funktionen aufrufen. Wenn man auf diesen "Gott"-Modus aus Gründen der Sicherheit verzichten möchte (die maximale Basis-Klasse bestimmt den "Gott"-Level), dann ist es doch mit der Referenzzählung und den typsicheren Objekten eine einfache Sache der Programmlogik zufolgen, womit ein praktischer Debug-Modus frei daherkommt. Für den Release-Modus wechselt man einfach die Implementierung zu einer Dezentralen und alle sind glücklich :).

Wieso brauchst du überhaupt die Referenzzählung?

Einfachste (einzige?) Möglichkeit speicherleckfrei zu programmieren. Wenn die Speicherfreigabe automatisiert ist, dann hat man viel gewonnen. Die Referenzzählung homogenisiert die Programmausführung in einem gewissen Sinne und liefert kontrollierbare Ergebnisse. Die map-Implementierung kommt nur durch das Beispiel zustande und ist einfach nur deswegen da. Es funktioniert immerhin damit;). Eine allgemeine Template-Parametrisierung wollte ich noch nicht als Ersatz schreiben bevor mir nicht die anderen Randbedingungen klar waren, deswegen auch der Thread.

Mir sind jetzt ein paar mehr Dinge klar geworden. Ich werde als nächstes wohl zu einem lokalen Referenzzähler wechseln und den Ort der Smart-Pointer weise wählen, damit sie nicht überall im Programm auftauchen. Den globalen Ansatz möchte ich dennoch weitervervolgen, gerade weil ich denke, dass das angesprochene Problem der multiplen Vererbung durch einfache Typ-Listen gelöst werden kann.

Viele Grüße
Bergmon

[dot]

Wenn ein Prinzip von vornherein ausgeschlossen wird, kann das zu Problemen führen, die ich zuvermeiden suche.

Was für Probleme wären das zum Beispiel? Versuch nicht Probleme für deine Lösungen zu finden, sondern versuch deine konkreten Probleme zu lösen ;)

Was für Vorteile bringt dir die globale Referenzzählung? Wieso muss sie unbedingt global sein?

Ein Vorteil der zentralen Verwaltung ist, wie ich finde, dass man einfach auf den aktuellen Zustand des Programms schauen kann. Man sieht die Klassen, die allokiert sind und kann sogar typsicher Funktionen aufrufen.

Also um typsicher Funktionen aufzurufen brauch ich keine Referenzzählung und ganz sicher nicht irgendwelche globalen Mechanismen...

Wieso brauchst du überhaupt die Referenzzählung?

Einfachste (einzige?) Möglichkeit speicherleckfrei zu programmieren.

Also ich kann 90% der Zeit ohne Referenzzählung sehr viel besser exceptionsafe und leckfrei programmieren. Schau dir mal std::unique_ptr (auto_ptr nur richtig) und boost::scoped_ptr an. In 9.99999% der restlichen Fälle verwend ich dann intrusive Referenzzählung. Alles andere kommt praktisch nie vor. Und wenn es vorkommt, dann das meistens auch nur in Zusammenhang mit COM; persönlich versuche ich Reference Counting eher zu vermeiden, denn am Ende ist es imo ein Symtpom für unklare Beziehungen zwischen Objekten. std::shared_ptr ist in meiner Welt eine wirklich wirklich exotische Tierart...

Den globalen Ansatz möchte ich dennoch weitervervolgen, gerade weil ich denke, dass das angesprochene Problem der multiplen Vererbung durch einfache Typ-Listen gelöst werden kann.

Was für ein Problem?

[Bergmon]

Was für Probleme wären das zum Beispiel? Versuch nicht Probleme für deine Lösungen zu finden, sondern versuch deine konkreten Probleme zu lösen ;)

Das ist völlig richtig, nur es kann durchaus passieren, dass einem ein Problem nicht einfällt. Und dann heißt das nicht, dass es keines gibt. Im Allgemeinen ist das nicht entscheidbar und deswegen mache ich mir lieber allgemeine Gedanken um diese Unentscheidbarkeit mitzuerfassen.

Also um typsicher Funktionen aufzurufen brauch ich keine Referenzzählung und ganz sicher nicht irgendwelche globalen Mechanismen...

Finde in einer dezentralen Struktur alle allokierten Elemente einer bestimmten Klasse. Das ist bestimmt nicht einfach und mit diesem Mechanismus ist es so einfach, wie es nur gehen kann :). Es geht nicht darum, ob man es braucht oder nicht, stell dir einfach vor, es wird benötigt, was dann?

Also ich kann 90% der Zeit ohne Referenzzählung sehr viel besser exceptionsafe und leckfrei programmieren. Schau dir mal std::unique_ptr (auto_ptr nur richtig) und boost::scoped_ptr an. In 9.99999% der restlichen Fälle verwend ich dann intrusive Referenzzählung. Alles andere kommt praktisch nie vor. Und wenn es vorkommt, dann das meistens auch nur in Zusammenhang mit COM; persönlich versuche ich Reference Counting eher zu vermeiden, denn am Ende ist es imo ein Symtpom für unklare Beziehungen zwischen Objekten. std::shared_ptr ist in meiner Welt eine wirklich wirklich exotische Tierart...

Danke für den Tip. Die sind alle sehr praktisch, wenn dein Objekt nur in einer Liste zu einer Zeit auftaucht, oder? Doch was nimmt man, wenn man verschiedene Listen hat, mit Zeigern auf gleiche Objekte? Dann braucht man doch einen Referenzzähler (also z.B. boost::shared_ptr?), oder? Man kann nicht entscheiden, welche Liste wann welches Element freigibt, gerade weil es keine Hauptliste gibt, wenn es dezentral ist. Eigentlich sollte das gar nicht so selten vorkommen.

Was für ein Problem?

Ach, das war das Problem mit der mehrfachen Vererbung. Der einfache Separationsansatz scheitert bei mehrfacher Vererbung. CodingCat hatte mich darauf hingewiesen und das war wirklich ein guter Punkt.

[dot]

Also um typsicher Funktionen aufzurufen brauch ich keine Referenzzählung und ganz sicher nicht irgendwelche globalen Mechanismen...

Finde in einer dezentralen Struktur alle allokierten Elemente einer bestimmten Klasse. Das ist bestimmt nicht einfach und mit diesem Mechanismus ist es so einfach, wie es nur gehen kann :).

Toll. Und wann brauch ich das?
Wenn ich das brauche, dann bau ich das System so, dass das geht.
Abgesehen davon ist deine Struktur nichtmehr dezentral ;)

Es geht nicht darum, ob man es braucht oder nicht, stell dir einfach vor, es wird benötigt, was dann?

Doch, genau darum geht es. Warum sollte ich ein System bauen das alles mögliche kann was ich nicht brauche und für all die unnötigen Features auch noch damit bezahlen, dass die Dinge die ich tatsächlich brauche viel komplexer und ineffizienter werden als sie eigentlich sein müssten!?
Mit dem Argument baust du nur noch Systeme die alles können aber nichts wirklich.
Die für die konkrete Anwendung passenden Tradeoffs zu finden, ist doch gerade die Essenz der Softwareentwicklung.
Rat mal wieso es so viele verschiedene Arten von Smartpointern gibt (Reference Counting ist ja nur eine Möglichkeit unter vielen)? Richtig, weil es eben genau nicht den einen Smartpointer für alles gibt...

Doch was nimmt man, wenn man verschiedene Listen hat, mit Zeigern auf gleiche Objekte?

Stinknormale Zeiger, außer man braucht was anderes.

Dann braucht man doch einen Referenzzähler (also z.B. boost::shared_ptr?), oder? Man kann nicht entscheiden, welche Liste wann welches Element freigibt, gerade weil es keine Hauptliste gibt, wenn es dezentral ist. Eigentlich sollte das gar nicht so selten vorkommen.

Einen Referenzzähler verwendet man, wenn man Shared-Ownership Verhältnisse hat. Und das hat man meiner Erfahrung nach in Wahrheit äußerst selten. Nur weil ich eine oder mehrere Listen haben will die Zeiger auf Objekte enthalten, bedeutet das noch lange nicht, dass die Lebensdauer der Objekte von der Lebensdauer aller entsprechenden Elemente in allen Listen abhängt.

[Jonathan]

Danke für den Tip. Die sind alle sehr praktisch, wenn dein Objekt nur in einer Liste zu einer Zeit auftaucht, oder? Doch was nimmt man, wenn man verschiedene Listen hat, mit Zeigern auf gleiche Objekte? Dann braucht man doch einen Referenzzähler (also z.B. boost::shared_ptr?), oder? Man kann nicht entscheiden, welche Liste wann welches Element freigibt, gerade weil es keine Hauptliste gibt, wenn es dezentral ist. Eigentlich sollte das gar nicht so selten vorkommen.

Also ich bin der Meinung, dass man sich immer im klaren darüber sein sollte, wem welches Objekt gehört. In den allermeisten Fällen ist das sehr eindeutig und dann weiß man auch, wann man es löschen kann (nämlich, wenn sein Besitzer es nicht mehr benötigt).
Dazu gibt es dieses schöne Beispiel, dass ich in einem Java RTS erlebt habe: Ein Gebäude wurde zerstört, woraufhin es nicht mehr in der zentralen Liste war und nicht mehr gezeichnet wurde und nicht mehr angreifbar war. Aber ein Arbeiter hatte noch eine Referenz darauf, weil er seine Rohstoffe dort ablieferte. Das Ergebnis war, dass dieser Arbeiter unendlich Rohstoffe abliefern konnte, obwohl das haus nicht mehr existierte. Sobald man diesem Arbeiter aber einen anderen Befehl gab, war das Haus wirklich weg. Ja, der tolle Java Garbadge Collector, hat dafür gesorgt, dass es keine Speicherzugriffsfehler durch zu frühes löschen des Objektes gab. Aber eigentlich ist das schlecht, weil man so den Fehler erst viel später bemerkt. Wenn es direkt knallt, merkt man wenigstens, dass da etwas schief läuft.

Meiner Meinung nach, kann man weder mit Garbadge Collectorn noch mit Smartpointern solch ein Problem lösen. Die dienen nur der Bequemlichkeit und dass man nichts aus versehen vergessen kann.

[dot]

Meiner Meinung nach, kann man weder mit Garbadge Collectorn noch mit Smartpointern solch ein Problem lösen.

Ich würde sagen der Garbage Collector bzw. das Reference Counting macht den Bug überhaupt erst möglich ;)

[simbad]

Ich finde auch, das man versuchen sollte solche uneindeutigen Besitzverhältnisse zu vermeiden. Wenn man dann doch nicht dran vorbei kommt, dann sollte man sich was für diesen speziellen Fall einfallen lassen.
Denn häufig ist ja auch die Fehlerreaktion relevant.
Ich bin kein Freund von solchen, "das richten wir dann schon" methoden.

[Bergmon]

Hmm, was mir noch zu dem vorgestellten Smart-Pointer eingefallen ist.

Ich habe nicht im Asm-Output nachgeschaut. Doch eigentich müsste z.B. in einem Feld von ptr<int>, also

Code: Alles auswählen

ptr<int> p[10];

die Addressen alle in einer Reihe liegen:
Referenzen - ... - Addresse Daten - Addresse Daten - ....
, während sie bei einem lokalen Referenzzähler immer wechselseitig auftauchen:
Addresse Daten - Addresse Referenz - Addresse Daten - Addresse Referenz - ...
Für den Fall, dass ich auf diese Daten sequentiell Zugreife, wäre ich mit dem globalen ptr schneller, als bei dem lokalen, weil die Cache-Ausnutzung optimal ist. Ich werde das mal überprüfen.

Ich möchte auch noch ein Mal klarstellen, dass ich diesen Smart-Pointer nur vorstellen wollte. Das bedeutet in keinsterweise das ich jemanden von seiner Nützlichkeit überzeugen wollte. Er erschien mir eher eine Kuriosität, auf die ich just in dem Moment gestoßen bin.

Der Hack für den statischen Fall erzeugt verwaiste Einträge in der Referenzliste, was mir am Anfang ebenfalls gar nicht bewusst war.

[dot]

Nicht wenn du intrusive Referenzzählung verwendest...

[Bergmon]

Kannst du mir die Mechnismen genauer erläutern? Intrusive Referenzzählung sagt mir leider nicht soviel. (Google liefert diesen Thread als erstes Ergebnis :lol: (in englischer Sprache, gibt es wohl mehr))

[dot]

Beim intrusive reference counting ist der Counter einfach Teil des referenzierten Objekts. Beispiel: COM.

[Schrompf]

Auf Englisch "intrusive reference counting". Es gibt allgemein einige "Intrusive"-Konzepte wie z.B. auch die Boost Intrusive Containers - das Prinzip ist bei allen gleich: anstatt eine Verwaltungsaufgabe durch eine eigene Klasse abzubilden, quetscht man die Aufgabe in die zu verwaltende Klasse mit rein. Bei einer Intrusive List z.B. leitet man eine Klasse von dem List Node ab und kann danach Instanzen der Klasse selbst als Listenknoten verwenden. Wenn man die Instanzen eh mit new anlegt, erspart man sich dadurch den Zusatzaufwand für das Anlegen und Verwalten der List Nodes.

[Bergmon]

Achso, dann habe ich aber auch wieder Sprünge in einem Feld von Objekten:

Referenzzähler - Objektdaten - Referenzzähler - Objektdaten - ...

[dot]

Ja hast du, aber nicht in einem Feld von Zeigern auf diese Objekte.

Abgesehen davon würd ich mit Reference Couting wie gesagt sehr sehr sparsam umgehen...