---
title: 'Cache-Friendly Data Layout'
source: 'https://academia.sh/en/courses/cpp-templates/cache-friendly-data-layout'
course: 'Templates and Performance'
language: en
updated: '2026-10-21T05:02:45+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - 'Explains how the cache line and locality determine the access cost of a loop.'
    - 'Builds and compares the array of structures and structure of arrays layouts for the same data.'
    - 'Counts non-contiguous jumps in an access pattern by pointer difference.'
    - 'Says which access pattern a data layout suits.'
---

# Cache-Friendly Data Layout

The cache line, spatial and temporal locality, array of structures versus structure of arrays, row order and column order, false sharing, and counting how many non-contiguous jumps a data layout leaves.

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.

```cpp
// 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 `int`s, 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 `int`s 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`.

```cpp
// 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.

```cpp
// 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.

```cpp
// 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;
}
```

```text
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.