Loops, layout and the cache

The one comparison where the two languages differ by construction is the order of a two-dimensional array. Fortran stores a matrix column by column, C++ stores it row by row, and a loop written for one of them walks the memory of the other backwards. This page measures it: the same sixteen million doubles, summed in both orders, in both languages, five runs each.

The task

The array is one flat block of n * n doubles with n = 4000, which is 128 MB: far larger than the 3 MB cache of this machine, so every pass over a column with the wrong stride misses. The program sums every element twice, once with i in the inner loop and once with j, and prints the sum and the time of the loop alone. Filling the array and printing are outside the measurement.

In Fortran the element (i, j) of a column-major matrix is at i + (j-1)*n of the flat block, so the inner loop over i walks consecutive addresses. In C++ the element [i][j] of a row-major matrix is at i*n + j, so the inner loop over j does. The two programs are the same algorithm with the index order swapped, which is the whole subject of the page.

The Fortran program

The file layout.f90:

program layout_f use, intrinsic :: iso_fortran_env, only: dp => real64 implicit none integer :: n, i, j, count_rate, t0, t1 real(dp), allocatable :: a(:) real(dp) :: s character(len=8) :: order, arg call get_command_argument(1, order) call get_command_argument(2, arg) read (arg, *) n allocate(a(n * n)) a = 1.0_dp + real([(i, i = 1, n * n)], dp) call system_clock(t0, count_rate) s = 0.0_dp if (trim(order) == 'fast') then do j = 1, n do i = 1, n s = s + a(i + (j - 1) * n) end do end do else do i = 1, n do j = 1, n s = s + a(i + (j - 1) * n) end do end do end if call system_clock(t1) print '(a,a,a,i0,a,es22.14,a,es10.3,a)', 'fortran ', trim(order), ' n=', n, ' sum=', s, & ' time=', real(t1 - t0) / real(count_rate), ' s' end program layout_f

gfortran -Wall -Wextra -std=f2018 -O2 layout.f90 -o layout_f
./layout_f fast 4000

The C++ program

The file layout.cpp:

#include <chrono> #include <cstdio> #include <cstdlib> #include <string> #include <vector> int main(int argc, char** argv) { const std::string order = argc > 1 ? argv[1] : "fast"; const int n = argc > 2 ? std::atoi(argv[2]) : 4000; std::vector<double> a(static_cast<size_t>(n) * n); for (size_t i = 0; i < a.size(); ++i) { a[i] = 1.0 + static_cast<double>(i + 1); } const auto start = std::chrono::steady_clock::now(); double s = 0.0; if (order == "fast") { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { s += a[static_cast<size_t>(i) * n + j]; } } } else { for (int j = 0; j < n; ++j) { for (int i = 0; i < n; ++i) { s += a[static_cast<size_t>(i) * n + j]; } } } const auto stop = std::chrono::steady_clock::now(); const double secs = std::chrono::duration<double>(stop - start).count(); std::printf("c++ %s n=%d sum=%22.14e time=%10.3e s\n", order.c_str(), n, s, secs); return 0; }

g++ -std=c++23 -O2 -Wall -Wextra layout.cpp -o layout_cpp
./layout_cpp fast 4000

The timings

fast is the contiguous order in the language the program is written in, slow the other one. Five runs of each binary, the time printed by the program itself:

programorderminmedianslow / fast
Fortran, gfortran -O2fast (i inner)32.0 ms33.0 ms1.0
Fortran, gfortran -O2slow (j inner)177.0 ms179.0 ms5.5
C++, g++ -O2fast (j inner)32.7 ms32.9 ms1.0
C++, g++ -O2slow (i inner)180.0 ms180.7 ms5.5

GNU Fortran (Alpine 15.2.0) 15.2.0 and G++ (Alpine 15.2.0) 15.2.0, both at -O2, on an Intel Core i3-6006U at 2.00 GHz with 4 logical CPUs and a 3 MB cache, inside a Docker container that shares a host. Five runs per row, min and median; the slow Fortran rows were 177, 178, 179, 180 and 193 ms, which is the size of the noise here.

What the numbers say

The order is worth a factor of 5.5 and the language is worth about two per cent. On the contiguous order Fortran takes 32.0 ms and C++ 32.7 ms; on the strided order 177 and 180. Both compilers produce the same loop at -O2 because both are GCC 15.2.0, which is worth saying plainly: this is one compiler's back end, not a measurement of two independent implementations. A comparison against clang or against Intel's compilers would answer a different question, and neither compiler is in this image.

What the numbers do show is that a language does not make a loop fast. The Fortran program is not fast because it is Fortran: it is fast because the loop walks the array the way the array is stored. The same source in the other order is five times slower, and no compiler flag recovers it, which lesson 120 shows with the vectoriser switched off.

The two languages make the mistake in opposite directions, and that is the practical point. A programmer who moves from C++ to Fortran writes do i outside and do j inside, which is the slow order in Fortran; a programmer who moves the other way writes the same thing, which is the fast order in C++. The habit is invisible in the source and costs a factor of five, which is why both languages have a page about it and why the loop that matches the declaration is worth a comment.

When the size changes

The factor of 5.5 is a property of an array that does not fit in the cache. At n = 800 the block is 5.1 MB and still larger than the 3 MB cache; at n = 600 it is 2.9 MB and fits, and both orders finish in about a millisecond, too close to the clock's resolution to separate. The same measurement at three sizes is what makes the cache the explanation rather than the loop: a loop order cannot matter once the whole array is in the fastest memory, and nothing about the language changes between the three runs.

Both programs take n on the command line, so the experiment is one command each:

./layout_f fast 600
./layout_f slow 600
./layout_cpp fast 600
./layout_cpp slow 600

fortran fast n=600  sum=  6.48005400000000E+10  time= 2.000E-03 s
fortran slow n=600  sum=  6.48005400000000E+10  time= 2.000E-03 s
c++     fast n=600  sum=  6.48005400000000e+10  time= 9.277e-04 s
c++     slow n=600  sum=  6.48005400000000e+10  time= 9.886e-04 s

Exercises

  1. Declare the Fortran array as a(n, n) and index it a(i, j), then sum it with the same two loop orders. Which order is fast now, and why is it the same one as before?
  2. Change the fill to a = 1.0 in Fortran and to a.assign(n*n, 1.0) in C++. Do the timings move? What does the answer say about the cost of the fill?
  3. Build both at -O3 and run the slow order. Does the optimiser fix the stride, and by how much?
  4. Time a matrix-vector product with the matrix in both layouts. Which layout makes the vector contiguous for every row, and does the timing show it?

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and G++ (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