Column-major order and array memory

A Fortran array is a block of memory read in one fixed order: the first index moves fastest, then the second, and so on. Everything an array does follows from that order, from the value print shows to the speed of a loop, and the programs that run slowly usually disagree with it somewhere. This lesson makes the order visible and then measures what it costs to fight it.

The first index moves fastest

For a rank-two array m(nr, nc) the element m(i, j) sits at position i + (j - 1) * nr: the first index is the fast one, so the whole first column comes before the first element of the second column. The storage is the same run of values a vector would have, which is why reshape needed no copying rule beyond memory order.

The file layout.f90 prints a two by three matrix in three ways:

program layout_demo implicit none integer :: m(2, 3), i, j m = reshape([1, 2, 3, 4, 5, 6], [2, 3]) print *, "m :", m print *, "m(1,:) :", m(1, :) print *, "m(:,1) :", m(:, 1) do j = 1, 3 do i = 1, 2 print '(a,i1,a,i1,a,i3)', "m(", i, ",", j, ") =", m(i, j) end do end do end program layout_demo

gfortran -Wall -Wextra -std=f2018 layout.f90 -o layout
./layout

m : 1 2 3 4 5 6
m(1,:) : 1 3 5
m(:,1) : 1 2
m(1,1) = 1
m(2,1) = 2
m(1,2) = 3
m(2,2) = 4
m(1,3) = 5
m(2,3) = 6

The loop that prints one element per line runs j outside and i inside, which is memory order, and the values come out 1 to 6 with no jump. Swap the two loops and the same values appear in another sequence; the matrix is the same, only the reading changed.

Rows and columns

The row m(1, :) is 1 3 5, three elements that are two apart in memory, and the column m(:, 1) is 1 2, two adjacent elements. A column is contiguous; a row is not.

That asymmetry is the whole subject. An array section that walks a row reads every second value of the block, which the hardware handles by fetching a whole cache line for one number; a section that walks a column reads one line after another and uses every value it fetched. The difference does not show in a small matrix, and it does in a large one.

The loop order that matters

A loop nest should walk the array in memory order, so the innermost loop must be the one over the first index. The two nests below compute the same sum, once with i inside and once with j inside:

do j = 1, n do i = 1, n s = s + m(i, j) * v(i) end do end do do i = 1, n do j = 1, n s = s + m(i, j) * v(i) end do end do

The first walks down a column and is contiguous; the second walks across a row and jumps n elements at every step. Both are correct Fortran, and a compiler is not required to exchange the loops for the programmer.

A measured timing

The file timing.f90 times both nests on a 2000 by 2000 matrix, ten repetitions each, and prints the average of the ten in milliseconds:

program timing_demo implicit none integer, parameter :: n = 2000, reps = 10 real, allocatable :: m(:, :), v(:) integer :: i, j, r, t0, t1, rate real :: s allocate(m(n, n)) allocate(v(n)) m = 1.0 v = 2.0 call system_clock(count_rate=rate) s = 0.0 call system_clock(t0) do r = 1, reps do j = 1, n do i = 1, n s = s + m(i, j) * v(i) end do end do end do call system_clock(t1) print '(a,f8.1,a)', "i inner, contiguous : ", real(t1 - t0) / rate * 1000.0 / reps, " ms" call system_clock(t0) do r = 1, reps do i = 1, n do j = 1, n s = s + m(i, j) * v(i) end do end do end do call system_clock(t1) print '(a,f8.1,a)', "j inner, strided : ", real(t1 - t0) / rate * 1000.0 / reps, " ms" print '(a,f10.1)', "checksum : ", s end program timing_demo

gfortran -Wall -Wextra -std=f2018 -O2 timing.f90 -o timing
for i in 1 2 3 4 5; do ./timing; done

i inner, contiguous : 8.7 ms
j inner, strided : 33.1 ms
checksum : 33554432.0
i inner, contiguous : 8.7 ms
j inner, strided : 27.5 ms
checksum : 33554432.0
i inner, contiguous : 8.6 ms
j inner, strided : 30.4 ms
checksum : 33554432.0
i inner, contiguous : 9.1 ms
j inner, strided : 29.2 ms
checksum : 33554432.0
i inner, contiguous : 8.9 ms
j inner, strided : 36.9 ms
checksum : 33554432.0

Five runs: the contiguous nest takes 8.7, 8.7, 8.6, 9.1 and 8.9 ms, with a minimum of 8.6 ms and a median of 8.7 ms; the strided nest takes 33.1, 27.5, 30.4, 29.2 and 36.9 ms, with a minimum of 27.5 ms and a median of 30.4 ms. The checksum is the same in every run, which is the proof that the two nests computed the same thing.

The machine and the flags

The numbers above were measured on the machine this course is written on: 4 cores (nproc), CPU Intel(R) Core(TM) i3-6006U CPU @ 2.00GHz from /proc/cpuinfo, GNU Fortran (Alpine 15.2.0) 15.2.0, Alpine Linux 3.24.3 (x86_64) in a Docker container, with -O2 and no other flags. The spread between the runs comes from the shared container host, and the ratio between the two nests is the part that repeats.

The timing lesson that follows this one changes the optimisation level and the vectoriser; this one is about the order of the indices, which no flag can repair. The rule is short: walk the first index in the innermost loop, and write m(i, j) with i changing fastest.

Exercises

  1. Swap the two loops of the element print in layout.f90. In which order do the six pairs come out now?
  2. Print m(2, :) and m(:, 3) for the matrix. Which one is contiguous?
  3. Time the contiguous nest with n = 500 instead of 2000. How do the two times compare with the ones on the page?
  4. Change the array to m(n, n) with the two indices exchanged and keep the loop order. Does the fast nest become the slow one?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Which index of a Fortran array moves fastest in memory?

    Answer

    The first one

    Fortran is column-major: the first index varies fastest.

  2. What does print *, m show for a matrix?

    Answer

    The elements in memory order, column by column

    A list-directed print walks the storage order.

  3. Which section of a two by three matrix is contiguous in memory?

    Answer

    m(:, 1)

    A column occupies adjacent elements; a row is strided.

  4. Which loop nest walks a matrix in memory order?

    Answer

    The outermost loop over the last index and the innermost over the first

    The innermost loop must vary the fastest-moving index.

  5. What does this program print? program p implicit none integer :: m(2, 3) m = reshape([1, 2, 3, 4, 5, 6], [2, 3]) print *, m(1, :) end program p

    Answer

    1 3 5

    The first row holds the first index fixed and walks the second.

  6. Where does m(i, j) of a matrix m(nr, nc) sit in memory?

    Answer

    At position i + (j - 1) * nr

    The first index runs fastest, so each column adds nr positions.

  7. Why is a strided walk slower than a contiguous one?

    Answer

    Each step touches a new cache line and uses only part of it

    The hardware fetches whole cache lines, and a stride wastes them.

  8. Which flags were used for the timing on this page?

    Answer

    gfortran -Wall -Wextra -std=f2018 -O2

    The command block on the page shows the flags of the build that was timed.

  9. What is the median of the five contiguous times on the page?

    Answer

    8.7 ms

    Sorted they are 8.6, 8.7, 8.7, 8.9 and 9.1, so the middle value is 8.7.

  10. What proves that the two loop nests computed the same value?

    Answer

    The printed checksum is identical in every run

    The checksum accumulates the same sum in both nests.

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container, on 4 cores of an Intel(R) Core(TM) i3-6006U CPU @ 2.00GHz.

Article author: Arthur Isaev

Banner image