Brian - July 17th, 2010 - Recycle Array
When I was writing Word Duelist, I was scrambling for a way to improve performance and reduce garbage generation. One area where this was prominent was the particle system, a system which would repeatedly generate lots of light-weight objects and discard them soon after.
After doing a little research, I stumbled upon a handy little data structure that works like the following:
Creation: Create a fixed pool of memory (with a maximum size) with pre-allocated 'dummy' objects.
Addition: Get an item from the next free spot in the pool and let the caller fill that item out appropriately. One important side-effect is this may involve exposing more of your object than you'd like since you won't be using the constructor again.
Removal: Swap the item to be removed with the last valid item in the array and decrement the size.
The data structure has the following characteristics:
(1) All memory is allocated up-front.
(2) O(1) item "addition"
(3) O(1) item removal
(4) O(N) search, O(1) random access
(5) No garbage generation. We're working with a fixed pool where items don't actually get deallocated until the array is destroyed.
(6) Unstable - the order of the objects will change
#6 is worth mentioning - the data structure does not provide any guarantee that the order you add items will be the order those items are in at any time. Thus, this is best used for something where you don't care about the order, like a particle system.
Here's a (admittedly rough) mockup implementation:
Just something I slapped together in 20 minutes, so there's clearly room for improvement. If someone has a better name than "Recycle Array" I'd be happy to change it - I'm not terribly happy with the name.
Found some awesome games in the XBLIG playtest queue.
July 25th, 2010 at 8:45 pm
Hey, Nice article. I think the term you are looking for in that last paragraph is ‘Resource Pool’ and it’s quite a common approach for reducing garbage collection.
July 26th, 2010 at 5:18 am
Thanks.
I think it serves the function of a resource pool, but then, a lot of other data structures can be used for that too (ring buffer, standard array with ‘IsAlive’ flags). With the name, I wanted to highlight that this is meant to be a container that stores items, not just a pool from which you grab new items.
Recycle Array is still a rubbish name.
I’m leaning more toward UnorderedPool or UnorderedArray these days.