Memory Allocation Problem for recursion through Multi-nomial Tree

[erementarz]

Hi,

I'm experiencing an OutofMemoryError exception while recursing through a tree with a large number of branches (30) but relatively small depth (5). Here's the basic idea of the code:

I start growing the tree using a depth-first method, and after I reach the leaf node, I assign a value to the node and then recursively calculate the value of the their parent node with some formula. Ideally I hope Java's garbage collector can recycle all the memory of all the child nodes once I get the value of the parent node, as I won't have any use of them. So according to that I only need to store at most 30 * 5 nodes in the memory at any time. However apparently that is not the case, and could someone please let me know how I can recycle the memory for the recursion?

thanks,
Colin

[bugmenot]

it's really hard to tell what you are doing without seeing some code

in your "tree", do the nodes have references to their children; if so, then the children are not garbage collected, because they are reachable

what you describe about going into the leaves and returning back up, is simply just called "recursion"; and you don't really need to think about trees at all

[erementarz]

Yes each node has references to all 30 children, and I guess the reason I call it a tree is that the code is about simulating the option price in multiple periods, and in each period there are, say, 30 different prices the underlying asset can take. I'm attaching the code here.

So in this case, I create the nodes on the fly as I go down the tree, and want to get rid of the child nodes as I return back up. What would be an efficient way of doing this without running out of memory?

public static double traverse (TreeNode cn)
	{
		int i = cn.getIndex(); // current node index (period)
		double vhNew; // upperbound for the current node value
		if (i != m)
		{
			for (int j=0;j<b;j++)
			{
				double sNew = cn.getPrice() * (1 + drift*dt + sigma*Math.sqrt(dt)* randn());
				TreeNode child = cn.setChild(sNew, j);
				traverse(child); 
			}
			
			double vhSum = 0;
			for (int j=0;j<b;j++)
			{
				vhSum += cn.getChild(j).getVh();
			}
			vhNew = Math.max(cn.getPrice() - k,
						Math.exp(-r*dt)*vhSum/b);
		}
		else // leaf node
		{
			// Vh = max (S-K, 0)
			vhNew = (cn.getPrice() - k > 0)? cn.getPrice()-k : 0;
		}
		cn.setVh(vhNew);

		return vhNew;
	}

[bugmenot]

i think something's actually wrong with your logic. i can't see your code, so I don't know what methods like getIndex(), setChild(), and stuff do; but... your recursion only stops if i == m, where i is obtained from getIndex(). how is getIndex() gotten? that stopping condition only makes sense if, say, the getIndex() value keeps track of the depth of the node in the tree or something

i am guessing that setChild() creates a new TreeNode object and sets its "price" and "index" to its arguments. so for every node, its children will always get indexes from 0 to 29, and each of its children will get indexes from 0 to 29. so it does not have anything to do with the depth

maybe i'm wrong; but it's really hard to tell without your other code

[erementarz]

thanks for the reply bugmenot!
The index(which is a misnomer i guess, it would be better called period here) is assigned to the node when it is first created by the constructor. And yes you are right, setChild() creates a new TreeNode object, and I let this child node's index be the (parent index + 1) to indicate it's the price of the next period. So it takes values from 0 to m, which is 5 in this case.
There is another set of index [0...29], which keeps track of ith child in a TreeNode's children array.

I guess the logic is fine, since the code runs for cases with less branches. It's just that once branch number exceeds 30 it gives me out of memory error.

[Ezzaral]

I guess the logic is fine, since the code runs for cases with less branches. It's just that once branch number exceeds 30 it gives me out of memory error.

If you are hitting out of memory exceptions at 150 nodes, I would say the logic is not fine and you are recursing the collection much more than necessary. As mentioned above, since your limiting variables (i,m,b) are external to the method, it's difficult to say what's breaking down, but none of your traversals are limited to parameters of the current node and since you say every node has a reference to every other node, you are probably checking the same nodes over and over again.