Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
94 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Memory Management

Memory is one of your top resources. It's your workspace; it's the floor of your room, where you can put toys while you play with them. And if you don't put the toys away once in a while, you'll run out of space and won't be able to play with any more toys. Until your mother comes up with a black binbag and starts putting everything into it shouting that you.. sorry, childhood flashback. *Ahem*. Moving on.

One of the most disrepectful things you can do to a player's system is leak memory. Your program's leaving mess on the pavement, and you're not scooping up after it. Gradually, the player's system gets slower and slower as the OS pages more and more memory to disk; until eventually they have to stop playing and reboot.

So here's the first thing our memory manager needs to do: track memory usage. It needs to keep an eye on all the blocks of memory we carve out, to ensure that said blocks get released again in the proper fashion.

Now, I've been a little, uh, 'economical with the truth.' We don't need to track *all* our memory. There's two types of memory involved: stack memory, and heap memory. Heap memory we worry about; stack memory we don't. There's also a few things that it's fairly impractical to manage - things like Singletons, or other 'large objects' that are so obvious that failing to release them would cause other noticable bad behaviour (things like the Kernel or Application objects). But for most of the objects our engine handles, they could slip away into obscurity at any time, never to be seen again... We need to keep a list of pointers to our objects.

Here's how we approach it. We create a new class, IMMObject:

class IMMObject
{
   private:
      static std::list<IMMObject *> liveObjects;
   protected:
      IMMObject();
      virtual ~IMMObject();
   public:
};

//a 'static initialiser' is needed in one of the source
//files to give the std::list a definitive presence
std::list<IMMObject *> IMMObject::liveObjects;

IMMObject::IMMObject()
{
   liveObjects.push_back(this);
}

IMMObject::~IMMObject()
{
   // We add an empty virtual destructor to make sure that
   // the destructors in derived classes work properly.
}

Righty ho. To clean up all objects floating around at the end of the program, we loop through the liveObjects list, deleteing each pointer - and voila, no memory leaks. So that's ok - except, we can only do that at the end of the program. What if we're in the middle of the game and find ourselves running low on memory? We can't just delete all our objects and start again, but there'll probably be some objects we *could* delete, if we knew about them. So here we get to the next requirement of our memory manager: Garbage Collection. We should be able to remove from memory all the 'orphaned' objects that aren't needed any more.

But wait: how do we tell if an object isn't needed any more? We could have some kind of a flag that the object's user sets when it's done with it, but that's potentially disasterous if objects are being shared around (and they most certainly will be). So, coupled to Garbage Collection is a third requirement: Reference Counting. A system for tracking how many things are using an object, and for marking it as 'collectable' when they all say they're done. So, we try the IMMObject class again:

class IMMObject
{
   private:
      static std::list<IMMObject *> liveObjects;
      long refCount;
   protected:
      IMMObject();
      ~IMMObject();
   public:
      void AddRef();
      void Release();
      static void CollectGarbage();
};

IMMObject::IMMObject()
{
   liveObjects.push_back(this);

   //update the constructor to initialise refCount to zero
   refCount=0;
}

void IMMObject::AddRef()
{
   ++refCount;
}

void IMMObject::Release()
{
   --refCount;
}

void IMMObject::CollectGarbage()
{
   for(std::list<IMMObject *>::iterator it=liveObjects.begin(); it!=liveObjects.end(); )
   {
      IMMObject *ptr=(*it);
      ++it;
      if(ptr->refCount<=0)
      {
         liveObjects.remove(ptr);
         delete ptr;
      }
   }
}

There are two problems with this approach. Firstly, there's the rather icky construction in the CollectGarbage() function - the iterator has to be incremented at a weird time to make sure it doesn't get stepped on by the call to remove(). Also, this method is bad when the ratio of live objects to dead objects is high: when you've got 5000 objects being managed, but only 10 of them need removing, that's still 5000 objects being checked; not good. A better solution is to give the liveObjects list a parter - deadObjects:

class IMMObject
{
   private:
      static std::list<IMMObject *> liveObjects;
      statid std::list<IMMObject *> deadObjects;
      long refCount;
   protected:
      IMMObject();
      ~IMMObject();
   public:
      void AddRef();
      void Release();
      static void CollectGarbage();
};

std::list<IMMObject *> IMMObject::deadObjects;

void IMMObject::Release()
{
   --refCount;
   if(refCount<=0)
   {
      liveObjects.remove(this);
      deadObjects.push_back(this);
   }
}

void IMMObject::CollectGarbage()
{
   for(std::list<IMMObject *>::iterator it=deadObjects.begin(); it!=deadObjects.end(); it++)
   {
      delete (*it);
   }
   deadObjects.clear();
}

Much neater, don't you think? (There's still an optimisation there - liveObjects.remove still searches the list for the object (which can take even longer than the initial method, in fact), so the object should store some kind of iterator allowing the list to remove it directly. But I leave it up to you.)

There's two more things we should add to the IMMObject class before we move on. Firstly, a fail-safe function, to be called at the end of the program, that will purge the liveObjects list (and log anything unreleased, because if there's anything still around at that time then something screwy's going on). Secondly, if we're going to track all the objects that are around, we might as well lay a base for tracking memory usage, too; so we add a pure virtual function, for derived classes to implement, that returns the size of the object.

class IMMObject
{
   private:
      static std::list<IMMObject *> liveObjects;
      static std::list<IMMObject *> deadObjects;
      long refCount;
   protected:
      IMMObject();
      virtual ~IMMObject();
   public:
      void AddRef();
      void Release();
      static void CollectGarbage();
      static void CollectRemainingObjects(bool bEmitWarnings=false);
      virtual unsigned long size()=0;
};

//define a quick macro to make things easier on derived classes
#define AUTO_SIZE unsigned long size(){return sizeof(*this);}

void IMMObject::CollectRemainingObjects(bool bEmitWarnings)
{
   CollectGarbage();
   for(std::list<IMMObject*>::iterator it=liveObjects.begin();it!=liveObjects.end();it++)
   {
      IMMObject *o=(*it);
      if(bEmitWarnings)
      {
         //log some kind of error message here
         //we'll be covering how to log messages later this article
      }
      delete o;
   }
   liveObjects.clear();
}

And there we go: a nice little base class to automatically memory-manage our objects. You might want to polish it up a bit - inline the AddRef()/Release() functions, for example - but again, I leave it up to you.





Smart Pointers
Contents
  Introduction
  Memory Management
  Smart Pointers
  Error Logging
  Miscellanous Utilities

  Source code
  Printable version
  Discuss this article

The Series
  Part I
  Part II
  Part III
  Part IV
  Part V