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.
