Working with large arrays - OutOfRam

I have an algorithm where I create two bi-dimensional arrays like this:

  TYPE
   TPtrMatrixLine = array of byte;
   TCurMatrixLine = array of integer;
   TPtrMatrix     = array of TPtrMatrixLine;                                    
   TCurMatrix     = array of TCurMatrixLine;  


  function x
  var  
     PtrsMX: TPtrMatrix;
     CurMx : TCurMatrix;         
  begin 
   { Try to allocate RAM }
   SetLength(PtrsMX, RowNr+1, ColNr+1);                              
   SetLength(CurMx , RowNr+1, ColNr+1);
   for all rows do 
    for all cols do 
     FillMatrixWithData; <------- CPU intensive task. It could take up to 10-20 min
  end;

The two matrices have always the same dimension. Usually there are only 2000 lines and 2000 columns in the matrix but sometimes it can go as high as 25000x6000 so for both matrices I need something like 146.5 + 586.2 = 732.8MB of RAM. The problem is that the two blocks need to be contiguous so in most cases, even if 500-600MB of free RAM doesn't seem much on a mod开发者_开发问答ern computer, I run out of RAM.

The algorithm fills the cells of the array with data based on the neighbors of that cell. The operations are just additions and subtractions.

The TCurMatrixLine is the one that takes a lot or RAM since it uses integers to store data. Unfortunately, values stored may have sign so I cannot use Word instead of integers. SmallInt is too small (my values are bigger than SmallInt, but smaller than Word). I hope that if there is any other way to implement this, it needs not to add a lot of overhead, since processing a matrix with so many lines/column already takes a lot of time. In other words I hope that decreasing memory requirements will not increase processing time.

Any idea how to decrease the memory requirements? [I use Delphi 7]

---

Update Somebody suggested that each row of my array should be an independent uni-dimensional array. I create as many rows (arrays) as I need and store them in TList. Sound very good. Obviously there will be no problem allocation such small memory blocks. But I am afraid it will have a gigantic impact on speed. I use now

TCurMatrixLine = array of integer;                                   
TCurMatrix     = array of TCurMatrixLine; 

because it is faster than TCurMatrix= array of array of integer (because of the way data is placed in memory). So, breaking the array in independent lines may affect the speed.

---

The suggestion of using a signed 2 byte integer will greatly aid you.

Another useful tactic is to mark your exe as being LARGE_ADDRESS_AWARE by adding {$SetPEFlags IMAGE_FILE_LARGE_ADDRESS_AWARE} to your .dpr file. This will only help if you are running on 64 bit Windows and will increase your address space from 2GB to 4GB.

It may not work on Delphi 7 (I seem to recall you are using D7) and you must be using FastMM since the old Borland memory manager isn't compatible with large address space. If $SetPEFlags isn't available you can still mark the exe with EDITBIN.

If you still encounter difficulties then yet another trick is to do allocate smaller sub-blocks of memory and use a wrapper class to handle mapping indices to the appropriate sub-block and offset within. You can use a default index property to make this transparent to the calling code.

Naturally a block allocated approach like this does incur some processing overhead but it's your best bet if you are having troubles with getting contiguous blocks.

---

If the absolute values of elements of CurMx fits word then you can store it in word and use another array of boolean for its sign. It reduces 1 byte for each element.

---

Have you considered to manually allocate the data structure on the heap?
...and measured how this will affect the memory usage and the performance?

Using the heap might actually increase speed and reduce the memory usage, because you can avoid the whole array to be copied from one memory segment to another memory segment. (Eg. if your FillMatrixWithData are declared with a non-const open array parameter).