using delete/defragmenting memory

[tition]

Dear all,


My program allocates lots of dynamic memory (under windows) to make a large computation, until it crashes with a "bad_alloc" error. At the time of crash, the Task Manager reports that my program uses only about 360MB of RAM, however, the system load section of the Task Manager reports well above 1GB of memory usage.

I believe the reason for that is that windows does not defragment the memory I release with the delete operators, and so the memory usage is in reality much higher that Task Manager's report.

Is it possible for me to somehow "pause" my program and call *explicitly* some "Memory defragment" System function? Thanks a lot for your advice!



***more details on where I believe the problem lies***

My basic memory unit is called "root" (the terminology comes from mathematics), and it is exactly 8*5 = 40 bytes long. I allocate arrays of roots using
new root[size];.
When I need to resize my arrays, I call
new root[newSize];.
Then I copy my old roots onto the newly allocated memory, and release the old array. This is where the big memory defragmentation problem occurs, I believe.

***more details on the symptoms of my problem***

The debugger does not report a mistake, I get the error as a windows message in my TranslateMessage(&msg);DispatchMessage(&msg); cycle. The program crashes after around 45 minutes of computations, so this is *not* an easily reproducible mistake. The program runs correctly and gives proper output on all smaller examples I have tested.

My computer has 512MB RAM, and I can certainly move on to a stronger computer (we have a computational computer cluster in my University), however I prefer to try to fix the problem on my own computer, since I will need to reserve the cluster in question well in advance.

***more details on my program***

My program is solving the following problem. I have a number of hyperplanes - less than 15 choose 4 = 1365 - all passing through the origin in 5 dimensional space. I must compute explicitly the chambers in which they split the 5 dimensional space. The problem looks deceptively easy - for example, a typical chamber would have about 30+ faces, 30+ edges (one dimensional) and 450+ edges (3 dimensional). Each of those is described with a 5 dimensional vector of rational numbers (rational number= two ints (numerator and denominator)), from where my 40 byte "root" comes from.


The program crashes somewhere around chamber number 36500.

***

Again, thanks for your advice on my problem!

[jsmith]

I'm not a windows programmer, but if Windows works anything like any other OS, then Task Manager reports the amount of memory that the program has requested from the kernel.

The C/C++ runtime library requests memory from the kernel when it needs it. However, it will typically request memory in larger chunks (ie, not 40 bytes at a time). The runtime library then manages the memory given to it (this memory is called the heap). You could be seeing fragmentation of the heap.

Your allocation/deallocation scheme might be causing this fragmentation, the ultimate manifestation of which will be that your program appears to run out of memory even though system resources are plentiful. This can happen if your process exceeds its virtual address space.

One way to check would be print out some pointers and see if they are growing towards 0xFFFFFFFF. If they are, then you need to consider writing a custom allocator.

[helios]

Could there possibly be any memory leaks?

[tition]

I do not know. I believe that, when there are memory leaks, Task Manager would report a large memory use from my program, which it does not.

I have, of course, put a lot of time in debug, and I believe that I made no memory leak mistake; however, in case I did, how could I make a test for it?


@jsmith: the pointers could indeed have grown higher than 0xFFFFFFFF. Due to the origin of the problem, every 4-dimensional facet of my chambers is splitted some <15 times (the same number 15 participating in the original post). By "splitting" I mean that object gets destroyed and its descendants replace it, then each of them gets destroyed and replaced, and so on, with a depth of <15.

Provided that the number of vertices of such a 4-dimensional face is approximately constant (which is a *very* speculative statement), that means that the actual size of the pointers could be <15 times larger than 350mb, which is more than enough to get the 0xFFFFFFFF size of pointers.

That's a very interesting possible explanation, it never ocurred to me! Also, it explains why the program crashes at 1GB of virtual memory only - windows should (but does it?) be able to handle 1GB memory.

Thanks a lot for the idea!

[z05DSL3A]

How is the virtual memory configured on your computer?

[helios]

Task Manager would report a large memory use from my program, which it does not.

What do you mean it does not? Your estimate is 360 MB and Windows is reporting 1 GB.

Memory debuggers, among other things, can detect memory leaks in a program.

In a 32-bit system, 4 GB is the upper limit for RAM, so I doubt that any pointer could have a value higher than 0xFFFFFFFF.

[tition]

@ helios:

Task Manager displays two things.
1) The amount of memory a given program uses. This number is around 360MB for my program. It is not an estimate, its Task Manager's report
2) It displays the total "System load" which is displayed to be around 1.1 GB.

Maybe I am failing to understand something here...
just made a simple program with a 1mb memory leak in a cycle, and you have right, Task Manager reports low memory use of my program, while the system load is high.

[z05DSL3A]

Are you are hitting the limits of your virtual memory? If you only have 512Mb of physical ram and your page file is set to max at ~512Mb then you will crap out at 1Gb of total system load.

[tition]

Hmm, you are right too, the virual memory allowance of my HD is 756 mb - sorry for answering that late, I mostly do the programming on a weaker mashine and then run it at home on my 512 RAM pc.

[tition]

[Edit: something else was wrong with my program. Here is anyways the code to call memory defragmentation explicitly].

#include <windows.h>
 const int MaxNumHeaps= 5000;
void AttemptMemoryCompactification()
{
  HANDLE HeapHandles[MaxNumHeaps];
  int NumUsedHeaps= GetProcessHeaps(MaxNumHeaps,HeapHandles);
  for (int i=0;i<NumUsedHeaps;i++)
  {
    HeapCompact(HeapHandles[i],0);
  }
}

The reference is:

http://msdn.microsoft.com/en-us/library/aa366598(VS.85).aspx


Cheers everyone!
:))))))


Big thanks to jsmith: the key words to google were "heap fragmentation" from your post! Thanks!

[helios]

No, no.
When Windows reports memory usage it reports exactly the total memory a program has allocated. It doesn't take into account the memory that exists between two different allocations, so heap fragmentation doesn't influence the reported memory usage.

[tition]

Edit: I cannot reconstruct what I saw... I owe you an apology helios. Sorry man! I messed something up! You are right!


Old post

Today I ran a test with the current version of my program without the heap defrag you see above. The reported memory use was 240MB+ on the process, and 600MB+ system load (for at most double the number of chambers). Then I implemented the defrag you see above. That was the only difference in the code. The reported memory use on the Task Manager dropped to 16MB, and the system load reported in accordance.

It doesn't take into account the memory that exists between two different allocations, so heap fragmentation doesn't influence the reported memory usage.


The fragmentation occurs inside the heap.

No, no.
When Windows reports memory usage it reports exactly the total memory a program has allocated.
Wanna bet?

[jsmith]

yw!

This is the first time I've ever seen heap fragmentation actually cause a problem.

There is an interesting problem with STL vectors that this brings to mind.

Vectors typically allocate more memory than they need, with the idea of avoiding
continuous reallocations on every insert. So the question is, by how much should
a vector grow when it needs to be resized? Originally, and I believe that GCC's
vector implementation does this, it would double in size.

1 element became 2, 2 became 4, 4 became 8. But that's a problem, because 1 + 2 is 3, which means that when it becomes size 4, it cannot reuse any of the memory allocated previously since the block isn't big enough. The result is that the vector slowly migrates toward the top of the address space.

It turns out that the best resize algorithm is the golden ratio: that is, the vector should grow by a factor of ( 1 + sqrt(5) ) / 2. This avoids the migration problem.

Kind of similar to the problem you had here.

[helios]

Hm... I'm curious. Could you upload your code or the project? I would like to take a look at it.

[tition]

Sure :) Before I dump the whole thing though, is there any file upload etiquette (how should I attach it)? The program is about 6000 lines of code.

[helios]

I think you better compress it and upload it to any of these (ordered by quality):
http://www.fileden.com/
http://www.wikifortio.com/
http://www.mediafire.com/
http://www.sendspace.com/
http://rapidshare.com/
http://www.megaupload.com/

[tition]

Registering account at www.fileden.com
...
done!
http://www.fileden.com/getfile.php?file_path=http://www.fileden.com/files/2009/2/27/2341100/RootSA.zip


My project is a dll file and provides 3 functions. They are:
TestFunctionC
RunASmallExampleB3
RunABigExampleSubAlgebraOfD5

Use RunASmallExampleB3() to see what the program does. When the dialog gets displayed check the graphics checkbox. Then click "Draw em all" from the menu to see what the program does in short, or click "small increment" or "increment" to see the algorithm step by step. If you click the graphics checkbox in between the increments the program will crash (not 100% sure)

[Edit] Unfortunately I was confused with memory fragmentation. Something else was wrong with my code, what - I will find out!

To load the dll use some code along the lines

  _chdir("C:\\rootFKFT\\cpp\\Debug_MemorySucker");
  char tempC[100];
  _getcwd(tempC,300);
  HINSTANCE hGetProcIDDLL = LoadLibrary(_T("rootSA.dll"));
  DWORD a;
  if (hGetProcIDDLL==0)
  {
     a= GetLastError();
  }
  FARPROC lpfnGetProcessID = GetProcAddress(HMODULE (hGetProcIDDLL),"TestFunctionC");
  FARPROC lpfnGetProcessID2 = GetProcAddress(HMODULE (hGetProcIDDLL),"RunASmallExampleB3");
  FARPROC lpfnGetProcessID3 = GetProcAddress(HMODULE (hGetProcIDDLL),"RunABigExampleSubAlgebraOfD5");
  typedef int (__stdcall * pICFUNC)(int*, int*, int*, int*);
  pICFUNC TestFunctionC;
  typedef int (__stdcall * pICFUNC_NoArguments)(void);
  pICFUNC_NoArguments RunASmallExampleB3;
  pICFUNC_NoArguments RunABigExampleSubAlgebraOfD5;
  TestFunctionC = pICFUNC(lpfnGetProcessID);
  RunASmallExampleB3 = pICFUNC_NoArguments(lpfnGetProcessID2);
  RunABigExampleSubAlgebraOfD5= pICFUNC_NoArguments(lpfnGetProcessID3);
  int intMyReturnVal = RunASmallExampleB3();
  intMyReturnVal = RunABigExampleSubAlgebraOfD5();
  FreeLibrary(hGetProcIDDLL);

If looking at the graphics, you can click the center of the coordinate system to move it around (left click picks up left click puts down). Same holds for the (up to 5) base vectors of the coordinate system.

[tition]

helios, I cannot reconstruct what I thought I did this morning... You were right and I was wrong: I owe you an apology.

I recall besides the events I described in the previous post, I did one "minor" other optimization (turning off the creation of the "ThePoly" member in the constructor of "CombinatorialChamber").

This is where the big problem has occurred, obviously - there is something wrong with that object. (what I will find out and perhaps even entertain people in the lounge).

Once again, if I offended you, sorry! You were right and I - wrong - hope I didn't waste your time much! And also thanks for giving me the benefit of the doubt - after all, it made me discover the true problem!

[helios]

Me? Offended? Nah. I got to confirm my theory on the Windows monitoring system.

Next time you realize a previous post of yours is wrong, though, instead of deleting the text, strike it with the [s][/s] tag.

[tition]

Understood hehe (forum posting etiquette I guess...?)

Btw, through being able to run my program longer now, I discovered another, this time algorithmic mistake, in an "optimizazation" I made in order to reduce memory.

*disclaimer: (simple) math follows*
here it is:
If all vertices of a given polyhedron lie outside of another polyhedron and vice versa, that doesn't mean that the two polyhedra don't intersect! Of course it is totally obvious (when you see it) and you can even show an example in two dimensions... (but not in one hehe). However it took me hours of debugging to figure it out.... lol