An exhaustive evaluation of  row-major, column-major and  Morton
	       layouts for large two-dimensional arrays

			      July 2003

       Jeyarajan Thiyagalingam, Olav Beckmann, Paul~H.~J.~Kelly

	      Department of Computing, Imperial College
			  180 Queen's Gate,
			 London SW7 2AZ, U.K.
		    {phjk,ob3,jeyan\}@doc.ic.ac.uk


Abstract 
======== 
Morton layout is a compromise storage layout between the programming
language mandated layouts row-major and column-major, providing
substantial locality of reference when traversed in either
direction. This paper explores the performance of Morton, row-major
and column-major layouts in detail on some representative
architectures.

Using a small suite of dense kernels working on two-dimensional
arrays, we have carried out an extensive study of the impact of poor
array layout and of whether Morton layout can offer an attractive
compromise. Whether Morton layout is better than traversing a
column-major array in row-major order (or vice versa) depends on
problem size and architecture. Morton layout generally leads to much
more consistent performance and only a small improvement in its
performance could make it an attractive alternative.