Cache-Friendly Data Layout

The previous two lessons measured the cost of concurrency: how many times a lock is acquired, how many synchronization points a publish asks for. This lesson returns to a single thread, because how data is laid out in memory changes the cost even without concurrency. The processor does not move memory byte by byte; it moves it in fixed-size blocks called cache lines. When you touch one value, the neighboring bytes around it come into near memory along with it. If you will soon touch some of those neighbors, this is a good trade; if you will not, most of the moved bytes were wasted. The question the course measures is the same again: where does a mechanism move the cost? The answer in this lesson is the kind memory. We do not print the line size or addresses, because both depend on the machine; the measure counts whether two values that a loop touches one after the other sit side by side in memory.

Locality

There are two kinds of locality. Spatial locality is the expectation that a program that touches a value will soon touch its neighbor too; walking the elements of an array in order is an example. Temporal locality is the expectation that a program that touches a value will soon touch the same value again; a loop variable or a running total is an example. The cache line rewards spatial locality: values that sit side by side in the line arrive in a single transfer.

In multidimensional arrays the same idea appears as row order and column order. In C++, int table[rows][columns] is in row order: the elements of the same row are contiguous. An inner loop that walks along rows obeys spatial locality; an inner loop that walks along columns skips a whole row length at every step. We show this difference below with a jump count.

Array of Structures and Structure of Arrays

A set of points is stored with three fields, x, y and z. The first layout is the array of structures (AoS): each point is a structure and all the points sit in one array. In memory the order is x0 y0 z0 x1 y1 z1 .... The second layout is the structure of arrays (SoA): each of the three fields sits in its own array. In memory the order is x0 x1 x2 ... y0 y1 y2 ... z0 z1 z2 ....

A loop that walks only the x field skips the other two fields at every step in the array of structures; the x values that follow one another are not contiguous, with y and z between them. In the structure of arrays the x values are side by side. The header below builds the two layouts and the measure. The measure records, in order, the addresses a loop touches and checks whether the distance between two consecutive touches is exactly one int. No address is printed; only the count comes out.

// data_layout.hpp — two data layouts and a measure that records the touches
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>

constexpr int POINT_COUNT = 4;

struct Point {
    int x, y, z;
};

struct PointArray {
    std::array<Point, POINT_COUNT> points;
};

struct FieldArrays {
    std::array<int, POINT_COUNT> x, y, z;
};

inline PointArray build_array_of_structures() {
    PointArray d;
    for (int i = 0; i < POINT_COUNT; ++i) d.points[i] = Point{i, 10 + i, 20 + i};
    return d;
}

inline FieldArrays build_structure_of_arrays() {
    FieldArrays d;
    for (int i = 0; i < POINT_COUNT; ++i) {
        d.x[i] = i;
        d.y[i] = 10 + i;
        d.z[i] = 20 + i;
    }
    return d;
}

inline bool is_contiguous(const int* before, const int* after) {
    auto a = reinterpret_cast<std::uintptr_t>(before);
    auto b = reinterpret_cast<std::uintptr_t>(after);
    return b - a == sizeof(int);
}

struct Jumps {
    int skipped = 0;
    int total = 0;
};

inline Jumps tally(const std::vector<const int*>& touches) {
    Jumps j;
    for (std::size_t i = 0; i + 1 < touches.size(); ++i) {
        ++j.total;
        if (!is_contiguous(touches[i], touches[i + 1])) ++j.skipped;
    }
    return j;
}

The contiguity test converts the pointers to integers and compares the difference with sizeof(int). Subtracting pointers of two separate arrays would be undefined; converting to integers is necessary for this reason. skipped counts the non-contiguous jumps and total counts all jumps.

Row Order and Column Order: Counting Jumps

Put the same idea into numbers on a single flat array. A table of four rows and four columns sits in row order in a single array of sixteen elements: the expression m[r * 4 + c] is element c of row r. Consider two nested loops. In the first, the outer loop runs over rows and the inner loop over columns; consecutive touches are side by side in the array. In the second, the outer loop runs over columns and the inner loop over rows; consecutive touches skip one row length, that is four ints, at every step, and go back when the column changes.

The point to notice is that sixteen touches produce fifteen jumps: a jump is the step between two consecutive touches. In row order none of the fifteen jumps skips. In column order all fifteen skip, because two consecutive touches are either four ints ahead or behind. A jump that goes backward is not counted as contiguous either: the contiguity test requires the difference to be exactly one int.

// matrix.hpp — two traversal orders over a flat array of four rows and four columns
#pragma once
#include <array>

#include "data_layout.hpp"

constexpr int ROWS = 4;
constexpr int COLUMNS = 4;

inline Jumps row_order_tally(const std::array<int, ROWS * COLUMNS>& m) {
    std::vector<const int*> touches;
    for (int r = 0; r < ROWS; ++r)
        for (int c = 0; c < COLUMNS; ++c) touches.push_back(&m[r * COLUMNS + c]);
    return tally(touches);
}

inline Jumps column_order_tally(const std::array<int, ROWS * COLUMNS>& m) {
    std::vector<const int*> touches;
    for (int c = 0; c < COLUMNS; ++c)
        for (int r = 0; r < ROWS; ++r) touches.push_back(&m[r * COLUMNS + c]);
    return tally(touches);
}

This is the same tally function as in the previous section; there is no new measure, only two new access patterns. In a real table this difference turns into the chance that every skipping jump brings in a different cache line. If a row of the table is longer than a cache line, every skipping jump lands on a different cache line, so for large tables fitting the loop order to the layout of the data is the first place to look.

False Sharing and alignas

Data layout does not concern only a single thread. If two threads write to two independent variables but the two variables land on the same cache line, one thread’s write invalidates the other’s line, and the two threads keep emptying each other’s cache. This is called false sharing: the variables are not shared, but the line is. The code is correct and there is no data race; each write only forces the ownership of the line to change hands. This is a different cost from the waiting points in the lesson on locks or atomics: no synchronization is visible in the code, and the cost comes from the layout.

The fix is to separate the fields the threads write onto different lines. In C++ the alignas specifier does this: if a type is given alignas(N), the objects of that type are placed at addresses that are multiples of N, and the size of the type is rounded up to a multiple of N. Two consecutive Aligned elements are therefore at least N bytes apart.

Here the number 64 is an assumption: on common processors the cache line is this size, but it is not a constant the language states and it may not be right on every hardware. For this reason we name the number and keep it in one place, and the measurement uses that assumption, not the real line. The static_assert below also checks at compile time that the alignment really is the requested value. The count looks at whether the difference between the addresses of two consecutive elements is smaller than the assumed line size; if it is smaller, the two are candidates to land on the same line.

// sharing.hpp — packed and aligned counters, counting same-line candidates
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
#include <thread>
#include <vector>

constexpr std::size_t LINE_ASSUMPTION = 64;  // assumption: common processor cache line

struct Packed {
    long value = 0;
};

struct alignas(LINE_ASSUMPTION) Aligned {
    long value = 0;
};

static_assert(alignof(Aligned) == LINE_ASSUMPTION, "alignment is not the requested value");
static_assert(sizeof(Aligned) % LINE_ASSUMPTION == 0, "size was not rounded to the line");

template <typename T>
int same_line_candidates(const std::array<T, 4>& items) {
    int candidates = 0;
    for (std::size_t i = 0; i + 1 < items.size(); ++i) {
        auto a = reinterpret_cast<std::uintptr_t>(&items[i]);
        auto b = reinterpret_cast<std::uintptr_t>(&items[i + 1]);
        if (b - a < LINE_ASSUMPTION) ++candidates;
    }
    return candidates;
}

template <typename T>
long four_writers(std::array<T, 4>& items) {
    std::vector<std::thread> workers;
    for (int t = 0; t < 4; ++t) {
        workers.emplace_back([&items, t] {
            for (int k = 0; k < 10000; ++k) ++items[t].value;
        });
    }
    for (auto& worker : workers) worker.join();
    long total = 0;
    for (const auto& e : items) total += e.value;
    return total;
}

Each thread writes only to its own element; both versions are therefore correct and give the same total. For long elements, which are eight bytes on this platform, same_line_candidates counts three of the three pairs, and for the sixty-four-byte aligned elements it counts none of the three. What is counted here is not a real transfer but the situation the layout may cause.

Measurement: x Field Only, Table and Counters

The program below runs three measurements together and prints the counter of each.

// layout_measurement.cpp — x field only and three fields together
#include <array>
#include <iostream>
#include <vector>

#include "data_layout.hpp"
#include "matrix.hpp"
#include "sharing.hpp"

int main() {
    PointArray aos = build_array_of_structures();
    FieldArrays soa = build_structure_of_arrays();

    std::vector<const int*> aos_x;
    std::vector<const int*> soa_x;
    int aos_total = 0;
    int soa_total = 0;
    for (int i = 0; i < POINT_COUNT; ++i) {
        aos_x.push_back(&aos.points[i].x);
        aos_total += aos.points[i].x;
        soa_x.push_back(&soa.x[i]);
        soa_total += soa.x[i];
    }
    Jumps a = tally(aos_x);
    Jumps s = tally(soa_x);
    std::cout << "x field only memory aos=" << a.skipped << "/" << a.total
              << " soa=" << s.skipped << "/" << s.total << "\n";
    std::cout << "sum x aos=" << aos_total << " soa=" << soa_total << "\n";

    std::array<int, ROWS * COLUMNS> table{};
    for (int i = 0; i < ROWS * COLUMNS; ++i) table[i] = i;
    Jumps row = row_order_tally(table);
    Jumps column = column_order_tally(table);
    std::cout << "row and column order memory row=" << row.skipped << "/"
              << row.total << " column=" << column.skipped << "/" << column.total << "\n";

    std::array<Packed, 4> packed{};
    std::array<Aligned, 4> aligned{};
    std::cout << "false sharing memory packed=" << same_line_candidates(packed) << "/3"
              << " aligned=" << same_line_candidates(aligned) << "/3\n";
    long packed_total = four_writers(packed);
    long aligned_total = four_writers(aligned);
    std::cout << "false sharing result packed=" << packed_total
              << " aligned=" << aligned_total << "\n";

    std::vector<const int*> aos_three;
    std::vector<const int*> soa_three;
    for (int i = 0; i < POINT_COUNT; ++i) {
        aos_three.push_back(&aos.points[i].x);
        aos_three.push_back(&aos.points[i].y);
        aos_three.push_back(&aos.points[i].z);
        soa_three.push_back(&soa.x[i]);
        soa_three.push_back(&soa.y[i]);
        soa_three.push_back(&soa.z[i]);
    }
    Jumps au = tally(aos_three);
    Jumps su = tally(soa_three);
    std::cout << "three fields together memory aos=" << au.skipped << "/" << au.total
              << " soa=" << su.skipped << "/" << su.total << "\n";
    return 0;
}

x field only memory aos=3/3 soa=0/3
sum x aos=6 soa=6
row and column order memory row=0/15 column=15/15
false sharing memory packed=3/3 aligned=0/3
false sharing result packed=40000 aligned=40000
three fields together memory aos=0/11 soa=11/11

CP13. The first line shows that the loop walking only the x field made three jumps over four elements in both layouts, that in the array of structures all three are non-contiguous, and that in the structure of arrays none skips: aos=3/3, soa=0/3. The second line confirms that the two layouts give the same total, so the difference is not in the result but in the position of the touches in memory.

CP14. The count gives only the non-contiguous jumps, not the line size: a small set of four points may fit in a single cache line, and every skipped jump may not cause a new line transfer. For this reason 3/3 is not a transfer count but the direction in which the layout breaks contiguity; the real transfer count gains meaning as the set grows and depends on the machine.

CP15. The third line shows that in the table of four rows and four columns, walking in row order makes none of the fifteen jumps skip (row=0/15), while walking in column order makes all of them skip (column=15/15). The two loops touched the same sixteen elements; only the order was different. The jumps that go backward in column order also entered the count, because the contiguity test accepts only a forward step of exactly one int.

CP16. In the fourth line, the packed array, made of long elements that are eight bytes on this platform, made all three consecutive pairs same-line candidates (packed=3/3); the array given alignas made none of them (aligned=0/3). This number is not a real cache line measurement; it rests on the LINE_ASSUMPTION assumption. If the assumption is wrong, the count is wrong too; for this reason we named the value and checked with static_assert that the alignment is the requested value.

CP17. In the fifth line both versions gave 40000. Because each thread wrote only to its own element there was no data race, and the layout did not change the result. alignas does not change correctness; it changes where the cost is paid, and this change is not visible in the output and is the part this lesson deliberately does not measure.

The Bounding Measurement

The layout this lesson measured, the advantage of the structure of arrays, holds in a loop that touches only one field. The last line measures the same two layouts this time with a loop that reads three fields together: for each point x, y, z are read in order. Here the table turns around: in the array of structures the three fields of a point are side by side, and so are the fields of the next point, so none of the eleven jumps skips: aos=0/11. In the structure of arrays every read jumps to a different array: soa=11/11.

What decides contiguity is not the data but the access pattern. The same data can sit in the best layout for one pattern and the worst for another. For this reason there is no rule such as “the structure of arrays is faster” or “the array of structures is more natural”. The question is which fields the loop touches together; if the fields are read together, the array of structures keeps contiguity, and if they are read separately, the structure of arrays does.

Summary

• The mechanism this lesson measured moves the cost to the kind memory: a data layout determines how much of what a loop touches one after another it leaves contiguous; the measure is not time but the number of non-contiguous jumps.
• The cache line moves memory in blocks; spatial locality rewards the neighbor, and temporal locality rewards touching the same value again.
• The array of structures keeps the fields contiguous together, and the structure of arrays keeps them contiguous separately; the access pattern decides which one suits.
• x field only left aos=3/3 in the array of structures and soa=0/3 in the structure of arrays; three fields together left aos=0/11 and soa=11/11 in the same two layouts.
• Walking in row order left row=0/15 skips and walking in column order left column=15/15; the order must fit the layout of the data.
• False sharing is independent variables landing on the same line; the fix is to give each thread its own line, with alignas; the line size here is an assumption.

Next Step

In this lesson we assumed we knew which layout suits which pattern, but in a real program we cannot know which layout to touch without knowing which loop is hot. The next lesson opens profiling: with the question of where a counter finds the hot spot, we will build an instrumented profiler.