Row-major vs Column-major confusion

Question

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

Let’s 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.

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.

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.

Leave a Comment Cancel reply