Mar 17, 2000

Garbage Collection is the term used to describe an algorithm that frees allocated memory when it is no longer in use. There are lots of such algorithms available, each with its advantages and disadvantages.

I will present here a method of doing garbage collection that is useful for handling normal game data.

Contents:

• [alink=s1]Reference Counting [/alink]
• [alink=s2]Smart Pointers [/alink]
• [alink=s3]Usage [/alink]
• [alink=s4]Reference counting and STL [/alink]
• [alink=s5]Multithreaded Operation [/alink]
• [alink=s6]Overhead [/alink]
• [alink=s7]Pros-Cons [/alink]
  
  [size="5"][aname=s1]Reference Counting
  
  This is not an unknown term, and it's being used in lots of places to handle shared objects with proper release when the object is no longer needed. This is done by attaching a counter to the object, which holds the number of places that hold a pointer to the object. The user code is responsible for calling AddRef() and Release() to increment and decrement the counter. When the counter reaches 0, the object is deleted.
  
  Any one who has ever used this method knows that it can be error prone if the AddRef() and Release() functions are not called properly, resulting in either memory leaks or invalid pointers. Later in this article, a way to solve this problem will be presented.
  
  To provide the actual reference counting, a base class which handles the counter is created. All this class provides is an addRef() function which increments the countera, a subRef() function which decrements the counter and returns true if the counter is 0.
  
  
  class RefCntObject
{
public:
virtual ~RefCntObject() {}

/** Default constructor. Initial reference count is 0,
and will be incremented as soon as the object is
pointed to. */
RefCntObject() : m_refcnt(0) {}

/** Add 1 to the reference count. */
void addRef() { m_refcnt++; }

/** Subtract 1 from the reference count.
Returns true if the reference count has reached 0
and the object should be deleted. */
bool subRef() { return (--m_refcnt <= 0); }

private:
int m_refcnt;
};
  All objects which we want to include in this allocation scheme, must be instances of a class derived from this base class. It doesn't have to be a direct parent, just an ancestor, so that the object will have the reference counter available.
  
  
  [size="5"][aname=s2]Smart Pointers
  
  What is a pointer? A definition may be a variable which holds the address of some memory location. A more interesting way to define anything in programming is by its attributes and actions. A pointer has the attribute of holding an address, and has several actions: (assumes: int* p)
  
  ActionExampleDereferencingint b=*p;Member accessp->somethingNULL checkif (p) ....A smart pointer is a type that provides all of the above requirements, and perhaps does something extra which is useful. In this case, a smart pointer will make sure to call the addRef() subRef() for us, freeing us from worrying.
  
  When should the reference counting be changed for an object? When ever someone acquires a pointer to the object, the counter should be incremented. When ever someone lets go of a pointer to the object, the counter should be decremented. The last one to let go of the pointer should also delete the object.
  
  Using C++ features, here is a template class for such a smart pointer. It assumes the template parameter provides the reference counting operations.
  
  
  template
class RefCntPointer
{
public:
/** Construct from normal pointer, default to NULL */
RefCntPointer(T* ptr=0) : m_ptr(ptr) { addRef(); }

/** Construct from another smart pointer. Copy Constructor */
RefCntPointer(const RefCntPointer& p) : m_ptr(p.m_ptr) { addRef(); }

/** Destructor. */
~RefCntPointer() { subRef(); }
  The constructors store the pointers and call addRef() to increment the counter, due to this new pointer. The destructor cleans up the counter. This is obviously not enough, since the smart pointer can be changed by assignment
  
  
  /** Assignment operator. */
RefCntPointer& operator= (const RefCntPointer& p)
{
// Use the other operator (code reuse)
return *this = p.m_ptr;
}

/** Assignment operator. */
RefCntPointer& operator= (T* ptr)
{
if (m_ptr != ptr)
{
subRef();
m_ptr=ptr;
addRef();
}
return *this;
}
  
  Note that the operator first decrements the counter for the old pointer, and then assigns the new pointer and increments its counter.
  
  Now several operators to provide the pointer actions, and some useful conversions:
  
  
  /** Dereferencing operator. Provided to behave like the normal pointer. */
T& operator * () const { return *m_ptr; }

/** Member access operator. Provided to behave like the normal pointer. */
T* operator -> () const { return m_ptr; }

/** Conversion operators */
operator T* () const { return m_ptr; }
operator const T* () const { return m_ptr; }

/** boolean test for NULL */
operator bool () const { return m_ptr!=0; }

/** Address of pointer. May cause memory leaks if pointer is modified. */
T** operator & () { return &m_ptr; }
  I recommend removing the last operator, to avoid problems. Use it only if absolutely necessary.
  
  Here is the implementation of the private part of the class, which modifies the counter:
  
  
  private:
void addRef()
{
// Only change if non-null
if (m_ptr) m_ptr->addRef();
}

void subRef()
{
// Only change if non-null
if (m_ptr)
{
// Subtract and test if this was the last pointer.
if (m_ptr->subRef())
{
delete m_ptr;
m_ptr=0;
}
}
}

T* m_ptr;
};
  
  [size="5"][aname=s3]Usage
  
  Using these pointers means simply to replace the declaration of the pointer:
  
  
  MyObject* p; --> RefCntPointer p;
  All the rest of the code can remain the same, as this type provides the same semantics as a regular pointer.
  
  
  [size="5"][aname=s4][size="5"]Reference counting and STL
  
  A lot of times it is needed to hold objects in a data structure, and not worry about deleting them when clearing, or erasing the objects from the structure. This reference counting scheme does all of that for you. All you need to do is use structures of smart pointers, and you're done.
  
  Example:
  
  td::vector > v;
v.push_back(new MyObject);Now if you clear the vector, or erase the pointer, the object will be freed. If you want to erase it without deleting it, because you need the object somewhere, simply get the pointer and hold it before erasing:
  
  RefCntPointer ptr=v[0];
v.pop_back();Now the pointer was removed, but the object wasn't deleted. To delete it now, simply do:
  
  ptr=NULL;
  
  [size="5"][aname=s5][size="5"]Multithreaded Operation
  
  In multithreaded programs, it is necessary to synchronize shared objects, to avoid inconsistencies due to scheduling in the middle of an (in/de)crement. This can be done by adding a mutex to each object, and locking it before doing the actual change of counter.
  
  Implementation of this is OS specific.
  
  
  [size="5"][aname=s6][size="5"]Overhead
  
  There are 2 kinds of overhead when using this scheme:
  
  1. Space, requiring 1 int per object.
  2. Time, the (in/de)crement of the counter whenever a pointer changes.
  Usually, when correctness is required, this is a small price to pay.
  
  
  [size="5"][aname=s7][size="5"]Pros-Cons
  
  Drawbacks:
  
  This scheme cannot be used in data structures where pointer circles are formed (e.g. doubly linked lists). For tree like structures (trees, vectors, singly linked lists) it can be safely used. Most game data is stored in tree-like structures so it is useful for games.
  
  Advantages:
  
  • A simple system, can be easily integrated into existing software
  • Time distributed garbage collection, with very low latency, as it is done when you would normally delete objects.
  • Does not require a special allocator.
  • Frees you from the worry of calling delete or managing the counter manually.
    [url=""][/url]