Thread: Using less malloc and free makes code _slower_

I have written a program that uses a queue structure. It is implemented as a struct containing a void * array, and indexes pointing to the first and last element in the queue.
I use this structure to store pointers, but I also use it to store long ints.

So when I wrote the first version of the code when I needed to store a long int I would malloc a space for it and store it in the queue:

Code:

pdata=malloc(sizeof(node_id));
*pdata = v;
queue_add(qbfs,(void *)pdata);

(node_id is a typedef for long int and queue_add is the function I wrote for inserting an element in the queue).

For removing an element I would read from the pointer and then free it:

Code:

pdata = (node_id*)queue_get(qbfs);
u = *pdata;
free(pdata);

Now I wanted my code to run faster, and I thought all these mallocs and frees were not good. So I created a variant of my queue structure that contains a long int array, to be able to store my long ints directly. This made the code run _much_ slower. I tried every variation I could think of, but everything just seems to slow my code down. In the end I've done a version which uses the same queue structure but casts the long ints to pointers, replacing the above snippets of code by lines such as:

Code:

queue_add(qbfs,(void *)v);

u = (node_id)queue_get(qbfs);

(I have checked that long ints and pointers are the same size on the machine I'm using, and that this does not change the results of the program).
The resulting code is much slower. To compare the running times of the two:

Code:

real    0m21.208s
user    0m3.688s
sys     0m17.517s

versus

Code:

real    0m3.900s
user    0m2.740s
sys     0m1.148s

I use some random calls in my program but I used a srandom(0) at the beginning of both versions, and checked that the results are identical.
I've run diff between the two versions a thousand time to check that the differences are only in the queue management.

I've compiled the two versions of the code in the same way (no option except -W and -Wall), and am running them on the same machine. I have done the compilations and timing several times to check that I was not getting mixed up between which version is which.

I've isolated these snippets of code to launch them on their own in a program that does 2 millions inserts and two millions remove from the queue, and in this case, the cast version is faster.

I must be missing something really obvious but I am out of my depth.
Any idea how using the same code, with less malloc and free, can run slower? And why is it spending so much more time in sys state?

Thank you for reading.

laserlight: I was reluctant to post my code because it's a bit large and I was unable to isolate the problem in a small bit of code. Anyway, in case it may help I put it up here:
https://bitbucket.org/chlorine/queue/src

There are three versions:
malloc-free.c is the original one, in which I do a malloc before inserting a pointer in the queue, and a free after removing it.
cast.c is the one that I described, in which I cast a long int to void * before inserting it in the queue (will only work on architectures in which long int and void * are the same size)
longint-queue.c is a third version in which I created a queue variant for storing long ints. It has the same bad performance as cast.c

All the differences are in the function bfs_r, which performs a breadth first search in a graph (hence the need for a queue).

It needs parameters to run, the ones I used are:
100000 200000 1 3000 5 10 0


Codeplug: thanks for the input, I would never had thought to check that. However as far as I can tell all pointers are properly aligned.

I didn't know that casting long ints to pointers could create an overhead. The cast version isn't one I would like to use indeed, I just created it for posting because it was closest to the original code.
The version I'm wondering about is longint-queue.c. What I do is store values in a queue (not a linked list):

Code:

typedef struct queue{
  node_id size;
  void **elts;
  node_id begin;
  node_id end;
}queue;

In the original version I would malloc a pointer to a long int and insert it in the queue:

Code:

  pdata=malloc(sizeof(node_id));
  *pdata = v;
  queue_add(qbfs,(void *)pdata);

In longint-queue.c I created a variant of the queue structure that stores long ints rather than void *, and I replaced the above snippets of code with

Code:

node_id_queue_add(qbfs,v);

This version is as slow as the cast one. I thought this was for similar reasons but maybe not. Sorry if it was misleading.

Originally Posted by MK27

Keep in mind that the OS (all of them, I believe) allocates memory in 4Kb pages. That's 1000 ints. I'm not sure how truly expensive malloc/free is except when you need to get a new page from the OS.

You may want to check that... Windows allocates and deallocates on 4 byte boundaries on x86, 8 bytes on x64... as a matter of data alinment. If you are using the OS level memory management HeapAlloc() allocates by bytes.

Originally Posted by MK27

Stack and heap memory are allocated to the program by the OS in 4Kb pages.

OOPs... my bad... I read you as meaning malloc etc....

Yes there are page size requirements for heap creation and heap expansion but allocation within the heap is merely a matter of alignment.

When you malloc(1) you don't get 4k...

However HeapCreate() will get you some multiple of 4k.

MK27: I understand your point and your mishaps do give a bit of consolation

However I'm still bummed out that the second version works so much more slower than the original.

MK27: sorry, I just realized I only replied half your post.

I did try to use gprof, but the results were more confusing than helping.
If I understand the output correctly, it seems that in the slow version the whole code is slower, and not just the function I modified.
Compare:

Code:

index % time    self  children    called     name
...
                7.61   62.29    1000/1000        main [1]
[2]     90.9    7.61   62.29    1000         bfs_r [2]
                9.93   47.14 49031199/49031199     neighbours_r [3]
                1.56    1.41 49031199/260124630     queue_add [5]
                1.62    0.15 49031199/260124630     queue_get [6]
...

for the quick version to

Code:

index % time    self  children    called     name
...
               13.38   81.87    1000/1000        main [1]
[2]     92.7   13.38   81.87    1000         bfs_r [2]
               13.90   61.32 49031199/49031199     neighbours_r [3]
                1.88    1.45 49031199/49031199     node_id_queue_add [11]
                2.07    0.29 49031199/49031199     node_id_queue_get [13]
...

for the slow one.

bfs_r, which is the modified function, is slower (self seconds column) in the slow version, but so are its children!
And the time difference do not lie mainly in the queue dealing functions, but in the neighours_r function which is exactly the same in both version.

I really don't know what to make of this.