Sign in to follow this  
evolutional

C++ Implementation of Garbage Collection

Recommended Posts

evolutional    1393
I've been looking around at various garbage collection techniques decribed on Wikipedia with the aim to implement one into my metaclass framework. I will not be implementing GC for all objects (and therefore will not overloading the new operator) and will focus mainly upon my metaclass/scripting environment. However my GC should be fairly generic - I want to be able to drop it into a new project and go from there if needed. My setup is fairly simple, I have a templated class that handles pools of objects. Allocations are drawn from the pools (expanding by a specified amount if there's no free space) and frees are 'given back' to the pool via the implementation of freelists. This is, I assume, a fairly common system in commerical game development. Because I'm not allocating objects with new, I have to call the Alloc() method from my pool system, I should theoretically be able to assign these new objects to a garbage collector at this time as the GC is tied into the basic environment. So now, I'm stuck on actually implementing a form of Garbage Collection; the method I wish to use is that of a Tracing GC. I'm pretty clear on how this method works in theory, but only have one implementation example of it (a la GameMonkey script). The current example I have is based on a tri-colour scheme, with the GC being performed incrementally. I could base my GC on this, but would rather look around for other examples, hear some pros and cons and get some general opinions from you guys. Can you please point me in the direction of any solid examples of a tracing GC, preferably if you've used it yourself in some way. Or, if you don't think tracing is the way - could you recommend any other methods that would be compatible with my memory allocation setup? Thanks in advance!

Share this post


Link to post
Share on other sites
evolutional    1393
Quote:
Original post by Fruny
You know that one don't you?


Yes, I came across that one as part of my searches. It seems to be using the Mark and Sweep technique which I think is a variant of the basic algorithm. I'm wondering if this method is the one that the GameMonkey code is using - I think I'll study the code as I dismissed it before (for whatever reason).

Thanks for the prod Fruny :)

Share this post


Link to post
Share on other sites
MaulingMonkey    1730
Fruny: Nice link, picked up the keyword "incremental" in relation to GC and suddenly opened my eyes as I realized (with the help of links) that GC can work in parallel/in increments with a "realtime" system (read: game) without temporary stalls.

I'm interested in implementing this kind of functionality, the main thing my mind seems to be catching on is how to implement automatic tracing of pointers (that is, without implementing a manual trace_children() function or the like in each class that adds collected pointers) without mantaining a redundant list of pointers to all the pointers within a collected_object base. I can think of one very ugly and inefficient solution that depends on what's technically undefined behavior... (read: casting a (&member_collected_pointer - this) to a member pointer on class creation by having each collected_pointer take an argument (reference or pointer) to collected_object, which would add to the static member list of collected_object_pointer_list< type >... and this dosn't even deal with containers of such pointers!)

EDIT: Attached a very crude example of implementing GC. I don't even know if it works right, all I know is that my example program manages to run without crashing ^_^.

garbage.hh
#ifndef IC__INDUSTRY__GARBAGE
#define IC__INDUSTRY__GARBAGE

#include <algorithm>
#include <set>

namespace industry
{
namespace garbage
{
class collected_pool;
template < typename type_t > class collected_pointer;
class do_collect;
class do_destroy;
struct do_delete
{
template < typename value_t >
void operator()( value_t * pointer )
{
delete pointer;
}
};
class collected_object
{
private:
friend class collected_pool;
friend class do_collect;
template< class > friend class collected_pointer;
collected_pool & pool;
protected:
virtual void collect_children( void ) const {}
public:
collected_object( collected_pool & pool )
: pool( pool )
{
}
virtual ~collected_object( void )
{
}
};
template < typename type_t > class collected_pointer
{
type_t * pointer;
public:
collected_pointer( void )
: pointer( 0 )
{
}
collected_pointer( type_t * pointer )
: pointer( pointer )
{
if ( !pointer ) return;
pointer->pool.collect( pointer );
}
template < typename copy_t >
collected_pointer( const collected_pointer< copy_t > & c_pointer )
: pointer( static_cast< type_t * >( c_pointer.pointer ) ) //yehck!! :P
{
if ( !pointer ) return;
pointer->pool.collect( pointer );
}
collected_pointer< type_t > operator=( type_t * new_pointer )
{
pointer = new_pointer;
if ( !pointer ) return;
pointer->pool.collect( pointer );
}
template < typename copy_t >
collected_pointer< type_t > operator=( const collected_pointer< copy_t > & new_c_pointer )
{
pointer = new_c_pointer;
if ( !pointer ) return;
pointer->pool.collect( pointer );
}
type_t & operator* ( void ) const
{
return *pointer;
}
type_t * operator->( void ) const
{
return pointer;
}
type_t & get( void ) const
{
return pointer;
}
};
class collected_pool
{
std::set< collected_object * > roots;
std::set< collected_object * > allocated;
std::set< collected_object * > grey; //list to possibly free, for incremental GC
public:
void add_root( collected_object * object )
{
roots.insert( object );
}
template < typename type_t > type_t * create( void )
{
//WARNING: unless the return is made reachable from one of the roots,
//the returned value isn't reachable, and thus GC will attempt to clean it!!!
type_t * pointer = new type_t( *this );
allocated.insert( pointer );
return pointer;
}
void destroy( collected_object * pointer )
{
roots.erase( pointer ); //just in case
allocated.erase( pointer );
delete pointer;
}
void run_incremental_gc_loop( void );
void collect( collected_object * pointer )
{
grey.erase( pointer );
pointer->collect_children();
}
void collect( collected_object & object )
{
collect( &object );
}
~collected_pool( void )
{
std::for_each( allocated.begin() , allocated.end() , do_delete() );
}
};
class do_collect
{
public:
void operator()( collected_object * pointer )
{
pointer->pool.collect( pointer );
}
};
class do_destroy
{
collected_pool & pool;
public:
do_destroy( collected_pool & pool )
: pool( pool )
{
}
void operator()( collected_object * pointer )
{
pool.destroy( pointer );
}
};
void collected_pool::run_incremental_gc_loop( void )
{
//WARNING: should probably add a time-delay wait forced in here
//so that we don't end up doing two loops before a created object can be returned
//to be added to some reachable object's pointers.
grey = allocated;
//YET ANOTHER WARNING: I'm not sure if insertion can be run in parallel
//with setting one set to another - as long as all those not being
//inserted during this timeframe (and optionally any/all of those that are)
//we should be OK. (this is in relation to running GC in a seperate thread)
std::for_each( roots.begin() , roots.end() , do_collect() );
//greylist is now blacklist, delete at will:
std::for_each( grey.begin() , grey.end() , do_destroy( *this ) );
}
}
}

#endif //ndef IC__INDUSTRY__GARBAGE



test.cc
#include <iostream>

#include "garbage.hh"

using namespace industry::garbage;
using namespace std;

struct my_object : public collected_object
{
std::set< my_object * > children;
my_object( collected_pool & pool )
: collected_object( pool )
{
}
protected:
virtual void collect_children( void ) const
{
for_each( children.begin() , children.end() , do_collect() );
}
};

int main ( int argc , char ** argv )
{
collected_pool pool;
collected_pointer< my_object > ptr = pool.create< my_object >();
pool.run_incremental_gc_loop();
cout << "Ran to the end without crashing!!! Woohoo!!!" << endl;
string buffer;
getline( cin , buffer );
}



[Edited by - MaulingMonkey on March 29, 2005 6:52:14 AM]

Share this post


Link to post
Share on other sites
evolutional    1393
nmi: Thanks for the links. I'm reading the Wilson paper now and it seems to be very good. I didn't realise, but the GC linked by Fruny is based on this paper, which seems to be a good thing.

MaulingMonkey: Yes, the automatic tracing of pointers will potentially be an issue. I think I'm going to look at the manual ways first (as I won't have that many objects GC'd) but will definitely need to consider some form of automatic tracing scheme if and when I need something more sophisticated.

The incremental scheme is something I think is necessary for realtime systems. When using the simple reference-counted GC described in Enginuity, one of the sticking points was the slowdown associated with the full GC sweep each frame. In games, this is unacceptable - especially if your particle systems and other temporary entity systems are tied into the GC.

I think one of the papers linked by nmi will be useful as it discusses the age of objects; an incremental system with this consideration seems useful as you can manage the frequency of the scans. There's no point scanning new objects as soon as they're added. One concern I do have with incremental GC is this; you're forever fighting against the creation of new objects, so it is possible that you might not reclaim objects in time. It seems then, that some intelligence needs to be built into it in the way that it calculates the number of work units on each cycle. As such, far more dialog will be needed between the host environment and the GC than I'd anticipated - but this isn't a bad thing. I think I'm going to write a formal plan for the system, rather than just try and code it.

Share this post


Link to post
Share on other sites
MaulingMonkey    1730
Quote:
Original post by evolutional
nmi: Thanks for the links. I'm reading the Wilson paper now and it seems to be very good. I didn't realise, but the GC linked by Fruny is based on this paper, which seems to be a good thing.

MaulingMonkey: Yes, the automatic tracing of pointers will potentially be an issue. I think I'm going to look at the manual ways first (as I won't have that many objects GC'd) but will definitely need to consider some form of automatic tracing scheme if and when I need something more sophisticated.


Well, see my attached example in the post that I've edited in above. Again, to reiterate the disclaimer : I'm not sure if it works right. I've only done the basic test of making sure it seems to execute without segfaulting or the like. It provides a pooled allocator/GC scheme. (sidenote: main.cc's my_object should have a collected_pointer rather than a regular pointer). It does everything "manually" by which I mean it uses a virtual function called collect_children() which must collect all the children (as in "reachable" - members, parent class(es), pointed to in containers - whatever). Main sticking points: spaghetti-like, untested, and you must provide said collect_children function (read: implement manually).

Quote:
I think one of the papers linked by nmi will be useful as it discusses the age of objects; an incremental system with this consideration seems useful as you can manage the frequency of the scans. There's no point scanning new objects as soon as they're added. One concern I do have with incremental GC is this; you're forever fighting against the creation of new objects, so it is possible that you might not reclaim objects in time. It seems then, that some intelligence needs to be built into it in the way that it calculates the number of work units on each cycle. As such, far more dialog will be needed between the host environment and the GC than I'd anticipated - but this isn't a bad thing. I think I'm going to write a formal plan for the system, rather than just try and code it.


Prehaps base the number based on framerate and RAM use? That is, if you have yet to start causing page faults based on overusing RAM, there's little incentive to ramp up GC too much (except to prevent fragmentation) - but the closer to that boundry you get, the more economical GC becomes (that is, page swapping will hurt framerate more than GC).

Share this post


Link to post
Share on other sites
nmi    978
Maybe lets say some words to garbage collection.

When doing manual memory management (via malloc/free or new/delete), the application is responsible to free memory that is not needed anymore.
When using a garbage collector, the GC MAY delete memory that is not referenced by the application anymore. (The GC is free to choose WHEN to release the memory!)

The good thing about GC is, that allocation of memory may be as cheap as decrementing a pointer and returning it. Manual memory managers need to search a tree/list/whatever to find a matching block.

Releasing memory is (or at least can be) deferred when using a GC. So as long as the application has operation phases with low CPU usage, the GC may use it to search for unreferenced memory. This leads to a higher efficiency compared to manual memory management. (see generational GC)

If there are no phases of CPU usage, the application may stall or at least become slower while using more memory than would be needed by manual memory management. Here reference counting may be good, especially if there are no circular structures. (Using reference counting together with tracing to detect circular references would be another choice.)

To actually use GC in C++, the garbage collector needs to know where pointers are. If raw pointers are used (like int*), this leads to conservative techniques like Boehm-Weiser, since the GC cannot distinguish an integer and a pointer for instance. Using only smart pointers to reference objects on the GC heap can avoid this problem.

Share this post


Link to post
Share on other sites
bkt    178
I should definately be reading some of these; my implementation is very crude and I didn't even use templates (bad me!). I'll be looking over this stuff as well. Thanks guys!

Share this post


Link to post
Share on other sites
evolutional    1393
Thanks for the code MaulingMonkey, it's somewhat different to the implementation I've been studying so the comparison should be interesting. I can see that it follows the same sort of techniques however, so the implementation should make sense to me.

There's some food for thought about the actual implementation of this in my system, especially as the implementation model itself can vary somewhat.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this