Garbage Collection
-
seldon schrieb:
Eine shared_ptr-artige Vorgehensweise bricht bei Ringstrukturen zusammen, um diesen Einwand gleich abzufangen.
Wenn ich Ringkonstrukte hab, dann hab ich sowieso ganz andere, schlimmere Probleme
-
dot schrieb:
seldon schrieb:
Eine shared_ptr-artige Vorgehensweise bricht bei Ringstrukturen zusammen, um diesen Einwand gleich abzufangen.
Wenn ich Ringkonstrukte hab, dann hab ich sowieso ganz andere, schlimmere Probleme
Wie implementierst du eine doppelt verkettete Liste?
-
Michael E. schrieb:
dot schrieb:
seldon schrieb:
Eine shared_ptr-artige Vorgehensweise bricht bei Ringstrukturen zusammen, um diesen Einwand gleich abzufangen.
Wenn ich Ringkonstrukte hab, dann hab ich sowieso ganz andere, schlimmere Probleme
Wie implementierst du eine doppelt verkettete Liste?
Nicht mit zirkulären shared_ptr!?
Sowas wäre imo ein schwerer Designfehler. Was macht es für einen Sinn dass sich Listenelemente gegenseitig besitzen? Ihre Lebensdauer ist im Allgemeinen völlig unabhängig. Sofern es sich nicht um eine ganz merkwürdige Art von Liste handelt, klingt mir Reference Counting da von vornherein nach einer sehr schlechten Idee.
Aber zum Glück ist die Welt ja bei shared_ptr noch lange nicht zu Ende.
Zuallermindest gibt es weak_ptr um solche Beziehungen aufzulösen...
-
dot schrieb:
Nicht mit zirkulären shared_ptr!?
Sowas wäre imo ein schwerer Designfehler. Was macht es für einen Sinn dass sich Listenelemente gegenseitig besitzen? Ihre Lebensdauer ist im Allgemeinen völlig unabhängig. Sofern es sich nicht um eine ganz merkwürdige Art von Liste handelt, klingt mir Reference Counting da von vornherein nach einer sehr schlechten Idee.
Aber zum Glück ist die Welt ja bei shared_ptr noch lange nicht zu Ende.
Zuallermindest gibt es weak_ptr um solche Beziehungen aufzulösen...Und jetzt erklär mir bitte noch, wie der GC entscheiden soll, ob er weak_ptr oder shared_ptr benutzen soll
Deine Erklärung, warum shared_ptr für doppelt verkettete Listen Quatsch ist, ist richtig. Trotzdem wirst du wohl nicht behaupten, dass doppelt verkttete Listen mit ihren zirkulären Pointern Quatsch sind. Also funktioniert ein GC wohl nicht mit shared_ptr. Nichts anderes wurde behauptet.
-
Wir reden hier ja über ein Objektsystem, wie es Java besitzt, also Klassen als Referenztypen. Alle Java-Objekte haben Referenzzähler, aber diese alleine reichen nicht aus, um in allen Strukturen den tatsächlichen Todeszeitpunkt eines Objektes zu bemerken. Stell dir vor, du hättest keine nackten Zeiger, sondern nur shared_ptrs - wie baust du eine doppelt verkettete Liste und verhinderst Speicherlecks? Wie Michael richtig bemerkt, enthalten doppelt verkettete Listen massig Ringstrukturen im relevanten Sinn, und die muss man unter diesen Bedingungen anders abkanzeln.
Java und die meisten (wenn nicht alle) anderen Sprachen mit diesem Problem lösen das durch einen Garbage-Kollektor, der alle Weile mal kuckt, ob die Objekte noch gebraucht werden. Wenn man sich auf den Standpunkt stellen kann, dass diese Verzögerung bei Speicher kein Problem darstellt (was häufig der Fall ist), funktioniert das da auch ganz gut, aber eine allgemeine Ressourcenverwaltung kann man auf diese Weise halt nicht betreiben.
-
Darum gings doch nie!? Es ging darum zu zeigen, dass es nix ausmacht dass eine shared_ptr Lösung nicht mit zirkulären Abhängigkeiten klarkommt weil das sowieso ein Designfehler wäre.
Dass C++ nicht Java ist, ist mir klar und ich bin jeden Tag aufs Neue froh drüber
-
dot schrieb:
Darum gings doch nie!?
Eigentlich schon :p Keiner bezweifelt den Sinn von shared_ptr in C++ und jeder weiß, welche Alternativen es gibt. Aber seldon spricht doch über GC-Strategien und dass es keinen Sinn macht, dass ein GC sich auf shared_ptr stützt.
-
Dann hab ich seldons Post falsch verstanden
-
seldon schrieb:
Wir reden hier ja über ein Objektsystem, wie es Java besitzt, also Klassen als Referenztypen. Alle Java-Objekte haben Referenzzähler, aber ...
Ich hoffe dies ist ein Gedankenexperiment, denn dem ist nicht so...
-
Zeus: Wie erkennt der GC dann tote Objekte?
-
Ach, ich Depp. Du hast natürlich Recht, Hotspot betreibt mark-and-sweep über Eden und die Survivor-Spaces (richtig?). Ich bin da gehörig durcheinandergeraten, tut mir Leid.
Also, auf ein neues: Javas Objektsystem wäre durch Referenzzählung allein nicht darstellbar. Letztendlich besteht das Problem, dass der Zeitpunkt, wann ein Objekt nicht mehr gebraucht wird, in diesem System nicht trivial bestimmbar ist, und der Rest der Argumentation gegen eine GC-gestützte, allgemeine Ressourcenverwaltung bleibt unverändert.
-
Java 1.5?/1.6 und 1.7 verwenden paralleles Generation-GC, sowie .NET seid 2.0 als Standard Garbage Collection. Bei Java kann man sogar den GC über eine Parameter auswechseln, deswegen kann auch eine Kopplung von Referenzzähler in das Objektmodell nicht gegeben sein, oder? In dieser Weiße arbeiten nach meinen Kenntnisstand nur Delphi, Objective C/C++ <= 2.0 und Vala - wobei es durchaus unterschiede gibt. - Evtl. verstehen wir untereinander beim Begriff "Objektmodell" auch etwas anders.
Die toten Objekte zu erkennen ist im Gegensatz beim Referenzzählung kein triviales Angelegenheit, demnach bei jeden unterschiedlich GC-Konzept auch anders. Mit fehlt gerade auch als Beispiel nur das berühmte "Wagen-Prinzip" ein, dass ein Abgleich zwischen den gefunden Stackpointer mit deren Länge gegen ein Bereich(- welches ein Wagen symbolisiert) in ein anderen Wagen kopiert und den alten Bereich bereinigt - damit sind alle toten Bereiche(und damit auch dessen Objekte) freigibt. Bei diesen Beispiel sieht man, dass das mitführen von Referenzzähler nicht vorgesehen ist, weil nach dem Konzept ein überflüssige Information ist - aber nicht wie in den Sprachen die ich aufgezählt habe.
GC ist für mich ein zu komplexe Thema um sie alle in eine Schublade zu stecken - immerhin gibst es wissenschaftliche Material zu Nonblocking{lockfree} Real-Time Garbage Collection - zu lesen, hoffentlich find ich die zeit für native nano.
-
Was mir bei Java/C#/... abgeht, ist die Möglichkeit einfach und elegant Shared Ownership von "disposable" Resourcen zu implementieren.
In C++ geht das ja super-fein mit shared_ptr.Natürlich kann man sich in Java/C#/... auch eine Klasse basteln die nen Ref-Count für ein bestimmtes Objekt managt, und dann bei 0 eben Dispose()/close() macht. Nur ist das alles andere als elegant. Und vor allem: es fehlt ein Standard.
-
Michael E. schrieb:
Zeus: Wie erkennt der GC dann tote Objekte?
Wie bereits von zeus gesagt, ist das von GC zu GC unterschiedlich.
Ich weiß, dass der Flash-GC so arbeitet, dass er den Objektgraphen entlangwandert. Das heißt, irgendwo gibt es eine Menge von Objekten, die der GC kennt und er versucht für jedes Objekt zu beweisen, dass es von einem solchen Objekt referenziert wird. Dafür macht er eine Tiefensuche im Graphen und markiert alle Objekte, die referenziert werden. Den Rest löscht er. In der Praxis bricht der GC von Flash leider ab einer bestimmten Iterationstiefe ab und dann gibts memory leaks.
//edit eine kleine Korrektur...
-
Naja, generationell sind GCs in gemanagten Sprachen seit einer ganzen Weile eigentlich alle, aber damit ist noch nicht gesagt, wie genau die Feststellung funktioniert, dass ein Objekt tot ist.
Soweit ich das überblicke, läuft das bei Java so:
Das Speicherlayout des Heaps sieht vom Konzept her so aus:
| Eden | Survivor 1 | Survivor 2 | Tenured | +------+------------+------------+----------------------------------+Dabei ist Eden die Region, in der neue Objekte angelegt werden, eine der Regionen Survivor 1 und Survivor 2 enthält Objekte, die wenige GC-Durchläufe überlebt haben, während die jeweils andere leer ist, und Tenured ist eine Region für Objekte, die schon lange leben, die selten geprüft wird.
Ein normaler GC-Durchlauf passiert, wenn Eden vollläuft. Dieser überprüft die Objekte in Eden und dem belegten Survivor-Space, zerstört die, von denen er beweisen kann, dass sie tot sind und verschiebt den Rest in den leeren Survivor-Space bzw. nach Tenured, wenn sie inzwischen alt genug sind. Dadurch landen die lebendigen Objekte kompaktiert im vormals leeren Survivor-Space, während Eden und der vorher belegte Survivor-Raum frei werden. Dann können neue Objekte wieder in Eden angelegt werden, und der nächste GC-Durchlauf verfährt halt mit verdrehten Survivor-Spaces.
Das Verfahren ist dann performant, wenn die meisten Objekte nur sehr kurz leben (sonst muss ja massig Zeug verschoben werden, und man hat die ganze Problematik mit anderen Threads, die die Objekte zu benutzen versuchen), deswegen wird Tenured nur selten in einem gesonderten Modus angefasst, der dann den gesamten Tenured-Bereich aufräumt und kompaktiert.
Eine andere Frage ist, wie der GC feststellt, dass ein Objekt tot ist. Wenn ich das richtig verstanden habe (und ganz sicher bin ich mir da nicht) benutzen GCs in Java 6 und früher (fragt mich nicht wie lang früher) dafür ein nebenläufiges mark-and-sweep-Verfahren, und in Java 7 wurde etwas neues eingeführt, das ich noch nicht kenne (vermutlich eine Tri-Color-Kiste o.ä.). Hier könnte man bis zu einem gewissen Punkt womöglich mit Referenzzählern arbeiten, aber da das allein nicht ausreicht wird es wohl nicht gemacht.
Wenn ich von "Objektmodell" spreche, meine ich in der Hauptsache, dass Objekte in Java einer Referenzsemantik folgen. In C++ ist die Sache einfach - man legt ein Objekt auf den Stack, und wenn der Stapelrahmen zerstört wird, ist auch das Objekt dahin. In Java legt man das Objekt auf den Heap, und wenn der Block endet, in dem es erstellt wurde, können an anderen Stellen schon zwanzig Referenzen auf das selbe Objekt liegen. Der genaue Zeitpunkt, wann ein Objekt zerstört werden kann, ist so nicht trivial feststellbar, und das ist ein Problem, wenn man (und durch diesen Vorschlag kamen wir ja in die Diskussion) Ressourcenverwaltung allgemein (also nicht nur Speicher) durch den GC erledigen lassen will.
-
Das Prinzip nennt sich Generational Garbage Collection.
Gibt es einen bestimmten Grund den Generationen putzige aber sinnlose Namen wie Eden, Survivor, Tenured zu geben?
Hab' ich noch nie gehört, und finde ich auch reichlich doof.Generation X reicht doch vollkommen (pun intended).
Im Endeffekt ist Generational Garbage Collection aber bloss eine Optimierung, und nicht nötig um das Prinzip bzw. die Limitierungen eines GC zu erklären - ob nun Mark & Sweep oder anders.
Daher kann ich mich grad des Eindrucks nicht erwähren, dass du hier ein bisschen einen auf wichtig machst
-
Die Begriffe Eden, Survivor und Tenures habe ich mir nicht ausgedacht, sie stammen aus der Dokumentation von Sun. Die Generationen durchzunummerieren ist auch nicht ganz trivial, weil die Survivor-Spaces ihre Rollen dauernd tauschen. Generationen 0, 1a/1b und 2 könnte man machen, aber was soll das?
Für mein Verständnis ist dieser Teil des GC-Konzeptes keine bloße Optimierung, sondern grundlegender als die Wahl des Algorithmus zur Auswahl toter Objekte; ob jetzt mark & sweep oder mark & don't sweep oder stop & copy ist eine ziemliche Detailfrage (wenn auch, wie das bei Detailfragen oft der Fall ist, für Performance durchaus von großer Bedeutung). Wenn ich eine Datenbank entwerfe, betrachte ich auch nicht die Auswahl des Indexverfahrens als Kern der Sache. Das ist aber eine ganz andere Diskussion - worum es mir hier geht, ist, dass der Tod eines Objektes in Java keinen Event-Charakter hat (Begriff ad hoc ausgedacht), so dass man sofort auf ihn reagieren könnte, sondern erst später festgestellt wird und auch erst später festgestellt werden kann.
Was Wichtigtuerei angeht, wenn das so rüberkommt, hab ich was falsch gemacht; ich bin auf dem Gebiet sicher keine Koryphäe und wollte diesen Eindruck auch nicht erwecken. Ich meine lediglich genug von der Materie zu verstehen, um den ursprünglichen Vorschlag einer vollständig GC-gestützten Ressourcenverwaltung begründet abtun zu können.
-
Also erstmal war da ja der
, also bitte nicht zu ernst nehmen. Ich hätte vermutlich einfach nix sagen sollen - ich hab' nur nicht verstanden warum du Dinge lang & breit erklärst, die mit dem was du eigentlich sagen wolltest nix zu tun haben 
Was die Begriffe angeht: das ist falsch rübergekommen: ich glaub schon dass du dir die nicht ausgedacht hast. Ich finde sie nur trotzdem doof.
Zurück zum Thema:
worum es mir hier geht, ist, dass der Tod eines Objektes in Java keinen Event-Charakter hat (Begriff ad hoc ausgedacht), so dass man sofort auf ihn reagieren könnte, sondern erst später festgestellt wird und auch erst später festgestellt werden kann.
Ja, genau, das ist der Knackpunkt!
Nur was ich nicht verstehe: was hat das deiner Meinung nach mit "generational GC" vs. "non-generational CG" zu tun?
Ich behaupte nämlich: gar nix.Diesen "Event-Character" könnte es nur geben, wenn sofort bei Update jeder einzelnen Referenz im Programm immer geguckt wird, ob dadurch jetzt Objekte in der Luft hängen, und diese dann eben auch freigegeben.
D.h. man müsste bei jedem Update einer Referenz irgendwie prüfen, ob das "alte" Objekt dadurch "unreachable" geworden ist.
Eine Möglichkeit wäre nach jedem Update einer Referenz den ganzen Graphen mit einem der bekannten GC Algorithmen zu checken. Dass das zu langsam ist, ist glaube ich klar.
Eine andere Möglichkeit wäre Reference-Counting, das ist grade noch akzeptabel schnell, nur das kommt eben mit Zyklen nicht klar. Also auch no-go.Und eine Möglichkeit die nicht viel zu langsam ist, aber trotzdem mit Zyklen klarkommt, kenne ich nicht.
Dass ein GC zu Garbage gewordene Objekte nicht sofort erkennen kann, hat also damit, ob jetzt Generationen zur Optimierung der Collections verwendet werden oder nicht, nichts zu tun. Sondern einfach damit, dass eine Collection zu teuer ist, um sie nach jedem Update einer Referenz zu machen.
Die Freigabe von Objekten wird also sowieso schonmal bis zur nächsten Collection verzögert.
Das einzige was Generationen hier noch ändern, ist, dass es passieren kann dass Garbage-Objekte auch bei der nächsten Collection nachdem sie zu Garbage wurden nicht gefunden werden, sondern u.U. erst ein paar Collections später. Die Generationen bewirken hier also nur eine zusätzliche Verzögerung.
