Massive amount of object creation in C++

Question

Is there any pattern how to deal with a lot of object instantiations (40k per second) on a mobile device? I need these objects separately and they cannot be combined. A reusage of objects would probably be a solution. Any hints?

Answer 1

Yes. Keep old objects in a pool and re-use them, if you can. You will save massive amounts of time due to the cost of memory allocation and deletion.

Answer 2

If the objects are all the same size, try a simple cell allocator with an intrusive linked list of free nodes:

free:
    add node to head of list

allocate:
    if list is non-empty:
        remove the head of the list and return it
    else:
        allocate a large block of memory
        split it into cells of the required size
        add all but one of them to the free list
        return the other one

If allocation and freeing are all done in a single thread, then you don't need any synchronisation. If they're done in different threads, then possibly 40k context switches per second is a bigger worry than 40k allocations per second ;-)

You can make the cells be just "raw memory" (and either use placement new or overload operator new for your class), or else keep the objects initialized at all times, even when they're on the "free list", and assign whatever values you need to the members of "new" ones. Which you do depends how expensive initialization is, and probably is the technical difference between a cell allocator and an object pool.

Answer 3

Hard to say exactly how to improve your code without more information, but you probably want to check out the Boost Pool libraries. They all provide different ways of quickly allocating memory for different, specific use cases. Choose the one that fits your use case best.

Answer 4

If the objects are the same size, you can allocate a large chunk of memory and use placement new, that will help with the allocate cost as it will all be in contiguous memory:

Object *pool = malloc( sizeof(Object) * numberOfObjects );
for(int i=0; i<numberOfObjects; i++)
    new (&pool[i]) Object()  

Answer 5

I think you could consider these design patterns:

• Object Pool
• Factory

Further info

I hope this help you too: Object Pooling for Generic C++ classes

Answer 6

I've used similar patterns for programming stochastic reaction-diffusion systems (millions of object creations per second on a desktop computer) and for real-time image processing (again, hundreds of thousands or millions per second).

The basic idea is as follows:

• Create an allocator that allocates large arrays of your desired object; require that this object have a "next" pointer (I usually create a template that wraps the object with a next pointer).
• Every time you need an object, get one from this allocator (using the new-syntax that initializes from the block of memory you call).
• Every time you're done, give it back to the allocator and place it on a stack.
• The allocator gives you something off the stack if the stack is nonempty, or something from its array buffer otherwise. If you run out of buffer, you can either allocate another larger buffer and copy the existing used nodes, or have the allocator maintain a stack of fully-used allocation blocks.
• When you are done with all the objects, delete the allocator. Side benefit: you don't need to be sure to free each individual object; they'll all go away. Side cost: you'd better be sure to allocate anything you want to preserve forever on the heap instead of in this temporary buffer (or have a permanent buffer you use).

I generally get performance about 10x better than raw malloc/new when using this approach.

Answer 7

You might be able to use the flyweight pattern if your objects are redundant. This pattern shares memory amongst similar objects. The classical example is the data structure used for graphical representation of characters in a word processing program.

Wikipedia has a summary.

There is an implementation in boost.