Aging Pointer

An AgingPointer is strictly not a pointer, but acts like one, with special properties that provide, in effect, zero-cost garbage collection if certain conditions are met. It is called an AgingPointer because it automatically becomes 'nil' when it becomes 'too old'. Like a real pointer,

• It references an object/record/structure (item) of a given type.

• Its value indicates when it references nothing.

• A pointer value can be obtained for a new item.

Thus it can be used in a variety of linked-list structures.

In a typical implementation, the AgingPointer is a large (32-bit or 64-bit) integer. The items that it may reference are elements of a fixed-size array associated with the type of the pointer.

The above pointer properties are typically implemented like this:

• The array index of the referenced item is derived by masking (or by a modulo operation) that reduces the AgingPointer (large integer) to the range of the array index. This is not valid if the pointer is 'nil'.

• An AgingPointer (large integer) that is less than an Age variable (large integer) is considered 'nil', or 'too old'.

• A new AgingPointer (new item) is obtained by copying a Next Pointer variable, then incrementing the Next Pointer variable. If this makes the Next Pointer reference the same item location as the Age variable, then the Age variable is incremented. This makes all references to the oldest item 'nil' (or 'too old') without need to know about these references. This automatic aging is the magic trick of the free garbage collection.

Initially, the Age variable is set to the most negative large integer value, and the Next Pointer variable is set to one more. (Or, if unsigned integers are used, the initial values are 0 and 1.)

The hidden costs of this pattern are the extra work of nil-testing and de-referencing, and the following restrictions:

• Items are automatically deleted by age; this may or may not be desirable.

• When items reference older items, the automatic aging can truncate the tail end of the chain; but when items reference newer items, the automatic aging may truncate the head end, which is generally unworkable.

• When the Age variable overflows, the scheme will crash unless the 'nil' test is given a 'modulo' property. But in many applications the fixed lifetime of the scheme is sufficiently long, or the scheme gets restarted.

-- JimClark

---

In what situations would an AgingPointer be of use?

• The "automatically deleted by age" looks like it might be useful for LRU caching, especially when multiple threads/CPUs are all trying to access the cache.
• See GarbageCollectionUnderVersioning

---

CategoryPointer CategoryStructuralPatterns CategoryConcurrency