Date: Wed, 14 Jul 93 10:52:19 EDT
From: dave AT echologic DOT com (Dave Hayden 908- 946-1107)
To: djgpp AT sun DOT soe DOT clarkson DOT edu
Subject: Re: memory problems

As I understand it, John Weiss's problem with large 2D arrays comes
from all the paging.  He must access the array in both row and column
order.  When it's allocated by rows and accessed by columns, each
access hits a new page and the disk thrashes madly.


Right now, the elements are allocated to pages something like this:

			Index
	    0  1  2  3  4  5  6  7  8  9 10 11 ....
	 0+---------------------------------------
	 1| 0  0  0  0  0  0  0  0  1  1  1  1 ...
	 2| 3  3  3  3  3  3  3  3  4  4  4  4
	 3| 7  7  7  7  7  7  7  7  8  8  8  8
	 4|11 11 11 11 11 11 11 11 12 12 12 12
	 5|15 15 15 15 15 15 15 15 16 16 16 16
	 .|
	 .|                          Page number
	 .|


So why not allocate them like this instead:

	    0  1  2  3  4  5  6  7  8  9 10 11 ....
	 0+---------------------------------------
	 1| 0  0  0  0  0  1  1  1  1  2  2  2
	 2| 0  0  0  0  0  1  1  1  1  2  2  2
	 3| 7  7  7  7  7  8  8  8  8  9  9  9
	 4| 7  7  7  7  7  8  8  8  8  9  9  9
	 5|15 15 15 15 15 16 16 16 16 17 17 17
	 .|15 15 15 15 15 16 16 16 16 17 17 17
	 .|
	 .|

In other words, let each page contain a block of values intead of part
of one row or column.  Obviously this means you have to write your own
routine to get an element from it's subscripts, but in C++ you could just
overload the [] operator for this.

This will make the program run slower if you're not paging, but I
think it will help prevent thrashing if you do page.

Dave