# Dynamic Memory Allocation and Memory Management

In an average game, there are hundreds or maybe thousands of objects in the scene. Is it completely correct to allocate memory for all objects, including gun shots (bullets), dynamically via default new()?

Should I create any memory pool for dynamic allocation, or is there no need to bother with this? What if the target platform are mobile devices?

Is there a need for a memory manager in a mobile game, please? Thank you.

Language Used: C++; Currently developed under Windows, but planned to be ported later.

• Which language? – Kylotan Feb 6 '11 at 22:07
• @Kylotan: the language used: C++ currently developed under Windows but planned to be ported later. – Bunkai.Satori Feb 6 '11 at 23:00

In an average game, there are hundreds or maybe thousands of obects in the scene. Is it completely correct to allocate memory for all objects, includiding gun shots(bullets), dynamically via default new()?

That really depends what you mean by "correct." If you take the term quite literally (and ignore any concept of correctness of the implied design) then yes, it is perfectly acceptable. Your program will compile and run fine.

It may perform sub-optimally, but it still may also perform well enough to be a shippable, fun game.

Should I create any memory pool for dynamic allocation, or is there no need to bother with this? What if the target platform are mobile devices?

Profile and see. In C++, for example, dynamically allocation on the heap is usually a "slow" operation (in that it involves walking through the heap looking for a block of appropriate size). In C#, it's usually an extremely fast operation because it involves little more than an increment. Different language implementations have different performance characteristics with respect to memory allocation, fragmentation upon release, et cetera.

Implementing a memory pooling system can certainly bring about performance gains -- and since mobile systems are usually underpowered relative to desktop systems, you may see more of a gain on a particular mobile platform than you would on a desktop. But again, you'd have to profile and see -- if, currently, your game is slow but memory allocation/release doesn't show up on the profiler as a hot spot, implementing infrastructure to optimize memory allocation and access probably won't get you much bang for your buck.

Is there a need for a memory manager in a mobile game, please? Thank you.

Again, profile and see. Is your game running fine now? Then you may not need to worry.

All of that cautionary-speak aside, using dynamic allocation for everything isn't strictly speaking necessary and so it can be advantageous to avoid it -- both because of the potential performance gains, and because allocating memory that you need to track and eventually release means you have to track and eventually release it, possibly complicating your code.

In particular, in your original example you cited "bullets," which tend to be something that get created and destroyed frequently -- because many games involve lots of bullets, and bullets move fast and thus reach the end of their lifetime quickly (and often violently!). So implementing a pool allocator for them and objects like them (such as particles in a particle system) can usually result in efficiency gains and would likely be the first place to start looking at using pool allocation.

I am unclear if you are considering a memory pool implementation to be distinct from a "memory manager" -- a memory pool is a relatively well-defined concept, so I can say with some certainty that they can be a benefit if you implement them. A "memory manager" is a bit more vague in terms of its responsibility, so I would have to say that whether or not one is required depends on what you think that "memory manager" would do.

For example if you consider a memory manager to be a thing that just intercepts calls to new/delete/free/malloc/whatever and provides diagnostics on how much memory you allocate, what you leak, et cetera -- then that can be a useful tool for the game while it's in development to help you debug leaks and tune your optimal memory pool sizes, and so on.

• Agreed. Code in a way that allows you to change things later. If in doubt, benchmark or profile. – axel22 Feb 6 '11 at 19:59
• @ Josh: +1 for excellent answer. What I would probably need to have is a combination of dynamic allocation, static allocation, and memory pools. However, the performance of the game will guide me in the proper mix of those three. This is clear candidate for the Accepted Answer for my question. However, I would like to keep the question open for a while, to see what others will contribute. – Bunkai.Satori Feb 6 '11 at 20:03
• +1. Excellent elaboration. The answer to almost every performance question is always "profile and see". Hardware is too complex these days to reason about performance from first principles. You need data. – munificent Feb 6 '11 at 23:05
• @Munificent: thanks for your comment. So the goal is making up the game working and stalbe. There is no need to worry too much about performance in the middle of the development. It all can and will be fixed after game completion. – Bunkai.Satori Feb 6 '11 at 23:31
• I think this is an unfair representation of C#'s allocation time- for example, every C# allocation also includes a sync block, the allocation of Object, etc. In addition, the heap in C++ requires modification only when allocating and freeing, whereas C# requires collections. – DeadMG Feb 7 '11 at 0:48

I don't have much to add to Josh's excellent answer, but I'll comment on this:

Should I create any memory pool for dynamic allocation, or is there no need to bother with this?

There is a middle ground between memory pools and calling new on each allocation. For example, you can allocate a set number of objects in an array, then set a flag on them to 'destroy' them later. When you need to allocate more, you can overwrite the ones with the destroyed flag set. This kind of thing is only slightly more complex to use than new/delete (as you would have 2 new functions for that purpose) but is simple to write and can give you big gains.

• +1 for nice addition. Yes, you are correct, that is a good way on managing simpler game elements such as: bullets, particles, effects. Especially for those, there would be no need to allocate memory dynamically. – Bunkai.Satori Feb 6 '11 at 22:28

Is it completely correct to allocate memory for all objects, including gun shots (bullets), dynamically via default new()?

No, of course not. No memory allocation is correct for all objects. operator new() is for dynamic allocation, that is, it is appropriate only if you need the allocation to be dynamic, either because the object's lifetime is dynamic or because the type of the object is dynamic. If the type and lifetime of the object are known statically, you should allocate it statically.

Of course, the more information you have about your allocation patterns, the faster these allocations can be made via specialist allocators, such as object pools. But, these are optimizations and you should only make them if they're known to be necessary.

• +1 for good answer. So to generalize, the correct approach would be: in the beginning of development, to plan, which objects can be allocated statically. During development, to allocate dynamically only those objects that absolutely have to be allocated dynamically. At the end, to profile, and adjust possible memory allocation performance issues. – Bunkai.Satori Feb 7 '11 at 8:34

Kind of echoing Kylotan's suggestion but I would recommend solving this at the data structure level when possible, not at the lower allocator level if you can help it.

Here's a simple example of how you can avoid allocating and freeing Foos repeatedly using an array with holes with elements linked together (solving this at a "container" level instead of an "allocator" level):

struct FooNode
{
explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

// Stores a 'Foo'.
Foo element;

// Points to the next foo available; either the
// next used foo or the next deleted foo. Can
// use SoA and hoist this out if Foo doesn't
// have 32-bit alignment.
int next;
};

struct Foos
{
// Stores all the Foo nodes.
vector<FooNode> nodes;

// Points to the first used node.
int first_node;

// Points to the first free node.
int free_node;

Foos(): first_node(-1), free_node(-1)
{
}

const FooNode& operator[](int n) const
{
return data[n];
}

void insert(const Foo& element)
{
int index = free_node;
if (index != -1)
{
// If there's a free node available,
// pop it from the free list, overwrite it,
// and push it to the used list.
free_node = data[index].next;
data[index].next = first_node;
data[index].element = element;
first_node = index;
}
else
{
// If there's no free node available, add a
// new node and push it to the used list.
FooNode new_node(element);
new_node.next = first_node;
first_node = data.size() - 1;
data.push_back(new_node);
}
}

void erase(int n)
{
// If the node being removed is the first used
// node, pop it from the used list.
if (first_node == n)
first_node = data[n].next;

// Push the node to the free list.
data[n].next = free_node;
free_node = n;
}
};


Something to this effect: a singly-linked index list with a free list. The index links allow you to skip over removed elements, remove elements in constant-time, and also reclaim/reuse/overwrite free elements with constant-time insertion. To iterate through the structure, you do something like this:

for (int index = foos.first_node; index != -1; index = foos[index].next)
// do something with foos[index]


And you can generalize the above kind of "linked array of holes" data structure using templates, placement new and manual dtor invocation to avoid the requirement for copy assignment, make it invoke destructors when elements are removed, provide a forward iterator, etc. I chose to keep the example very C-like to more clearly illustrate the concept and also because I'm very lazy.

That said, this structure does tend to degrade in spatial locality after you remove and insert things a lot to/from the middle. At that point the next links could have you walking back and forth along the vector, reloading data formerly evicted from a cache line within the same sequential traversal (this is inevitable with any data structure or allocator that allows constant-time removal without shuffling elements while reclaiming spaces from the middle with constant-time insertion and without using something like a parallel bitset or a removed flag). To restore the cache-friendliness, you can implement a copy ctor and swap method like this:

Foos(const Foos& other)
{
for (int index = other.first_node; index != -1; index = other[index].next)
insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
nodes.swap(other.nodes):
std::swap(first_node, other.first_node);
std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);


Now the new version is cache-friendly again to traverse. Another method is store a separate list of indices into the structure and sort them periodically. Another is to use a bitset to indicate what indices are used. That will always have you traversing the bitset in sequential order (to do this efficiently, check 64-bits at a time e.g. using FFS/FFZ). The bitset is the most efficient and non-intrusive, requiring only a parallel bit per element to indicate which ones are used and which are removed instead of requiring 32-bit next indices, but the most time-consuming to write well (it won't be fast for traversal if you're checking one bit at a time -- you need FFS/FFZ to find a set or unset bit immediately among 32+ bits at a time to rapidly determine ranges of occupied indices).

This linked solution is generally the easiest to implement and non-intrusive (doesn't require modifying Foo to store some removed flag) which is helpful if you want to generalize this container to work with any data type if you don't mind that 32-bit overhead per element.

Should I create any memory pool for dynamic allocation, or is there no need to bother with this? What if the target platform are mobile devices?

need is a strong word and I'm biased working in very performance-critical areas like raytracing, image processing, particle simulations, and mesh processing, but it is relatively very expensive to be allocating and freeing teeny objects used for very light processing like bullets and particles individually against a general-purpose, variable-sized memory allocator. Given that you should be able to generalize the above data structure in a day or two to store anything you want, I think it'd be a worthwhile exchange to eliminate such heap allocation/deallocation costs outright from being paid for every single teeny thing. On top of reducing allocation/deallocation costs, you get better locality of reference traversing the results (fewer cache misses and page faults, i.e.).

As for what Josh mentioned about GC, I haven't studied C#'s GC implementation quite as closely as Java's, but GC allocators often have an initial allocation that's very fast because that's using a sequential allocator which can't free memory from the middle (almost like a stack, you can't delete things form the middle). Then it pays for the expensive costs to actually allow removing individual objects in a separate thread by copying memory and purging the formerly allocated memory as a whole (like destroying the entire stack at once while copying the data to something more like a linked structure), but because it's done in a separate thread, it doesn't necessarily stall your application's threads so much. However, that carries a very significant hidden cost of an additional level of indirection and the general loss of LOR after an initial GC cycle. It is another strategy to speeding up allocation though -- make it cheaper in the calling thread and then do the expensive work in another. For that you need two levels of indirection to reference your objects instead of one since they will end up getting shuffled in memory between the time you initially allocate and after a first cycle.

Another strategy in a similar vein that's a little easier to apply in C++ is just don't bother to free your objects in your main threads. Just keeping adding and adding and adding to the end of a data structure which doesn't allow removing things from the middle. However, mark those things that need to be removed. Then a separate thread could take care of the expensive work of creating a new data structure without the removed elements and then atomically swap the new one with the old one, e.g. Much of the cost of both allocating and freeing elements can be passed on to a separate thread if you can make the assumption that requesting to remove an element doesn't have to be satisfied immediately. That not only makes freeing cheaper as far as your threads are concerned but makes allocation cheaper, since you can use a much simpler and dumber data structure which never has to handle removal cases from the middle. It's like a container that only needs a push_back function for insertion, a clear function to remove all elements, and swap to swap contents with a new, compact container excluding removed elements; that's it as far as mutating goes.