How to avoid System.OutOfMemoryException in c# when building a non recombining trinomial tree

c#, list, memory-management, out-of-memory

Solution

What we have here is a classic problem of doing an enormous amount of processing up front... and then storing EVERYTHING into memory to be processed at a later time.

While simple, given harsh enough conditions (like having a billion entries), it will eat up all the memory.

Now, the OP didn't really specify what the intention of the tree was or how it was going to be used... but I would propose that instead of building it all at once... build it as you need it.

Lazy Evaluation with `yield`

Instead of doing everything all at once and having to store it... it might be ideal to do it ONLY when you actually require it. Check out this post for more info and examples of using `yield`.

This won't work great though if you need to traverese the tree a bunch of times... but it might still allow you to have deeper depth than you currently do.

Problem

I have "successfully" implemented a non recombining trinomial tree to price certain fixed-income derivatives. (Something like shown in the picture below - but with three branches that don't reconnect) Unfortunately it turned out that the number of nodes I can use was severely limited by the available memory. If I build a tree with 20 time-steps this results in 3^19 nodes (so 1,1 Billion nodes) The nodes of each time step are saved in `List<Node>` and these arrays are stored in a `Dictionary<double,List<Node>>` Each node is instantiated via `new Node(...)`. I also instantiate each of the lists and the dictionary via `new Class()` Perhaps this is the source of my error. Also `System.OutOfMemoryException` isn't thrown because of the Dictionary/List-Object being to large (as is often the case) but because I seem to have too many Nodes - after a while `new Node(...)` can't allocate any further memory. Eventually the 2GB max List-Capacity will also kick in I think - seeing as how List grows exponentially larger with each time step. Perhaps my data-structure is too wasteful or not really suited for the task at hand. A possible solution could be to save the tree to a text-file thus avoiding the memory-problem completely. This however would necessitate a HUGE workaround. Edit: To add some more background. I need the tree to price path dependant products. This means that unfortunately I will have to access all the nodes. What is more after the tree has been build I start from the leaves and go backwards in time to determine the price. I also already only generate the nodes I need. Edit2: I have given the topic some though and also considered the various responses. Could it be that I just need to serialize the respective tree levels to the hard-drive. So basically - I create one time-step (`List<Node>`) write it to Disk etc. Later on when I start from the leaves - I will just have to load it in reverse oder.

Original source