Caches (schwache Dictionaries)

Es besteht die Notwendigkeit, Objekte zu verwalten, die externen Zustand repräsentieren und eine einzelne Instanz der externen Realität zuordnen, wobei die Zulassung mehrerer Instanzen, die derselben externen Ressource zugeordnet sind, die Synchronisation zwischen den Instanzen unnötig erschweren würde. In diesen Fällen ist die Unterstützung eines Caches von Instanzen ein gängiges Idiom; eine Factory-Funktion wird verwendet, um entweder eine neue oder eine bestehende Instanz zurückzugeben.

Die Schwierigkeit bei diesem Ansatz besteht darin, dass eines von zwei Dingen toleriert werden muss: Entweder wächst der Cache unbegrenzt, oder es muss eine explizite Verwaltung des Caches an anderer Stelle in der Anwendung erfolgen. Letzteres kann sehr mühsam sein und führt zu mehr Code, als zur Lösung des Problems eigentlich notwendig ist, und ersteres kann für langlaufende Prozesse oder sogar relativ kurze Prozesse mit erheblichen Speicheranforderungen inakzeptabel sein.

• Externe Objekte, die durch eine einzelne Instanz repräsentiert werden müssen, unabhängig davon, wie viele interne Benutzer es gibt. Dies kann nützlich sein, um Dateien darzustellen, die als Ganzes zurück auf die Festplatte geschrieben werden müssen, anstatt für jeden Gebrauch gesperrt und modifiziert zu werden.
• Objekte, deren Erstellung teuer ist, die aber möglicherweise von mehreren internen Konsumenten benötigt werden. Ähnlich wie im ersten Fall, aber nicht unbedingt an externe Ressourcen gebunden und möglicherweise kein Problem für gemeinsam genutzten Zustand. Schwache Referenzen sind in diesem Fall nur nützlich, wenn es eine Art von "weichen" Referenzen gibt oder wenn die Wahrscheinlichkeit hoch ist, dass die Benutzer einzelner Objekte eine überlappende Lebensdauer haben.

Zirkuläre Referenzen

• DOMs erfordern eine riesige Menge an zirkulären (zu Eltern- und Dokumentknoten) Referenzen, aber diese könnten eliminiert werden, indem ein schwaches Dictionary verwendet wird, das jeden Knoten seinem Elternknoten zuordnet. Dies könnte besonders nützlich sein im Kontext von etwas wie xml.dom.pulldom, wodurch die Operation .unlink() zu einem No-Op werden könnte.

Dieser Vorschlag ist in die folgenden Abschnitte unterteilt

• Vorgeschlagene Lösung
• Implementierungsstrategie
• Mögliche Anwendungen
• Frühere Arbeiten zu schwachen Referenzen in Python
• Schwache Referenzen in Java

Der vollständige Text eines frühen Vorschlags ist als Anhang enthalten, da er nicht online verfügbar zu sein scheint.

Invalidierung

Frühere Ansätze zur Invalidierung von schwachen Referenzen basierten oft darauf, eine starke Referenz zu speichern und alle Instanzen von schwachen Referenzobjekten prüfen zu können, um sie zu invalidieren, wenn der Referenzzähler ihres Referenten auf eins fällt (was anzeigt, dass die vom schwachen Referenz gespeicherte Referenz die letzte verbleibende Referenz ist). Dies hat den Vorteil, dass die Speicherverwaltung in Python nicht geändert werden muss und dass jeder Typ schwach referenziert werden kann.

Der Nachteil dieses Invalidierungsansatzes ist, dass er davon ausgeht, dass die Verwaltung der schwachen Referenzen häufig genug aufgerufen wird, sodass schwach referenzierte Objekte innerhalb eines angemessenen Zeitrahmens bemerkt werden. Da dies einen Scan einer Datenstruktur zur Invalidierung von Referenzen bedeutet, eine Operation, die O(N) bezüglich der Anzahl der schwach referenzierten Objekte ist, wird dies für ein einzelnes schwach referenziertes Objekt nicht effektiv amortisiert. Dies setzt auch voraus, dass die Anwendung Code aufruft, der schwach referenzierte Objekte häufig behandelt, was schwache Referenzen für Bibliotheks-Code weniger attraktiv macht.

Ein alternativer Ansatz zur Invalidierung besteht darin, dass der Deallokationscode die Möglichkeit von schwachen Referenzen berücksichtigt und beim Deallokieren eines Objekts einen spezifischen Aufruf an den schwachen Referenzverwaltungs-Code zur Invalidierung vornimmt. Dies erfordert eine Änderung im tp_dealloc-Handler für schwach referenzierbare Objekte; ein zusätzlicher Aufruf ist am "Anfang" des Handlers für Objekte erforderlich, die schwache Referenzierung unterstützen, und es wird eine effiziente Möglichkeit benötigt, von einem Objekt zu einer Kette von schwachen Referenzen für dieses Objekt zu gelangen.

Darstellung

Zwei Möglichkeiten, wie schwache Referenzen der Python-Ebene präsentiert wurden, sind explizite Referenzobjekte, mit denen eine Operation ausgeführt werden muss, um eine nutzbare Referenz auf das zugrunde liegende Objekt abzurufen, und Proxy-Objekte, die die ursprünglichen Objekte so weit wie möglich maskieren.

Referenzobjekte sind einfach zu handhaben, wenn zusätzliche Objektverwaltungs-Schichten in Python hinzugefügt werden. Referenzen können explizit auf Lebendigkeit geprüft werden, ohne Operationen auf den Referenten aufrufen und eine spezielle Ausnahme abfangen zu müssen, die ausgelöst wird, wenn eine ungültige schwache Referenz verwendet wird.

Eine Reihe von Benutzern bevorzugen jedoch den Proxy-Ansatz, einfach weil die schwache Referenz dem ursprünglichen Objekt so sehr ähnelt.

Vorschlag: Virtuelle Referenzen

In dem Versuch, die wiederkehrende Diskussion über Referenzzählung vs. Garbage Collection teilweise zu lösen, möchte ich eine Erweiterung von Python vorschlagen, die bei der Erstellung von "gut strukturierten" zirkulären Graphen helfen sollte. Insbesondere sollte sie mindestens Bäume mit Eltern-Rückverweise und doppelt verkettete Listen ohne die Sorge vor Zyklen ermöglichen.

Der grundlegende Mechanismus, den ich vorschlagen möchte, ist der einer "virtuellen Referenz" oder von hier an "vref". Eine vref ist im Wesentlichen ein Handle auf ein Objekt, das den Referenzzähler des Objekts nicht erhöht. Das bedeutet, dass das Halten einer vref auf einem Objekt das Objekt nicht davon abhält, zerstört zu werden. Dies würde es dem Python-Programmierer ermöglichen, zum Beispiel die oben erwähnte Baumstruktur zu erstellen, die automatisch zerstört wird, wenn sie nicht mehr benötigt wird – indem alle Eltern-Rückverweise zu vrefs gemacht werden, erzeugen sie keine Referenzzyklen mehr, die die Zerstörung des Baumes verhindern.

Um diesen Mechanismus zu implementieren, muss der Python-Kern sicherstellen, dass niemals "reale" Zeiger auf Objekte zeigen, die nicht mehr existieren. Die Implementierung, die ich vorschlagen möchte, beinhaltet zwei grundlegende Ergänzungen zum aktuellen Python-System:

1. Ein neuer "vref"-Typ, über den der Python-Programmierer virtuelle Referenzen erstellt und manipuliert. Intern ist es im Grunde ein Python-Objekt auf C-Ebene mit einem Zeiger auf das Python-Objekt, auf das es sich bezieht. Im Gegensatz zu allem anderen Python-Code ändert es jedoch nicht den Referenzzähler dieses Objekts. Zusätzlich enthält es zwei Zeiger zur Implementierung einer doppelt verketteten Liste, die unten verwendet wird.
2. Die Hinzufügung eines neuen Feldes zum grundlegenden Python-Objekt [PyObject_Head in object.h], das entweder NULL ist oder auf den Kopf einer Liste aller vref-Objekte zeigt, die darauf verweisen. Wenn sich ein vref-Objekt an ein anderes Objekt anhängt, fügt es sich dieser verknüpften Liste hinzu. Wenn dann ein Objekt mit vrefs darauf deallokiert wird, kann es diese Liste durchlaufen und sicherstellen, dass alle vrefs darauf auf einen sicheren Wert, z. B. Nothing, zeigen.

Diese Implementierung sollte hoffentlich minimale Auswirkungen auf den aktuellen Python-Kern haben – wenn keine vrefs existieren, sollte sie nur einen Zeiger zu allen Objekten hinzufügen und bei jeder Deallokation eines Objekts eine Prüfung auf einen NULL-Zeiger.

Auf der Ebene der Python-Sprache habe ich zwei mögliche Semantiken für das vref-Objekt in Betracht gezogen –

Pointer-Semantik

In diesem Modell verhält sich eine vref im Wesentlichen wie ein Python-Zeiger; das Python-Programm muss die vref explizit dereferenzieren, um das tatsächliche Objekt zu manipulieren, auf das es verweist.

Ein Beispiel-vref-Modul, das dieses Modell verwendet, könnte die Funktion "new" enthalten. Wenn es als 'MyVref = vref.new(MyObject)' verwendet wird, gibt es ein neues vref-Objekt zurück, so dass MyVref.object == MyObject ist. MyVref.object würde dann auf Nothing geändert, wenn MyObject jemals deallokiert wird.

Für ein konkretes Beispiel können wir einige neue C-artige Syntax einführen

• & – unärer Operator, erstellt eine vref auf einem Objekt, dasselbe wie vref.new().
• * – unärer Operator, dereferenziert eine vref, dasselbe wie VrefObject.object.

Wir können dann definieren

1.     type(&MyObject) == vref.VrefType
2.        *(&MyObject) == MyObject
3. (*(&MyObject)).attr == MyObject.attr
4.          &&MyObject == Nothing
5.           *MyObject -> exception

Regel #4 ist subtil, ergibt sich aber daraus, dass wir eine vref auf (eine vref ohne echte Referenzen) erstellt haben. Daher wird die äußere vref zu Nothing gelöscht, wenn die innere unvermeidlich verschwindet.

Proxy-Semantik

In diesem Modell manipuliert der Python-Programmierer vref-Objekte so, als würde er das Objekt manipulieren, auf das es verweist. Dies wird erreicht, indem die vref so implementiert wird, dass alle Operationen darauf auf ihr referenziertes Objekt umgeleitet werden. Mit diesem Modell macht der Dereferenzierungsoperator (*) keinen Sinn mehr; stattdessen haben wir nur den Referenzoperator (&) und definieren

1.  type(&MyObject) == type(MyObject)
2.        &MyObject == MyObject
3. (&MyObject).attr == MyObject.attr
4.       &&MyObject == MyObject

Auch hier ist Regel #4 wichtig – hier ist die äußere vref tatsächlich eine Referenz auf das ursprüngliche Objekt und *nicht* die innere vref. Dies liegt daran, dass alle Operationen, die auf eine vref angewendet werden, tatsächlich auf ihr Objekt angewendet werden, so dass das Erstellen einer vref einer vref tatsächlich das Erstellen einer vref des Objekts der letzteren zur Folge hat.

Die erste, Pointer-Semantik, hat den Vorteil, dass sie sehr einfach zu implementieren wäre; der vref-Typ ist extrem einfach und erfordert mindestens ein einzelnes Attribut, Objekt, und eine Funktion zur Erstellung einer Referenz.

Ich mag jedoch die Proxy-Semantik wirklich. Sie belastet den Python-Programmierer nicht nur weniger, sondern ermöglicht auch nette Dinge wie die Verwendung einer vref überall dort, wo das tatsächliche Objekt verwendet würde. Leider wäre sie in der aktuellen Python-Implementierung wahrscheinlich extrem schwierig, wenn nicht praktisch unmöglich, zu implementieren. Ich habe jedoch einige Ideen, wie das gemacht werden könnte, wenn es interessant erscheint; eine Möglichkeit ist die Einführung neuer Typüberprüfungsfunktionen, die die vref behandeln. Dies würde hoffentlich ältere C-Module, die keine vrefs erwarten, einfach einen TypeError zurückgeben lassen, bis sie behoben werden können.

Schließlich gibt es noch einige weitere zusätzliche Fähigkeiten, die dieses System bieten könnte. Eine, die mir besonders interessant erscheint, beinhaltet die Ermöglichung, dass der Python-Programmierer "Destruktor"-Funktionen zu einer vref hinzufügen kann – diese Python-Funktion würde unmittelbar vor der Deallokation des referenzierten Objekts aufgerufen, was es einem Python-Programm ermöglichen würde, sich unsichtbar an ein anderes Objekt anzuhängen und zu beobachten, wie es verschwindet. Das scheint nett zu sein, obwohl ich noch keine praktischen Anwendungen dafür gefunden habe... :)

– Dianne