Caches (weak dictionaries)

There is a need to allow objects to be maintained that represent external state, mapping a single instance to the external reality, where allowing multiple instances to be mapped to the same external resource would create unnecessary difficulty maintaining synchronization among instances. In these cases, a common idiom is to support a cache of instances; a factory function is used to return either a new or existing instance.

The difficulty in this approach is that one of two things must be tolerated: either the cache grows without bound, or there needs to be explicit management of the cache elsewhere in the application. The later can be very tedious and leads to more code than is really necessary to solve the problem at hand, and the former can be unacceptable for long-running processes or even relatively short processes with substantial memory requirements.

• External objects that need to be represented by a single instance, no matter how many internal users there are. This can be useful for representing files that need to be written back to disk in whole rather than locked & modified for every use.
• Objects that are expensive to create, but may be needed by multiple internal consumers. Similar to the first case, but not necessarily bound to external resources, and possibly not an issue for shared state. Weak references are only useful in this case if there is some flavor of “soft” references or if there is a high likelihood that users of individual objects will overlap in lifespan.

Circular references

• DOMs require a huge amount of circular (to parent & document nodes) references, but these could be eliminated using a weak dictionary mapping from each node to its parent. This might be especially useful in the context of something like xml.dom.pulldom, allowing the .unlink() operation to become a no-op.

This proposal is divided into the following sections:

• Proposed Solution
• Implementation Strategy
• Possible Applications
• Previous Weak Reference Work in Python
• Weak References in Java

The full text of one early proposal is included as an appendix since it does not appear to be available on the net.

Invalidation

Past approaches to weak reference invalidation have often hinged on storing a strong reference and being able to examine all the instances of weak reference objects, and invalidating them when the reference count of their referent goes to one (indicating that the reference stored by the weak reference is the last remaining reference). This has the advantage that the memory management machinery in Python need not change, and that any type can be weakly referenced.

The disadvantage of this approach to invalidation is that it assumes that the management of the weak references is called sufficiently frequently that weakly-referenced objects are noticed within a reasonably short time frame; since this means a scan over some data structure to invalidate references, an operation which is O(N) on the number of weakly referenced objects, this is not effectively amortized for any single object which is weakly referenced. This also assumes that the application is calling into code which handles weakly-referenced objects with some frequency, which makes weak-references less attractive for library code.

An alternate approach to invalidation is that the de-allocation code to be aware of the possibility of weak references and make a specific call into the weak-reference management code to all invalidation whenever an object is deallocated. This requires a change in the tp_dealloc handler for weakly-referencable objects; an additional call is needed at the “top” of the handler for objects which support weak-referencing, and an efficient way to map from an object to a chain of weak references for that object is needed as well.

Presentation

Two ways that weak references are presented to the Python layer have been as explicit reference objects upon which some operation is required in order to retrieve a usable reference to the underlying object, and proxy objects which masquerade as the original objects as much as possible.

Reference objects are easy to work with when some additional layer of object management is being added in Python; references can be checked for liveness explicitly, without having to invoke operations on the referents and catching some special exception raised when an invalid weak reference is used.

However, a number of users favor the proxy approach simply because the weak reference looks so much like the original object.

Proposal: Virtual References

In an attempt to partly address the recurring discussion concerning reference counting vs. garbage collection, I would like to propose an extension to Python which should help in the creation of “well structured” cyclic graphs. In particular, it should allow at least trees with parent back-pointers and doubly-linked lists to be created without worry about cycles.

The basic mechanism I’d like to propose is that of a “virtual reference,” or a “vref” from here on out. A vref is essentially a handle on an object that does not increment the object’s reference count. This means that holding a vref on an object will not keep the object from being destroyed. This would allow the Python programmer, for example, to create the aforementioned tree structure tree structure, which is automatically destroyed when it is no longer in use – by making all of the parent back-references into vrefs, they no longer create reference cycles which keep the tree from being destroyed.

In order to implement this mechanism, the Python core must ensure that no -real- pointers are ever left referencing objects that no longer exist. The implementation I would like to propose involves two basic additions to the current Python system:

1. A new “vref” type, through which the Python programmer creates and manipulates virtual references. Internally, it is basically a C-level Python object with a pointer to the Python object it is a reference to. Unlike all other Python code, however, it does not change the reference count of this object. In addition, it includes two pointers to implement a doubly-linked list, which is used below.
2. The addition of a new field to the basic Python object [PyObject_Head in object.h], which is either NULL, or points to the head of a list of all vref objects that reference it. When a vref object attaches itself to another object, it adds itself to this linked list. Then, if an object with any vrefs on it is deallocated, it may walk this list and ensure that all of the vrefs on it point to some safe value, e.g. Nothing.

This implementation should hopefully have a minimal impact on the current Python core – when no vrefs exist, it should only add one pointer to all objects, and a check for a NULL pointer every time an object is deallocated.

Back at the Python language level, I have considered two possible semantics for the vref object –

Pointer semantics

In this model, a vref behaves essentially like a Python-level pointer; the Python program must explicitly dereference the vref to manipulate the actual object it references.

An example vref module using this model could include the function “new”; When used as ‘MyVref = vref.new(MyObject)’, it returns a new vref object such that MyVref.object == MyObject. MyVref.object would then change to Nothing if MyObject is ever deallocated.

For a concrete example, we may introduce some new C-style syntax:

• & – unary operator, creates a vref on an object, same as vref.new().
• * – unary operator, dereference a vref, same as VrefObject.object.

We can then define:

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

Rule #4 is subtle, but comes about because we have made a vref to (a vref with no real references). Thus the outer vref is cleared to Nothing when the inner one inevitably disappears.

Proxy semantics

In this model, the Python programmer manipulates vref objects just as if she were manipulating the object it is a reference of. This is accomplished by implementing the vref so that all operations on it are redirected to its referenced object. With this model, the dereference operator (*) no longer makes sense; instead, we have only the reference operator (&), and define:

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

Again, rule #4 is important – here, the outer vref is in fact a reference to the original object, and -not- the inner vref. This is because all operations applied to a vref actually apply to its object, so that creating a vref of a vref actually results in creating a vref of the latter’s object.

The first, pointer semantics, has the advantage that it would be very easy to implement; the vref type is extremely simple, requiring at minimum a single attribute, object, and a function to create a reference.

However, I really like the proxy semantics. Not only does it put less of a burden on the Python programmer, but it allows you to do nice things like use a vref anywhere you would use the actual object. Unfortunately, it would probably an extreme pain, if not practically impossible, to implement in the current Python implementation. I do have some thoughts, though, on how to do this, if it seems interesting; one possibility is to introduce new type-checking functions which handle the vref. This would hopefully older C modules which don’t expect vrefs to simply return a type error, until they can be fixed.

Finally, there are some other additional capabilities that this system could provide. One that seems particularly interesting to me involves allowing the Python programmer to add “destructor” function to a vref – this Python function would be called immediately prior to the referenced object being deallocated, allowing a Python program to invisibly attach itself to another object and watch for it to disappear. This seems neat, though I haven’t actually come up with any practical uses for it, yet… :)

– Dianne