ansaurus

Question

Answer 1

+1 A:

Probably just the behavior of the heap manager your CRT uses. It's probably updating free lists, or some other internal structure to manage memory.

You probably should reexamine how your program allocates and uses memory if your bottleneck is here.

Terry Mahaffey 2009-12-26 23:32:44

Answer 2

+2 A:

If your program doing all of the free()ing on exit, then you might as well just skip the calls. The entire process heap is freed when you app exits.

Edit: ----

Ok, now that the code is posted, it appears to me that you aren't just freeing on exit, so you should definitely try and figure out if this is a wierd symptom of a bug, or just a costly implementation of free(). Instead of removing the free() calls, time how long it takes to execute them. is the heap manager really using up the whole 19 seconds?

I do see several places were multiple allocations have the same scope and lifetime. You could turn these into a single malloc/free call, althought that would make the code less clear and harder to mantain. So you have to ask yourself, how much does that 20 seconds matter?

John Knoeller 2009-12-26 23:36:59

Answer 3

+5 A:

Is it possible that you are linking against a debug version of the runtime library that is doing something extra in free() like filling the memory with a garbage value? I have seen this behavior when you link against overly aggressive memory debugging libraries. The code that you have posted does not look strange. I would be interested to know what would happen if you replaced the arrays with std::vector or std::deque though. Vector should have behavior quite similar to the arrays and Deque may actually improve the speed a little if the arrays are large because the memory manager will not have to guarantee contiguous space.

D.Shawley 2009-12-27 00:02:54

Answer 4

A:

Having had a look at the code one big thing that comes to my mind is this - mixture of malloc(...), new(...), delete(...), free(...)

BoundingBox* tempBox = new BoundingBox();
// ....
//Delete the bounding box
delete tempBox;

yet in other places you have

Bin* xLeft = (Bin*)malloc(dnObjects * sizeof(Bin));
// ....
free(xMins);

In short, you are mixing the C++'s runtime in calling new(...) and delete(...) with malloc(...) and free(...).. After all, this is in C++, so a question for you here...

Why did you use the malloc(...) and free(...) which is from C in the middle of this C++ code? The repercussions I could see here, is that the C++ runtime is different in terms of using the memory allocation unlike C in the aspect of OOP paradigm.

Having said this, your best bet is:

Replace all calls to malloc with new.
Replace all calls to free with delete.

Re run the program again and see if that makes a different. Can you confirm this?

Hope this helps, Best regards, Tom.

tommieb75 2009-12-27 01:07:23

Answer 5

A:

+1 to malloc/free making my eyes hurt in C++. Ignoring that for a second and looking at the code, three ideas:

Roll up your malloc calls to one large malloc and free (for the x/y/left/right/etc structures) instead of 12. Set the pointers into this large buffer as appropriate.
Still talking about the x/y/left/right variables: Employ a small stack based buffer, that you can use when the number of objects is small. When the number of objects is large, then dynamically allocate. When it is not, just set your pointer to the local stack buffer. This can avoid dynamic memory management all together for small inputs.
Right now, your "object" list is dynamically allocated, freed, and reallocated with each recursive call (!!). This is confusing because ownership isn't clear; but also it's a performance issue. Consider reworking the code so one list of "objects" is ever used.

Terry Mahaffey 2009-12-27 02:04:41

Answer 6

A:

C++ stores some extra information when you allocate using new like the type of the object or number of characters(in case of array) etc..If you are using free, it could be a fragmentation problem where you are actually deleting only the chunks of data in between but not freeing the actual information stored by new. Just a thought.

Algorist 2009-12-27 03:23:45

Answer 7

A:

When you corrupt the heap, it often becomes very slow. Try to run it in debug mode with debug version of your runtime as well.

Charles Eli Cheese 2009-12-27 10:10:02

Answer 8

A:

It could be poor locality of reference for your code. For example, I see the following:

//Allocate memory for split options
float* xMins = (float*)malloc(nObjects * sizeof(float));
float* yMins = (float*)malloc(nObjects * sizeof(float));
float* zMins = (float*)malloc(nObjects * sizeof(float));
float* xMaxs = (float*)malloc(nObjects * sizeof(float));
float* yMaxs = (float*)malloc(nObjects * sizeof(float));
float* zMaxs = (float*)malloc(nObjects * sizeof(float));
...
free(xMins);
free(xMaxs);
free(yMins);
free(yMaxs);
free(zMins);
free(zMaxs);

Now, assuming that the allocations proceed basically linearly, then free(xMaxs); may need to dereference memory that was allocated some number of pages away from xMins (which was just dereferenced during free(xMins);), so you might need to swap in a page from the backing store in order to perform the free (which causes a huge slowdown in execution when that happens). Re-ordering the free()'s to match the allocation order could help... In this case, that'd mean

free(xMins);
free(yMins);
free(zMins);
free(xMaxs);
free(yMaxs);
free(zMaxs);

Aidan Cully 2009-12-27 21:11:00

Answer 9

A:

It sounds like you are running your program from a debugger in Windows, which by default causes a special debug heap to be used, which dramatically slows down memory deallocations. This applies even to non-debug builds, as long as they are launched from a debugger (such as Visual Studio). You should be able to disable this behavior by setting the environment variable _NO_DEBUG_HEAP=1 before running your program (I recommend setting it in the project configuration settings rather than in the system settings, if possible).

You didn't describe anything about your programming environment in the original question, however, so I had to make certain assumptions about it that might be wrong. If you're not running your program under Windows, for example, then my answer doesn't apply and I have no idea what the cause of your problem might be.

2009-12-28 06:18:07

ansaurus

tags:

views:

answers:

Why is free() bogging my program down?

related questions