049. Fortran is column-major#

topic: Arrays

The order you loop through multidimensional arrays can have a big impact on speed. Fortran is column-major, meaning consecutive elements of a column are stored next to each other in memory, and you should loop through arrays in this order.

column-major.f90 | | 0 | Godbolt Compiler Explorer logo | Fortran logo#
program column_major
   use iso_fortran_env, only: wp => real64, int64

   integer, parameter :: m = 10000, n = m
   integer :: array(m, n)
   integer :: i, j, tot
   integer(int64) :: irate, tic, toc

   call system_clock(count_rate=irate)  ! # of clock ticks per second
   array = 0

   ! FASTER: Looping consecutively through columns
   call system_clock(count=tic)
   tot = 0
   do j = 1, size(array, dim=2)
      do i = 1, size(array, dim=1)
         ! Do something with array(i, j)
         tot = tot + array(i, j)
      end do
   end do
   call system_clock(count=toc)
   print "(g12.3)", (toc - tic) / real(irate, wp)

   ! SLOWER: Looping consecutively through rows
   call system_clock(count=tic)
   tot = 0
   do i = 1, size(array, dim=1)
      do j = 1, size(array, dim=2)
         ! Do something with array(i, j)
         tot = tot + array(i, j)
      end do
   end do
   call system_clock(count=toc)
   print "(g12.3)", (toc - tic) / real(irate, wp)

end program
Output1#
   0.225    
   0.398

Another way to think about this is to say that the first (leftmost) index (\(i\)) varies fastest when considering all elements of the array in storage order, as illustrated here, so you want that to be the innermost loop. The last (rightmost) index (\(j\) in 2-D), varies slowest, so we want this to be our outermost loop.

Tip

Different languages use different storage. For example, C is row-major, and this is what NumPy uses by default. Want NumPy arrays to be stored Fortran-style (column-major) instead? Specify order='F' when creating arrays!

Note

Although Fortran’s array storage order is column-major, semantically we still refer to the first dimension (dim=1 in the above program, first index (i) in the array(i, j) indexing) as the row dimension (with index \(i\)).

Note

This idea extends to arrays with more than two dimensions. In general, the loop nesting order for fastest access will be last dimension \(\to \ldots \to\) first dimension, as shown here. Also, the 1-D slice arr(:, 1, 1, ..., 1) is contiguous, like the column slice arr(:, 1) is for 2-D arrays.

Some further references:

1

Compiled using GNU Fortran (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 with no flags