Cache-Friendly 数据结构设计

CPU 寄存器访问：      ~1 个周期
L1 Cache 访问：       ~4 个周期
L2 Cache 访问：       ~12 个周期
L3 Cache 访问：       ~40 个周期
主内存（RAM）访问：    ~200+ 个周期

内存地址：  [0..63]字节  [64..127]字节  [128..191]字节
              ↓ 一次性加载到 L1
            缓存行1        缓存行2          缓存行3

// 数组：内存连续
std::vector<int> arr = {1, 2, 3, 4, 5, ...};
// 内存布局：[1][2][3][4][5]... 紧密排列

// 链表：内存分散
std::list<int> lst = {1, 2, 3, 4, 5, ...};
// 内存布局：[1]→(随机地址)→[2]→(随机地址)→[3]...

// 遍历1000万个int求和

std::vector<int> v(10000000);
int sum = 0;
for (int x : v) sum += x;
// 耗时：~5ms（缓存命中率极高，数据连续）

std::list<int> l(10000000);
for (int x : l) sum += x;
// 耗时：~50-80ms！（每次跳转可能是一次缓存未命中）

struct Particle {
    float x, y, z;       // 位置
    float vx, vy, vz;    // 速度
    float mass;
    int id;
};

std::vector<Particle> particles(10000);

// 只需要更新位置，但每次都要把整个 Particle（含速度、质量等）加载进缓存
for (auto& p : particles) {
    p.x += p.vx;
    p.y += p.vy;
    p.z += p.vz;
}

[x y z vx vy vz mass id][x y z vx vy vz mass id]...
└────── Particle 1 ─────┘└────── Particle 2 ─────┘

struct ParticleSystem {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> mass;
    std::vector<int> id;
};

ParticleSystem particles;

// 只访问需要的数组，缓存行里全是有用数据
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];
}

x: [x1][x2][x3][x4]...   ← 连续，全是x坐标，缓存利用率100%
y: [y1][y2][y3][y4]...
vx:[vx1][vx2][vx3]...

// 如果你总是"整体"访问一个对象的所有字段
for (auto& p : particles) {
    render(p.x, p.y, p.z, p.color, p.texture);  // 用到几乎所有字段
}

struct Counters {
    std::atomic<int> counterA;  // 线程1频繁写
    std::atomic<int> counterB;  // 线程2频繁写
};
Counters c;

// 线程1
while (true) c.counterA++;

// 线程2
while (true) c.counterB++;

缓存行: [counterA][counterB][padding...........]
         ↑线程1写            ↑线程2写

struct alignas(64) PaddedCounter {   // 强制64字节对齐
    std::atomic<int> value;
    char padding[64 - sizeof(std::atomic<int>)];  // 填充满一条缓存行
};

struct Counters {
    PaddedCounter counterA;
    PaddedCounter counterB;
};

缓存行1: [counterA][padding..................]  ← 独占一条缓存行
缓存行2: [counterB][padding..................]  ← 独占一条缓存行

struct alignas(std::hardware_destructive_interference_size) PaddedCounter {
    std::atomic<int> value;
};

// ❌ 链式结构：每次解引用都可能是一次缓存未命中
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};
// 遍历树时，每跳一次指针都可能跳到内存中很远的地方

// ✅ 用扁平数组模拟树（如果结构相对固定，比如完全二叉树）
std::vector<int> heap;  // 父节点i，左子=2i+1，右子=2i+2
// 整棵树连续存储在一个数组里，遍历时缓存命中率大幅提升

// ❌ 字段顺序不合理，编译器被迫插入大量 padding
struct BadLayout {
    char a;      // 1字节
    // 7字节 padding（为了让 double 8字节对齐）
    double b;    // 8字节
    char c;      // 1字节
    // 7字节 padding
};
// sizeof(BadLayout) = 24 字节（实际有效数据只有10字节！）

// ✅ 按大小从大到小排列字段，减少 padding
struct GoodLayout {
    double b;    // 8字节
    char a;      // 1字节
    char c;      // 1字节
    // 6字节 padding（只需补到8的倍数）
};
// sizeof(GoodLayout) = 16 字节

// 验证
std::cout << sizeof(BadLayout);   // 24
std::cout << sizeof(GoodLayout);  // 16

#include <xmmintrin.h>  // 或 <immintrin.h>

for (size_t i = 0; i < v.size(); i++) {
    if (i + 16 < v.size()) {
        __builtin_prefetch(&v[i + 16]);  // 提前告诉CPU："16个元素后会用到这块内存"
    }
    process(v[i]);
}