CPU Cache & メモリ階層 完全ガイド 2025: L1/L2/L3, Cache Line, False Sharing, 性能最適化

メモリアクセス = コスト
Cache Hit = 安い
Cache Miss = 高い

RAM から 1 byte 読む?
-> 64 bytes の Cache Line 単位で取得

for (int i = 0; i < n; i++) {
    process(arr[i]);
    // CPU が arr[i+1], arr[i+2] を先読み
}

// Blocking なし
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            C[i][j] += A[i][k] * B[k][j];

// Blocking あり
for (int ii = 0; ii < n; ii += BLOCK)
    for (int jj = 0; jj < n; jj += BLOCK)
        for (int kk = 0; kk < n; kk += BLOCK)
            for (int i = ii; i < ii + BLOCK; i++)
                for (int j = jj; j < jj + BLOCK; j++)
                    for (int k = kk; k < kk + BLOCK; k++)
                        C[i][j] += A[i][k] * B[k][j];

// Array - Cache friendly
int arr[1000];
for (int i = 0; i < 1000; i++)
    sum += arr[i];  // 連続メモリ、Prefetch が効く

// LinkedList - Cache hostile
struct Node {
    int value;
    struct Node* next;
};

Node* curr = head;
while (curr) {
    sum += curr->value;
    curr = curr->next;  // 場所不明、Cache Miss
}

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

Point points[1000];

for (int i = 0; i < 1000; i++)
    sum += points[i].x;
// 毎回 16 bytes を取得、使うのは 4 bytes のみ

struct Points {
    float x[1000];
    float y[1000];
    float z[1000];
    int color[1000];
};

for (int i = 0; i < 1000; i++)
    sum += points.x[i];
// 4 bytes 取得、100% 活用、SIMD も容易

struct Bad {
    char a;     // 1 byte + 7 padding
    double b;   // 8 bytes
    char c;     // 1 byte + 7 padding
};
// sizeof(Bad) = 24 bytes (16 無駄!)

struct Good {
    double b;   // 8 bytes
    char a;     // 1 byte
    char c;     // 1 byte + 6 padding
};
// sizeof(Good) = 16 bytes

struct Counters {
    atomic<int> a;  // 4 bytes
    atomic<int> b;  // 4 bytes
};
// 同じ Cache Line (64 bytes) に配置される

perf c2c record ./my_program
perf c2c report

struct Counters {
    alignas(64) atomic<int> a;
    alignas(64) atomic<int> b;
};

#include <new>
struct Counters {
    alignas(std::hardware_destructive_interference_size) atomic<int> a;
    alignas(std::hardware_destructive_interference_size) atomic<int> b;
};

thread_local int a;
thread_local int b;

// AtomicLong - False Sharing 発生しうる
AtomicLong counter = new AtomicLong();
counter.incrementAndGet();

// LongAdder - セルに分散して False Sharing 回避
LongAdder counter = new LongAdder();
counter.increment();

[I] -> read  -> [E] (単独) or [S] (共有)
[E] -> write -> [M]
[S] -> write -> [M] (他コアに invalidate)
[M] -> 他コア read -> [S] + writeback

[Socket 1]      [Socket 2]
   |               |
[Memory 1]    [Memory 2]
   |               |
   +--- Bus -------+

numactl --cpunodebind=0 --membind=0 ./my_program
numactl --hardware

#include <numa.h>
void* mem = numa_alloc_local(size);

// Bad - False Sharing
class BadCounter {
    long count;
}

// Good - Padding
class GoodCounter {
    long p1, p2, p3, p4, p5, p6, p7;
    long count;
    long p9, p10, p11, p12, p13, p14, p15;
}

@sun.misc.Contended
class Counter {
    long count;
}

perf stat -e cache-misses,cache-references ./my_program

perf stat -e L1-dcache-load-misses,L1-dcache-loads ./my_program

valgrind --tool=cachegrind ./my_program
cg_annotate cachegrind.out.PID

static void BM_Array(benchmark::State& state) {
    int arr[1000];
    for (auto _ : state) {
        long sum = 0;
        for (int i = 0; i < 1000; i++)
            sum += arr[i];
        benchmark::DoNotOptimize(sum);
    }
}
BENCHMARK(BM_Array);

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        for (k = 0; k < N; k++)
            C[i][j] += A[i][k] * B[k][j];

for (i = 0; i < N; i++)
    for (k = 0; k < N; k++)
        for (j = 0; j < N; j++)
            C[i][j] += A[i][k] * B[k][j];

for (ii = 0; ii < N; ii += T)
    for (kk = 0; kk < N; kk += T)
        for (jj = 0; jj < N; jj += T)
            for (i = ii; i < ii+T; i++)
                for (k = kk; k < kk+T; k++)
                    for (j = jj; j < jj+T; j++)
                        C[i][j] += A[i][k] * B[k][j];