Wednesday, July 4, 2012

Row Major Order vs Column Major Order in Computer Science

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:

int A[3][4] =  {{19,22,31,42},
                 {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:

19
22
31
42
50
61
32
83
93
47
15
66

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:

19
22
31
42
50
61
32
83
93
47
15
66
Here in Java the element that contains 42 would not be stored next to the element containing 50. 83 is not contiguous to 93.

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,

int A[3][4] =  {{19,22,31,42},
                 {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:

19
50
93
22
61
47
31
32
15
42
83
66

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 a = vec2(3.0, 4.0); // stored column vec [3.0,4.0]
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

9 comments:

Unknown said...

please change your wall color to some subtle shade.Its too loud and makes it difficult to concentrate on the screen.

Unknown said...

What do you mean by the wall color?

Unknown said...

what is the differece between row major and column major at the time of initialising

n said...

chup be amaniya..

Jason said...

Hey, thanks for writing this article. I'm taking a CS class on machine organization and this topic came up (row major vs column major ordering). I found your article helpful.

Unknown said...

Great insight on Matrices order. Thank you.

Unknown said...

thnks a lot........... and please change the black background its hard to read the text here.

Dhal said...

please resolve my doubt

in both of the representations we saw the difference is only in storing the data but what about the addresses of the cells in the 2D array?

LdB said...

It makes ZERO difference whether your matrix is ROW or COLUMN major, you set the GLSL matrix via glUniformMatrix4fv and that call carries a flag to transpose the matrix.

On WebGL and OpenGL ES you aren't allowed to use the flag so you simply transpose the matrix manually with a small bit of code (its trivial) just before you call glUniformMatrix4fv.

The code timing hit to change the order against the language like C and Java is huge as you correctly detailed. The small time lose to transpose the result matrix when sending it out is tiny in comparison.

The bottom line is work with whatever order your language wants and transpose it when passing it to OpenGL. This whole issue gets beaten up to more than what it is.

Transposing a matrix in C is as simple as declaring a union on the structure

typedef union {
// This is our normal ROW MAJOR C array
float m[4][4];
// OpenGL expects COLUMN MAJOR array
struct {
float m00, m01, m02, m03;
float m10, m11, m12, m13;
float m20, m21, m22, m23;
float m30, m31, m32, m33;
};
} mat4_t;

// The transpose call trivial it just shuffles the values
// The optimizer will work out the best way to do it
mat4_t transpose(mat4_t matrix) {
return mat4(
matrix.m00, matrix.m01, matrix.m02, matrix.m03,
matrix.m10, matrix.m11, matrix.m12, matrix.m13,
matrix.m20, matrix.m21, matrix.m22, matrix.m23,
matrix.m30, matrix.m31, matrix.m32, matrix.m33
);
}

Post a Comment