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.