Programming

So, I've been told and heard a million times that malloc and free are expensive calls to be avoided. So many times I avoid malloc by reusing already allocated memory blocks. Store them on free lists somewhere myself and don't call free when I know malloc will be called very shortly thereafter.

I am writing an in-memory communication queue API for my multi-threaded application. Originally there was only to be one set of threads in the application who would be using this queue. Now, there may be more sets of threads and therefore more queues. Because they all use the same size payload to communicate, they could also all share their allocations. However, if that were to happen then the free list would have to be mutex protected across thread groups.

So...here's the rub. At this point the free list is my bottleneck. Before it wasn't such a big deal because I only had one set of threads which needed a mutex anyway. So I crafted the API to protect the free list and the queue together. Now the free list would either be wasteful (unshared) or shared (and slow). The other option, of course, at this point is to rebuke my "malloc is slow" mentality and alloc and free the payloads as needed.

Anyone want to jump in and comment. What do you think will be faster and why?

Method 1:

(producer)
- Malloc payload
- grab queue mutex
- place on queue
- alert threads (condition var)
- unlock mutex

(consumer)
- lock queue mutex
- block condition var
- acquire work off queue
- unlock mutex
- free payload

Method 2:

(producer)
- grab free list mutex
- get item off free list (or malloc if list is empty)
- unlock free list mutex
- place on queue
- alert threads (condition var)
- unlock mutex

(consumer)
- lock queue mutex
- block condition var
- acquire work off queue
- unlock mutex
- grab free list mutex
- place item on free list
- unlock free list mutex

My guess is that at this point, the overhead of malloc and free is probably less than that of a mutex lock for the free items list. That's my hunch, but I know malloc and free have to be protecting their heaps for multi-thread access, but they could be using a lock-free algorithm too. Also, by using malloc and free a lot I have the potential to fragment memory if interleaving application calls allocate memory too. Given this is an API I'm writing, I have to take that into consideration a little too. I'd love to get back to the simple life and not manage a free list, but I also don't want to kill performance to do it. Of course, if the free list is the performance hog it may be, then I obviously don't want to use it and just let malloc and free do their jobs.

Oh...what to do...what to do.... Comments, questions, I'd love to hear some input on this one. I'd prototype it, but I don't have a whole lot of time, and I just got done prototyping a posix in-memory queue vs. AIX message queue application and I'm prototyped out, lol. Given the API I'm writing, I'm guessing you can pick the winner of that shoot-out.

Oh...I just got another idea too....

I could continue with the current methodology and have free lists for each queue protected by the queue's own mutex. However, to make it not wasteful I could "shuttle" free items from one queue to another only when I'd otherwise do a malloc in that queue's group. Sooner or later things would balance out as each group of queues acquired enough items to support its existance and then they'd never malloc again, just recycle their own free list. Of course...then I may as well not even do the shuttling and just let them balance out on their own. Hummm...pros and cons here too as this is an API and I don't really know how the groups of threads will be used.

Hummm...... Interesting, but still not ideal. Maybe I'm just overthinking it and malloc and free would be more than fine. I wonder what their real overhead is anyway.

malloc is tremendously expensive when it invokes sbrk() to expand the process. It should not be that bad when it doles out previously obtained memory. The trouble here is that there are various implementations of malloc and some platforms even have multiple malloc libraries so you can't paint all malloc implementations with the same brush. I would go with malloc/free to start with and do something else only if forced. Then each producer can have its own queue and there is no need for explicit shuttling of freed buffers among producers.

A performance hack... get stuff working and then monitor the memory requirements. Let's say that you find that a typical process needs about 10 MB of malloc'ed stuff. So malloc and free a 10 MB area at startup...a unix process will not shrink

So basically, at the very worst it'll be slow during all the initial queue allocs and then level off as it doles out previously obtained memory from its pool. I'd rather not over compilicate things for nothing, so now my only other concern is fragmentation and pinning the heap with small allocs at the end. But, since I'll be calling malloc and free quite often hopefully those shouldn't be a big deal. However, I will be forcing free to do a lot of coelecing...but that shouldn't be slow either, and not all malloc implementations coelece. So...I'll just do it that way and see what happens. Heck, it's the way my initial prototype of the in-memory posix queue vs. os message queue did it and it still outperformed the os message queue...so, I guess it can't be too bad. I just wanted it faster if possible.

THANKS!

Anyone else?

But you are calling malloc repeatedly with the same size buffer right? It's not obvious how it can fragment under those circumstances. And it should not coalesce unless it needs to. You seem to think that your malloc was written by a bozo. If this is the case, maybe you can download another version somewhere.

I think he believes that malloc has inherent problems. In the Linux world, glibc malloc is based on the Doug Lea code. Which does not have performance issues like those he described. I don't understand where he got the idea.

DW-

You did profile this code and see that malloc ate your lunch, right?

If not, you should profile your code before you go thru all this. malloc will show up in gprof or whatever profiler you use with gcc versions before 4.0. (I think you're on Linux.)

I seldom see malloc using even measurable amounts of time compared with the other functions - on HPUX, and several Linux distros.

Perderabo,

I am in the API, but since I'm just writing an API I am subservent to what the application does, and I can't assume it won't make interspersed malloc calls that, due to my frequent calls to malloc, may end up fragmenting. Either way, I'm no longer going to worry about it...if it becomes a problem then I'll fix it then.

Jim,

I am on AIX, and I'm sure you're both correct that the malloc is OK. I was just being overly cautious because I've heard several times not to frequently call malloc and free in applications. However, since the potential overhead and/or extra code to get around it for this particular application is unwieldy, I'll just see what happens and if it doesn't perform or I see issues then I'll fix it then.

Thanks everyone! At least you soothed my concerns that doing frequent malloc and frees may not be as bad as I once thought.