Sunday, June 3, 2007

A Generic Pool Collection Class

I originally intended to write this article for Ziggy's XNA Article Contest. Unfortunately, real life got in the way in the form of a few weeks of crunch-time at work followed by a much-needed (and fabulous) vacation in Paris. Between those things and spending the little free time I had last month on my Dream-Build-Play entry (and not as much time on that as I'd have liked), I didn't get the article finished in time for his deadline. He received some great entries, though, so if you haven't already, head over there to read them. My favorites are the two HLSL articles by Jamezilla, one on Bloom/Blur Post-Processing and the other on Shockwave Distortion; and the article on Bezier Curves by Cubed2D. But all of the entries are worth a read.

EDIT: It looks like just as I was posting this entry, Ziggy was announcing the contest winner. Congrats to KrisC for his article on Graphic User Interfaces in XNA!

Resource Pools

Games need to be able to maintain collections of various types of resources, including such things as projectiles, particles, enemies, etc. Most non-game .NET applications would simply allocate such resources dynamically and then let the garbage collector dispose of them when they are no longer needed. Unfortunately, dynamic memory allocation and deallocation can, and will, cause slowdowns at indeterminable times. For games, or any real-time software, this is obviously unacceptable. As a game programmer, you need to be in control of when resource allocation and deallocation occurs and how long it takes.

The solution to this is to create resource pools where all of the memory for each resource type is allocated up-front during the game's initialization. When a resource is needed, an available item can be removed from that resource type's pool. When the resource is no longer needed, it can be returned to the pool.

Because a resource pool is a group of objects of the same type that has a fixed size, they are almost always implemented as an array. However a resource pool also has to keep track of which objects are currently being used, and there are multiple ways to do that. One way is to simply add a field in the resource class that specifies whether that particular object is active. The problem with that approach is that you have to rewrite code to manage each particular resource's pool. That is, you'll need separate code to manage your projectile pool and your particle pool, even though the code is doing basically the same thing. You could get around this "block copy" approach by having a parent class that maintains the active flag and contains the methods used to get a free object from the pool, update the active objects in the pool, reset the pool, etc. But that requires that all of your resource classes inherit from that parent, which isn't always desirable (and sometimes may not even be possible).

The most flexible approach is to have a generic Pool class, similar to the other .NET generic collections, that handles the maintenance of resource pools and can hold any type of object. In this article, we'll look at an efficient implementation of a Pool class and how to use it for a variety of different resource types.

Along the way, I'll describe some of the design decisions and trade-offs that go into writing generic classes. However, this is not intended to be a tutorial on writing C# generics. If that's what you are looking for, I recommend first reading a good book or online tutorial that covers the topic.

Desired Features of a Generic Pool

The following features are required for our Pool class to be useful.

Get — Takes a free item from the pool and marks it as active.

Return — Returns an active item to the pool and marks it as available.

Clear — Returns all active items to the pool and makes them all available.

Capacity — Gets the total number of items in the pool, both available and active.

AvailableCount — Gets the total number of available items in the pool. This is necessary to ensure the user doesn't attempt to Get more than the available number of objects. Therefore any call to Get should be preceeded by a test to ensure there are objects available.

ActiveCount — Gets the total number of active items in the pool.

CopyTo — Copies all of the active objects in the pool to a one-dimensional array. This is needed so that a resource pool can hold vertex data which can be easily copied to an array for passing to the GPU.

GetEnumerator — Gets an enumerator that can iterate over the pool's active items.

AllNodes — Gets an enumerator that can iterate over all of the items in the pool, active and inactive. This can be useful if there is one-time initialization that needs to be performed on all of the resource objects in a pool before they are ever used. Generally, however, after initialization, users should only be accessing active objects.

efficiency — Because resources such as particles and projectiles are generally being allocated and returned many times per frame, the pool class must be as efficient as possible. Where possible, all methods should be constant time — O(1) — and none should be worse than linear — O(n).

encapsulation — The implementation details should be hidden from the user as much as possible. In particular, the user should not have direct access to the active flag which should be modified only by the Pool class itself.

ease-of-use — The class should put as few restrictions on the user as possible so that it can be used as easily as other collection classes. In particular, it should have very little restriction on the types of objects that it can hold.

Implementation

To meet the efficiency requirements, the Pool class is implemented as an array along with a Queue containing the available (non-active) objects. By maintaining the list of available objects as a queue, the Get and Return methods can be O(1).

To meet the encapsulation requirements, the pool array is not an array of the objects being held by the pool, but an array of a Node struct. Each node contains the item being stored in the Pool along with the index of that item in the array. Because the node has to be given to the user so that it can be returned to the pool when the user is finished with it, the active flag is not stored in the node itself. If it were, the user would have direct access to it and could change it themselves, which we want to avoid. Instead, there is a separate array of booleans whose elements correspond to the elements in the pool array. Thus the NodeIndex field in the Node struct provides the index into both the pool array and the active array.

Finally, the ease-of-use requirements are mostly met by virtue of the class being implemented as a generic. As mentioned earlier, this removes the limitation of having a parent class for all resources that are to be stored in pools. However, since we are storing the actual resource objects inside Node structs, we need to be able to allocate each one when we create the nodes in the array. This means we have to limit resources to types that have a public, parameterless constructor. In other words, you can't store basic data types such as ints, floats, etc., inside a Pool. Since this Pool class is intended for holding resources that are more complicated than the basic data types, that restriction shouldn't be a problem.

The use of nodes when getting and returning pool elements is another design trade-off that slightly limits ease-of-use, in that the user has to deal with another data structure besides the one they want to store in the pool. To remove the slight burden this presents, the iterator returned by the GetEnumerator method provides direct access to the resource objects rather than nodes. Another enumerator is provided by the ActiveNodes property which can be used to iterate through nodes. This gives the user the flexibility to access active resource objects directly, or to access nodes for times when they may need to return an item to the pool. In general, I'd recommend using the ActiveNodes property inside an Update method, where the update may cause the resource to be finished and need to be returned to the pool; and the GetEnumerator property inside a Draw method, where you just want to go through all of the active resources and draw them.

The other disadvantage of storing the resource objects inside Node structs in this way, is that for value types (structs) stored in a pool, the user will only ever get a copy of the object instead of having direct access to it. That means that when using a Pool of a struct type, setting the node's Item field doesn't change the value of the item in the pool. To get around this problem, the SetItemValue method is provided to update the value of a given node in the pool.

Using the Pool Collection

Hopefully the comments provided with the class are fairly self-explanatory. The following subsections provide an overview of how to use the class.

Initialization

To use a Pool collection, all you have to do is construct it with the number of elements to be stored, generally at program initialization. This number of elements in the pool should be more than you will likely need, but not many more. It may require some tweaking to get that number just right for each specific use but generally you should have a pretty good idea of how many elements you need based on the design of your game and how many of each projectile, particle, etc. are likely to be active.

class Missile { private Vector2 position; private Vector2 velocity; private int configValue; public Missile() { } public void Init(int configValue) { this.configValue = configValue; } public void Fire(Vector2 position, Vector2 heading) { this.position = position; this.heading = heading; } public bool Update() { // Move missile, etc. ... // See if missile is finished if (reachedMaxDistance) { return false; } return true; } public bool Collided(Rectangle otherObject) { if (otherObject.Intersect(position)) { return true; } return false; } public void Draw() { // Draw missile ... } } public Pool missilePool; public void Init() { missilePool = new Pool<Missile>(MaxMissiles); // If there is any one-time initialization of all // resources, it can be done here. Generally, // though, this shouldn't be needed. foreach (Pool<Missile>.Node missile in missilePool.AllNodes) { missile.Init(ConfigValue); } }

Update

During the update portion of each frame, you will get items from the pool if needed, update all active items, and return items that are no longer needed.

public void Update() { // See if the user has fired a missile // (and verify there are some left in the pool) if (MissileFired && missilePool.AvailableCount > 0) { // Get a missile from the pool. Missile missile = missilePool.Get().Item; // Initialize the missile's position and velocity. missile.Fire(player.Position, player.Heading); } foreach (Pool<Missile>.Node node in missilePool.ActiveNodes) { if (!node.Item.Update()) { // If something happened during its Update to // make the missile no longer active, return // it to the pool. missilePool.Return(node); } else { // Note that if Missile was a struct instead // of a class, you would have to do the // following here: // missilePool.SetItemValue(node); // Loop through objects it might hit. foreach (GameObject item in ActiveObjects) { if (node.Item.Collided( item.BoundingRectangle)) { missilePool.Return(node); } } } } }

Draw

During the draw portion of each frame, you will get items from the pool if needed, update all active items, and return items that are no longer needed.

public void Draw() { // Draw each active missile foreach (Missile missile in missilePool) { missile.Draw(); } }

XNA Creator's Club Particle Sample

To provide a more complete example of using the Pool collection, I've modified Microsoft's XNA Creator's Club Particle Sample. The only changes from the original are the inclusion of the Pool class itself, in Pool.cs; and modifications to the ParticleSystem class, in ParticleSystem.cs. All changes have been marked with conditional compilation instructions (#if USE_POOL_CLASS) to make it easy to compare the original code with the new code.

Pool Collection Class

You can download the source file here.

17 comments:

Andrew said...

Very very nice article!! Yeah, pools are great! My pooling system isn't as efficient as yours. You certainly gave me some ideas. Thanks

Andrew said...

Dude.. it seems the html is eating up your code a bit.. All the generics have been lost :( At first I was confused and thought perhaps you just had untested code ;)

thomas h aylesworth said...

Thanks for the comments, Andrew. But I'm confused by your statement about "the generics have been lost." Did you download the source?

Pool.cs

If you're having problems downloading that, or if you can be more specific about the problem you are having, please let me know!

Thanks,

Tom

Anonymous said...

the source is fine. he just means on the web page it's missing all of the < and >'s so the creation of the Pool didn't look like it was a generic. I was confused by that at first as well. Thanks for sharing :D

thomas h aylesworth said...

Whoops! Thanks for pointing that out. It should be fixed now.

Moped said...

I don't think this implementation will work with value types.

Moped said...

Nevermind. :)

Moped said...

Your code is great; it's very readable and well thought out. Have you thought about default-constructing items on demand, rather than in the constructor? It'll rid your constructor of the loop. I extended your code a little:

lock(sync)
{
if(active.Count == capacity)
{
throw new InvalidOperationException(
"All pool items active");
}

T item = (available.Count == 0) ?
default(T) : available.Dequeue();
Debug.Assert(item != null, "Dequeued null item");

active.Add(item);

return item;
}

Moped said...

Alright, last comment, I promise. In the snippet above, it should be "new T()", not "default(T)".

thomas h aylesworth said...

Thanks for the comments, IronMoped. I'm glad you find the class useful!

The reason for initializing the pool items in the constructor is that time spent during initialization isn't as important as time spent in the game loop. For the same reason, it's preferable to dynamically allocate everything during initialization instead of during the game loop.

roni schuetz said...

your code is great but I missing the part of Multi Thread awareness - or do I missunderstand here something?

Anonymous said...

To avoid the problem with structs returning a copy, couldn't you use a dictionary in place of the node system? It would require replacing "pool" with a Dictionary<int,T> and "active" with a Dictionary<int,bool>, and using GetHashCode for objects in order to index them. The class retains its generic quality and decoupling from the objects it is managing, but also removes the ugliness brought forth by the node setup.

Unknown said...

Dictionaries can create a lot of garbage, be careful

Anonymous said...

Using enumerators, generated by foreach causes allocations at run-time --> problems with GC --> you shouldn't use it

thomas h aylesworth said...

Because the Node type used by my Pool class is a value type, neither the use of a Dictionary nor the foreach enumerator create any excess garbage. I have verified this using the CLR Profiler, and have used this class in games that iterate through thousands of objects per frame without any problems with garbage collection.

For some good articles on how to use collections and foreach without putting a strain on the garbage collector, see Foreach, Garbage, and the CLR Profiler on the Cornflower Blue blog as well as Shawn Hargreave's post Twin paths to garbage collection nirvana.

Shawn's post recommends my generic pool class as the right way to handle this very problem.

Hernan Zaldivar said...

Great solution Thomas!! download links seem to be broken, can u upload them to somewhere else please?

THANKS! greetings from Argentina
HERNAN

Hernan Zaldivar said...

I have a question, if I have 3 types of enemies (FastEnemy, NormalEnemy and SlowEnemy) that inherits from a base class Enemy, can I create only one repository o should I create 3 repository, one for each type of enemy?

THANKS!