I was just reading this great article on Wikipedia about Row Major Order and Column Major Order and how they relate to Computer Science and storage of two-dimensional arrays. It was really enlightening for me so unless you know all about it, I would suggest giving it a read if you see anything you like here. I have been doing some stuff with GLSL and reading about it and I was surprised to read that it uses column major order when storing matrices (which are basically just 2D arrays).
When I took Linear Algebra at the University a while back we had talked a bit about the differences between doing things using either rows or columns and that you could do both. I did not quite understand this at the time, I knew that you could do the same things in different ways if you used rows or columns. But now I know that at least when it comes to computers there can be applications where either one could be better than the other.
Row-Major Order
I am going to talk for a bit about Row-Major Order, and anyone that is close with the C/C++ programming language will know that two dimensional arrays are stored in physical memory contiguously like so:
{50,61,32,83},
{93,47,15,66}};
This array would be stored in memory in Row-Major Order with rows one after the other stored in memory, with the array cells contiguously stored as shown below:
If you know that your array is in Row-Major Order and initialized with data of a certain type and size then you can calculate the linear offset in memory of a certain element from the beginning of the array. The figure I created below shows how to calculate such an offset.
'Two-Dimensional' Arrays in Java vs C++
This is also how two dimensional arrays are usually stored in assembly, but you have enough control at that level to store them however you want. It is important to know if you are using Java, that despite being similar in many ways to C++, it does not actually support two-dimensional arrays. Probably the biggest characteristic of an array whether one-dimensional or two-dimensional is that it is stored in contiguous memory, all of it together. In Java what we have are arrays of arrays. It might sound nit-picky but it is not quite the same thing as the two-dimensional arrays in C/C++.
In Java, they do it similar to Row-Major Order. If we take the above example again. If we declare an integer array in java int A[3][4] it would initialize an array that we could reference as simply A, where A.length would return 3. A can be referenced as an array of references or 'pointers' to 3 different integer arrays. In Java it is worth mentioning that because these are references Java's arrays are inherently jagged. You can have different number of elements in each array, and even a null row. We could set A[2] = null; and it would delete the reference putting the integer array and the 4 ints up for garbage collection.
In the above array int A[3][4] in Java each of our three rows would have elements that were stored in contiguous memory, but the rows themselves are not stored in adjacent memory addresses. You cannot count on them to be anywhere related in memory:
Column-Major Order
There are several programming languages that store two-dimensional arrays in Column-Major Order rather than by row. This is popular for matrix operations so it can be found in the MATLAB computing language, Fortran the scientific computing language, and because of heavy matrix math in graphics operations, shading languages such as GLSL and HLSL use Column-Major Ordering.
Using Column-Major Order, columns instead of rows are stored in sequence. If we take our original array A,
{50,61,32,83},
{93,47,15,66}};
And we store the above array in Column Major order it becomes the following stored contiguously in adjacent cells of memory, with one column after the other as shown below:
If the array is stored like this, then the linear offset can be calculated as explained by the following figure I created with LaTeX below:
Graphics shader languages and the like use Column-Major Ordering because certain matrix operations require us to consider a matrix as sets of column vectors. This would be very slow if we had our matrices in storage in Row-Major Order. In fact the extra work needed if we have to consider a Row-Major Ordered array as a Column-Major Order array is that of transposing the matrix. This is relatively expensive and is hard to do in place for arrays with an unequal amount of rows and columns.
Column-Major Ordering in OpenGL Shader Language - GLSL In the open graphics library OpenGL the shader language called GLSL has arrays in the form of vectors and two-dimensional arrays in the form of square matrices. There are mat2, mat3, and mat4 data types, which store 2x2, 3x3, or 4x4 matrices respectively (float by default). Initialization in GLSL is mostly handled through constructors and it has pretty good flexibility about this. You can assume always though that initialization will be handled in Column-Major order. The following illustrates my point:
vec2 c = vec2(5.0, 6.0);
mat2 ac = mat2(a,c); // Stored in memory as [3.0,4.0,5.0,6.0] mat2 d = mat2(3.0,4.0,5.0,6.0); //two column same as ac
