Zyklische Referenzen

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.