Tips for working with huge working sets of RAM

Question

I am working on a .Net 3.5 application designed specifically for a powerful PC that processes and calculates data a lot. Recently, I came across the need for a 4000 x 5000 two-dimensional array, which is very large for a 32-bit PC and will give me an OutOfMemoryException. The only way to avoid using such an array is to descend onto a very difficult, laborious road, filled with pain and suffering.

Are there any tips or tricks that professionals use to work with large working sets of RAM? Do you know of any libraries that would be useful (in particular for .Net)? Is there a way to get Windows to allocate more RAM for my process?

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

Answer 1

If most of your elements are null, then you probably don't need to create an array at all.

John offers one approach that will work - implementing a sparse array using linked lists. Here is 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 other properties and methods go here } 

Now you can store Element objects in Dictionary<CellLocation, Element> . In fact, I would put this dictionary in my own class so that it can implement methods such as:

 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 an element in one row and column, a sparse array still has to do a linear search to find a row, and then another linear search to find a column in that row, while this method can find an element with one search in the hash table.

There are also circumstances in which it will be significantly slower. To find all the elements in a row, it takes as many hash table queries as there are cells in the row, and when using a sparse array, the linked list simply moves.

Answer 2

Judging by your comments, I think that now I can answer your question. If most of the links are null, you can hash the keys in a table, which in turn points to your elements. There is a constant O (1) loopup time in the hash map, and you don’t have to worry about key collisions, because each [x, y] pair is unique. You will also not have to worry about memory collisions, as most links are null.

Answer 3

Well, one thought is to discard the two-dimensional array for the database instead. Something like SQLite has a small footprint and can be easily deployed using an application. There is even a C # wrapper for it.

SQLite will read this data from a single file. And therefore, reading and writing from disk can lead to a performance hit. Although the size of the performance may depend on the nature of the application. For example, index searches should be fast. But mass computing across the entire database will certainly be slower. So ... I don't know, but maybe it's worth considering.

Answer 4

You can efficiently store a mesh structure where most elements have a zero value in a sparse array. They can be implemented in different ways, but usually use modified linked lists for rows and columns. There is a good introduction to the topic here .

Answer 5

Is the array fixed? those. the values ​​in the array do not change ... it may be worth dumping the contents of the array to disk and using memory matching technology, and then you can load part of the dumped array into the memory card for reading .. otherwise it will not work if the data and elements in the array changed ...

just my 2cents ...

Hope this helps, Regards, Tom.

Answer 6

There are two “simple” directions at the OS or Process level.

• Add a / 3GB switch to your boot.ini and change your application to use / LARGEADESSESSAWARE . You immediately get an additional 1G of virtual address space, but not without a compromise . Well this is the right choice for you.
• Often the problem is not the lack of memory, its fragmentation also matters for your context (huge sequential arrays). Some time ago, I put some methods online that helped me fragmentation for my own code - should be at least partially applicable to the managed one.

Answer 7

It looks like you are actually doing this adjacency matrix. If so, and the baseline is sparse, then it is probably best to switch to an adjacency list. http://en.wikipedia.org/wiki/Adjacency_list