Cache-Friendly C++: Data Locality, Struct Layout, AoS vs SoA and False Sharing

Two loops that do the same arithmetic over the same data can run at very different speeds depending only on the order in which they touch memory. This post explains why, starting from how CPU caches fetch memory in cache lines, and then covers data locality, struct layout and padding, AoS versus SoA, false sharing between threads, and prefetching, with benchmark code you can run on your own machine.

Introduction: Same Work, Different Access Order

Traversing a 2D array column by column instead of row by row can make the same loop dramatically slower.
CPUs fetch memory in cache line units (the memory block size fetched at once by CPU cache, usually 64 bytes). When access order follows “consecutive addresses,” cache hits (fast access when needed data is in cache) increase. When jumping around, cache misses (must fetch from main memory when not in cache) increase. Paying attention to data locality (keeping frequently used data close and consecutive to improve cache efficiency) through row-major traversal, struct alignment, and keeping related data together can make the same operation much faster.

Slow Code:

static int matrix[1000][1000];
// ❌ Column-major traversal (slow)
for (int col = 0; col < 1000; ++col) {
    for (int row = 0; row < 1000; ++row) {
        sum += matrix[row][col];  // Jumps 4000 bytes each step: a new cache line almost every access
    }
}

Fast Code:

// After copying and pasting: g++ -std=c++17 -O2 -o cache_fast cache_fast.cpp && ./cache_fast
#include <iostream>
#include <chrono>
int main() {
    // static: a 4MB local array can overflow the default stack (1MB on Windows)
    static int matrix[1000][1000] = {};
    long long sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    // ✅ Row-major traversal (fast)
    for (int row = 0; row < 1000; ++row) {
        for (int col = 0; col < 1000; ++col) {
            sum += matrix[row][col];  // Cache hit
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "sum=" << sum << " time=" << ms << "ms\n";
    return 0;
}

Execution Result: Outputs sum=0 time=Nms. N depends on your CPU, cache sizes, and compiler; run both versions on the same machine and compare. At higher optimization levels the compiler may vectorize or even interchange simple loops, so check that the loop you meant to measure is still there (look at the assembly or use a benchmark library such as Google Benchmark with benchmark::DoNotOptimize). Cause: CPU cache prefetches consecutive memory

---

CPU Cache Basics

Memory Hierarchy

Rough orders of magnitude (vary by CPU):
CPU Register    < 1ns    (fastest)
    ↓
L1 Cache        ~1ns     (32-64KB)
    ↓
L2 Cache        ~3ns     (256KB-1MB)
    ↓
L3 Cache        ~10ns    (8-32MB)
    ↓
RAM             ~100ns   (several GB)
    ↓
SSD             ~100us   (hundreds of GB)
    ↓
HDD             ~10ms    (several TB, slowest)

Cache Line: Usually fetches memory in 64-byte units

Memory Hierarchy Visualization

flowchart TB
    subgraph fast[Fast Access]
        R[Register]
        L1[L1 Cache 32KB]
        L2[L2 Cache 256KB]
    end
    subgraph slow[Slow Access]
        L3[L3 Cache 8MB]
        RAM[RAM 100ns]
    end
    R --> L1 --> L2 --> L3 --> RAM

Cache Hit vs Miss

int arr[1000];
// Cache hit: sequential access
for (int i = 0; i < 1000; ++i) {
    sum += arr[i];  // Fast
}
// Cache miss: irregular access
for (int i = 0; i < 1000; i += 64) {
    sum += arr[i];  // Slow (cache line waste)
}

Detailed Code Explanation: Cache Hit (Sequential Access):

• Accesses arr[0], arr[1], arr[2], … in order.
• Cache line usually fetches 64 bytes (16 ints) at once.
• When reading arr[0], arr[0]~arr[15] are loaded into cache together.
• Next 15 accesses are cache hits (very fast, on the order of a nanosecond).
• Result: Only about 62 fetches from memory out of 1000 accesses (1000/16). Cache Miss (Irregular Access):
• Jumps by 64: arr[0], arr[64], arr[128], …
• Accesses different cache lines each time, causing cache misses.
• All 16 accesses must fetch from memory.
• Remaining 15 elements loaded into cache are discarded unused.
• Result: In the worst case every access pays main-memory latency instead of cache latency. What this means in practice:
• The real gap is smaller than the raw latency ratio, because hardware prefetchers detect constant strides and out-of-order execution overlaps several misses.
• The gap grows as the data set outgrows each cache level; for small arrays that fit in L1 both patterns can be equally fast.
• Measure with your own sizes rather than relying on a fixed factor.

---

Data Locality

Temporal Locality

// ✅ Good: repeated access to same data
int sum = 0;
for (int i = 0; i < 100; ++i) {
    sum += data[0];  // data[0] stays in cache
}
// ❌ Bad: different data each time
for (int i = 0; i < 100; ++i) {
    sum += data[rand() % 10000];  // Many cache misses
}

Spatial Locality

struct Point {
    int x, y, z;
};
std::vector<Point> points(1000);
// ✅ Good: sequential access
for (const auto& p : points) {
    sum += p.x + p.y + p.z;  // Cache-friendly
}
// ❌ Bad: pointer chasing
struct Node {
    int value;
    Node* next;
};
Node* head = /* ... */;
for (Node* p = head; p != nullptr; p = p->next) {
    sum += p->value;  // Many cache misses
}

---

Reducing Cache Misses

Pattern 1: Use Contiguous Memory

// ❌ Bad: linked list (cache misses)
std::list<int> data;
for (int val : data) {
    sum += val;  // Cache miss per node
}
// ✅ Good: vector (cache-friendly)
std::vector<int> data;
for (int val : data) {
    sum += val;  // Contiguous memory, cache hits
}

Pattern 2: Row-Major Traversal

const int N = 1000;
int matrix[N][N];
// ❌ Column-major (slow)
for (int col = 0; col < N; ++col) {
    for (int row = 0; row < N; ++row) {
        matrix[row][col] = 0;  // Cache miss
    }
}
// ✅ Row-major (fast)
for (int row = 0; row < N; ++row) {
    for (int col = 0; col < N; ++col) {
        matrix[row][col] = 0;  // Cache hit
    }
}

Detailed Code Explanation: C++ 2D Array Memory Layout:

• int matrix[N][N] is stored in row-major order in memory.
• Memory order: matrix[0][0], matrix[0][1], …, matrix[0][N-1], matrix[1][0], …
• Elements of the same row are contiguous in memory. Column-Major Traversal (Slow):

Access order: matrix[0][0] → matrix[1][0] → matrix[2][0] → ...
Memory order: [0][0] [0][1] [0][2] ... [1][0] [1][1] ...

• Reading matrix[0][0] loads matrix[0][0]~[0][15] into cache.
• But next accesses matrix[1][0], which is 1000 * 4 bytes = 4KB away.
• Cached matrix[0][1]~[0][15] are discarded unused.
• Result: Almost all accesses are cache misses (very slow). Row-Major Traversal (Fast):

Access order: matrix[0][0] → matrix[0][1] → matrix[0][2] → ...
Memory order: [0][0] [0][1] [0][2] ... (matches!)

• Reading matrix[0][0] loads matrix[0][0]~[0][15] into cache.
• Next 15 accesses (matrix[0][1]~[0][15]) are all cache hits.
• Result: Only 1 cache miss per 16 accesses (very fast). Cache line loads (1000x1000 int matrix, 64-byte lines):
• Row-major: about 1,000,000 / 16 = 62,500 cache lines are loaded, each fully used.
• Column-major: each step jumps 4000 bytes, so up to one line per access (up to 1,000,000 loads) unless the lines touched by previous columns are still in cache.
• How much slower column-major runs depends on cache sizes and the prefetcher; on typical desktop CPUs it is noticeably slower once the matrix no longer fits in cache. Production Tip: Choosing wrong traversal order in matrix multiplication, image processing, etc. significantly degrades performance.

---

Struct Layout Optimization

Minimize Padding

// ❌ Bad: lots of padding (16 bytes)
struct Bad {
    char c1;    // 1 byte
    // 3 bytes padding
    int i;      // 4 bytes
    char c2;    // 1 byte
    // 3 bytes padding
};
// ✅ Good: minimal padding (12 bytes)
struct Good {
    int i;      // 4 bytes
    char c1;    // 1 byte
    char c2;    // 1 byte
    // 2 bytes padding
};

Separate Hot/Cold Data

// ❌ Bad: frequently and rarely used data mixed
struct Entity {
    int id;              // Frequently used
    float x, y, z;       // Frequently used
    std::string name;    // Occasionally used
    std::string description;  // Rarely used
};
// ✅ Good: separate hot data only
struct EntityHot {
    int id;
    float x, y, z;
};
struct EntityCold {
    std::string name;
    std::string description;
};
std::vector<EntityHot> hotData;
std::map<int, EntityCold> coldData;

---

AoS vs SoA Worked Example

Memory Layout Comparison

flowchart LR
    subgraph AoS["AoS: Array of Structures"]
        direction TB
        A1["(x0,y0,z0,vx0,vy0,vz0,r0,g0,b0)"]
        A2["(x1,y1,z1,vx1,vy1,vz1,r1,g1,b1)"]
        A1 --> A2
    end
    subgraph SoA["SoA: Structure of Arrays"]
        direction TB
        S1["x: (x0,x1,x2,...)"]
        S2["vx: (vx0,vx1,vx2,...)"]
        S3["r: (r0,r1,r2,...)"]
        S1 --> S2 --> S3
    end

AoS (Array of Structures)

#include <vector>
#include <chrono>
#include <iostream>
struct ParticleAoS {
    float x, y, z;      // Position (12 bytes)
    float vx, vy, vz;   // Velocity (12 bytes)
    float r, g, b;      // Color (12 bytes)
    // Total 36 bytes
};
void updatePositionsAoS(std::vector<ParticleAoS>& particles) {
    for (auto& p : particles) {
        p.x += p.vx;
        p.y += p.vy;
        p.z += p.vz;
    }
}
int main() {
    std::vector<ParticleAoS> particles(100000);
    // Initialization...
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100; ++i) {
        updatePositionsAoS(particles);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "AoS: " << ms << " ms\n";
    return 0;
}

AoS Memory Layout:

Memory: [x0,y0,z0,vx0,vy0,vz0,r0,g0,b0][x1,y1,z1,vx1,vy1,vz1,r1,g1,b1]...
        ↑ 36 bytes (9 floats)      ↑ 36 bytes
Cache line (64B) holds ~1.7 particles → loads colors even when only using position (waste)

SoA (Structure of Arrays)

struct ParticleSystemSoA {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> r, g, b;
    void resize(size_t n) {
        x.resize(n); y.resize(n); z.resize(n);
        vx.resize(n); vy.resize(n); vz.resize(n);
        r.resize(n); g.resize(n); b.resize(n);
    }
    size_t size() const { return x.size(); }
};
void updatePositionsSoA(ParticleSystemSoA& particles) {
    const size_t n = particles.size();
    for (size_t i = 0; i < n; ++i) {
        particles.x[i] += particles.vx[i];
        particles.y[i] += particles.vy[i];
        particles.z[i] += particles.vz[i];
    }
}

SoA Memory Layout:

x array:  [x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,...]
vx array: [vx0,vx1,vx2,vx3,vx4,vx5,vx6,vx7,vx8,vx9,vx10,vx11,...]
r array:  [r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,r12,r13,r14,r15,...]
Cache line (64B) holds 16 floats → utilizes all x[i]~x[i+15] when reading x[i]

AoS vs SoA Selection Guide

Situation	Recommended	Reason
Process same field in bulk (position updates)	SoA	Maximum cache efficiency
Use multiple fields of one object together	AoS	Simpler code
Apply SIMD vectorization	SoA	Easy to process 4/8 in parallel
Query/modify individual entities	AoS	Access with single index

---

False Sharing

False Sharing Principle

flowchart LR
    subgraph bad[❌ False Sharing]
        CL["Cache Line 64B"]
        C0["counter[0]"]
        C1["counter[1]"]
        C2["counter[2]"]
        CL --> C0 --> C1 --> C2
        T1["Thread 1 modifies"] -.->|invalidates| C0
        T2["Thread 2 modifies"] -.->|invalidates| C1
    end

When one thread modifies counter[0], the cache for counter[1] and counter[2] in the same cache line is invalidated, forcing other threads to reload from memory every time.

Problem: Multiple Threads Modify Same Cache Line

#include <thread>
#include <vector>
#include <atomic>
#include <chrono>
#include <iostream>
// ❌ Bad: false sharing occurs
void badParallelCounter() {
    const int numThreads = 4;
    std::vector<int> counters(numThreads, 0);  // 4 ints = 16 bytes, same cache line!
    std::vector<std::thread> threads;
    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t]++;  // Causes other threads' cache line invalidation
            }
        });
    }
    for (auto& th : threads) th.join();
}

Cause: When counters[0], counters[1], … fit in the same 64-byte cache line, every time one thread modifies counters[0], that cache line is invalidated, and other threads using counters[1] must refetch from memory.

Solution: Cache Line Alignment

#include <cstddef>
// ✅ Good: align to cache line boundary
struct alignas(64) CacheLineAlignedCounter {
    int value;
    char padding[64 - sizeof(int)];  // Prevent cache line sharing
};
void goodParallelCounter() {
    const int numThreads = 4;
    std::vector<CacheLineAlignedCounter> counters(numThreads);
    std::vector<std::thread> threads;
    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t].value++;
            }
        });
    }
    for (auto& th : threads) th.join();
}

Using C++17 alignas

// Each counter placed on separate cache line
struct alignas(64) ThreadLocalCounter {
    std::atomic<int64_t> count{0};
};
void benchmarkCounters() {
    const int numThreads = 4;
    std::vector<ThreadLocalCounter> counters(numThreads);
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<std::thread> threads;
    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t].count.fetch_add(1, std::memory_order_relaxed);
            }
        });
    }
    for (auto& th : threads) th.join();
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Aligned: " << ms << " ms\n";
}

Performance Difference: When threads were contending for the same line, removing false sharing can give a large speedup, because each core stops invalidating the others’ caches. How large depends on core count and how often the counters are written; measure it.

---

Using Prefetch

Basic Usage

#include <xmmintrin.h>  // _mm_prefetch (or GCC/Clang: __builtin_prefetch)
void processWithPrefetch(const std::vector<int>& data) {
    const size_t n = data.size();
    const int PREFETCH_DISTANCE = 8;  // How many elements ahead to preload
    for (size_t i = 0; i < n; ++i) {
        // Preload next block into cache
        if (i + PREFETCH_DISTANCE < n) {
            __builtin_prefetch(&data[i + PREFETCH_DISTANCE], 0, 3);
            // Args: (address, 0=read, 3=all cache levels)
        }
        process(data[i]);
    }
}

Prefetch in Linked List Traversal

struct Node {
    int value;
    Node* next;
};
int sumListWithPrefetch(Node* head) {
    int sum = 0;
    Node* curr = head;
    while (curr != nullptr) {
        // Preload next node (before following pointer)
        if (curr->next != nullptr) {
            __builtin_prefetch(curr->next, 0, 3);
        }
        sum += curr->value;
        curr = curr->next;
    }
    return sum;
}

Following Index Array

// indices[i] is index into data → access data[indices[i]]
void gatherWithPrefetch(const std::vector<float>& data,
                        const std::vector<size_t>& indices) {
    const size_t n = indices.size();
    float sum = 0;
    for (size_t i = 0; i < n; ++i) {
        if (i + 4 < n) {
            __builtin_prefetch(&data[indices[i + 4]], 0, 3);
        }
        sum += data[indices[i]];
    }
}

Warning: If prefetch distance is too large, data gets evicted from cache. If too small, no effect. Experiment with 4~16.

---

Practical Optimization Patterns

Pattern 1: Block Processing

const int BLOCK_SIZE = 64;  // Cache line size
void processBlocked(int* data, int N) {
    for (int i = 0; i < N; i += BLOCK_SIZE) {
        int end = std::min(i + BLOCK_SIZE, N);
        for (int j = i; j < end; ++j) {
            process(data[j]);
        }
    }
}

Pattern 2: Loop Fusion

std::vector<int> data(10000);
// ❌ Bad: multiple traversals
for (int& val : data) {
    val *= 2;
}
for (int& val : data) {
    val += 10;
}
// ✅ Good: single traversal
for (int& val : data) {
    val *= 2;
    val += 10;
}

Pattern 3: Improve Locality with Sorting

struct Entity {
    int type;
    // Data...
};
std::vector<Entity> entities;
// Sort by type
std::sort(entities.begin(), entities.end(),
          [](const Entity& a, const Entity& b) {
              return a.type < b.type;
          });
// Process same types consecutively (cache-friendly)
for (const auto& e : entities) {
    processType(e.type, e);
}

Pattern 4: Data Reorganization (SoA)

// ❌ Bad: AoS (Array of Structures)
struct Particle {
    float x, y, z;     // Position
    float vx, vy, vz;  // Velocity
    float r, g, b;     // Color
};
std::vector<Particle> particles(10000);
// Update position only (colors also loaded into cache, waste)
for (auto& p : particles) {
    p.x += p.vx;
    p.y += p.vy;
    p.z += p.vz;
}
// ✅ Good: SoA (Structure of Arrays)
struct ParticleSystem {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> r, g, b;
};
ParticleSystem particles;
particles.x.resize(10000);
// ...
// Update position only (only position data loaded into cache)
for (size_t i = 0; i < particles.x.size(); ++i) {
    particles.x[i] += particles.vx[i];
    particles.y[i] += particles.vy[i];
    particles.z[i] += particles.vz[i];
}

SoA Detailed Explanation:

• AoS Problem: Each particle is 7 floats (x,y,z,vx,vy,vz,r, 28 bytes), so reading x0 pulls the whole particle and part of the next into cache. A loop that only uses x uses 4 of every 28 bytes it loads, and the rest is wasted. Cache efficiency: about 14% (1/7)
• SoA Advantage: Cache line (64 bytes) holds 16 floats. Reading x0 loads x0~x15 into cache. Next 15 accesses are all cache hits! Cache efficiency: 100%
• Performance Impact: When a loop touches only one or two fields, SoA moves far less data through the cache, and contiguous arrays of one type are easy for the compiler to vectorize. The real speedup depends on struct size, particle count, and what else the loop does, so benchmark both layouts.

---

Common Errors and Solutions

Error 1: Severe Degradation from Column-Major Traversal

Symptom: 2D array processing is much slower than expected. Cause: C/C++ arrays are row-major but traversed column-major. Solution:

// ❌ Wrong order
for (int col = 0; col < COLS; ++col)
    for (int row = 0; row < ROWS; ++row)
        process(matrix[row][col]);
// ✅ Correct order (row-major)
for (int row = 0; row < ROWS; ++row)
    for (int col = 0; col < COLS; ++col)
        process(matrix[row][col]);

Error 2: Multithreading Slowed by False Sharing

Symptom: Adding threads makes it slower. Cause: Different threads modify variables in the same cache line. Solution:

// ❌ Sharing same cache line
std::atomic<int> counters[8];
// ✅ Cache line alignment
struct alignas(64) AlignedCounter {
    std::atomic<int> value{0};
};
std::vector<AlignedCounter> counters(8);

Error 3: Performance Degradation from Excessive Prefetch

Symptom: Adding __builtin_prefetch makes it slower. Cause: Prefetching too far ahead evicts valid data from cache. Solution:

// ❌ Distance too large (cache pollution)
__builtin_prefetch(&data[i + 64], 0, 3);
// ✅ Appropriate distance (4~16)
__builtin_prefetch(&data[i + 8], 0, 3);

Error 4: Index Mismatch When Mixing SoA and AoS

Symptom: After converting to SoA, some particles reference wrong data. Cause: Only some arrays resized during resize, or index calculation error. Solution:

// ✅ Maintain SoA size consistency
struct ParticleSystem {
    std::vector<float> x, y, z, vx, vy, vz;
    void resize(size_t n) {
        x.resize(n); y.resize(n); z.resize(n);
        vx.resize(n); vy.resize(n); vz.resize(n);
    }
};

Error 5: Using list Instead of vector

Symptom: std::list traversal much slower than std::vector. Cause: List nodes are scattered, causing many cache misses. Solution:

// ❌ list for traversal only
std::list<int> items;
for (auto v : items) sum += v;
// ✅ vector for traversal-heavy workloads
std::vector<int> items;
for (auto v : items) sum += v;

---

Performance Benchmarks

Benchmark 1: Row-Major vs Column-Major

#include <iostream>
#include <chrono>
const int N = 4096;
int matrix[N][N];
void benchmarkRowMajor() {
    long long sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < N; ++col) {
            sum += matrix[row][col];
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Row-major: " << ms << " ms (sum=" << sum << ")\n";
}
void benchmarkColMajor() {
    long long sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    for (int col = 0; col < N; ++col) {
        for (int row = 0; row < N; ++row) {
            sum += matrix[row][col];
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Col-major: " << ms << " ms (sum=" << sum << ")\n";
}
int main() {
    benchmarkRowMajor();
    benchmarkColMajor();
    // Compare the two numbers on your machine; the ratio depends on CPU and cache sizes
}

Benchmark 2: AoS vs SoA

Illustrative only; measure on your machine. Set up 100,000 particles and update positions 100 times in each layout. Expect SoA to win when the loop reads only position and velocity fields, and the gap to shrink or disappear when the loop uses every field of each particle.

Benchmark 3: Eliminating False Sharing

Illustrative only; measure on your machine. Run 4 threads that each increment their own counter 10 million times, first with the counters packed next to each other, then with each counter alignas(64) (or std::hardware_destructive_interference_size where available). With packed counters, every increment invalidates the line in the other cores’ caches, so adding threads can make the loop slower than a single thread. Padding removes that traffic.

Benchmark 4: vector vs list Traversal

// 1 million element traversal sum
std::vector<int> vec(1000000);
std::list<int> lst(1000000);
// Illustrative only; measure on your machine.
// vector: contiguous, prefetcher-friendly, one cache line holds 16 ints
// list:   one heap node per element; each step follows a pointer to a possibly distant address
// Expect the list traversal to be several times slower, more so after heavy insert/erase churn

---

Production Patterns

Pattern 1: ECS (Entity-Component-System) Style SoA

// Common pattern in game engines
struct TransformComponent {
    std::vector<float> x, y, z;
    std::vector<float> rotX, rotY, rotZ;
};
struct RenderComponent {
    std::vector<uint32_t> textureId;
    std::vector<float> r, g, b, a;
};
void updateTransforms(TransformComponent& tf, float dt) {
    for (size_t i = 0; i < tf.x.size(); ++i) {
        tf.x[i] += 0.1f * dt;  // Sequential position access only
        tf.y[i] += 0.1f * dt;
        tf.z[i] += 0.1f * dt;
    }
}

Pattern 2: Cache Line Size Constants

namespace cache {
    constexpr size_t LINE_SIZE = 64;
    constexpr size_t L1_SIZE = 32 * 1024;
    constexpr size_t L2_SIZE = 256 * 1024;
}
template<typename T>
struct alignas(cache::LINE_SIZE) CacheLineAligned {
    T value;
};

Pattern 3: Optimize After Profiling

// 1. Check cache misses with profiler (perf, VTune)
// 2. Identify loops with many cache misses
// 3. Apply traversal order, SoA conversion, prefetch
// 4. Verify with benchmarks

Pattern 4: Data-Oriented Design Checklist

- [ ] Use contiguous memory (vector > list)
- [ ] Row-major traversal (2D arrays)
- [ ] Consider SoA (when processing same fields in bulk)
- [ ] Separate hot/cold (group frequently used fields only)
- [ ] Cache line alignment for multithreading (prevent false sharing)
- [ ] Experiment with prefetch (pointer chaining, index arrays)

---

Performance Comparison Summary

Optimization	When it helps most	Difficulty
Row-major traversal	Large 2D data that does not fit in cache	Easy
SoA conversion	Hot loops that read a few fields of many objects	Medium
Eliminate false sharing	Threads writing to adjacent variables at high rates	Easy
Replace list with vector	Traversal-heavy code; small elements	Easy
Prefetch	Irregular but predictable access (pointer chains, index arrays)	Medium

The size of each effect depends on your data sizes, CPU, and compiler, so treat this table as a list of things to try and measure, not as expected gains.

---

Related Articles

• Profiling C++ Before Optimizing
• Cache-Friendly C++
• C++ STL Algorithms Basics

Frequently Asked Questions (FAQ)

One-Line Summary: Leveraging contiguous memory and locality increases cache hits, improving performance. Next, read Compile-Time Optimization (#15-3). Previous Article: [C++ Practical Guide #15-1] Profiling and Finding Bottlenecks: Performance Measurement Basics

Q. How do I tell whether false sharing is actually slowing down my multithreaded code?

A. The typical symptom is per-thread counters or flags that scale worse as you add threads even though no two threads touch the same variable. Pad or align each thread’s data to its own cache line, for example with alignas(64) or std::hardware_destructive_interference_size where your compiler provides it, and compare timings; a large speedup means false sharing was the cause. On Linux, perf c2c can point directly at cache lines bouncing between cores.

Q. Should I convert all my structs from AoS to SoA?

A. No. SoA helps when hot loops touch only a few fields of many objects. If code usually works with whole objects, or accesses objects one at a time, AoS keeps related fields in the same cache line and is often better. Profile first and change only the hot data.