 |
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.
|
