This article presents an efficient garbage collection system for C++ called AutoGC (Automatic Garbage Collection). The system presented uses so-called Smart Pointers and Reference Counting and is more efficient than the Mark and Sweep garbage collection systems present in the languages of Java and Lisp, but the extra efficiency does come at a cost. The cost limits what kind of code you can write but for most applications the cost should be affordable. I am currently using this system to write a computer game and are using this programming work to fine-tune to AutoGC system.
Bjarne Stroustrup's book The C++ Programming Language describes a simple string class that is both efficient and elegant in its internal workings. After writing a C++ computer game I became frustrated with the difficulties in finding memory leaks in my program. I then wondered whether or not it was possible to generalise the ideas presented in the string class to arbitrary classes. After some experimentation I found a positive answer to this question in most cases.
Given an arbitrary class Foo for which AutoGC should be used the constructor must be defined like so:
private:
Foo_A(/* args */) : Auto_G_C(DCODE_FOO_A)
{
// ...
}
public:
static ptr<Foo_A> ctor(/* args */)
{
return new Foo_A(/* args */);
}
Every class that uses AutoGC should inherit from Auto, which in turn inherits from Root. The symbol DCODE_FOO is an enumeration constant defined in the file enum-debug-code.hh. The purpose of the enumeration constant is so that Debug Memory Management (D.M.M.) (see an earlier article) can be used for this class. The purpose of the public ctor(/* args */) method is so that (roughly speaking) Foo objects are allocated on the heap not the stack (like Java Objects), which makes life simpler for the internals of the AutoGC system. The destructor of Foo should be defined like so:
private:
template <class T>; friend class ptr;
~Foo_A()
{
// ...
}
The ptr class mentioned above is available by clicking here. The destructor above is private so that only friend ptr template class may invoke it.
Two other garbage collection systems are possible. One I call ManualGC requires the programmer to keep track of memory and explicitly free/delete memory that is no longer required. The other system I call SuperGC is a natural generalisation of AutoGC. It is less efficient than AutoGC, but it works in situations where AutoGC cannot be used. The idea of the Root class is that like with the Auto class, the Manual and Super classes can inherit from Root.
NOTE: I haven't yet worked out how AutoGC should react to a situation of multiple inheritance. Suffice to say that more work needs to be done in this area. It is not a priority for me as my computer games do not use multiple inheritance.
This garbage collection system is faster than either Java's or Lisp's garbage collection system, but the extra speed comes at a cost. The cost is that the graph of memory usage of ptr objects must be acyclic. A cyclic situation results in a potential memory leak. Provided that the programmer prevents the cyclic situation from happening, then the system works just fine. If the programmer cannot guarantee the acyclic situation then either the ManualGC, SuperGC or some other garbage collection system could be employed. Here are some examples of classes which give rise to cyclic ptr situations.
class A_A : public Auto_G_C { public: ptr<A_A> pa; // ... }; |
ptr<A> pa = A_A::ctor(); pa->pa = pa; |
class A_A : public Auto_G_C { public: STAR_OK(A_A)* pa; // ... }; |
class A_A : public Auto_G_C { public: ptr<Auto_G_C> pr; // ... }; |
ptr<A> pa = A_A::ctor(); pa->pr = pa.operator->(); |
class A_A : public Auto_G_C { public: STAR_OK(Auto_G_C)* pr; // ... }; |
class B_A; class A_A : public Auto_G_C { public: ptr<B_A> pb; // ... }; class B_A : public Auto_G_C { public: ptr<A_A> pa; // ... }; |
ptr<A_A> pa = A_A::ctor(); ptr<B_A> pb = B_A::ctor(); pa->pb = pb; pb->pa = pa; |
class A_A : public Auto_G_C { public: STAR_OK(B_A)* pb; // ... }: class B : public Auto_G_C { public: STAR_OK(A_A)* pa; // ... }; |
I have written an Elisp (Emacs Lisp) preprocessor that parses C++ code and verifies that no cyclic ptr situations exist. For telling the preprocessor that pointers to AutoGC objects are okay, the C++ preprocessor symbol STAR_OK is defined as follows:
#define STAR_OK(x) x
|
For telling the preprocessor that cyclic ptr situations are okay, the C++ preprocessor symbol LOOP_OK is defined as follows:
#define LOOP_OK(x) x
|
The last source file above is the main file as that is the one that calls the functions from the other three source files.
To run the preprocessor on my computer, I added the following lines to my Makefile:
ELISP_LOCATION = ~/dlisp/
EMACS_LOCATION = "~/../Program Files/emacs-21.3/bin/emacs.exe"
ELISP_FUNCTION = autogc--do-tritus
autogc:
cd $(ELISP_LOCATION); $(EMACS_LOCATION) -batch -l autogc.el -f $(ELISP_FUNCTION)
|
and built using the command make autogc. You will need to set the above three Make variables to the correct values for your machine. You will also need to modify the Elisp function stored in variable ELISP_FUNCTION to inspect your source code.
In the above file _List_Node.hh the LOOP_OK macro is used twice to defeat the preprocessor's search for cyclic ptr situations and the STAR_OK macro is used once to defeat the preprocessor's search for illegitimate use of pointers to AutoGC objects.
| Back to Research Projects |
|
This page has the following hit count:
|