Out of memory recursion

Question

I have 2GB RAM. We have an application that performs the "Export / Import" operation. We have a recursive function that has one local variable of type Set, which continues to populate each iteration. This set continues to grow, and at some point we run out of memory.

Is there an alternative data structure that can optimally use memory?

Here is sample code

GetObjectsForExportImpl(long lExportOptions, __int64 numIdProject, XExportSets &exportSets, long lClientId, CComPtr<IEPIPDServer> ptrIPDServer,FILE *fp) { XExportSets exportLocal; //Thats a structure containing the Set QueryObjectsForExport(lExportOptions, numIdProject, exportLocal, lClientId, ptrIPDServer); SetIDs::iterator it = exportLocal.setShared.begin(); for (; it != exportLocal.setShared.end(); ++it) { //recursive call pExportObject->GetObjectsForExportImpl(lExportOptions, numIdProject, exportSets, lClientId, ptrIPDServer,fp); } } 

Answer 1

An alternative structure is unlikely to help. Let's say you switch to a class that uses half the memory. However, you only delay death.

A 2 GB structure size usually indicates that you need to switch to a disk-based structure, database or hash map with memory mapping.

Answer 2

Process pieces of data with chunks, not all at once.

I.e:

 while (not end-of-file) { data = read_some_information(); export_some_information(data); } 

If you are not in a very specific case when you need all the data for export (which is unlikely)

Answer 3

Compare your method call method for a while:

 GetObjectsForExportImpl( long lExportOptions, __int64 numIdProject, XExportSets &exportSets, long lClientId, CComPtr<IEPIPDServer> ptrIPDServer, FILE *fp ) 

to your subsequent recursive call:

 hr = pExportObject->GetObjectsForExportImpl( lExportOptions, numIdProject, exportSets, lClientId, ptrIPDServer, fp); 

If something magical doesn't happen between them, you simply call the method with your own set of arguments. I suspect you wanted to put "exportLocal" instead of "exportSets" there, because otherwise, what was the point of exportLocal.setShared.begin ()? You just keep re-creating the new exportLocal, telling it to start, recursive, etc.

In short, I think the problem is a coding error, not a recursion problem.

As a side note - can you think of a way to make it a loop, not a recursion? Cycles are almost always faster, easier, easier to understand, and quick to debug.

Answer 4

Sorry - I really don't know C ++, but I can help a little. If you can use index notation to access elements, and you have pointers to parent elements, you can use the stack to do the first pass of depth and avoid the insignificant cost of recursion. Here is the C # code you can translate:

 Stack<int> childIndex = new Stack<int>(); childIndex.Push(0); TreeNode<Folder> workingFolder = GetNodeById(folderId); TreeNode<Folder> returnFolder = ShallowClone(workingFolder); while (childIndex.Count > 0) { int idx = childIndex.Peek(); if (idx < workingFolder.Children.Count) { visit(workingFolder.Children[idx]); // increment count for this level childIndex.Pop(); childIndex.Push(idx + 1); // replace current working folders and push new index workingFolder = workingFolder.Children[idx]; returnFolder = f; childIndex.Push(0); } else { // no (more) children workingFolder = (workingFolder.Parent == null ? workingFolder : workingFolder.Parent); returnFolder = (returnFolder.Parent == null ? returnFolder : returnFolder.Parent); childIndex.Pop(); } } 

Answer 5

If your recursion eats 2 GB of memory, you will probably have problems with any type of data structure in memory. Can you post some of your code so we can better understand what you are doing?

One idea might be to use a database table to store the Set when creating it. You can insert a new record for each recursion, and the record can have an FK link to the parent record in the table. This way you can move up and down recursion by following the parent links in the records.

Answer 6

I don't think recursion has much to do with your problem. The problem is that the data you create is big. Switching to an iterative solution will not help. As already mentioned, write down the output as you go through, rather than saving it in the structure inside the memory.

However, you can minimize what happens on the stack by passing pointers in your recursive calls, rather than whole structures.