Tips For Dealing With Huge RAM Working Sets

Question

I am working on a .Net 3.5 application designed specifically for a high-powered PC that does lots of data manipulation and computation. I recently encountered a need for a 4000 x 5000 two-dimensional array of objects, which is very large for a 32-bit PC and will give me an OutOfMemoryException. The only way to avoid using an array like this is by going down a very complex, time-consuming road filled with pain and suffering.

Are there any tips or tricks that the pros use to deal with large working sets of RAM? Do you know of any libraries that would be helpful (specifically for .Net)? Is there a way to force Windows to allocate more RAM for my process?

EDIT: The array I am using will contain mostly null references, and I am using the array to keep track of adjacent objects. Seeing how most of them are null references, I would also assume there is a more efficient approach to keeping track of adjacent objects, finding a neighbor for any given object, etc.

Answer 1

Judging by your comments, I think I can now answer your question. If most of the references are null then you can hash the keys into a table that in turn point to your elements. There is constant time O(1) loopup time in a hash map and you wont have to worry about key collisions because each [x,y] pair is unique. You also wont have to worry about memory collisions since most of the references are null.

Answer 2

If the majority of your elements are null, then perhaps you don't really need to create an array at all.

Jon suggests one approach that'll work - implementing a sparse array using linked lists. Here's another:

public struct CellLocation
{
   int Row;
   int Column;
}

public class Element
{
   public Element(int row, int column)
   {
      Location = new CellLocation {Row = row, Column=column};
   }

   public readonly Location { get; private set; }

   // your class's other properties and methods go here
}

Now you can store Element objects in a Dictionary<CellLocation, Element>. In fact, I'd put that dictionary into a class of its own, so that it can implement methods like:

public IEnumerable<Element> AdjacentElements(Element elm)
{
   for (int row = -1; row <= 1; row++)
   {
      for (int column = -1; column <= 1; column++)
      {
         // elm isn't adjacent to itself
         if (row == 0 && column == 0)
         {
            continue;
         }
         CellLocation key = new CellLocation { 
            Row=elm.Location.Row + row, 
            Column=elm.Location.Column + column 
         };
         if (!Cells.ContainsKey(key))
         {
            continue;
         }
         yield return Cells[key];
      }
   }
}

There are operations for which this can be faster than a sparse array. To find the element at a single row and column, a sparse array still has to do a linear search to find the row, and then another linear search to find the column in that row, whereas this method can find an element with one lookup into a hash table.

There are also circumstances in which it will be substantially slower. To find all the elements in a row requires as many hash-table lookups as there are cells in the row, while doing it with a sparse array just entails traversing a linked list.