-O levels measured

The optimisation level is the first flag anyone changes and the one whose effect is least often measured. This lesson takes a small matrix multiply, builds it six ways, and reports what each build costs on this machine: a forty-fold range between -O0 and -O3, a further fourfold gain from the intrinsic that replaces the loops, and an -Ofast that buys nothing here while promising to change the arithmetic.

The kernel

A 400 by 400 matrix product written as three loops, in the order that keeps the inner loop contiguous: the i loop runs over a and c down a column, and b(k,j) is a scalar for the whole of it. The arrays are filled from their indices, so every build computes on exactly the same numbers.

The file optimise.f90:

program optimise implicit none integer, parameter :: n = 400 real, allocatable :: a(:,:), b(:,:), c(:,:) integer :: i, j, k character(len=16) :: mode integer :: t0, t1, rate call get_command_argument(1, mode) allocate(a(n, n), b(n, n), c(n, n)) do j = 1, n do i = 1, n a(i, j) = real(i + j) / real(n) b(i, j) = real(i - j) / real(n) end do end do call system_clock(t0, rate) if (trim(mode) == 'intrinsic') then c = matmul(a, b) else c = 0.0 do j = 1, n do k = 1, n do i = 1, n c(i, j) = c(i, j) + a(i, k) * b(k, j) end do end do end do end if call system_clock(t1) print '(a,es15.6,a,es10.3,a)', 'trace = ', c(1, 1), ' matmul = ', real(t1 - t0) / real(rate), ' s' end program optimise

The printed value is one element of the result rather than the sum of all of them, because a sum would add its own cost to the measurement. It is enough to show that every build computed the same thing: the same seven digits appear in all six rows below.

What the levels do

-O0 is the default and means no optimisation: every source expression becomes the obvious instructions, every variable lives in memory, and the program is a direct translation. It is the build for a debugger, as lesson 113 said, and it is the baseline here.

-O1 keeps the code small and does the cheap transformations: constant folding, common subexpressions, values in registers. -O2 adds the ones that usually pay, including vectorisation, instruction scheduling and inlining of small procedures, and it is the level a release build should start from. -O3 adds more aggressive inlining, loop unrolling and transformations that can increase the size of the binary, and it is the level to measure rather than to assume.

-Ofast is -O3 plus -ffast-math, which lets the compiler reassociate floating-point expressions, assume no NaN or infinity, and ignore the IEEE rules of lesson 089. It can make a numerical program faster and can also make it wrong; the test build of lesson 114 must never use it.

The measurements

gfortran -Wall -Wextra -std=f2018 -O2 optimise.f90 -o opt2
./opt2
./opt2 intrinsic

trace =   1.338312E+02  matmul =  2.300E-02 s
trace =   1.338313E+02  matmul =  6.000E-03 s

Five runs of each build on this machine, the loop alone timed, so allocation and filling are outside the table:

buildminmedianfaster than -O0
-O0591 ms610 ms1.0
-O167 ms67 ms8.8
-O220 ms20 ms30
-O314 ms15 ms42
-O2, MATMUL intrinsic5 ms6 ms118
-Ofast14 ms15 ms42

GNU Fortran (Alpine 15.2.0) 15.2.0, Alpine Linux 3.24.3, an Intel Core i3-6006U at 2.00 GHz with 4 CPUs and a 3 MB cache; five runs per row, min and median. The container shares a host, and the -O0 row shows it: its five runs were 591, 609, 610, 628 and 651 ms, a spread of ten per cent that does not change the conclusion.

The first step from zero to one is the big one, thirty to one, because it removes the memory traffic of a build that keeps every intermediate in a variable. From -O2 to -O3 the gain is about 1.4 times, which is real and small: the loop is already vectorised at -O2, and -O3 mostly unrolls it. Nothing in the table is a law; a different kernel lands on different numbers, which is why the flags are worth measuring on the program you have.

The intrinsic is faster

MATMUL at -O2 takes 5 ms where the three loops at the same level take 20 ms, four times faster with no flags changed. The intrinsic does not go through the loops in the source: gfortran turns c = matmul(a, b) into a call to a library routine written for the shape of the matrices, blocked for the cache and vectorised, and its cost for a 400 by 400 product on this machine is a few milliseconds.

The lesson is not that the loops are wrong. It is that a numerical program should call the intrinsic for the operations the language has, and keep the hand-written loop for the cases it does not cover. The same argument applies to DOT_PRODUCT, SUM over a dimension and TRANSPOSE, all of which the compiler implements better than a loop a reader writes in five minutes. Lesson 041 is the tour of them.

-Ofast and what it promises

-Ofast produced 14 and 15 ms, the same as -O3 on this kernel, and the same printed value. That is the honest result for a loop whose arithmetic is simple: there was no reassociation to win. On a long dot product or a reduction it can be a different story, and the difference is that -ffast-math allows the compiler to change the order of additions, to assume that no value is a NaN and to treat 0.0 * x as zero even for an infinity x.

A program that checks ieee_is_nan, that relies on -0.0, or that compares two sums for equality can change its answer under that flag. The rule that follows is short: measure -O3 first, reach for -Ofast only when the profile says the arithmetic is the bottleneck, and never build the test suite with it.

Rules for optimisation flags

Build the release at -O2, measure -O3 on the real program, and keep the flags in the Makefile rather than in a comment. Call the intrinsic before writing the loop. Measure with the real size and the real data, five runs, and report min and median beside the machine and the compiler, because a number without them is not a measurement. And keep the test build of lesson 114 at the flags it needs, whatever the release build uses: the two builds exist for different questions.

Exercises

  1. Change the inner loop to run over j and measure all four levels again. Which level suffers most from the wrong order, and why?
  2. Build optimise.f90 at -O2 -march=native. Does the time change on this machine?
  3. Replace the inner statement with c(i, j) = c(i, j) + a(i, k) * b(k, j) + 1.0e-9 and compare -O3 with -Ofast. Do the printed values still agree?
  4. Compare sum(a), matmul(a, b) and the loops in one program. Which of the three is the intrinsic worth?

Questions

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

  1. What does -O0 mean?

    Answer

    No optimisation, every variable in memory

    It is the build for a debugger.

  2. How much faster was -O3 than -O0 on this kernel?

    Answer

    About 42 times

    591 ms against 14 ms, min of five runs.

  3. Which step gave the largest gain?

    Answer

    From -O0 to -O1

    Thirty to one, because -O0 keeps every value in memory.

  4. Why is MATMUL faster than the three loops?

    Answer

    It calls a library routine blocked for the cache and vectorised

    5 ms against 20 ms at the same -O2.

  5. What does -Ofast add to -O3?

    Answer

    -ffast-math, which changes the floating-point rules

    Reassociation, no NaN, no signed zero.

  6. Why must the test build never use -Ofast?

    Answer

    It may change results and hide the exceptions the tests look for

    The checks of lessons 114 and 115 depend on exact IEEE behaviour.

  7. What did -Ofast change on this kernel?

    Answer

    Nothing measurable: 14 and 15 ms like -O3

    There was no reassociation to win.

  8. What must a timing state beside the number?

    Answer

    The machine, the compiler, the flags and the number of runs

    A number without them is not a measurement.

  9. Which level should a release build start from?

    Answer

    -O2

    Then measure -O3 on the real program.

  10. Why does the page print c(1,1) instead of the sum of c?

    Answer

    The sum would add its own cost to the measured loop

    It still shows that every build computed the same thing.

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, with min and median stated.

Article author: Arthur Isaev

Banner image