C – How Many `malloc` Calls Are Too Many?

cmallocmemory

I'm implementing a system in C, implemented partially as a library. The library does most of the memory management itself, with the application layer just having to call *_destroy functions on the top-level objects.

While checking for memory leaks, I noticed that the number of calls to malloc seemed quite high, relative to the size of the application code. The performance of the code seems fine, but I've been bitten by "fast enough" code before when trying to scale.

The number of allocations roughly matches the number of objects created, including child objects of the top-level ones. So creating a single top-level object might trigger 7 malloc calls, since it needs one for itself and then a couple for it's children that may also need a few children.

Unfortunately, I'm relatively new to C programming, though generally experienced as a programmer, and have no idea whether or these numbers are normal or not.

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.

Also, should I worry about the performance of malloc/free or is that the realm of real-time performance (games etc.)?

Best Answer

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.

Related Solutions

C Memory Usage – When to Use malloc and free

I'm not going to debug your code, there's not enough context to do this anyway, but I'm going to show you an idiom that you will probably find easier to use correctly. As a bonus, it will also be faster.

Have a look at your loop body. You are allocating memory during each iteration and free it under certain circumstances depending on the overall control flow. This puts very high mental load on anybody (including yourself) reading the code and trying to verify that each malloc is paired with a corresponding free on each possible path of execution.

What if you instead took the memory allocation and deallocation outside the loop?

const size_t maxcwd = PATH_MAX;
char * cwd = malloc(maxcwd);
if (cwd == NULL)
  {
    fprintf(stderr, "error: cannot start shell: out of memory\n");
    return EXIT_FAILURE;
  }
while (true)
  {
    if (getcwd(cwd, maxcwd))
      {
        // Good, use it…
      }
    else
      {
        // Bad, do something else…
      }
  }
free(cwd);

Note how there is only a single malloc and a single free and it is fairly easy to see that they pair up correctly. The code will also be faster because there are much fewer allocations and deallocations performed.

However, the code is not ideal. Why allocate a huge array upfront that might never be needed and why fail if it is still too small? It would be better to dynamically resize the array as needed.

size_t cwdsize = 0;
char * cwd = NULL;
while (true)
  {
    while ((cwd == NULL) || (getcwd(cwd, cwdsize) == NULL))
      {
        size_t newsize = (cwdsize > 0) ? (cwdsize << 1) : 128;
        char * temp = realloc(cwd, newsize);
        if (temp == NULL)
          {
            fprintf(stderr, "error: out of memory\n");
            break;
          }
        cwdsize = newsize;
        cwd = temp;
      }
    // cwd is now always good to use…
  }
free(cwd);

Of course, the code is a little verbose and you might decide to factor it out into a function. This is also the pattern used by the POSIX getline function which I find very elegant.

It is too bad that GNU readline does not support the same idiom. It always allocates new memory and you have to remember to free it after every call. Even worse, there is no way for it to report failure to allocate memory.

bool keep_going = true;
while (keep_going)
  {
    char * line = NULL;
    // Other stuff that needs to be done…
    line = readline("$ ");
    if (line == NULL)
      {
        // Probably EOF
        keep_going = false;
        goto finally;
      }
  finally:
    free(line);
  }

If you also have other error paths, you can safely say goto finally; multiple times in your loop. This is because free(NULL) is a safe no-op. If you're dealing with resources where the deallocation function must only be called with valid resources, your cleanup code would have to check itself whether it actually has a resource to free. This disciplined use of goto basically mimics deterministic destruction in C++ and is a very useful idiom in C.

C Performance – How Efficient is malloc and How Do Implementations Differ?

There are multiple implementations of malloc and they can use very different algorithms. Two very widely used implementations are jemalloc and dlmalloc. In both cases the links have a lot of information about the thought process and trade-offs made in a general purpose allocator.

Bear in mind a malloc implementation has very little information to go on, just the size of the allocation requested. A free implementation only has the pointer and whatever data 'malloc' may have secretly attached to it. As such there ends up being a fair amount of heuristics i.e. inspired guesswork in deciding how to allocate and deallocate.

Some issues that an allocator needs to address are:

alignment - some memory alignment are faster than others
fragmentation - naive allocation and freeing can leave holes that cause bloat
performance - going back to the OS for more memory can be expensive
Common requests - in practice applications (especially C++) often do a lot of small allocations so making these efficient can help a lot

Taking all this into account, what you'll find is that the allocators tend to be complex pieces of software so that, in general usage, they perform well. However, in specific cases, it may well be better to manage memory outside the allocator if you happen to know a lot more about the structure of the data. Obviously the downside is that you need to do the work yourself.

Best Answer

Related Solutions

C Memory Usage – When to Use malloc and free

C Performance – How Efficient is malloc and How Do Implementations Differ?

Related Topic