Garbage Collector?

I'd actually suggest smart pointers. You may be forced into a situation where you have to work with a raw pointer, in which case you should delete it as soon as it is about to go "out of scope" (or whenever makes the most sense). You can also use a bit of a mix between smart pointers and raw pointers if necessary (smart pointers to actually maintain the lifespan of an object, and raw pointers for passing around for functions that only temporarily need that reference).

The main complaint people have with garbage collectors is that they may collect garbage at a bad time and cause a weird occasional stutter in your game. Whether or not that actually happens depends on the garbage collector, how you use it, and how you're using memory.

The only time that I've seen a "GC" used in a C++ game engine was on a games console where the game had to manage VRAM itself (usually your graphics driver does this), so when deleting a VRAM resource, like a texture, it was put into a queue of resources to be released in 2-frames time (to account for GPU latency).
...and this wasn't really a garbage collector, but a garbage queue.

In a multi-threaded game engine that I wrote, when an object's reference count reached zero, it was also put in a queue for deletion, which would occur after a sync point, otherwise another thread could possibly try and access the object after it had been deleted. Again though, this isn't as much a "GC" as a multi-threaded reference counter.

Usually GC's in games only exist in the embedded extension/'scripting' language, like C#/Lua/Python etc...

1. Is it adviseable to implement a custom garbage collector for a game engine written in C++, or
   
2. just delete objects immediately as soon as they become unreferenced?
   

1. I strongly advice to do so for your engine itself. It makes sense to do so with loaded resources using reference counting. A full mark-and-sweep garbage collection would require each collectable object to be able to export pointers to all other objects they are using. In my experience, it was very easy to forget export a pointer and causing a leak. I'm not 100% sure efficient GC is possible at all in C/C++.
   
2. Perhaps I'm being pedantic but once an object is unused, it doesn't change much whatever we delete it now or a few seconds later. The point is not to delete objects, but to figure out objects which can be safely deleted.
   

1. ... I'm not 100% sure efficient GC is possible at all in C/C++.
   

Have you tried Boehm's Garbage Collector (http://www.hpl.hp.com/personal/Hans_Boehm/gc/)? In my experience, it's quite fast.

Perhaps I'm being pedantic but once an object is unused, it doesn't change much whatever we delete it now or a few seconds later. The point is not to delete objects, but to figure out objects which can be safely deleted.

That depends on the object. For instance, an object might lock a mutex in its constructor and unlock it in its destructor. You wouldn't want that object destroyed a few seconds after it should be. Of course in that case it will probably live on the stack and this is not an issue. But my point is that destructors might do more than just clean up memory. I don't like garbage collectors for this reason.

I second smart pointers. Smart pointers are modern C++'s "garbage collector", but are not enabled by default, and you just enable them explicitly for the variables you want. C++'s unofficial motto is: "Only pay for what you use", smart pointers are you-only-pay-for-when-you-want-it "garbage collection".

It really depends on the nature of the object. For resources as meshes and textures, I have some custom object management system that makes sure these objects are released if they are unreferenced for a few seconds. For objects like this it makes sense, as there isn't a clear ownership. However, for objects that do have a clear ownership, smart pointers or garbage collection doesn't really make sense, and could even be considered anti-pattern. They can easily break the class invariant, if there is a composition relationship between class A en B where class A owns zero or more instances of class B, deleting A should delete all instances of B that were linked to this A. The garbage collector keeping instances of B alive because of some remaining references while it's owner is destroyed can result in your application misbehaving as it's in a state you didn't consider possible in the design.

Unique pointers on the other hand are something different, and these are more suitable for situations like this. They ensure there is a clear ownership, and if the owner is deleted the owned objects are as well. There is still a risk of breaking the class invariant using unique pointers however, if you have an object C that has a 1..1 aggregation relationship to class B, and B gets deleted, C will become invalid as it is missing it's required link to B. But at least now you can assert on that situation. Personally I would introduce a third kind of smart pointer, consisting of a unique pointer (owner), weak pointer (reference that may change to null if object is deleted) and hard pointer (reference that will assert if object is deleted). That way your class invariant can be kept valid through the automatic pointer management. Shared pointers should be used only for situations where there really is a shared ownership of the pointer, which is almost never the case.

Have you tried Boehm's Garbage Collector (http://www.hpl.hp.co.../Hans_Boehm/gc/)? In my experience, it's quite fast.

Whatever it's fast in practice is a different thing than being efficient.What I understand from the Boehm collector is that it scans objects blobs for pointers. We can see some additional machinery in the last C++ revision, which adds support for GC and allows to specify memory areas as "guaranteed to not contain pointers".
This is a key point.
Languages such as C# or Java forbid modification of memory which is not associated to a type: they have intrinsic knowledge of what it's being allocated. C/C++ has not and this causes the GC to run much more conservatively.
Rather than bolting GC on C++, I'd consider another language.

That depends on the object. For instance, an object might lock a mutex in its constructor and unlock it in its destructor.

Yes correct. Perhaps we should debate if this is correct usage. I think it's not. And this is the main reason in my opinion to not use GC. People tends to forget that object lifetimes are important.

Here's another very nice example I've seen in the past.
A game used particle systems to make explosions. They were created on the fly each time it's needed. Rather than disabling the PS after a certain time, this code relied on the finalizer to get the PS cleaned. What it happened is that the explosion sometimes "looped". Rather than fixing the problem, the author made an habit of calling GC collect every time possible and this still didn't work 100% of the cases.

While destructors can be trusted for a variety of operations, I think they lose that property when they become finalizers. If timely release is a concern, either GC goes out of the window, or we call [font=courier new,courier,monospace]finalize [/font]manually.

However, for objects that do have a clear ownership, smart pointers or garbage collection doesn't really make sense, and could even be considered anti-pattern. They can easily break the class invariant, if there is a composition relationship between class A en B where class A owns zero or more instances of class B, deleting A should delete all instances of B that were linked to this A.

Which is what smart pointers do. They give clear ownership to objects that otherwise wouldn't have clear ownership, and delete the object the moment it is no longer being referenced (not seconds later - the exact moment it is no longer referenced).

The garbage collector keeping instances of B alive because of some remaining references while it's owner is destroyed can result in your application misbehaving as it's in a state you didn't consider possible in the design.[/quote]
Garbage collection, yes, proper usage of smart pointers, no.

Unique pointers on the other hand are something different, and these are more suitable for situations like this.[/quote]
Unique pointers are a type of smart pointers.

They ensure there is a clear ownership, and if the owner is deleted the owned objects are as well. There is still a risk of breaking the class invariant using unique pointers however, if you have an object C that has a 1..1 aggregation relationship to class B, and B gets deleted, C will become invalid as it is missing it's required link to B.[/quote]
That's exactly what smart pointers solve. Look up weak_ptr.

But at least now you can assert on that situation. Personally I would introduce a third kind of smart pointer, consisting of a unique pointer (owner), weak pointer (reference that may change to null if object is deleted) and hard pointer (reference that will assert if object is deleted).[/quote]

I just went over this in a different thread, so I'm just going to copy+paste the relevant portion here:
std::unique_ptr = I own this object, nobody else owns it _or_ uses it.
std::shared_ptr = I own this object, possibly with shared ownership (through other std::shared_ptrs), and possibly with shared use (through weak_ptrs).
std::weak_ptr = I don't own this object, I just use it.
Regular raw pointer '*' = I don't own this object, I just use it (only use if the pointer's lifetime is garunteed to be longer than the class containing it)

Smart pointers solve most the things you are complaining about. They declare the intent of ownership and usage, explicitly state the lifetime of the object, delete the object instantly (not seconds later), with far less risk than manual management, and keep things compact in terms of memory usage, without large performance hits.
There is still place for resource manager classes, and sometimes in a performance critical area, you still need to use raw pointers. But I certainly don't think smart pointers are an anti-pattern, unless misused.

If you want assertions instead of exceptions, that's something you can easily do on your own: assert(!myWeakPtr.expired())

Unique pointers are a type of smart pointers.

The topic was about garbage collectors, and typically garbage collectors thread pointers as shared pointers. While unique pointers are also a type of smart pointers, they are significantly different then what garbage collectors do. So I specifically meant shared pointers when I was talking about it being an antipattern, as in most cases there is no such thing as shared ownership.

Smart pointers solve most the things you are complaining about. They declare the intent of ownership and usage, explicitly state the lifetime of the object, delete the object instantly (not seconds later), with far less risk than manual management, and keep things compact in terms of memory usage, without large performance hits.

I'm afraid you misunderstood the situation I was explaining. Those three type of smart pointers you mentioned (unique, shared and weak) are exactly the ones the lack the ability to maintain the class invariant when object B needs to have a reference to object A, but doesn't own it. Neither shared pointer (as B doesn't have ownership, not even shared ownership) or weak pointer (as these can expire, which according to the class invariant is not allowed) make this kind of relationship possible. Of course you can use a weak_ptr in B to A here, and assert if B wants to use the pointer but it's no longer there, but it's a pain in the ass to debug an assertion that triggers any given time after the class invariant was broken. Preferably you assert at the moment this happens, so at the moment A is deleted while there are still non-owning references to this A that cannot exist in a valid state without this reference.

So personally, I would make a difference between ownership (99% of the cases non-transferable and non-shared), weak references (that automatically turn to null if object is destroyed) and hard references (for objects that cannot exist without the object pointed to, but neither own it). This would be a much more powerful system then garbage collectors can offer, with immediate assertion on fatal errors rather then continuing with one or more objects in invalid state for some time until it crashes or starts displaying undefined behaviour. Which from experience I can tell is extremely painful to debug as there is no callstack going back to when the problem really happened if it may even have happened minutes ago.

I shy away from using any kind of GC system in C++ projects, for the same reason that I shy away from all the nifty Boost features: When I need the facilities of a higher level language, I prefer to use a higher level language. ;)

What is the problem you are trying to solve with garbage collection? Are you trying to deal with cross-object references and lifetime management?

Even if you go with garbage collection, you should still avoid run-time allocations and explicitly run the garbage collector at load-time or whenever you can hide the massive frame spike you will get.

Personally I found that if the engine provides a framework in which every game object or objects of a specific system are centrally managed its easier to keep track of allocated memory and avoid leaks.
For instance, I have a render system (abstracted from any other functionality of the engine, it just knows how to render stuff) that you register all your graphic objects to, when the system is requested to shutdown or clear its contents (to change scenes or something like that) it will take the responsibility of deleting any graphic content registered to it.


The biggest advantage of smartpointers in my opinion is that you are guaranteed not to leave invalid pointers around when you do delete the object. If the likelyhood of that is very high for certain objects, smartpointers are a worthwhile solution.
Most of these problems however are avoided by being clean and organized when designing code (something that sometimes and for the peril of the programmers is skipped altogether) and having well defined interfaces to steer the users of a given code towards the right behavior.

What is the problem you are trying to solve with garbage collection? Are you trying to deal with cross-object references and lifetime management?

Even if you go with garbage collection, you should still avoid run-time allocations and explicitly run the garbage collector at load-time or whenever you can hide the massive frame spike you will get.

My main interest in GC is related to RTS-type games. I'm experimenting with different ways to reach a good balance between game performance and resource management. The suggestion of smart pointers is definitely interesting and I'm probing that scenario.

In the RTS genre, you constantly have dynamic objects being created and destroyed. The main thing I'm trying to work out is this:

Would a single sweep to collect a large amount of destroyed units be more efficient than interrupting the gameflow in order to destroy each individual unit as it is no longer in the game? Think of multiplayer RTS battles like Supreme Commander or Total Annihilation where you can literally have 100+ units being destroyed within the span of "seconds" (vs "minutes"). Interrupt game logic to destroy each unit individually as it becomes unreferenced or sweep occasionally to destroy several unreferenced units?

For something like a unit in an RTS, there's a definite point where it's no longer required -- when it's been destroyed (by damage, etc).
A GC will actually get in the way of this. For example, let's say upon creating a unit, it's added to a list of "player 1's units". One of player 2's tanks then targets our new unit. The unit then self destructs and is removed from the "player 1's units" list, however, it's not yet garbage, because player 2's tank still contains a "target" reference to it, so it's not freed.

Strong/weak smart-pointers do work though -- if the "player 1's units" list contains strong pointers, but the tank's "target" link is a weak pointer, then when the unit self-destructs and removes itself from the "player 1's units" list, then the tank's "target" will be set to null automatically, and the unit freed.

As for the cost of creating/deleting units - this should be almost completely cost-free. Either creating or destroying an instance of a unit shouldn't contain much code. If you're making a lot of fixed-size allocations, then a pool allocator will work very well, and is often used for things like projectiles or 'monsters' in games that are created/destroyed often.

Mostly In game is object memory pool, or directly allocate and delete by their manager!
I think this way will make game more flexible and efficiency.

I don't use garbage collection. Garbage collections and such cause too many hassles and inefficiencies. I like absolute control of the memory I'm using. Allocation and freeing can get deep into problems with fragmentation, cache issues and more.

One thing I like to do, for example, is reuse already allocated memory when it's not being used. This can increase performance of dynamic objects significantly and if it's using certain methods you can push fragmentation out of your mind forever.

I'd actually suggest smart pointers.

I second that. You can use reference counting to destroy object instances when nothing holds a reference an object any longer. You can also hook up your reference count system so that the count is decremented when a smart-pointer falls out of scope... the result: automatic disposal. If you're up for a challenge and know what you're doing you can even override C++'s new and delete operators so that you can allocate all objects to a custom, managed heap; but you will need to implement heap defragmentation, optimized memory copy/move algorithms and quite a few other things. I can be done but is hard... however, the end-result can be a spectacular and efficient memory management system.

Just to demonstrate what I'm talking about:

[source lang="cpp"]void f()
{
SmartPtr pCarModel = somePtr;

// do stuff with the car model...

pCarModel->ReleaseRef( );
}[/source]

Edit:
@ATC: Damn! Ninja'd! I should have read the whole thread.

Original:

For handling instances where a unit references another unit, I.E. it's target that it is firing at, I would have a shared_ptr list of the entities in an entity factory or I would have a shared_ptr list of the entities in a factory and then a weak_ptr list of those same entities pointing to the shared_ptr entities in a target aquisition class.

Then get a weak_ptr to the object, so that we can test if it exists or not before we use it in the A.I. procedure of the thing that is targeting it.

This isn't really GC, but it's a safe way of handling inter-entity coupling that will not lead to dead pointers floating around. And I think it's a good example of the use of the weak_ptr.

A shared_ptr isn't necessarily for shared resources, it's what you use to hold a pointer to any dynamically allocated object where the dynamically allocated object exists at least for the lifetime of the object that is owning it.
weak_ptr exists to get rid of pointers that are pointing to deleted data.

And that's about what I know on the topic. I've never had the need to use unique_ptr, it's not bad or anything, it's just a tool to fit a design pattern of preventing more than 1 object from holding onto 1 value that I haven't had the need for as I don't program strict classes like that.



class EntityFactory {

std::weak_ptr<Entity> GetEntity( /* name, position, targeting data */ );

protected:
// Use a map or an oct tree depending upon your situation
std::vector<std::shared_ptr<Entity>> entities;
};

class Tank : public Entity {

void FireAtTarget() {
if( std::shared_ptr<Entity> shared_target = target.lock() ) {
// We now have a reference to target, fire at it
// maybe test if target is dead and then unset target
} else {
// Target has been destroyed, release the reference to it, or find a new target
std::weak_ptr<Entity> novalue;
target = novalue;
}
}
protected:
std::weak_ptr<Entity> target;
};



With shared_ptr and weak_ptr I don't really see the need for GC. And in addition, for things like particle systems you should be using statically allocated memory to handle those so you don't have the alloc/dealloc overhead. Like the following:



class Particle {
public:
// call ParticleAllocator::GetInstance()->CreateParticle() to get the memory for this particle
void* operator new(size_t);
// call ParticleAllocator::GetInstance()->DeleteParticle(p) to free the memory for this particle
void operator delete(void*);
};

class ParticleAllocator {
ParticleAllocator() {
hInstance = this;
for( unsigned int i = 0; i < max_particles; i++ ) {
dead_particles.push_back( &particle_memory );
}
}
void DeleteParticle(Particle* p) {
dead_particles.push_back( p );
}
Particle* CreateParticle() {
vector<Particle*>::iterator it = dead_particles.begin();
if( it != dead_particles.end() ) {
dead_particles.erase(it);
return *it;
} else {
// We have no more particles we can use
return NULL;
}
}

static ParticleAllocator* GetInstance() { return hInstance; }
protected:
static ParticleAllocator* hInstance;

Particle particle_memory[max_particles];
vector<Particle*> dead_particles;
};



This isn't really a great example of a particle system since batch rendering can't really be done with it, you might need to change it up for that but it's a good example of using statically allocated memory for dynamic objects. As a rule of thumb you want to use statically allocated memory for any dynamic object that has a short lifetime. For objects that have longer lifetimes, statically allocating memory doesn't really have much of an advantage since you end up wasting memory to ensure you have enough static allocations to meet you needs and if you're too conservative with your budget of memory for those objects you end up having bugs that arise from not having enough objects to allocate to every so often with one system or another.

As to GC.

In languages that have garbage collection generally they work by every variable in the game being passed by reference, essentially every object is stored as a shared_ptr in C++ 11 terms. And then there is a garbage collector that watches the references and deletes an object when there are no more references to it.

C# Example


// Object with value 5 created
Object myobj = Object(5)
// Object with value 6 created, object value with 5 is no longer referenced
myint = Object(6);

// Some time later: Object with value 5 is destroyed.



C++ Example


// Object with value 5 created
shared_ptr<Object> my_object = shared_ptr<Object>( new Object(5) );
// Object with value 6 created
// We do not need to delete Object(5), because it has it's reference count set to zero in the following code, it is immediately deleted.
my_object = shared_ptr<Object>( new Object(6) );


So what the shared_ptr gives you is the same sort of memory behavior of higher level languages, but much more immediately. Instead of using a GC.