|
The Simons
|
|
|
The Simons
|
This document describes the design rationale behind the dynamic memory model used in the Simons Component Library. The release version uses an idiom in which every component type has a corresponding smart pointer type through which references to the component are counted. The choice of this particular strategy is interesting; its evolution is described below.
The desire to support objects with a uniform reference semantics, capable of serialization and restoration, pointed to a dynamic model in which objects are created on demand and released when no longer needed. This clearly required automatic memory management with garbage collection. A number of strategies were explored during development. Concerns included portability (avoiding reliance on any machine-specific memory layout) and integration with the other design goals for the SCL, such as type polymorphism and exception handling.
Initially, a portable mark-and-sweep collector was developed. The benefits
of the mark-and-sweep approach were the ability to use standard C++ pointers
for all objects and the freedom to construct arbitrary object graphs (circular
graphs pose a problem for reference-counting). The overheads were a managed
memory block, a mark flag in each object and an unpredictable time-penalty
when collection was triggered (although this could be amortised by triggering
more frequent collections of a smaller reserved memory block). One
drawback was the need to redefine a mark() method frequently
in subclasses which added object references.
The collector made no assumptions about the underlying hardware or memory
architecture. A simple strategy was followed in which the new
operator was redefined in the root Object class, such that all
calls to allocate memory could be intercepted and the resulting object pointers
stored in a managed memory block, which grew on demand to accommodate more
pointers. When full, the managed area was explored from the low end, and all
object references reachable from the top-level (assumed to be those objects
that were created first and so stored at the low end of memory)
were marked in a recursive marking cycle, using a
mark() method defined in each class that introduced any object
references. Then, managed memory was swept, deleting unmarked objects and
compacting other object pointers into the low end of memory, clearing the
marks.
To cater for the fact that garbage collection could be triggered at any point during the execution of a method, local variables which had not yet been linked to global data had to be protected from early collection. This was hard to achieve without access to the stack-frames of executing methods. Instead, an assumption was made about the maximum number of local objects, which were those stored at the high end of managed memory. This strategy worked well for over a year in development, until larger recursive programs were written in which long-lived local variables were exposed outside the protected area and collected before their time. There was no way to fix this, without detailed stack-frame information, which was judged to be too dependent on specific memory architectures.
The second collector used a reference-counted smart pointer. The benefits of reference counting were the ability to measure the lifetimes of objects accurately and the incremental deletion of unused objects. The overheads were the reference count in each object and the time penalty for incrementing and decrementing this count. The drawbacks included special treatment for self-supporting circular object graphs and type conversion issues.
There are at least two ways of providing reference counting. The intrusive
approach adds a reference count to each object. The non-intrusive approach
either uses double indirection from the pointer to the counter to the object,
or a wide pointer to the counter and to the object. The intrusive approach
was chosen, to avoid double-indirection and double-allocation overheads. A
basic smart Pointer type was developed, which accepted a raw C++
Object* pointer.
When the smart pointer acquired an object, the object's count was
incremented; when the pointer released an object, the count was decremented.
If the count reached zero, the object was deleted. This happened either when
the Pointer went out of scope (during destruction) or during
reassignment. All counting and deallocation was provided in one place, in
the basic Pointer.
A strongly-typed template pointer Refer<T>
was derived from this, capable of being
specialised for each object type. This allowed -> dereferencing
to access the exact type of the stored object, using an inline typecast. All
other construction and assignment were inline, passing back arguments
to methods in the essentially typeless basic Pointer.
This was further optimised by replacing zero-valued pointers
by a distinguished null object, obviating the need for nullchecks during the
critical increment and decrement operations. This worked well until type
conversions were required. Unfortunately, a Refer<S> is
not automatically converted to a Refer<T>, even if the raw
pointer S* is in fact convertible to T*. This is
a significant drawback in polymorphic object-oriented programming styles.
An adaptation of the smart pointer was attempted in which type conversions were also supported. This had the same basic advantages, overheads and drawbacks of the reference counting approach. Two different approaches were explored.
The first used coercions back to raw pointers. Every smart pointer
Refer<T> had an operator T*() to return the
raw C++ pointer. This allowed assignments of subtype pointers to supertype
pointers, by the coercion from Refer<S> to S*
in the constructor for Refer<T> which expected a
T* argument. This provided for type upcasting as required.
However, having bi-directional conversions between smart pointers and raw
pointers produced conversion-route ambiguity everywhere in the binding of
methods, which could not determine whether to coerce to raw pointers, or
construct smart pointers. So, this strategy was eventually dropped.
The second approach extended the smart pointer interface to accept both
same-typed and differently-typed arguments. The idea was to force dynamic type
checking for differently-typed assignment, while bypassing this for same-typed
assignment. Initially, member templates (functions that introduce extra type
parameters on an individual basis) were introduced to handle the other
type. However, it was found that the base Pointer type could be
used to receive all differently-typed arguments without loss of expressiveness
(and in any case, member templates are not supported by all C++
implementations). The advantage of this approach was that both upcasting
and downcasting could be built automatically into the smart pointer. The
programmer no longer had to perform explicit type casts.
This solved the conversion-route ambiguities of the earlier strategy, but
did not solve all method overloading ambiguity. The compiler could not
resolve which smart pointer type to select in cases where methods were
overloaded, for example, on Refer<String> and
Refer<Object>. A work-around was to indicate explicitly
which type was intended at call-sites, by constructing the
intended pointer-type. This was not elegant; and in any case this approach
could not be used to distinguish different types of exception. When handling
exceptions, catch handlers must be able to distinguish the
most specific type of the exception raised by throw. Although
the C++ compiler could infer generalisation relationships between class-types
and raw pointer-types, it could not infer such relationships between smart
pointers, whose types are all treated as distinct.
Ultimately, the only way to provide for all the obvious pointer type conversions and sensitivity to exceptions was to define a hierarchy of smart pointer types that was isomorphic to the hierarchy of object types. In this way, pointers would be subject to the same generalisation and specialisation relationships as the objects to which they refer. This is another adaptation of the reference counting approach, similar to the handle-body idiom.
In this approach, every object of the type Object is given
a corresponding smart pointer of the type ObjectID. Each new
subclass has its own smart pointer type. The benefits of this are that
pointer types are linked explicitly in a type hierarchy; and special methods
of construction may be defined for certain pointer types. The only drawback
is the effort of defining each smart pointer separately (copy-and-paste
may be used). Each smart pointer type may convert automatically to any
pointer supertype, since the compiler is now sensitive to the pointer type
hierarchy. The exception catching mechanism is likewise sensitive to specific
pointer types, allowing full use of the throw ... catch
mechanism. Certain pointer types, such as ValueID, have special
constructors to wrap simple values as objects. Likewise, StringID
will wrap a literal character string in a String object.
Apart from this, the same benefits of smart pointers are obtained. The
main reference counting functionality is provided once in the base
Pointer and all derived pointers are coded inline, for efficiency
(apart from the -> dereference method, which performs a null-check
on the raw pointer and raises an exception if this is null).
Type upcasting is automatic, since the compiler understands the pointer
hierarchy. Type downcasting is explicit, using toType() and
tryType(). Dynamic type failure is integrated with exception
handling and exceptions are first-class objects.
Since parts of the SCL kernel are mutually-recursively dependent, a strategy
had to be found to make pointer types available before the components they refer
to have necessarily been declared. Separate header files are provided for each
pointer type. This allows a component to include all the headers of all the
pointer types on which it depends, in its own header. The pointer headers are
deliberately kept small; the implementation of their inlined methods is given
in the associated component's header file. As a consequence, every SCL
component is defined in three files: ComponentID.h declares
the smart pointer type; Component.h declares the component and
defines the inlined methods for both the component and the pointer type; and
Component.cc defines the compiled methods for the component and
pointer type.
This documentation was created by Dr Anthony J H Simons, Department of Computer Science, University of Sheffield, Regent Court, 211 Portobello Street, Sheffield S1 4DP, United Kingdom.
1.3