This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.


  Limited-Field Reference Counting
  Submitted by

It is well known that relying entirely on reference counting for memory and resource management can be harmful as resources involved in cyclic dependencies will never be freed. As such people often combine reference counting with a tracing garbage collector. The interpreter for the programming language Python is an example of an application employing such a scheme, thereby enhancing memory efficiency drastically. The purpose of the collector is to break cycles by freeing the associated resources; supposing that cyclically dependent resources are relatively rare, the collector needs only be invoked very infrequently to serve its intended purpose. Assuming such a system is in the place there is an elegant way of doing away with the reference count variable for every resource, thereby freeing up valuable memory.

The method I am about to describe is a minor variation on what the garbage collection literature calls limited-field reference counting. Limited-field reference counting uses reference counts that are smaller than usual: Suppose that n bits are set aside for storing a single reference count. Then the first 2^n - 1 values of the reference count are interpreted in the usual sense. The highest value has a special interpretation, however; it is interpreted as the 'sticky' reference count. The idea is that reference count is handled normally until it reaches 'sticky'. When this happens the reference count will never change again. In particular the resource associated with the reference count will never be freed by the reference counter; this is an example of where having a garbage collector is useful.

In many applications the vast majority of reference counts will be relatively low (often just 1). An example of such a system is Java in which all non-primitive variables need to be allocated on the heap. As a result there are often heap-allocated variables that are only used within the local scope, their reference count never exceeding 1. In software with this kind of usage pattern the number of resources with 'sticky' status should be in the minority. Thus the invocation frequency of the garbage collector need not be increased substantially to maintain the same level of memory efficiency as before.

In itself the described method may seem useless; unless we were to pack multiple reference counts together somehow, there would be no way of achieving n < 8. We can get around this apparent limitation by exploiting memory alignment. Practically all modern computer platforms require memory to be allocated at byte-indexed addresses that are a multiple of 2^n for some natural number n. For instance, n = 3 on x86. This means that any valid pointer will have its n lower bits set to zero; these unused bits are exactly what we need for storing a reference count. This suggests the following approach to implementing the reference counting part of a smart pointer:

* The reference count is found by extracting the n lower bits of the pointer. That is, ref_count = ptr & ((1 << (n+1))-1).

* Before deferencing the pointer we first mask out the n lower bits. That is, we deference ptr & ~((1 << (n+1))-1).

The remaining parts are easy: When incrementing the reference count we first make sure that ptr & ((1 << (n+1))-1) does not equal (1 << (n+1))-1. If it does, we do not change anything. Otherwise we simply increment ptr. Decrementing the reference count proceeds similarly.

All of the above can be neatly packaged into a templated smart pointer class. It can also be made largely platform independent with little effort: The constant n can usually be retrieved from the operating system header files at compile-time as this information is already required by the OS memory manager. The easiest way is perhaps to use a system traits class, providing this and other platform-specific pieces of information. This can then be filled out manually or using OS-provided compile-time information.

Note that a requirement of the algorithm is that there is a central authority that hands out resource handles and that all such handles are passed around by reference. This ensures that the reference counts stay synchronized throughout the system.

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.


Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.