Cache and data layout
A processor reads memory in cache lines of 64 bytes, and a loop that touches one field of a struct still brings the whole struct into the cache. The layout of the data decides how much of each line is useful.
The rules are small: keep together what is used together, separate what is not, and never let two threads write two variables that share a line. This lesson measures none of it with a timer; it shows the sizes and the sums, which are the facts the rules follow from.
Arrays of structs and structs of arrays
An array of particle_aos stores x, y and z next to each other for every particle, so summing x reads three floats per element and uses one. A struct of three arrays stores all the x together, and the same loop reads only what it uses.
The program sums the x coordinate in both layouts and prints 1000 and 1000, with the size of one AoS element: 12. The sums agree; the number of bytes that crossed the cache is what differs.
The trade is real: the SoA layout is worse when the code needs all three fields at once, and it complicates the interface. Choose it for the field a hot loop reads on its own, and leave the rest in the natural shape.
#include <iostream>
#include <vector>
struct particle_aos
{
float x;
float y;
float z;
};
struct particles_soa
{
std::vector<float> x;
std::vector<float> y;
std::vector<float> z;
};
int main()
{
const int count = 1000;
std::vector<particle_aos> aos(count, {1.0f, 2.0f, 3.0f});
particles_soa soa;
soa.x.assign(count, 1.0f);
soa.y.assign(count, 2.0f);
soa.z.assign(count, 3.0f);
float sum_aos = 0;
for (const particle_aos& particle : aos) {
sum_aos += particle.x;
}
float sum_soa = 0;
for (float value : soa.x) {
sum_soa += value;
}
std::cout << sum_aos << ' ' << sum_soa << ' ' << sizeof(particle_aos) << '\n';
}
g++ -std=c++23 -Wall -Wextra layout.cpp -o layout
./layout
1000 1000 12
The padding between the fields
A struct of a char and a double is 16 bytes: the double must start at an address divisible by 8, so seven bytes of padding follow the char, and the size is rounded up to the alignment of the type.
The program prints the two sizes and the offset of the double. Alignment is what lesson 094 measured in general; here it is the reason a struct of hot fields should not mix a char with a double if it can be avoided.
Reordering the members is free and often shrinks the struct by half. The compiler is not allowed to reorder them for you, because the order is part of what the program wrote.
#include <cstddef>
#include <iostream>
struct entry
{
char tag;
double value;
};
int main()
{
std::cout << sizeof(entry) << ' ' << offsetof(entry, tag) << ' ';
std::cout << offsetof(entry, value) << '\n';
}
g++ -std=c++23 -Wall -Wextra padding.cpp -o padding_cache
./padding_cache
16 0 8
Two counters on one cache line
False sharing is two threads writing two different variables that happen to sit on the same cache line. The variables are independent, and the hardware still moves the line between the cores on every write.
The program puts each counter in a struct aligned to 64 bytes, so the two are on separate lines, and two threads add 100000 to their own. The print is 100000, 100000 and 64, the size of one padded counter.
The fix costs memory: one line per counter instead of eight counters per line. It is worth it only for counters that are written often, which is exactly the case of a statistics block in a hot loop.
#include <atomic>
#include <iostream>
#include <thread>
struct aligned_counter
{
alignas(64) std::atomic<long> value{0};
};
int main()
{
aligned_counter first;
aligned_counter second;
std::thread a{[&] {
for (int i = 0; i < 100000; ++i) {
first.value.fetch_add(1, std::memory_order_relaxed);
}
}};
std::thread b{[&] {
for (int i = 0; i < 100000; ++i) {
second.value.fetch_add(1, std::memory_order_relaxed);
}
}};
a.join();
b.join();
std::cout << first.value << ' ' << second.value << ' ' << sizeof(aligned_counter) << '\n';
}
g++ -std=c++23 -Wall -Wextra -pthread sharing.cpp -o sharing
./sharing
100000 100000 64
The order of the loop
A two-dimensional array is stored row by row, so a loop over a row reads consecutive addresses and a loop down a column jumps a whole row at a time. Both compute the same sum, and only one of them uses each cache line fully.
The program sums a 100 by 100 matrix twice, once in row order and once in column order, and prints 990000 both times. The numbers agree because the sum is the same; the second loop pays for a cache miss on most of its reads.
The row-major loop is the one to write for a matrix stored this way. The column loop is sometimes necessary, and then blocking it into tiles of a few rows is the standard fix.
#include <iostream>
#include <vector>
int main()
{
const int size = 100;
std::vector<std::vector<int>> matrix(size, std::vector<int>(size));
for (int row = 0; row < size; ++row) {
for (int column = 0; column < size; ++column) {
matrix[row][column] = row + column;
}
}
long by_row = 0;
for (int row = 0; row < size; ++row) {
for (int column = 0; column < size; ++column) {
by_row += matrix[row][column];
}
}
long by_column = 0;
for (int column = 0; column < size; ++column) {
for (int row = 0; row < size; ++row) {
by_column += matrix[row][column];
}
}
std::cout << by_row << ' ' << by_column << '\n';
}
g++ -std=c++23 -Wall -Wextra order.cpp -o order_cache
./order_cache
990000 990000
The size that ignores padding
A static_assert that adds up the fields of a struct forgets the padding, and the compiler stops with the message that the assertion failed. It is the cheapest way to learn what the layout really is.
The program asserts that entry is 9 bytes, the char and the double with no padding. The compiler prints the failed assertion with the message that was written for it, and the real size is 16.
The assertion is also a useful test to keep: a struct that is written to a file or sent over a wire should have a size the program checks, and the check documents the assumption. The alternative is to read the value from sizeof at the point where it matters.
#include <cstddef>
struct entry
{
char tag;
double value;
};
static_assert(sizeof(entry) == 9, "entry is packed");
g++ -std=c++23 -Wall -Wextra assert.cpp -o assert_size
assert.cpp:9:29: error: static assertion failed: entry is packed
9 | static_assert(sizeof(entry) == 9, "entry is packed");
| ~~~~~~~~~~~~~~^~~~
assert.cpp:9:29: note: the comparison reduces to '(16 == 9)'
Exercises
- Add a second field to the shared counter and check that the two counters stay on separate lines.
- Swap the members of entry and print the new size and offsets.
- Change the matrix program to a vector of 10000 ints and compare the two loops with a timer.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is the difference between an array of structs and a struct of arrays?
Answer
The AoS keeps all fields of one element together, the SoA keeps one field of all elements together
The layout decides which bytes arrive together, and that is what the cache sees.
-
Why can a SoA be faster for a loop that reads one field?
Answer
Every byte of a cache line belongs to the field the loop uses
The AoS brings two unused floats per element into the cache, and those bytes are wasted.
-
What is false sharing?
Answer
Two threads write different variables that share one cache line
The variables are independent, and the line is still invalidated on every write.
-
How is false sharing avoided?
Answer
By padding each variable to a cache line, for example with alignas(64)
Separate lines mean separate coherence traffic, at the cost of memory.
-
What does this program print?
#include <iostream> #include <vector> struct particle { float x; float y; float z; }; int main() { std::vector<particle> values(1000, {1.0f, 2.0f, 3.0f}); float sum = 0; for (const particle& p : values) sum += p.x; std::cout << sum << ' ' << sizeof(particle); }Answer
1000 12
The loop sums 1000 ones, and one particle is three floats, 12 bytes.
-
What does this program print?
#include <atomic> #include <iostream> #include <thread> struct aligned { alignas(64) std::atomic<long> value{0}; }; int main() { aligned first, second; std::thread a([&] { for (int i = 0; i < 100000; ++i) first.value.fetch_add(1, std::memory_order_relaxed); }); std::thread b([&] { for (int i = 0; i < 100000; ++i) second.value.fetch_add(1, std::memory_order_relaxed); }); a.join(); b.join(); std::cout << first.value << ' ' << second.value << ' ' << sizeof(aligned); }Answer
100000 100000 64
Each thread increments its own counter, and the aligned struct is 64 bytes.
-
What does this program print?
#include <iostream> #include <vector> int main() { const int size = 100; std::vector<std::vector<int>> matrix(size, std::vector<int>(size)); for (int row = 0; row < size; ++row) for (int column = 0; column < size; ++column) matrix[row][column] = row + column; long by_row = 0, by_column = 0; for (int row = 0; row < size; ++row) for (int column = 0; column < size; ++column) by_row += matrix[row][column]; for (int column = 0; column < size; ++column) for (int row = 0; row < size; ++row) by_column += matrix[row][column]; std::cout << by_row << ' ' << by_column; }Answer
990000 990000
Both loops add the same 10000 entries, and the row and column sums of i + j are equal.
-
What is
sizeof(entry)for a struct with a char and a double?Answer
16
Seven bytes of padding follow the char and the size rounds up to the alignment of the double.
-
What does
alignas(64)on a member do?Answer
It makes the member start at an address divisible by 64
The alignment forces the member onto its own cache line in an array of such structs.
-
The build stops at this line. What does the compiler report?
struct entry { char tag; double value; }; static_assert(sizeof(entry) == 9, "entry is packed");Answer
static assertion failed: entry is packed
Padding makes the struct 16 bytes, and the assertion explains the failure in its message.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.
Article author: Arthur Isaev