Step 4 of 5

False sharing and alignment

Caches work on whole lines, and that has a nasty consequence for threads. When one core writes to a cache line, the cache coherence protocol invalidates that line in every other core's cache. If two threads keep writing to different variables that happen to sit in the same line, the line bounces between their cores on every write, even though the threads never touch each other's data. That's false sharing.

struct Counters { std::atomic<long long> a{0}; std::atomic<long long> b{0}; };   // 8 bytes apart: one line
// thread 1 increments counters.a 20 million times; thread 2 increments counters.b

Two threads doing exactly that took about 420 ms. With each counter moved onto its own cache line, the same work took about 190 ms (typical of several runs, GCC -O2, 4-core Linux machine): more than twice as fast, with no change to the logic.

Padding with alignas

alignas(64) makes the compiler start a type (or a variable) at an address that's a multiple of 64, and rounds its size up to match, so two of them can never share a line:

#include <atomic>
#include <iostream>

struct Counters {
    std::atomic<long long> a{0};
    std::atomic<long long> b{0};
};

struct alignas(64) Padded {
    std::atomic<long long> n{0};
};

struct PaddedCounters {
    Padded a;
    Padded b;
};

int main() {
    Counters c;
    PaddedCounters p;
    auto gap = [](const void* x, const void* y) {
        return static_cast<const char*>(y) - static_cast<const char*>(x);
    };
    std::cout << "plain:  " << sizeof(Counters) << " bytes, counters " << gap(&c.a, &c.b) << " bytes apart\n";
    std::cout << "padded: " << sizeof(PaddedCounters) << " bytes, counters " << gap(&p.a, &p.b) << " bytes apart\n";
}

plain:  16 bytes, counters 8 bytes apart
padded: 128 bytes, counters 64 bytes apart

• The padding costs memory (128 bytes for two 8-byte counters), so use it only for data that different threads write often: per-thread counters, the head and tail indexes of a concurrent queue, the slots of a thread pool.
• C++17's std::hardware_destructive_interference_size (in <new>) names the right distance for the platform. GCC's and Clang's libraries provide it, and it's 64 on x86, but it's a compile-time guess about the processor the program will run on. Many projects simply write 64 (or 128 for Apple's chips).
• The simpler cure is often not to share at all: give each thread its own counter in a local variable and combine them once at the end, as the threads module showed.

Your task

Write PaddedCounter, aligned to 64 bytes and holding a std::atomic<long long> value, with add(n) (a relaxed fetch_add, since nobody reads it until the threads are done) and get(). Then write Stats holding two of them, hits and misses, so the two can never share a cache line.

Challenge 2

Write struct alignas(64) Slot { int value; }, then bool same_line(const void* a, const void* b), true when both addresses are in the same 64-byte cache line, and std::size_t lines_spanned(const void* p, std::size_t bytes), how many cache lines the bytes bytes starting at p touch (at least 1 byte). Convert pointers with reinterpret_cast<std::uintptr_t>.

Challenge 3

Make the padding reusable: write template <typename T> struct Padded holding alignas(64) T value;, so every Padded fills at least a whole cache line. Then write long long sum_all(const std::vector<Padded<long long>>& per_thread), adding the per-thread totals.

Previous: Branches and branch prediction Next: Custom allocators with std::pmr