📂Programing

Row-major and Column-major of 2D Arrays

Overview ¹

This document explains row-major and column-major order of matrices or 2-dimensional arrays. Simply put, whether row-major or column-major, it’s about the preferred direction of reading through an array.

Differences

According to Wikipedia, some programming languages and libraries are designed with their native preference for either row or column-major order as follows:

• Row-major: A method where the rows of a matrix are accessed first, reading from left to right.

  • C/C++/Objective-C
  • PL/I
  • Pascal
  • Speakeasy
  • SAS
  • Rasdaman

• Column-major: A method where the columns of a matrix are accessed first, reading from top to bottom.

  • Fortran
  • MATLAB
  • GNU Octave
  • S-Plus
  • R
  • Julia
  • Scilab

Why the Difference

Let’s intuitively understand why there might be difficulties in reading matrices in a non-preferred way, rather than from a computer science perspective². Imagine we prefer reading matrices column-major.

$$ \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} $$

Given the matrix above, because we prefer column-major, we can comfortably read it as $1,2,3,4,5,\cdots$. However, if we are forced to read row-major, we would be reading in an unnatural order as $1,4,7,2,5,\cdots$.

From the computer’s perspective, logical arrays are allocated in physical memory, and we read matrix as instructed, but there’s a big difference between reading straightforwardly and mixing rows and columns.

Why Row-major

Imagine writing a program to print a given matrix on the screen. Logically, you would write from the top line to the right, then newline and proceed to the next line. Thus, most programming languages opt for row-major as it naturally aligns with writing on the console from top to bottom.

Why Column-major

Fortran, MATLAB, R, Julia…

The lineup is impressive. It’s evident at a glance that languages focused on science and computation adopt column-major. Considering that matrices originated from the abbreviation of simultaneous equations, it’s natural. There are no mathematicians who read matrices horizontally. Naturally, reading along rows from top to bottom, or in other words, column-major, is the standard.

Performance Comparison

julia> size = 10^4
10000

julia> M = rand(size, size);

A benchmark was conducted based on the Julia language. The two code fences below show that by merely changing the order of rows and columns, the execution time differed significantly: 36 seconds for reading rows first compared to 20 seconds for reading columns first in column-major Julia, verifying a dramatic performance difference of almost twice the speed.

julia> X = zeros(size, size);

julia> @time for i in 1:size
           for j in 1:size
               X[i,j] = (M[i,j] + 1)
           end
       end
 36.088533 seconds (489.82 M allocations: 8.789 GiB, 4.64% gc Time)

julia> X = zeros(size, size);

julia> @time for j in 1:size
           for i in 1:size
               X[i,j] = (M[i,j] + 1)
           end
       end
 19.936053 seconds (489.82 M allocations: 8.789 GiB, 7.59% gc Time)