Weak References

Data Types and Implementation

Bruno Haible
ILOG GmbH

2005-04-24

This talk explains the benefits and drawbacks of weak references. It generalizes the data types of weak pointer, weak list and weak hash-table. It explains how to implement these data types correctly and efficiently.

The User's Point of View

An object is a piece of memory that is explicitly allocated by the programmer and can refer to other objects in memory. A garbage collector is used to reclaim unused objects. How does the GC determine which objects are unused? It starts from a root set, usually the stacks of all threads and the global symbol table. It follows all pointer references recursively. An object is called reachable if there is a chain of pointers starting in the root set and ending at the given object. The GC thus determines which objects are reachable and then reclaims the memory occupied by the unreachable objects.

What is a weak pointer?

A weak pointer holds an object in a way that does it not cause to be reachable. It means, the object can be GCed. When this happened, accessing the weak pointer's contents returns NIL instead of the original object. In this case we say that the weak pointer has been "broken".

(make-weak-pointer value) => #<weak-pointer value>
(weak-pointer-value weak-pointer) => value, T or NIL, NIL

What is a weak hash-table?

A weak hash-table is a hash-table which does not automatically cause its key - value pairs to be reachable. It means, the GC can reclaim hash-table entries.

There are four kinds of weak hash-tables:

:key: A key - value entry is held as long as the key is reachable.
:value: A key - value entry is held as long as the value is reachable.
:key-and-value: A key - value entry is held as long as the key and the value are both reachable.
:key-or-value: A key - value entry is held as long as either the key or the value are reachable.

Example: In a debugger that deals with source code forms and filename+linenumber objects:
The table mapping source code forms to filename+linenumber would be of type :key.
The table mapping filename+linenumber to source code forms would be of type :value.
The table mapping source code forms to the function containing it would be of type :key-and-value.

Weak references, a strong feature

The following are examples of uses of weak pointers and weak hash table in practice.

Add extra information to objects belonging to sealed classes.

(defclass my-cons (cons) (my-extra-info))

does not work. Use of a weak hash-table of type :key works. The alternative is to add property lists to all kinds of important objects, not just symbols; but when the object class is given and cannot be augmented, the weak hash-table approach is the only one.
Memoize the prior results of a function that is assumed to be "pure" (not influenced by outside variables). A weak hash-table of type :key works again.
Uniquification: Ensure that only one object with a given property exists in memory. This can be implemented by storing the first such object in a weak hash-table of type :value.
Hash consing: Avoid different conses in memory with the same car and cdr. This is essential for the speed of some computer-algebra systems. It can be implemented through a weak hash-table of type :value.
In applications composed of multiple modules that are connected by protocols: Keep pointers between objects belonging to different modules, when the protocol between the modules has only an 'attach' operation, not both 'attach' and 'detach'.
Example: In a GUI application with model - view - controller architecture, the model must notify the view of any changes in the model. But it must not keep the view from being GCed. Rather, when the view is GCed, the model must simply stop sending events to it. This is a perfect use case for a weak-list.
It can be argued that the protocol between the modules should be changed to support a 'detach' operation as well. But this approach is intrusive. When it is followed consequently, you end up adding 'destroy-instance' methods for many classes. But 'destroy-instance' has not been integrated into CLOS from the beginning; therefore it is too late to impose it.
Global garbage collection: Allow garbage collection to work across process boundaries, or across a Lisp - C/C++/Java foreign interface boundary. There is a table from foreign object pointers to Lisp proxies; this table is a weak hash-table of type :value. There is also a table from Lisp objects to foreign handles that allows the foreign world to access it; this is a normal hash tables whose entries are removed when the reference count of a foreign handle drops to 0.

Drawbacks

Weak references represent an extra cost for the garbage collector. The GC has to keep all weak references in an extra list, and perform extra work when determining which objects are reachable. Whereas the time spent for collecting a heap of size N is O(N), the extra time spent in GC for W weak references is O(W²) in some implementations, O(W log W) in other implementations, and O(W) with a higher O constant in other implementations.

Therefore programmers should normally try use a minimum of weak references.

Weak datastructures

There are more weak datastructures, each tailored to particular use cases. All of them are implemented in GNU clisp 2.33.80.

Weak pointers. See above.
Weak lists. A weak list is an ordered collection of references to objects that does not keep the objects from being garbage-collected. It is semantically equivalent to a list of weak pointers, however with a more efficient in-memory representation than a plain list of weak pointers would be.
Weak lists are useful for notification based communication protocols between software modules, e.g. when a change to an object x requires a notification to objects k₁, k₂, ..., as long as such a particular k_n is alive.
Weak “and” relations. A weak “and” relation is an ordered collection of references to objects, that does not keep the objects from being garbage-collected, and which allows access to all the objects as long as all of them are still alive. As soon as one of them is garbage-collected, the entire collection of objects becomes empty.
Weak “and” relations are useful to model relations between objects that become worthless when one of the objects dies.
Weak “or” relations. A weak “or” relation is an ordered collection of references to objects, that keeps all objects from being garbage-collected as long as one of them is still alive. In other words, each of them keeps all others among them from being garbage-collected. When all of them are unreferenced, the collection of objects becomes empty.
Weak “or” relations are useful to model relations between objects that do not become worthless when one of the objects dies.
Weak associations (also called weak mappings). A weak association is a mapping from an object called key to an object called value, that exists as long as the key is alive. In other words, as long as the key is alive, it keeps the value from being garbage-collected.
Weak associations are useful to supplement objects with additional information that is stored outside of the object.
Weak “and” mappings. A weak “and” mapping is a mapping from a tuple of objects called keys to an object called value, that does not keep the keys from being garbage-collected and that exists as long as all keys are alive. As soon as one of the keys is garbage-collected, the entire mapping goes away.
Weak “and” mappings are useful to model properties of sets of objects that become worthless when one of the objects dies.
Weak “or” mappings. A weak “or” mapping is a mapping from a tuple of objects called keys to an object called value, that keeps all keys and the value from being garbage-collected as long as one of the keys is still alive. In other words, each of the keys keeps all others among them and the value from being garbage-collected. When all of them are unreferenced, the entire mapping goes away.
Weak association lists. A weak association list is an ordered collection of pairs, each pair being built from an object called key and an object called value. The lifetime of each pair depends on the type of the weak alist: :key, :value, :key-and-value, or :key-or-value, as for weak hash-tables.
Weak associations lists are useful to supplement objects with additional information that is stored outside of the object, when the number of such objects is known to be small.
Weak hash-tables. A weak hash-table is an unordered collection of pairs, each pair being built from an object called key and an object called value. There can be only one pair with a given key in a weak hash-table. The lifetime of each pair depends on the type of the weak hash-table. (See above.)
Weak hash-tables are useful to supplement objects with additional information that is stored outside of the object. This data structure scales up without performance degradation when the number of pairs is big.

A minimal set of weak datastructures

One can go on inventing weak datastructures similar to these... But what is the minimal set of weak datastructures that an implementation needs to support? There are two answers.

For practical purposes, only the weak pointers, weak :key mappings and weak hash-tables are essential. The others can be reduced to them:

Weak lists are not essential:
(make-weak-list x₁ ... x_n)
can be emulated through
(list (make-weak-pointer x₁) ... (make-weak-pointer x_n))
except that in this emulation, the removal of unneeded list elements will have to be performed at each access, instead of at GC time.
Weak “and” relations are not essential:
(make-weak-and-relation x₁ ... x_n)
can be emulated through
(list (make-weak-pointer x₁) ... (make-weak-pointer x_n))
except that in this emulation, the removal of unneeded list elements will have to be performed at each access, instead of at GC time.
Weak “or” relations are not essential:
(make-weak-or-relation x₁ ... x_n)
can be emulated through
(let ((all (list x₁ ... x_n)))
(list (make-weak-key-mapping x₁ all)
...
(make-weak-key-mapping x_n all)))
Weak mappings of other types:
(make-weak-value-mapping key value) ==
(make-weak-key-mapping value key)
(make-weak-key-and-value-mapping key value) ==
(make-weak-key-mapping key (make-weak-pointer value))
(make-weak-key-or-mapping key value) ==
(list (make-weak-key-mapping key value)
(make-weak-key-mapping value key))
Weak “and” mappings are not essential:
(make-weak-and-mapping x₁ ... x_n value)
can be emulated through
(make-weak-key-mapping x₁ (... (make-weak-key-mapping x_n value)...))
Weak “or” mappings are not essential:
(make-weak-or-mapping x₁ ... x_n value)
can be emulated through
(let ((all (list x₁ ... x_n value)))
(list (make-weak-key-mapping x₁ all)
(make-weak-key-mapping x_n all)))
Weak association lists are not essential:
(make-weak-type-alist key₁ value₁ ... key_n value_n)
can be emulated through
(list (make-weak-type-mapping key₁ value₁)
...
(make-weak-type-mapping key_n value_n))
except that in this emulation, the removal of unneeded list elements will have to be performed at each access, instead of at GC time.

For theoretical purposes, only the weak :key mappings are essential.

Weak pointers are not essential in theory:
(make-weak-pointer x)
can be emulated through
(make-weak-key-mapping x x)
But since many implementations have bugs when the value contains (or even is the same as) the key, this reduction is not adequate in practice.
Weak :key mappings and weak hash-tables can not be adequately implemented using weak pointers. Some implementations try to do so, by combining a weak pointer to the key and a strong pointer to the value, but the result suffers from the "key in value" problem: When the key occurs as a sub-object of the value, it remains always reachable as long as the value is reachable. This is unusable for many practical applications.
Weak hash-tables are not essential in theory:
They can be build from weak association lists (one per hash table bucket). The idea is that the programmer reimplements the bucket, collision management and rehashing code on his own.
But this requires that the programmer can compute the hash code of each key object, whether the hash-table's test be EQ, EQL, EQUAL, or EQUALP. There is no portable API for this, and it would be useless anyway, because such a hash code is only valid until the next GC, and there is no portable way to prohibit GC (not even in theory: think about Lisp implementations with incremental garbage collectors).
On the other hand, weak :key mappings can be emulated through weak hash-tables with a single key - value pair.
But this emulation is not particularly efficient, given the many slots and auxiliary vectors that a hash-table contains.

So, a good implementation should support all three:

Weak pointers,
Weak :key mappings,
Weak hash-tables.

Implementation Support

Here is a survey of the support for weak pointers in various programming systems featuring a garbage collector. We distinguish between different levels of support:

Level 1: Support for weak pointers or equivalent.
Level 2: Support for weak :key mappings or weak hash tables, with the restriction that the key must not occur in the value.
Level 3: Full support for weak :key mappings or weak hash tables.
Level 4: Full and scalable support for weak :key mappings or weak hash tables.

Level 1 - Implementations with weak pointers or equivalent

Common Lisp: GNU clisp 2.33.80, OpenMCL 0.14.1, Allegro CL 6.2, LispWorks 4.3, Corman Lisp 1.1, CMUCL 19a, SBCL 0.8.20
Scheme: GNU guile 1.7.1, MIT Scheme 7.7.1, BBN Scheme, MzScheme 205, Scheme48
Other Lisp: XEmacs 21.4, GNU Emacs 21.1, jlisp 1.03, mindy 1.2
Java 1.5
.NET CLR (mono 1.0.1, pnet 0.6.10)
Smalltalk: GNU Smalltalk 2.1.10
Python 2.4

Notes:
In CMUCL 19a and SBCL 0.8.20, the garbage collector fails to break weak pointers when it should.
In OpenMCL 0.14.1 the weak lists and weak association lists exist but are undocumented.
In pnet 0.6.10, the mere allocation of N weak pointers is O(N^2).
In Python 2.4, weak pointers can only point to objects for which the ability to be used as a weak pointer target has explicitly been declared in the class. And it costs one slot per instance. Which means that most classes cannot be used as weak pointer targets. This defeats many uses of weak pointers.
The list of implementations of languages other than Lisp and Scheme is not complete: There are other implementations of .NET and Smalltalk that support weak pointers.
The list of languages with weak pointer support is not complete: Some implementations of ML and Haskell also support weak pointers.

Level 2 - Implementations with severely restricted weak :key mappings or weak hash tables

Common Lisp: GNU clisp 2.33.80, OpenMCL 0.14.1, Allegro CL 6.2, LispWorks 4.3, CMUCL 19a
Scheme: GNU guile 1.7.1, MIT Scheme 7.7.1, BBN Scheme, MzScheme 205
Other Lisp: XEmacs 21.4, GNU Emacs 21.1
Java 1.5
Smalltalk: GNU Smalltalk 2.1.10

Level 3 - Implementations with weak :key mappings or weak hash tables

Common Lisp: GNU clisp 2.33.80, LispWorks 4.3
Other Lisp: XEmacs 21.4, GNU Emacs 21.1

Level 4 - Implementations with scalable weak :key mappings or weak hash tables

Common Lisp: GNU clisp 2.33.80, LispWorks 4.3
Other Lisp: XEmacs 21.4, GNU Emacs 21.1

Notes: In LispWorks, XEmacs, Emacs, the garbage collection of a chain of N weak :key mappings is O(N²) worst-case. Enough to make for a 3-minutes GC for N = 10000.

The Implementor's Point of View

In the simplest case, the garbage collection consists of two phases:

Mark phase: Recursively mark all reachable objects, starting from the root set.
Sweep phase: Move the marked objects to their new location, and update all pointers to point to the new locations. Then free unused memory pages.

Since the handling of weak objects requires the knowledge which objects are reachable, but the weak mappings and weak hash tables handling can augment this set, the right moment for this handling is right after the mark phase:

1. Mark phase.
1a. Weak object phase.
2. Sweep phase.

All weak data structures are kept in a list that is not part of the root set. In some implementations, this list is built up incrementally: each weak object is entered there when it is allocated. In other implementations, this list exists only during the garbage collection, and is built up during the mark phase.

Implementation - First try

The weak object phase looks like this:

Walk across the weak objects list. When you encounter a weak reference, look whether its target object has been marked. If yes, leave it in place; if not, replace it with #<unbound>.

This loop is adequate for level 1 and level 2, and its running time is O(W), where W is the number of weak objects.

This loop is not adequate for level 3, because it does not mark any object. In other words, it does not change the set of reachable objects. It therefore cannot implement rules like those essential for the weak :key mapping: "If the key is marked, then mark the value as well."

Implementation - Second try

The weak object phase looks like this:

Repeatedly:

Set modified := false.

Walk across the weak objects list.

When a weak object is unmarked, skip it.
When you encounter a weak :key mapping, look whether its key object has been marked. If yes, and if the value is not yet marked, mark the value (like it would have been done in the mark phase), and set modified := true.

Stop when nothing was modified.

[At this point the set of marked objects will not change any more.]
Walk across the weak objects list a last time.

When a weak object is unmarked, skip it.
When you encounter a weak pointer, and its target object has not been marked, replace it with NIL.
When you encounter a weak :key mapping, look whether its key object is marked. If yes, the value object must be marked as well. Otherwise replace both the key and the value object with #<unbound>.

This loop implements weak pointers and weak :key mappings for level 3. However, in the worst case, the number of repetitions in this phase is O(W), thus this phase has a runtime O(W²+N_w), where N_w is the size of the part of the heap that is being marked during this phase! In other words, the GC will handle 1000 weak objects without problem, but will hang the application when 1000000 weak objects are used and the reference graph is unlucky.

LispWorks 4.3, XEmacs 21.4, GNU Emacs 21.1, Hugs98 Mar2005 all have this bug. But it's possible to do better!

Implementation - Third try

The fix to the O(W²) problem of the previous algorithm is to watch more closely the effects of the marking done during the weak object phase, and re-process only small parts of the weak objects list instead of the entire list.

To this purpose, we define the watch set of a weak object to consist of

the weak object itself,
those weak references inside the weak object that act as a "trigger" for the marking of other objects. For weak-pointers this is empty; for weak :key mappings this is the key object; for weak “and” relations and weak “or” relations this consists of all the references inside the weak object.

The total watch set consists of the union of all watch sets of all weak objects in the list. More precisely, it is the union of all the (wobj, wref) pairs over all weak objects wobj. The algorithm makes use of an efficient data structure for the reverse mapping

wref --> set of all wobj such that (wobj, wref) is in the total watch set

This data structure can be an array, sorted by addresses, so that the lookup in it (through binary search) will be O(log W) in the worst-case. Or it can be a hash table, so that the lookup in it is O(1) on average.

Also we need a queue data structure, whose elements are the elements of the total watch set.

The weak object phase now looks like this:

Walk across the weak objects list and build the total watch set, i.e. the list of (wobj, wref) pairs.
Build up the reverse mapping datastructure.
Set queue := empty.
Walk across the weak objects list.

When a weak object is unmarked, skip it.

When you encounter a weak :key mapping, look whether its key object has been marked. If yes, and if the value is not yet marked, mark the value (like it would have been done in the mark phase); however if during this process a wref is marked that is in the total watch set, lookup the reverse mapping and add all corresponding wobjs to the queue.

While the queue is not empty:

Dequeue a wobj from the queue.
When it is unmarked, do nothing.
If it is a marked weak :key mapping, look whether its key object has been marked. If yes, and if the value is not yet marked, mark the value (like it would have been done in the mark phase); however if during this process a wref is marked that is in the total watch set, lookup the reverse mapping and add all corresponding wobjs to the queue.

[At this point the set of marked objects will not change any more.]
Walk across the weak objects list a last time.

When a weak object is unmarked, skip it.

When you encounter a weak pointer, and its target object has not been marked, replace it with NIL.

When you encounter a weak :key mapping, look whether its key object is marked. If yes, the value object must be marked as well. Otherwise replace both the key and the value object with #<unbound>.

Every element of the total watch set can be added to the queue only once (since when it is added, its wref makes a transition from the unmarked state to the marked state). Therefore the total number of elements that are dequeued from the watch set is bounded by the size of the total watch set, i.e. O(W).

The computation time of the entire weak object phase is therefore O((W + N_w) log W) worst-case, if an array was used as a data structure, or O(W + N_w) on average, if a hash table was used.

This is the algorithm implemented in GNU clisp 2.33.80.

Finalizers

A finalizer is a hook that is executed after a given object has become unreachable. The user provides a function taking one argument. When the GC has determined that the object is unreachable, it still keeps the object alive for a moment, and calls the function with the given object. At the same time, the finalizer is unregistered; this guarantees that it is invoked not more than once for a given object.

The handling of finalizers in the GC is similar to the handling of weak mappings:

The reachability status of some objects need to be considered before the sweep phase.
The finalizers can cause some unreachable object to become reachable nevertheless.

For these reasons, the handling of finalizers must be integrated with the weak object phase.

Haskell implementations go even one step further: They merge the weak :key mappings and the finalizers into a single primitive.

References

[1] Simon Peyton Jones, Simon Marlow, Conal Elliott: Stretching the storage manager: weak pointers and stable names in Haskell.

[2] J. J. Hallett, A. J. Kfoury: A formal semantics for weak references.