Performance: layout and vectorisation
A Fortran array of two dimensions is stored one column after another, so the first index runs through consecutive addresses and the second jumps a whole column at a time. A loop that walks the array along the wrong index reads every cache line once per element and takes four times as long, and the compiler will not fix it for you. This lesson measures both orders on the same data, shows when the difference disappears, and then measures what the vectoriser adds.
One sum, two loop orders
The program fills an n by n array, sums it in a loop whose order is chosen by an argument, and repeats the sum so that a small array can be timed as well. The accumulator is real64 although the array is single precision, so the two orders produce the same number and the only difference left is time.
The file layout.f90:
program layout
implicit none
real, allocatable :: a(:,:), col(:)
real(8) :: s
integer :: i, j, k, n, reps
character(len=8) :: order, size_arg, reps_arg
integer :: t0, t1, rate
call get_command_argument(1, order)
call get_command_argument(2, size_arg)
call get_command_argument(3, reps_arg)
read (size_arg, *) n
read (reps_arg, *) reps
col = [(real(i), i = 1, n)]
allocate(a(n, n))
a = spread(col, 2, n)
call system_clock(t0, rate)
s = 0.0_8
do k = 1, reps
if (trim(order) == 'ij') then
do i = 1, n
do j = 1, n
s = s + real(a(i, j), 8)
end do
end do
else
do j = 1, n
do i = 1, n
s = s + real(a(i, j), 8)
end do
end do
end if
end do
call system_clock(t1)
print '(a,i0,a,i0,a,es15.6,a,es10.3,a)', 'n = ', n, ' reps = ', reps, ' sum = ', s, ' per pass = ', &
real(t1 - t0) / real(rate) / real(reps), ' s'
end program layout
Column-major order
a(i,j) of a 3 by 2 array is stored in this order: a(1,1), a(2,1), a(3,1), a(1,2), a(2,2), a(3,2). The first index is the one that moves fastest, which is why a loop with i innermost reads consecutive addresses and a loop with j innermost reads one element per cache line and returns to the same cache line only after three thousand others have been loaded after it.
The same rule decides how to pass an array: a procedure that takes a(:,:) and loops over its first index is writing the fast loop, and the transposed loop is the one that costs. It also decides how to store data: if the program always walks the rows, declare the array as a(ncol, nrow) and index it a(j,i), and the loop becomes contiguous without changing anything else.
The timings
gfortran -Wall -Wextra -std=f2018 -O2 layout.f90 -o layout
./layout ij 4000 1
./layout ji 4000 1
n = 4000 reps = 1 sum = 3.200800E+10 per pass = 1.410E-01 s
n = 4000 reps = 1 sum = 3.200800E+10 per pass = 3.300E-02 s
Five runs of each on this machine, the loop alone timed by system_clock, so allocation and filling are outside the measurement:
| array | order | min | median | speed |
|---|---|---|---|---|
| 4000 x 4000, 64 MB | i outer, j inner | 140.0 ms | 141.0 ms | 1.0 |
| 4000 x 4000, 64 MB | j outer, i inner | 32.0 ms | 33.0 ms | 4.3 |
| 800 x 800, 2.6 MB | i outer, j inner | 1.4 ms | 1.5 ms | 1.0 |
| 800 x 800, 2.6 MB | j outer, i inner | 1.3 ms | 1.3 ms | 1.1 |
Nineteen million elements and a 4.3 times difference: the wrong order is not a constant factor that a faster machine hides, it is the difference between reading every byte once and reading it once per element in the row. The machine is an Intel Core i3-6006U at 2.00 GHz with 4 CPUs and a 3 MB cache, GNU Fortran (Alpine 15.2.0) 15.2.0, -O2, no other flags; the container shares a host, and one of the five runs of the last section reached 106 ms where the other four were 68 and 69, which is the size of the noise here.
Why the small array shows nothing
The 800 by 800 case is 2.6 MB and fits in the 3 MB cache. Once the array is in the cache, a stride of 800 elements costs misses that are already paid for, and both orders run at about 1.3 ms. The 4000 by 4000 array is 64 MB, so every pass through a column comes back to a cache line that was evicted long ago, and the wrong order pays for the whole array on every row.
That is the rule to remember: loop order and memory layout matter when the working set is larger than the cache. A program with a 200 by 200 matrix will not be fixed by reordering its loops, and a program with a million rows will be dominated by them. The size at which it starts to matter is the size of the last-level cache, which /proc/cpuinfo reports as cache size : 3072 KB on this machine.
The vectoriser
The other half of a fast loop is SIMD: one instruction that adds four or eight numbers. gfortran vectorises at -O2 and can say where. The sum above is a reduction into an accumulator, which the compiler does not vectorise without -ffast-math, and the report for it names no loop:
gfortran -Wall -Wextra -std=f2018 -O2 -fopt-info-vec-optimized layout.f90 -o layout
(no output: no loop in the file was vectorised)
An elementwise loop is the case that does vectorise. The second program multiplies every element by two and adds one, in the contiguous order, and reports which line it vectorised:
The file elementwise.f90:
program elementwise
implicit none
real, allocatable :: a(:,:), b(:,:)
integer :: i, j, n
character(len=8) :: size_arg
integer :: t0, t1, rate
call get_command_argument(1, size_arg)
read (size_arg, *) n
allocate(a(n, n), b(n, n))
a = 1.5
call system_clock(t0, rate)
do j = 1, n
do i = 1, n
b(i, j) = 2.0 * a(i, j) + 1.0
end do
end do
call system_clock(t1)
print '(a,i0,a,es14.6,a,es10.3,a)', 'n = ', n, ' checksum = ', sum(b), ' loop = ', &
real(t1 - t0) / real(rate), ' s'
end program elementwise
gfortran -Wall -Wextra -std=f2018 -O2 -fopt-info-vec-optimized elementwise.f90 -o elementwise
elementwise.f90:14:10: optimized: loop vectorized using 16 byte vectors
Line 14 is the assignment, and sixteen bytes are four single-precision reals per instruction. The gain over the same source built with -fno-tree-vectorize is real and small, five runs of each:
| build, 4000 x 4000 | min | median |
|---|---|---|
| -O2, vectorised | 61.0 ms | 61.0 ms |
| -O2 -fno-tree-vectorize | 68.0 ms | 69.0 ms |
About eleven per cent, on a loop that reads 64 MB and writes 64 MB: the arithmetic is not the bottleneck, the memory is, so four values per instruction buy a tenth and no more. That is the usual outcome for a loop over a large array, and the reason a programmer measures instead of assuming that SIMD is the answer. A loop with more arithmetic per element, such as a matrix multiply, gains much more.
Rules for performance work
Measure first, with the real size and the real build; a benchmark on a small array says nothing about the program with the real one. Keep the fast index innermost, and check every loop that walks a two-dimensional array. Do not trust the optimiser to reorder a loop it cannot prove independent. Then build with -fopt-info-vec-optimized once, read which lines it vectorised, and stop worrying about the ones it did not: a reduction, a loop with a call, or a loop with a branch in it will not turn into SIMD by asking. The next lesson compares the optimisation levels themselves.
Exercises
- Swap the two indices in the array declaration and in every reference, keeping the loop order, and run both cases again. Which order is fast now?
- Time sum(a) instead of the loop and compare it with the fast loop. Which is faster, and why?
- Build the elementwise program with -O3 and with -O2 -march=native. Does the report change, and does the time?
- Run the 800 by 800 case with reps = 1 instead of 50. Why is the number useless?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Which index of a Fortran array runs through consecutive addresses?
Answer
The first one
Fortran stores column by column.
-
How much faster was the contiguous loop on the 64 MB array?
Answer
About 4.3 times
140 ms against 32 ms, min of five runs.
-
Why were both orders equal at 800 by 800?
Answer
The array fits in the 3 MB cache
Once the data is cached, the stride costs nothing.
-
What does
-fopt-info-vec-optimizedreport?Answer
The loops the compiler vectorised, with their lines
Here it names line 14 of the elementwise program.
-
Why was the sum loop not vectorised?
Answer
It is a reduction, which gfortran does not vectorise without -ffast-math
The report for layout.f90 names no loop.
-
How much did vectorisation gain on the elementwise loop?
Answer
About eleven per cent
Memory is the bottleneck, not the arithmetic.
-
Which flag turns the vectoriser off?
Answer
-fno-tree-vectorize
It is the switch the comparison used.
-
Why is the accumulator real64 while the array is single precision?
Answer
So the two loop orders give the same number and only the time differs
A single-precision accumulator changes the result with the order.
-
When does the loop order start to matter?
Answer
When the working set is larger than the cache
2.6 MB in a 3 MB cache shows nothing.
-
What must a benchmark use to say anything about the program?
Answer
The real size, the real build and several runs
Five runs, min and median, on the real data.
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 of 4 CPUs, on an Intel Core i3-6006U at 2.00 GHz with a 3 MB cache. Every timing is five runs of the same binary at -O2, with min and median stated.
Article author: Arthur Isaev