Row-major vs Column-major confusion

Row-major vs Column-major confusion

I've been reading a lot about this, the more I read the more confused I get.

My understanding: In row-major rows are stored contiguously in memory, in column-major columns are stored contiguously in memory. So if we have a sequence of numbers [1, ..., 9] and we want to store them in a row-major matrix, we get:

|1, 2, 3|  |4, 5, 6|  |7, 8, 9|  

while the column-major (correct me if I'm wrong) is:

|1, 4, 7|  |2, 5, 8|  |3, 6, 9|  

which is effectively the transpose of the previous matrix.

My confusion: Well, I don't see any difference. If we iterate on both the matrices (by rows in the first one, and by columns in the second one) we'll cover the same values in the same order: 1, 2, 3, ..., 9

Even matrix multiplication is the same, we take the first contiguous elements and multiply them with the second matrix columns. So say we have the matrix M:

|1, 0, 4|   |5, 2, 7|   |6, 0, 0|  

If we multiply the previous row-major matrix R with M, that is R x M we'll get:

|1*1 + 2*0 + 3*4, 1*5 + 2*2 + 3*7, etc|  |etc.. |  |etc.. |  

If we multiply the column-major matrix C with M, that is C x M by taking the columns of C instead of its rows, we get exactly the same result from R x M

I'm really confused, if everything is the same, why do these two terms even exist? I mean even in the first matrix R, I could look at the rows and consider them columns...

Am I missing something? What does row-major vs col-major actually imply on my matrix math? I've always learned in my Linear Algebra classes that we multiply rows from the first matrix with columns from the second one, does that change if the first matrix was in column-major? do we now have to multiply its columns with columns from the second matrix like I did in my example or was that just flat out wrong?

Any clarifications are really appreciated!

EDIT: One of the other main sources of confusion I'm having is GLM... So I hover over its matrix type and hit F12 to see how it's implemented, there I see a vector array, so if we have a 3x3 matrix we have an array of 3 vectors. Looking at the type of those vectors I saw 'col_type' so I assumed that each one of those vectors represent a column, and thus we have a column-major system right?

Well, I don't know to be honest. I wrote this print function to compare my translation matrix with glm's, I see the translation vector in glm at the last row, and mine is at the last column...

This adds nothing but more confusion. You can clearly see that each vector in glmTranslate matrix represents a row in the matrix. So... that means that the matrix is row-major right? What about my matrix? (I'm using a float array[16]) the translation values are in the last column, does that mean my matrix is column-major and I didn't now it? tries to stop head from spinning

Answer by Y.C.Jung for Row-major vs Column-major confusion

You are right. it doesn't matter if a system stored the data in a row-major structure or a column-major one. It is just like a protocol. Computer : "Hey, human. I'm going to store your array this way. No prob. Huh?" However, when it comes to performance, it matters. consider the following three things.

1. most arrays are accessed in row-major order.

2. When you access memory, it is not directly read from memory. You first store some blocks of data from memory to cache, then you read data from cache to your processor.

3. If the data you want does not exist in cache, cache should re-fetch the data from the memory

When a cache fetches data from memory, locality is important. That is, if you store data sparsely in memory, your cache should fetch data from memory more often. This action corrupts your programs performance because accessing memory is far slower(over 100times!) then accessing cache. The less you access memory, the faster your program. So, this row-major array is more efficient because accessing its data is more likely to be local.

Answer by thurizas for Row-major vs Column-major confusion

I think you are mix up an implementation detail with usage, if you will.

Lets start with a two-dimensional array, or matrix:

    | 1  2  3 |      | 4  5  6 |      | 7  8  9 |  

The problem is that computer memory is a one-dimensional array of bytes. To make our discussion easier, lets group the single bytes into groups of four, thus we have something looking like this, (each single, +-+ represents a byte, four bytes represents an integer value (assuming 32-bit operating systems) :

   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-      |       |       |       |       |       |       |       |       |       -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-         \/                   \       /        one byte               one integer        low memory    ------>                          high memory  

Another way of representing

So, the question is how to map a two dimensional structure (our matrix) onto this one dimensional structure (i.e. memory). There are two ways of doing this.

1. Row-major order: In this order we put the first row in memory first, and then the second, and so on. Doing this, we would have in memory the following:

   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |  -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  

With this method, we can find a given element of our array by performing the following arithmetic. Suppose we want to access the $M_{ij}$ element of the array. If we assume that we have a pointer to the first element of the array, say ptr, and know the number of columns say nCol, we can find any element by:

     $M_{ij} = i*nCol + j$   

To see how this works, consider M_{02} (i.e. first row, third column -- remember C is zero based.

      $M_{02} = 0*3 + 2 = 2  

So we access the third element of the array.

2. Column-major ordering: In this order we put the first column in memory first, and then the second, and so or. Doing this we would have in memory the following:

   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   1   |   4   |   7   |   2   |   5   |   8   |   3   |   6   |   9   |  -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  

SO, the short answer - row-major and column-major format describe how the two (or higher) dimensional arrays are mapped into a one dimensional array of memory.

Hope this helps. T.

Answer by decltype_auto for Row-major vs Column-major confusion

Let's look at algebra first; algebra doesn't even have a notion of "memory layout" and stuff.

From an algebraic pov, a MxN real matrix can act on a |R^N vector on its right side and yield a |R^M vector.

Thus, if you were sitting in an exam and given a MxN Matrix and a |R^N vector, you could with trivial operations multiply them and get a result - whether that result is right or wrong will not depend on whether the software your professor uses to check your results internally uses column-major or a row-major layout; it will only depend on if you calculated the contraction of each row of the matrix with the (single) column of the vector properly.

To produce a correct output, the software will - by whatever means - essentially have to contract each row of the Matrix with the column vector, just like you did in the exam.

---

Thus, the difference between software that aligns column-major and software that uses row-major-layout is not what it calculates, but just how.

To put it more pecisely, the difference between those layouts with regard to the topcial single row's contraction with the column vector is just the means to determine

Where is the next element of the current row?  

• For a row-major-layout it's the element just in the next bucket in memory
• For a column-major-layout it's the element in the bucket M buckets away.

And thats it.

---

To show you how that column/row magic is summoned in practice:

You haven't tagged your question with "c++", but because you mentioned 'glm', I assume that you can get along with C++.

In C++'s standard library there's an infamous beast called valarray, which, besides other tricky features, has overloads of operator[], one of them can take a std::slice ( which is essentially a very boring thing, consisting of just three integer-type numbers).

This little slice thing however, has everything one would need to access a row-major-storage column-wise or a column-major-storage row-wise - it has a start, a length, and a stride - the latter represents the "distance to next bucket" I mentioned.

Answer by Matthew Gunn for Row-major vs Column-major confusion

Doesn't matter what you use: just be consistent!

Row major or column major is just a convention. Doesn't matter. C uses row major, Fortran uses column. Both work. Use what's standard in your programming language/environment.

Mismatching the two will !@#$ stuff up

If you use row major addressing on a matrix stored in colum major, you can get the wrong element, read past end of the array, etc...

Row major: A(i,j) element is at A[j + i * n_columns];  <---- mixing these up will  Col major: A(i,j) element is at A[i + j * n_rows];     <---- make your code fubar  

It's incorrect to say code to do matrix multiplication is the same for row major and column major

(Of course the math of matrix multiplication is the same.) Imagine you have two arrays in memory:

X = [x1, x2, x3, x4]    Y = [y1, y2, y3, y4]  

If matrices are stored in column major then X, Y, and X*Y are:

IF COL MAJOR: [x1, x3  *  [y1, y3    =   [x1y1+x3y2, x1y3+x3y4                 x2, x4]     y2, y4]        x2y1+x4y2, x2y3+x4y4]  

If matrices are stored in row major then X, Y, and X*Y are:

IF ROW MAJOR:  [x1, x2    [y1, y2     = [x1y1+x2y3, x1y2+x2y4;                  x3, x4]    y3, y4]       x3y1+x4y3, x3y2+x4y4];    X*Y in memory if COL major   [x1y1+x3y2, x2y1+x4y2, x1y3+x3y4, x2y3+x4y4]                if ROW major   [x1y1+x2y3, x1y2+x2y4, x3y1+x4y3, x3y2+x4y4]  

There's nothing deep going on here. It's just two different conventions. It's like measuring in miles or kilometers. Either works, you just can't flip back and forth between the two without converting!

Answer by Paul for Row-major vs Column-major confusion

Today there is no reason to use other then column-major order, there are several libraries that support it in c/c++ (eigen,armadillo,...). Furthermore column-major order is more natural, eg. pictures with [x,y,z] are stored slice by slice in file, this is column-major order. While in two dimension it may be confusing to choose better order, in higher dimension it is quite clear that column-major order is the only solution in many situation.

Authors of C created concept of arrays but perhaps they did not expect that somebody had used it as a matrices. I would be shocked myself if I saw how arrays are used in place where already everything was made up in fortran and column-major order. I think that row-major order is simply alternative to column-major order but only in situation where it is really needed (for now I don't know about any).

It is strangely that still someone creates library with row-major order. It is unnecessary waste of energy and time. I hope that one day everything will be column-major order and all confusions simply disappear.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72