How to handle many updating objects efficiently in C#?

Question

I'm developing a 2D overhead shooter game using C# and XNA. I have a class that I'll call "bullet" and need to update many of these instances every fraction of a second.

My first way to do this was to have a generic List of bullets and simply remove and add new bullets as needed. But in doing so the GC kicks in often and my game had some periodic jerky lag. (Alot of code cut out, but just wanted to show a simple snippet)

if (triggerButton)
{
    bullets.Add(new bullet());
}
if (bulletDestroyed)
{
    bullets.Remove(bullet);
}

My second and current attempt is to have a separate generic Stack of bullets that I push to when I'm done with a bullet, and pop off a bullet when I need a new one if there's anything in the stack. If there's nothing in the stack then I add a new bullet to the list. It seems to cut the jerky lag but then again, sometimes there's still some jerky lag springing up (though I don't know if it's related).

if (triggerButton)
{
    if (bulletStack.Count > 0)
    {
        bullet temp = bulletStack.Pop();
        temp.resetPosition();
        bullets.Add(temp);
    }
    else
    {
        bullets.Add(new bullet());
    }
}
if (bulletDestroyed)
{
    bulletStack.Push(bullet);
    bullets.Remove(bullet);
}

So, I know premature optimization is the root of all evil, but this was very noticeable inefficiency that I could catch early (and this was before even having to worry about enemy bullets filling the screen). So my questions are: Will pushing unused objects to a stack invoke the garbage collection? Will the references by kept alive or are objects still being destroyed? Is there a better way to handle updating many different objects? For instance, am I getting too fancy? Would it be fine to just iterate through the list and find an unused bullet that way?

Answer 1

There are a lot of issues here, and it's tricky to tell.

First off, is bullet a struct or a class? If bullet is a class, any time you construct one, then unroot it (let it go out of scope or set it to null), you're going to be adding something the GC needs to collection.

If you're going to be making many of these, and updating them every frame, you may want to consider using a List<bullet> with bullet being a struct, and the List being pre-allocated (generate it with a size large enough to hold all of your bullets, so it's not being recreated as you call List.Add). This will help dramatically with the GC pressure.

Also, just because I need to rant:

So, I know premature optimization is the root of all evil, but this was very noticeable inefficiency

Never, ever, be afraid to optimize a routine that you know is causing problems. If you're seeing a performance issue (ie: your lags), this is no longer premature optimization. Yes, you don't want to be optimizing every line of code, but you do need to optimize code, especially when you see a real performance issue. Optimizing it as soon as you see it's a problem is much easier than trying to optimize it later, as any design changes required will be much more easily implemented before you've added a lot of other code that uses your bullet class.

Answer 2

You may find the flyweight design pattern useful. There need be only one bullet object, but multiple flyweights may specify different positions and velocities for it. The flyweights can be stored in a preallocated array (say, 100) and flagged as active or not.

That should eliminate garbage-collection completely, and may reduce the space necessary for tracking each bullet's malleable properties.

Answer 3

I will admit that I don't have any experience in this per se, but I would consider using a traditional array. Initialize the array to a size that is more then you need, and would be the theoretical maximum number of bullets, say 100. Then starting at 0 assign the bullets at the beginning of the array, leaving the last element as a null. So if you had four active bullets your array would look like:

0 B 1 B 2 B 3 B 4 null ... 99 null

The benefit is that the array would always be allocated and therefore you are not dealing with the overhead of a more complex data structure. This is actually fairly similar to how strings work, since they are actually char[] with a null terminator.

Might be worth a shot. One downside, you'll have to do some manual manipulation when removing a bullet, probably move everything after that bullet up a slot. But you are just moving pointers at that point, so I don't think it would have a high penalty like allocating memory or a GC.

Answer 4

You are correct in assuming that by keeping the unused Bullets in a Stack prevents them from being Garbage Collected.

As for the cause of the Lag, have you tried any profiling tools? Just to find where the problem is.