Zyklische Referenzen

[audacia]

Folgender Code beschreibt eine Minimalversion meines Problemes:

class Node;
typedef COMSmartPtr <Node> NodePtr;
class Node : public IUnknown
{
private:
    ULONG refCount;
    NodePtr parent;
    vector <NodePtr> subNodes;
public:
    /* Standardimplementationen von QI, AddRef und Release */
    NodePtr getParent (void) { return parent; }
    unsigned getSubNodeCount (void) { return subNodes.size (); }
    NodePtr getSubNode (unsigned idx) { return subNodes[idx}; }
};

Ganz offensichtlich ist das ein klassischer Fall zyklischer Referenzen. Der übliche Workaround wäre, einen der Verweise nicht zählen zu lassen, z.B.:

Node* parent; // schwacher Verweis

Nun läuft das aber etwas meinen Absichten zuwider. Ich möchte, daß der gesamte Graph erhalten bleibt, solange auf einen Knoten noch eine externe Referenz existiert. Wenn jemand durch die Baumstruktur iteriert und alle Parent-Nodes wegwirft, soll er über currentNode->getParent() jederzeit wieder an ein valides Objekt kommen können.

Meine erste Idee - nicht besonders schön, aber es funktioniert - war, so etwas wie einen Kontext einzuführen:

class NodeGraph : public IUnknown
{
private:
    ULONG refCount;
    Node* firstNode;
public:
    /* Standardimplementationen von QI, AddRef und Release */
    ~NodeGraph (void) { delete firstNode; }
};

class Node : public IUnknown
{
private:
    NodeGraph* context;
    Node* parent;
    vector <Node*> subNodes;
    ~Node (void)
    {
        doSomethingWithSubNodes (); // <--
        deleteAllSubNodes ();
    }
public:
    /* Standardimplementation von QI */
    virtual ULONG STDMETHODCALLTYPE AddRef (void) { return context->AddRef (); }
    virtual ULONG STDMETHODCALLTYPE Release (void) { return context->Release (); }
    Node* getParent (void) { return parent; }
    unsigned getSubNodeCount (void) { return subNodes.size (); }
    Node* getSubNode (unsigned idx) { return subNodes[idx}; }
};

Nun sind zyklische Referenzen zwar seit jeher eines der Argumente für einen GC, doch ist die Reihenfolge beim GC nicht deterministisch, so daß ich ein Problem habe, wenn ich mich Finalizer darauf verlasse, daß z.B. die Sub-Nodes, auf die ich Referenzen habe, überhaupt noch existieren (was natürlich primär darauf hindeutet, daß Finalizer an sich eine schlechte Idee sind). Daher wüßte ich gerne: wie löst man so etwas in einer GC-Umgebung?

[knivil]

Folgender Code beschreibt eine Minimalversion meines Problemes

Nein, tut er nicht. Gib dir Muehe! Liegt das Problem beim recursiven Loeschen der Nodes? Was hat IUnknown damit zu tun? Ist es ein Baum/Wald oder ein (fast) vollstaendig verbundener Graph?

Bei solchen Graphen trennen ich meist Speicherverwaltung der Nodes und deren Benutzung. In deinem Fall wuerde Context einfach eine Liste aller Nodes (oder Zeiger auf jene) halten und beim Loeschen einfach die Liste abarbeiten ohne auch nur eine Node nach ihrem parend/children zu fragen. Alternativ kann aber jede Node auch einzeln eine Liste aller parents/children verwalten und im Falle eines Destruktoraufrufes die gegeben Eintraege in Eltern- und Kindknoten aktualisieren. D.h. braucht keine GC-Umgebung. In einer GC-Umgebung gibt es Mark&Sweep.

Und was meinst du mit Finalizer, wenn du C++ Code anbietest?

[audacia]

knivil schrieb:

Liegt das Problem beim recursiven Loeschen der Nodes? Was hat IUnknown damit zu tun? Ist es ein Baum/Wald oder ein (fast) vollstaendig verbundener Graph?

Soweit ich es sehe, läßt sich das alles meinen Beispielen und meinem Text entnehmen. IUnknown verwendete ich, weil die damit verbundene Referenzzählungssemantik bekannt ist und dazu taugt, meinen Ansatz zu erklären.

Als Voraussetzung kann also angenommen werden: ich habe referenzzählende Verweise (wie z.B. IUnknown), ich möchte im Destruktor eines Nodes etwas mit dessen Subnodes anstellen, und der ganze Graph soll erst zerstört werden, wenn keine externe Referenz mehr existiert. Das vorgegebene Interface für Node sehe so aus:

class INode : public IUnknown
{
public:
    virtual INodePtr getParent (void) = 0;
    virtual unsigned getSubNodeCount (void) = 0;
    virtual NodePtr getSubNode (unsigned idx) = 0;
};

knivil schrieb:

Bei solchen Graphen trennen ich meist Speicherverwaltung der Nodes und deren Benutzung.

In Java müßte dann also jeder, der eine Referenz auf einen Node erhält, auf dieser dispose() aufrufen; jeder Node gibt das wie oben an die Kontextstruktur weiter, die dann manuell Referenzzählung durchführt und, sobald der Referenzzähler 0 erreicht, das tatsächliche dispose() für den Graphen durchführt. Nur ist das recht ineffizient und außerdem _wesentlich_ umständlicher als obige Lösung in C++

knivil schrieb:

In deinem Fall wuerde Context einfach eine Liste aller Nodes (oder Zeiger auf jene) halten und beim Loeschen einfach die Liste abarbeiten ohne auch nur eine Node nach ihrem parend/children zu fragen.

Also etwa das, was mein Code oben macht, nur daß du gleich eine Liste aller Nodes speicherst? Wo ist der Vorteil?
Oder mißverstehe ich dich? Dann erkläre mal genauer.

knivil schrieb:

D.h. braucht keine GC-Umgebung.

Das weiß ich selbst. Siehe meine Frage

knivil schrieb:

Und was meinst du mit Finalizer, wenn du C++ Code anbietest?

Bitte lies den letzten Satz nocheinmal. Ich wüßte gerne, wie man so etwas in einer GC-Umgebung, also in Java, in C# oder Objective-C umsetzt, und dort gibt es zumeist so etwas wie Finalizer. Und weshalb die vermutlich nicht genügen, habe ich auch geschrieben.

Ich befürchte allerdings, daß die Antwort auf meine Frage "genauso" lautet, was in den meisten GC-Sprachen mit den genannten Umständen verbunden sein wird. Vermutlich habe ich also meine Frage falsch gestellt, da ein GC gar nicht zur Freigabe von Ressourcen verwendet werden kann oder sollte. (Es gibt ja, glaube ich, nicht mal in allen Umgebungen eine Garantie, daß der Finalizer aufgerufen wird?) Richtiger wäre dann wohl gewesen "wie löst man das in Java oder C#?.

[+fricky]

audacia schrieb:

(Es gibt ja, glaube ich, nicht mal in allen Umgebungen eine Garantie, daß der Finalizer aufgerufen wird?) Richtiger wäre dann wohl gewesen "wie löst man das in Java oder C#?.

vielleicht hilft dir das: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/ref/PhantomReference.html

[audacia]

+fricky schrieb:

vielleicht hilft dir das: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/ref/PhantomReference.html

Danke, aber es sieht so aus, als bekäme man da gar keinen Zugriff mehr auf das Objekt selbst. Ich bin nicht sicher, ob das hierfür so nützlich ist.

[hustbaer]

In GC' Sprachen meidet man solche Dinge einfach wie Gebiete in denen grad die Pest umgeht.

Ganz allgemein finde ich dass shared ownership (von Objekten die unmanaged Resourcen enthalten) in GC' Sprachen nicht "schön" implementiert werden kann. Auch ohne irgendwelche Zyklen.

Ansonsten hilft man sich vielleicht dadurch, dass man fordert, dass jeder der irgendwelche Nodes verwenden will, auch eine Referenz auf den zugehörigen "Context" hält. Und diese mit "Release()" explizit freigibt, wenn er fertig ist. Das spart wahrscheinlich erheblichen Aufwand, da man nicht jede Node-Referenz die man irgendwo verwendet "zählen" muss.

BTW: Das "managed Referenzen ungültig im Finalizer" Problem kann man umgehen, indem man bestimmte Dinge selektiv "rootet". Würde ich aber nicht empfehlen, ohne dass man sehr genau vorher darüber nachdenkt.

[knivil]

knivil schrieb:

Alternativ kann aber jede Node auch einzeln eine Liste aller parents/children verwalten und im Falle eines Destruktoraufrufes die gegeben Eintraege in Eltern- und Kindknoten aktualisieren.

Alle Referenzen wurden entfernt, Objekt kann vom GC eingesammelt werden, Zeitpunkt des Destruktoraufrufes ist aber variabel. Hier muesste man jedoch den Destruktor explizit aufrufen, bzw. das in einer seperaten Methode explizit machen, wie Node.remove().

[audacia]

hustbaer schrieb:

In GC' Sprachen meidet man solche Dinge einfach wie Gebiete in denen grad die Pest umgeht.

Das habe ich befürchtet.

hustbaer schrieb:

Ansonsten hilft man sich vielleicht dadurch, dass man fordert, dass jeder der irgendwelche Nodes verwenden will, auch eine Referenz auf den zugehörigen "Context" hält. Und diese mit "Release()" explizit freigibt, wenn er fertig ist. Das spart wahrscheinlich erheblichen Aufwand, da man nicht jede Node-Referenz die man irgendwo verwendet "zählen" muss.

Ja, man spart sich einen Referenzzählungsmechanismus, aber der Benutzer muß doppelt so viele Referenzen halten. Auch nicht schön.

Theoretisch wäre es ja auch in einer GC-Sprache möglich, so etwas halbwegs zu automatisieren, allerdings ist die einzige mir bekannte Sprache, die so viel Flexibilität bietet, C++/CLI. Und dann kann man es auch gleich in C++ schreiben.

hustbaer schrieb:

BTW: Das "managed Referenzen ungültig im Finalizer" Problem kann man umgehen, indem man bestimmte Dinge selektiv "rootet". Würde ich aber nicht empfehlen, ohne dass man sehr genau vorher darüber nachdenkt.

"Rooting" - das hieße vermutlich, daß man irgendwo in einer globalen Liste eine Referenz auf den Graphen unterbringt? Oder meinst du etwas anderes?

[hustbaer]

audacia schrieb:

hustbaer schrieb:

BTW: Das "managed Referenzen ungültig im Finalizer" Problem kann man umgehen, indem man bestimmte Dinge selektiv "rootet". Würde ich aber nicht empfehlen, ohne dass man sehr genau vorher darüber nachdenkt.

"Rooting" - das hieße vermutlich, daß man irgendwo in einer globalen Liste eine Referenz auf den Graphen unterbringt? Oder meinst du etwas anderes?

Nönö, genau das. "Zu einer GC-Root machen" halt.
Damit kann man fast beliebig tricksen.

[hustbaer]

knivil schrieb:

knivil schrieb:

Alternativ kann aber jede Node auch einzeln eine Liste aller parents/children verwalten und im Falle eines Destruktoraufrufes die gegeben Eintraege in Eltern- und Kindknoten aktualisieren.

Alle Referenzen wurden entfernt, Objekt kann vom GC eingesammelt werden, Zeitpunkt des Destruktoraufrufes ist aber variabel. Hier muesste man jedoch den Destruktor explizit aufrufen, bzw. das in einer seperaten Methode explizit machen, wie Node.remove().

Bitte nicht Destruktor sagen wenns um Finalizer geht.

[knivil]

Bitte nicht Destruktor sagen wenns um Finalizer geht.

Ok, es soll einfach eine Funktion/Methode sein, die man in C++ in den Destuktor stecken wuerde und explizit aufruft.

[Badestrand]

Wenn ich das Problem richtig verstehe, musst du also nur die externen Referenzen zählen. Eventuell könnte man intern rohe Zeiger verwenden, bei Nachfrage Smart Pointer nach außen geben und durch die Kontrolle über AddRef und Release die Root-Node mitzählen lassen, wie viele externe Referenzen es gibt.

Wenn IUnknown und COMSmartPtr so arbeiten, wie ich mir das vorstelle, könnte es so funktionieren:

class Node : public IUnknown, boost::noncopyable
{
	private:
		unsigned      refCount;
		Node*         parent;
		vector<Node*> subNodes;

	private:
		Node( Node* parent ) : parent(parent), refCount(0)  {}

	public:
		static NodePtr create()            { return NodePtr( new Node(NULL) ); }

        // Zum Testen
		void addChild()                    { subNodes.push_back(new Node(this)); }

		NodePtr getParent (void)           { return NodePtr(parent); }
		unsigned getSubNodeCount (void)    { return subNodes.size(); }
		NodePtr getSubNode (unsigned idx)  { return NodePtr(subNodes[idx]); }

		void AddRef()
		{
            // Referenz-Zählung wird an den Root-Knoten weitergegeben
			if ( parent )
				parent->AddRef();
			else
				++refCount;
		}

		void Release()
		{
            // Referenz-Zählung wird an den Root-Knoten weitergegeben
			if ( parent )
			{
				parent->Release();
			}
			else
			{
				if ( --refCount == 0 )
				{
					cout << "Destructing tree\n";
					// TODO: Destruct the tree
				}
			}
		}
};

Meinen ganzen Test-Code gibt's hier.

Kann aber auch gut sein, dass ich was übersehen habe.. Habe auch gerade nicht groß Zeit zu testen, muss weg

[audacia]

Badestrand schrieb:

Eventuell könnte man intern rohe Zeiger verwenden, bei Nachfrage Smart Pointer nach außen geben und durch die Kontrolle über AddRef und Release die Root-Node mitzählen lassen, wie viele externe Referenzen es gibt.

Das ist kaum anders als das, was ich bereits im ersten Post vorschlug, nur benutzt du den Root-Node als Kontextstruktur. Das wäre hinsichtlich des Codeumfangs eine kleine Optimierung, jedoch ist es nur für diesen Spezialfall und nicht für komplexere Graphen (die z.B. kein Root-Element haben) möglich, und außerdem ist es recht ineffizient, weil die Komplexität von AddRef() und Release() proportional zur Tiefe des jeweiligen Nodes ist.

Badestrand schrieb:

Kann aber auch gut sein, dass ich was übersehen habe.

Z.B. scheinst du übersehen zu haben, daß meine Frage eigentlich war, wie das in einer GC-Umgebung umgesetzt wird

[hustbaer]

knivil schrieb:

Bitte nicht Destruktor sagen wenns um Finalizer geht.

Ok, es soll einfach eine Funktion/Methode sein, die man in C++ in den Destuktor stecken wuerde und explizit aufruft.

OK. Dann ist es weder ein Destruktor noch ein Finalizer, sondern eine "Dispose" Funktion

[Badestrand]

audacia schrieb:

Das ist kaum anders als das, was ich bereits im ersten Post vorschlug

Oh richtig, hatte ich nicht erkannt.

audacia schrieb:

Das wäre hinsichtlich des Codeumfangs eine kleine Optimierung, jedoch ist es nur für diesen Spezialfall und nicht für komplexere Graphen (die z.B. kein Root-Element haben) möglich, und außerdem ist es recht ineffizient, weil die Komplexität von AddRef() und Release() proportional zur Tiefe des jeweiligen Nodes ist.

Hab ich mich jetzt nicht tiefer reingedacht, aber beide Punkte würde ich spontan nicht als Hindernisse sehen. Die Komplexität von AddRef/Release kann man umgehen, indem man jedem Knoten einen Zeiger auf den Root-Knoten mitgibt. Und irgendeinen Knoten wird man doch auch in komplexeren Graphen als "Root"-Knoten bestimmen können, muss ja keine logische Wurzel sein.

audacia schrieb:

Badestrand schrieb:

Kann aber auch gut sein, dass ich was übersehen habe.

Z.B. scheinst du übersehen zu haben, daß meine Frage eigentlich war, wie das in einer GC-Umgebung umgesetzt wird

Ok, sorry, darauf hab ich keine Antwort

[knivil]

OK. Dann ist es weder ein Destruktor noch ein Finalizer, sondern eine "Dispose" Funktion

Alles namentliche Erfindungen von Sprachen, die ich als "boese" empfinde. Dazu aber in einem anderen Thread mehr ...

[hustbaer]

knivil schrieb:

OK. Dann ist es weder ein Destruktor noch ein Finalizer, sondern eine "Dispose" Funktion

Alles namentliche Erfindungen von Sprachen, die ich als "boese" empfinde. Dazu aber in einem anderen Thread mehr ...

Ist doch egal wers erfunden hat (davon abgesehen dass es sowieso die Schweizer waren).
Es sind drei sehr verschiedene Dinge, und daher sollte man verschiedene Namen verwenden.

Oder willst du alle drei "Destruktor" nennen, damit sich überhaupt keiner mehr aus kennt?

[Badestrand]

Bin zufällig über ein relativ interessantes Paper gestolpert: http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf

[audacia]

Badestrand schrieb:

Bin zufällig über ein relativ interessantes Paper gestolpert: http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf

Sehr interessant. Das residiert fortan in meinen Bookmarks Ich frage mich, ob sich das ohne weiteres in nativen Sprachen umsetzen läßt; wenn die Gefahr von Zirkularverweisen sehr hoch oder nicht vollständig vorab determinisierbar ist, kann das eine angemessene Problemlösung sein.