1
CPU 读取数据的代价：
2
  L1 缓存命中：  ~1 ns    (4 cycles)
3
  L2 缓存命中：  ~5 ns    (20 cycles)
4
  L3 缓存命中：  ~20 ns   (80 cycles)
5
  主存访问：     ~100 ns  (400 cycles)
6

7
一个缓存行 = 64 字节
8
如果你要处理 1000 个粒子，每个粒子 64 字节：
9
  顺序访问（缓存友好）：~1000 次 L1 命中 = ~1 μs
10
  随机访问（指针追逐）：~1000 次 L3/主存 = ~20-100 μs
11

12
差距：20-100 倍！

1
// AoS：每个粒子是一个完整的结构体
2
struct Particle {
3
    float x, y, z;       // 位置：12 字节
4
    float vx, vy, vz;    // 速度：12 字节
5
    float r, g, b, a;    // 颜色：16 字节
6
    float mass;           // 质量：4 字节
7
    float lifetime;       // 生命周期：4 字节
8
};  // 总计：48 字节
9

10
// AoS 数组：粒子在内存中连续，但每个粒子的所有字段在一起
11
Particle particles[1000];
12

13
// 更新位置：只需要 x, y, z, vx, vy, vz
14
// 但缓存行包含整个 Particle（48 字节）
15
// 有效数据：24 字节 / 48 字节 = 50% 缓存利用率
16
void updatePositions(Particle* particles, int count, float dt) {
17
    for (int i = 0; i < count; i++) {
18
        particles[i].x += particles[i].vx * dt;
19
        particles[i].y += particles[i].vy * dt;
20
        particles[i].z += particles[i].vz * dt;
21
    }
22
}

1
// SoA：每种字段一个独立数组
2
struct Particles {
3
    float* x, *y, *z;       // 位置
4
    float* vx, *vy, *vz;    // 速度
5
    float* r, *g, *b, *a;   // 颜色
6
    float* mass;             // 质量
7
    float* lifetime;         // 生命周期
8
    int count;
9
};
10

11
// SoA 更新位置：只加载 x, y, z, vx, vy, vz
12
// 缓存行只包含同类型数据
13
// 有效数据：100% 缓存利用率
14
void updatePositions(Particles* p, float dt) {
15
    for (int i = 0; i < p->count; i++) {
16
        p->x[i] += p->vx[i] * dt;
17
        p->y[i] += p->vy[i] * dt;
18
        p->z[i] += p->vz[i] * dt;
19
    }
20
    // SIMD 友好！可以向量化
21
}

1
// 未优化的结构体：24 字节（3x 对齐填充）
2
struct BadLayout {
3
    char  a;     // 1 字节 + 7 字节填充
4
    double b;    // 8 字节
5
    char  c;     // 1 字节 + 7 字节填充
6
};
7
// sizeof(BadLayout) = 24 字节
8
// 有效数据：10 字节，浪费：14 字节 (58%)
9

10
// 优化后的结构体：16 字节
11
struct GoodLayout {
12
    double b;    // 8 字节
13
    char  a;     // 1 字节
14
    char  c;     // 1 字节 + 6 字节填充
15
};
16
// sizeof(GoodLayout) = 16 字节
17
// 有效数据：10 字节，浪费：6 字节 (37%)

1
#include <alignas>
2

3
// 缓存行对齐：避免伪共享
4
struct alignas(64) CacheLineAligned {
5
    std::atomic<int> counter;  // 独占一个缓存行
6
};
7

8
// 多个计数器，每个独占缓存行
9
struct Counters {
10
    alignas(64) std::atomic<int> http_requests;
11
    alignas(64) std::atomic<int> grpc_requests;
12
    alignas(64) std::atomic<int> db_queries;
13
};
14
// 每个计数器独占 64 字节缓存行
15
// 不同线程更新不同计数器不会伪共享

1
// 游戏引擎中的粒子系统
2
// 10000 个粒子，每帧更新
3

4
// AoS 版本：~2.5ms/帧
5
void updateParticlesAoS(Particle* particles, int count, float dt) {
6
    for (int i = 0; i < count; i++) {
7
        particles[i].x += particles[i].vx * dt;
8
        particles[i].y += particles[i].vy * dt;
9
        particles[i].z += particles[i].vz * dt;
10
        particles[i].lifetime -= dt;
11
    }
12
}
13

14
// SoA 版本 + SIMD：~0.3ms/帧 (8x 加速)
15
#include <immintrin.h>
16
void updateParticlesSoA(Particles* p, float dt) {
17
    __m256 dt_vec = _mm256_set1_ps(dt);
18
    int i = 0;
19
    for (; i + 8 <= p->count; i += 8) {
20
        __m256 x = _mm256_loadu_ps(&p->x[i]);
21
        __m256 vx = _mm256_loadu_ps(&p->vx[i]);
22
        __m256 y = _mm256_loadu_ps(&p->y[i]);
23
        __m256 vy = _mm256_loadu_ps(&p->vy[i]);
24
        __m256 z = _mm256_loadu_ps(&p->z[i]);
25
        __m256 vz = _mm256_loadu_ps(&p->vz[i]);
26

27
        x = _mm256_fmadd_ps(vx, dt_vec, x);
28
        y = _mm256_fmadd_ps(vy, dt_vec, y);
29
        z = _mm256_fmadd_ps(vz, dt_vec, z);
30

31
        _mm256_storeu_ps(&p->x[i], x);
32
        _mm256_storeu_ps(&p->y[i], y);
33
        _mm256_storeu_ps(&p->z[i], z);
34
    }
35
    // 处理剩余元素...
36
}

1
// 数据库行存储：OLTP 场景
2
// 只需要 id 和 name，但加载了整行
3

4
// 宽行：加载不需要的字段
5
struct Row {
6
    int64_t id;           // 8
7
    char name[256];       // 256
8
    char email[256];      // 256
9
    char address[512];    // 512
10
    char bio[1024];       // 1024
11
    // 总计：2056 字节
12
};
13

14
// 查询 SELECT id, name FROM users
15
// 需要的数据：264 字节
16
// 实际加载：2056 字节
17
// 缓存利用率：12.8%
18

19
// 列式存储：只加载需要的列
20
struct ColumnarTable {
21
    int64_t* ids;         // 连续的 id 数组
22
    char** names;         // 连续的 name 数组
23
    char** emails;        // ...
24
    // 查询时只加载 ids 和 names
25
    // 缓存利用率：~100%
26
};

1
// 网络包处理：只关心头部字段
2
// 加载整个包结构
3
struct Packet {
4
    uint8_t dst_mac[6];
5
    uint8_t src_mac[6];
6
    uint16_t ethertype;
7
    uint8_t version_ihl;
8
    uint8_t tos;
9
    uint16_t total_length;
10
    uint16_t identification;
11
    // ... 更多字段
12
    uint8_t payload[1500];  // 载荷
13
};  // 总计 ~1536 字节
14

15
// 分层处理：只加载需要的头部
16
struct EthernetHeader {
17
    uint8_t dst_mac[6];
18
    uint8_t src_mac[6];
19
    uint16_t ethertype;
20
};  // 14 字节
21

22
struct IPv4Header {
23
    uint8_t version_ihl;
24
    uint8_t tos;
25
    uint16_t total_length;
26
    // ... 只到选项字段
27
};  // 20-60 字节

1
# 测量缓存 miss
2
perf stat -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-load-misses \
3
    ./my_program
4

5
# 输出示例：
6
#   1,234,567,890  cache-references
7
#      12,345,678  cache-misses          # 1.0% miss rate
8
#   5,678,901,234  L1-dcache-loads
9
#    567,890,123   L1-dcache-load-misses  # 10.0% L1 miss rate
10

11
# 使用 cachegrind 模拟缓存行为
12
valgrind --tool=cachegrind ./my_program
13
# 输出：I1/D1/L2 缓存的命中/miss 统计

1
# 记录内存访问事件
2
perf record -e mem-loads,mem-stores ./my_program
3
perf report
4

5
# 查看内存访问延迟分布
6
perf mem record ./my_program
7
perf mem report

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <time.h>
4
#include <immintrin.h>
5

6
#define N 10000000
7

8
// AoS 版本
9
struct ParticleAoS {
10
    float x, y, z;       // 位置
11
    float vx, vy, vz;    // 速度
12
    float r, g, b, a;    // 颜色
13
    float mass;           // 质量
14
    float lifetime;       // 生命周期
15
};  // 48 字节
16

17
// SoA 版本
18
struct ParticleSoA {
19
    float *x, *y, *z;
20
    float *vx, *vy, *vz;
21
    float *r, *g, *b, *a;
22
    float *mass;
23
    float *lifetime;
24
};
25

26
int main() {
27
    // 分配 AoS
28
    struct ParticleAoS *aos = aligned_alloc(64, N * sizeof(struct ParticleAoS));
29
    for (int i = 0; i < N; i++) {
30
        aos[i].x = i; aos[i].y = i; aos[i].z = i;
31
        aos[i].vx = 1; aos[i].vy = 1; aos[i].vz = 1;
32
    }
33

34
    // 分配 SoA
35
    struct ParticleSoA soa;
36
    soa.x = aligned_alloc(64, N * sizeof(float));
37
    soa.y = aligned_alloc(64, N * sizeof(float));
38
    soa.z = aligned_alloc(64, N * sizeof(float));
39
    soa.vx = aligned_alloc(64, N * sizeof(float));
40
    soa.vy = aligned_alloc(64, N * sizeof(float));
41
    soa.vz = aligned_alloc(64, N * sizeof(float));
42
    for (int i = 0; i < N; i++) {
43
        soa.x[i] = i; soa.y[i] = i; soa.z[i] = i;
44
        soa.vx[i] = 1; soa.vy[i] = 1; soa.vz[i] = 1;
45
    }
46

47
    float dt = 0.016f;
48
    clock_t start, end;
49

50
    // AoS 更新位置
51
    start = clock();
52
    for (int i = 0; i < N; i++) {
53
        aos[i].x += aos[i].vx * dt;
54
        aos[i].y += aos[i].vy * dt;
55
        aos[i].z += aos[i].vz * dt;
56
    }
57
    end = clock();
58
    printf("AoS 更新位置: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
59

60
    // SoA 更新位置（标量）
61
    start = clock();
62
    for (int i = 0; i < N; i++) {
63
        soa.x[i] += soa.vx[i] * dt;
64
        soa.y[i] += soa.vy[i] * dt;
65
        soa.z[i] += soa.vz[i] * dt;
66
    }
67
    end = clock();
68
    printf("SoA 更新位置(标量): %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
69

70
    // SoA + AVX2 更新位置
71
    __m256 dt_v = _mm256_set1_ps(dt);
72
    start = clock();
73
    for (int i = 0; i + 8 <= N; i += 8) {
74
        __m256 x = _mm256_loadu_ps(&soa.x[i]);
75
        __m256 vx = _mm256_loadu_ps(&soa.vx[i]);
76
        x = _mm256_fmadd_ps(vx, dt_v, x);
77
        _mm256_storeu_ps(&soa.x[i], x);
78
        // y, z 同理...
79
    }
80
    end = clock();
81
    printf("SoA+AVX2 更新位置: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
82

83
    free(aos);
84
    return 0;
85
}

1
// AoSoA: 每块 8 个粒子（适配 AVX2 的 256 位寄存器）
2
struct ParticleBlock {
3
    float x[8], y[8], z[8];       // 位置
4
    float vx[8], vy[8], vz[8];    // 速度
5
    float r[8], g[8], b[8], a[8]; // 颜色
6
    float mass[8];
7
    float lifetime[8];
8
};  // 384 字节 = 6 个缓存行
9

10
// 访问第 i 个粒子的 x 坐标
11
int block = i / 8;
12
int offset = i % 8;
13
float px = blocks[block].x[offset];
14

15
// SIMD 处理一整块
16
__m256 x = _mm256_load_ps(blocks[block].x);  // 直接加载！连续的！

1
// 链式哈希表：指针追逐，缓存不友好
2
struct ChainHashNode {
3
    int key;
4
    int value;
5
    struct ChainHashNode *next;  // 指针追逐！
6
};
7

8
// 开放寻址哈希表：连续内存，缓存友好
9
struct OpenAddressingHash {
10
    int *keys;     // 连续数组
11
    int *values;   // 连续数组
12
    int *metadata; // 0=空, 1=占用, 2=已删除
13
    int capacity;
14
};
15

16
int hash_lookup(struct OpenAddressingHash *ht, int key) {
17
    int idx = key % ht->capacity;
18
    while (ht->metadata[idx] != 0) {
19
        if (ht->metadata[idx] == 1 && ht->keys[idx] == key)
20
            return ht->values[idx];
21
        idx = (idx + 1) % ht->capacity;  // 线性探测
22
    }
23
    return -1;  // 未找到
24
}
25
// 线性探测的局部性很好——相邻的槽在同一缓存行中

1
// 普通二叉搜索树：节点分散在堆上
2
struct BSTNode {
3
    int key;
4
    struct BSTNode *left, *right;  // 指针追逐
5
};
6

7
// B 树 / B+ 树：节点包含多个键，减少树高
8
#define BTREE_ORDER 16  // 每个节点 16 个键
9
struct BTreeNode {
10
    int num_keys;
11
    int keys[BTREE_ORDER - 1];
12
    struct BTreeNode *children[BTREE_ORDER];
13
    // 节点大小约 256 字节 = 4 个缓存行
14
    // 一次缓存未命中加载 15 个键
15
};

1
// 经典面试题：以下结构体的大小？
2
struct S1 { char a; int b; short c; };
3
// a: offset 0, 1 byte
4
// 填充: 3 bytes (int 需要 4 字节对齐)
5
// b: offset 4, 4 bytes
6
// c: offset 8, 2 bytes
7
// 填充: 2 bytes (总大小需要是 4 的倍数)
8
// sizeof(S1) = 12
9

10
struct S2 { int b; short c; char a; };
11
// b: offset 0, 4 bytes
12
// c: offset 4, 2 bytes
13
// a: offset 6, 1 byte
14
// 填充: 1 byte
15
// sizeof(S2) = 8  ← 比 S1 节省 33%！

1
// 多线程计数器：伪共享
2
struct Counters {
3
    std::atomic<int> http_requests;   // 偏移 0
4
    std::atomic<int> grpc_requests;   // 偏移 4 ← 同一缓存行！
5
    std::atomic<int> db_queries;      // 偏移 8 ← 同一缓存行！
6
};
7
// 3 个原子变量在同一个 64 字节缓存行中
8
// 不同线程更新不同计数器 → 伪共享！
9

10
// 修复方案 1：缓存行对齐
11
struct alignas(64) CacheLine {
12
    std::atomic<int> counter;
13
};
14

15
struct CountersFixed {
16
    CacheLine http_requests;   // 独占缓存行
17
    CacheLine grpc_requests;   // 独占缓存行
18
    CacheLine db_queries;      // 独占缓存行
19
};
20
// 每个计数器独占 64 字节，不同线程更新不会互相驱逐
21

22
// 修复方案 2：线程本地计数 + 定期汇总
23
struct ThreadLocalCounters {
24
    int http_requests;   // 非原子，线程本地
25
    int grpc_requests;
26
    int db_queries;
27
};
28

29
// 每个线程有自己的计数器（在 TLS 中）
30
static __thread struct ThreadLocalCounters tl_counters;
31

32
void increment_http() {
33
    tl_counters.http_requests++;  // 无锁，无伪共享
34
}
35

36
// 定期汇总到全局
37
void flush_counters() {
38
    global_http += tl_counters.http_requests;
39
    tl_counters.http_requests = 0;
40
}

1
// 原始版本：每条日志一个 malloc
2
struct LogEntry {
3
    long timestamp;       // 8
4
    int level;            // 4
5
    int thread_id;        // 4
6
    char message[256];    // 256
7
    struct LogEntry *next; // 8
8
};  // 280 字节，但 malloc 开销大
9

10
// 优化版本 1：环形缓冲区（连续内存）
11
struct LogBuffer {
12
    struct LogEntry entries[4096];  // 连续数组
13
    int head, tail;
14
    // 所有日志在连续内存中，缓存友好
15
};
16

17
// 优化版本 2：冷热分离
18
struct HotLogData {
19
    long timestamp;    // 8
20
    int level;         // 4
21
    int thread_id;     // 4
22
};  // 16 字节，4 条/缓存行
23

24
struct ColdLogData {
25
    char message[256]; // 256 字节
26
};  // 只在需要显示时才访问
27

28
struct LogBufferOptimized {
29
    struct HotLogData hot[4096];  // 热数据连续
30
    struct ColdLogData cold[4096]; // 冷数据连续但分开
31
};
32
// 过滤日志级别时只遍历 hot 数组，缓存利用率 100%
33
// 只有需要输出的日志才访问 cold 数组

1
// 原始：链表 + 大结构体
2
struct Connection {
3
    int fd;
4
    int state;
5
    char remote_addr[46];   // IPv6 地址字符串
6
    time_t last_active;
7
    int bytes_sent, bytes_recv;
8
    char user_agent[256];   // 冷数据！
9
    struct Connection *next; // 指针追逐
10
};
11

12
// 优化：数组 + 冷热分离
13
struct HotConnData {
14
    int fd;
15
    int state;
16
    time_t last_active;
17
    int bytes_sent, bytes_recv;
18
};  // 24 字节，2-3 条/缓存行
19

20
struct ColdConnData {
21
    char remote_addr[46];
22
    char user_agent[256];
23
};  // 302 字节
24

25
struct ConnTable {
26
    struct HotConnData hot[MAX_CONN];  // 连续数组
27
    struct ColdConnData cold[MAX_CONN]; // 冷数据分开
28
    int count;
29
};
30
// 遍历活跃连接时只访问 hot 数组
31
// 缓存行利用率从 24/302 = 8% 提升到 100%