GNU   davin.50webs.com/research
Bringing to you notes for the ages

       Main Menu          Research Projects         Photo Album            Curriculum Vitae      The Greatest Artists
    Email Address       Computer Games          Web Design          Java Training Wheels      The Fly (A Story)   
  Political Activism   Bob Dylan Quotes+       My Life Story          Smoking Cessation          Other Links      
Debugging Macros     String Class I     Linked List System I Java for C Programmers Naming Convention
    String Class II         How I use m4              Strings III                 Symmetrical I/O             Linked Lists II     
Run-Time Type Info   Virtual Methods      An Array System        Science & Religion            Submodes       
  Nested Packages      Memory Leaks    Garbage Collection      Internet & Poverty      What is Knowledge?
Limits of Evolution   Emacs Additions      Function Plotter           Romantic Love        The Next Big Thing
    Science Fiction     Faster Compilation Theory of Morality         Elisp Scoping               Elisp Advice      
  S.O.G.M. Pattern       Safe Properties         School Bullying          Charisma Control          Life and Death    
     Splitting Java          Multiple Ctors       Religious Beliefs         Conversation 1           Conversation 2    
   J.T.W. Language    Emacs Additions II      Build Counter             Relation Plotter          Lisp++ Language  
  Memory Leaks II   Super Constructors CRUD Implementation Order a Website Form There Is An Afterlife
More Occam's Razor C to Java Translator Theory of Morality II


An efficient garbage collection system for C++ Free Stuff

Abstract

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.

1. Motivation

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.

2. How to use AutoGC

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.

3. Limitations of AutoGC

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.


Code with a potential cyclic ptr situation
Example of a cyclic ptr situation
Code fixed to avoid the cyclic ptr situation
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

Here are the files that comprise the preprocessor:

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.

4. Some utility classes

Back to Research Projects
This page has the following hit count:
| Main Menu | Research Projects | Photo Album | Curriculum Vitae | The Greatest Artists |
| Email Address | Computer Games | Web Design | Java Training Wheels | The Fly (A Story) |
| Political Activism | Bob Dylan Quotes+ | My Life Story | Smoking Cessation | Other Links |
| Debugging Macros | String Class I | Linked List System I | Java for C Programmers | Naming Convention |
| String Class II | How I use m4 | Strings III | Symmetrical I/O | Linked Lists II |
| Run-Time Type Info | Virtual Methods | An Array System | Science & Religion | Submodes |
| Nested Packages | Memory Leaks | Garbage Collection | Internet & Poverty | What is Knowledge? |
| Limits of Evolution | Emacs Additions | Function Plotter | Romantic Love | The Next Big Thing |
| Science Fiction | Faster Compilation | Theory of Morality | Elisp Scoping | Elisp Advice |
| S.O.G.M. Pattern | Safe Properties | School Bullying | Charisma Control | Life and Death |
| Splitting Java | Multiple Ctors | Religious Beliefs | Conversation 1 | Conversation 2 |
| J.T.W. Language | Emacs Additions II | Build Counter | Relation Plotter | Lisp++ Language |
| Memory Leaks II | Super Constructors | CRUD Implementation | Order a Website Form | There Is An Afterlife |
| More Occam's Razor | C to Java Translator | Theory of Morality II
Last modified: Thu Oct 27 19:34:50 NZDT 2016
Best viewed at 800x600 or above resolution.
© Copyright 1999-2016 Davin Pearson.
Please report any broken links to