The usual answer for this thing is to wait until you can measure if there’s a problem.

My experience has been that malloc() is rarely an issue, but perhaps I also do more CPU-intensive work than you do, so malloc() isn’t in the critical path.

Definitely some people are constrained by the malloc performance. See, for example, https://github.com/blog/1422-tcmalloc-and-mysql , where github switched to using TCMalloc for MySQL and got a 30% performance improvement. There’s more discussion at http://www.reddit.com/r/programming/comments/18zija/github_got_30_better_performance_using_tcmalloc/ .

TCMalloc is one of several malloc replacements. Another is jemalloc, and a third is nedmalloc.

So, if you think it’s a problem (eg, because profiling shows that you’re stuck in malloc/free often) then try one of those out and see if it improves things.

If it’s a concern now, then perhaps you can think about how your code is structured. The biggest improvement is to realize that you don’t need to think of “one structure = one malloc.”

For example, I once wrote a parser for a tab-separated document. While I could have turned each row and field into its own string, it was faster to scan the document, count the number of rows and columns, and do a single malloc for the row/field pointers. Then in the second step, scan the document again, assign the correct pointers to the head of each field, and replace the tabs and newlines with a NUL to get proper NUL-terminated strings for the field.

This meant that my parser now “owned” the document string, which was acceptable. And it reduced the complexity of the code, even if the malloc performance wasn’t critical.

It’s not always the malloc and free performance that is an issue. You can run into problems with cache locality (or rather a lack of cache locality), and that can really hit performance if you are doing a lot of processing on the data.

If you are worried you could switch to a memory-pooled scheme for all, most, or some parts of your API. I’m sure there are plenty of tools out there to do this in a generic way, but more often than not the pooling requirements of an application are so basic that it’s trivial to implement yourself.

Unfortunately, you are the best judge of whether pooling will benefit your application, and whether it is worth the effort and increased complexity. Just remember, a pool can be as simple as a large char buffer.

Just watch out for memory alignment issues (like don’t start objects at non-aligned memory addresses).

A classic argument I like to give for memory pools is a 2D array…

So often, you see people allocate a chunk for the row pointers, and then loop through allocating each row… You have to do more error handling, the ‘delete’ function is a pain, and at the end of it you get a matrix whose row index and individual rows could be fragmented across your address space.

Yet, all you really needed to do was allocate one block of memory with enough space for a bunch of pointers and the 2D data segment, then index it. It’s not technically a pool, but it is smarter use of memory.

How many malloc calls is too many? If any?

To me it’s too many when you actually see malloc and free calls occupying the top hotspots in your profiler, or more subtly, you don’t see such calls but your tightest and most critical loops dereferencing pointers are showing up as huge hotspots with the profiler showing cache misses all over the place. Unfortunately that discovery could be made too late if fixing those hotspots suggests costly design changes.

So what would a good rule-of-thumb be for number of allocations? I know that less would generally be better, but changing the code to allow it would introduce complexity that I’m not willing to add without a significant increase in performance.

The most useful rule of thumb I’ve started to apply for myself doesn’t concern myself with such questions. It just seeks out simple designs that don’t even make these issues a design-level concern in the first place. And for lack of a better term I’ll call this a “collection-centric” or “data structure-centric” design mindset.

Collection-Centric Design Mindset

What I mean by this is take an API like this:

EXPORT Unit* unit_create(...);
EXPORT void unit_destroy(Unit* unit);

That’s not a “collection” or “data structure”-centric design mindset. It’s working at the granular level of allocating/creating and freeing/destroying one individual game unit at a time. And the unit_create function is giving you back a pointer to a unit that resides in “outer space”: just some element residing somewhere in the memory space which the caller must now explicitly free/destroy themselves with a call to this unit_destroy function.

And sometimes you need this level of explicit memory control over an individual instance of an object. But often if you zoom out and look at the broader design requirements, especially in like a game, and for the most performance-critical parts of it (usually implying that you’ll want to be creating a boatload of such instances), you’ll often find these things want to belong to some central container/data structure, like a game Scene, or Map, or Board, and that it makes no sense for these Units to live anywhere else or be “owned” by anything else*.

• There might be some auxiliary data structures in-game which want to reference/index/point to such units, like a spatial index used to accelerate collision detection, but those structures don’t “own” the elements. They refer to them, but there is still one central “owning” collection.

If that fits conceptually, then your APIs don’t need to take on the form of mallocing/creating and freeing/destroying individual instances of such objects. They can take on the form of inserting and removing such objects, with the memory management being an implementation detail of the container.

EXPORT UnitHandle units_insert(Units* units, ...);
EXPORT void units_remove(Units* units, UnitHandle unit);

Furthermore you have less error-prone code when it comes to memory leaks, because the units collection can be responsible for freeing all remaining elements when the collection is destroyed, e.g.

And the implementation of this container might store all these units in a contiguous dynamic array which is only reallocated (realloc) when the number of units reaches the array capacity, only to double in size (similar to std::vector in C++). Or it might allocate blocks that store 64 elements at a time, freeing those blocks when they become empty and allocating new blocks only when all the existing blocks are full with a free list sort of approach. You can play with that to your hearts’ content without breaking anything in the outside world in response to whatever hotspots you encounter because now your callers no longer depend on the idea that they allocate and free individual instances themselves. They merely request to insert and remove things to/from this container type.

That’s what I recommend these days when applicable, and when applicable, it’ll tend to simplify optimizations, reduce the amount of manual memory management code (and also the likelihood of human error), provide more breathing room to change implementations without changing interface designs, mitigate the temptation to get too knee-deep in gory details fiddling around with custom allocators (you consolidate the goal of efficient allocation with the data structure/collection itself, not tackle it as two disparate concerns which can get quite messy and gory if you tackle these allocators at such a generalized level, independent of any specific data structure/use case, that you’re concerning yourself with alignment and thread safety and so forth), etc.

Coupling

Just a quick mention but naturally this proposed solution couples and fuses your element with its central container (or if “container” seems too high-level for your needs, you can just think of it as a “memory pool” or even “instance storage” or whatever), making the two indivisible. But I’d say it’s a practical thing to do that has a lot of benefits at little practical cost.

Because what sort of practical flexibility is there to, say, decouple a pixel from the image that owns it, and allows pixels to be allocated and destroyed individually? And similarly for particles of a particle system? Because I see little, if any, but there is almost certainly a tremendous cost to such decoupling in this particular context.

So I’d say don’t worry about it. If your design conceptually calls for some central container, or at least has a strong enough performance-critical need that it could benefit from an organized memory allocation/pooling strategy, then tailor your design around this idea of “insertion/removal” over “creation/destruction” or “allocating/freeing”, and reap the benefits — of which first and foremost is the elimination of the need to worry about your designs encouraging too many malloc/free calls.