22. CPU 缓存与一致性

1. 存储层级与局部性

1.1 存储层级（Memory Hierarchy）

现代 CPU 用金字塔式的存储层级弥合「处理器速度」与「内存速度」的数量级差距。越靠近 CPU 越快、越小、越贵；越远离 CPU 越慢、越大、越便宜。Cache 就是缓解"内存墙"（memory wall）的核心设施。

            ┌─────────────────────────────┐
   4-5 cycles│  L1 Cache   (32-64KB/核)    │   ~1ns
            ├─────────────────────────────┤
  10-15 cycles│  L2 Cache  (256KB-1MB/核)  │   ~4-7ns
            ├─────────────────────────────┤
  30-50 cycles│  L3 Cache   (数MB, 共享)    │   ~10-20ns
            ├─────────────────────────────┤
 ~100+ cycles│  DRAM 主内存 (GB~TB)         │   ~60-100ns
            ├─────────────────────────────┤
   巨大      │  SSD / 磁盘 (持久化)         │   微秒-毫秒级
            └─────────────────────────────┘

1.2 局部性原理

Cache 之所以有效，靠时间局部性（刚访问的数据近期很可能再访问）与空间局部性（访问某地址时其邻近地址近期很可能被访问）。程序性能优化本质上就是优化这两种局部性。

// 空间局部性优劣对比：按行遍历 vs 按列遍历
#define N 1024
int a[N][N];

// 优：按行遍历，逐行连续访问，Cache 行利用率高
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        a[i][j] = 1;

// 劣：按列遍历，跨行跳访，每访问一次就产生一次 Cache Miss
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        a[i][j] = 1;

上面两个循环计算量完全相同，但行遍历比列遍历快一个数量级（缓存命中率差异）。这正是"性能优化先从访存模式下手"的原因。

2. Cache 结构：Line、Tag、Set

2.1 一个 Cache Line 的组织

内存与 Cache 之间以**缓存行（Cache Line）**为最小单位传输，典型 64 字节。Cache 行按物理地址划分字段：Tag（区分同一 Set 内的不同块）、Index/Set（定位到哪一组）、Offset（行内偏移）。

物理地址:  |    Tag (高位)    |  Set/Index (中位)  |  Offset (低位) |
           └─────────────────┴──────────────────┴───────────────┘
                标记哪一块        定位到哪一组        行内 0-63 字节

/* Cache 行对齐声明：保证结构体不跨缓存行，减少伪共享 */
#include <stdint.h>

struct aligned_metrics {
    uint64_t read_count;
    uint64_t write_count;
} __attribute__((aligned(64)));     /* GCC：按 64 字节对齐 */

2.2 三层模型

命中（Hit）：Tag+Set 匹配，直接返回数据，消耗仅几个周期；未命中（Miss）：需要向下层取回整个 Cache Line，代价为几十到上百周期。未命中率是衡量程序访存质量的核心指标。

3. 映射方式

3.1 三种基本映射

映射方式决定一个内存块可以放入缓存中的哪些位置，直接影响命中率与硬件成本。

3.2 组相联详解

现代 CPU 的 L1 通常为 8 路组相联，L2/L3 为 8-16 路。n 路组相联 = 有 n 个"路"，同一组内的 n 行可各自来自不同内存块，冲突时按替换策略淘汰。

4 路组相联示意（Set 1 有 4 个 Way）：
Set 1: |Way0|Way1|Way2|Way3|
       |Tag A|Tag B|Tag C|Tag D|   ← 可同时容纳 4 个不同的块
访问新的 Tag E → 命中 Set 1 → 替换策略决定淘汰哪个 Way

伪共享/冲突陷阱：若两个热点地址映射到同一组同一路，会导致频繁替换、互相驱逐（冲突未命中）。优化手段：填充 padding、对齐、错开访问偏移。

4. 替换策略

4.1 常见策略对比

现代处理器常用改进型 LRU 或随机：LRU 在高关联度下硬件开销大，随机在 8 路以上命中率已接近 LRU。对于顺序流（如流式遍历大数组），任何策略都几乎一样，因为访问模式是流式的。

# LRU 替换示意（哈希 + 双向链表，O(1)）
class LRUCache:
    def __init__(self, ways):
        self.ways = ways
        self.order = []                 # 维护访问顺序
        self.data = {}

    def access(self, tag):
        if tag in self.data:
            self.order.remove(tag)      # 命中：移到最近使用
            self.order.append(tag)
            return self.data[tag]
        if len(self.data) >= self.ways:
            evict = self.order.pop(0)   # 淘汰最久未使用
            del self.data[evict]
        self.order.append(tag)
        self.data[tag] = None           # 未命中，加载
        return None

5. 写策略：写回与写直达

5.1 两种写协议

写操作比读复杂：写命中后数据最终必须回到内存，何时写回由策略决定。

写回策略的数据流：
写命中 → 只改 Cache 行 + 置脏位(Dirty)
... 行被替换时 → 若脏则写回主存 → 清脏位

写分配 vs 写不分配：写不命中时，Write-Through 通常"写不分配"（直接写内存不占 Cache）；Write-Back 通常"写分配"（先把整行读入 Cache 再改）。现代 CPU L1/L2 均用 Write-Back，少部分（如直写式视频内存）用 Write-Through。

/* 写回带来的可见性问题在 C/C++ 中的体现 */
volatile int flag = 0;   /* volatile 防止编译器优化，但不等价于内存屏障 */

/* 多核下正确同步需要原子/内存屏障，仅 volatile 不够 */

6. 缓存一致性：MESI 协议

6.1 多核一致性问题

每核有私有 L1/L2，同一内存块会在多个核的缓存中同时存在副本。某核修改自己的副本后，其他核必须感知——这就是缓存一致性（Cache Coherence）。目标是：任意时刻，对任一地址的所有读都看到同一份最新写入。

6.2 MESI 四种状态

状态迁移核心规则：
读未命中 → 若其他核有 E/M 需先写回，再以 S/E 装载
写命中 → 若状态是 S/M 需先使其他核副本失效（Invalidate），再写并置 M
任何核修改(M)时，必须让所有其他副本变为 I

6.3 MESI 协议运作

每个 Cache 行带两位状态位，总线事务在核间广播读/写请求。写共享行时执行总线失效（Bus Invalidate）：广播 Invalidate，其他核若持有该行副本则置 I。

/* 多核下的原子自增：即使加了缓存行对齐，仍需要原子指令保证正确 */
#include <stdatomic.h>

atomic_int counter;                    /* C11 原子类型，内部用 LOCK 前缀指令 */
void worker(int n) {
    for (int i = 0; i < n; i++)
        atomic_fetch_add(&counter, 1);
}

MESI 在真实处理器上以状态编码 + 总线嗅探实现，另外还有 MOESI（加 O Owned 状态，AMD）、MESIF（Intel 加 F Forward 状态）等变体。伪共享正是 S 状态下写命中引发 Invalidate 风暴的性能杀手（见第 8 节）。

7. 总线嗅探与目录协议

7.1 两种一致性实现架构

总线嗅探：写核发出 Invalidate → 所有核都"听到" → 持副本核置 I
目录协议：写核通知内存目录 → 目录查表 → 仅向持副本的核发 Invalidate

总线嗅探在写共享行时会把失效广播给所有核（无论是否持有），带宽开销随核数线性增长；目录协议通过维护"块 → 核集合"的目录，只通知相关核，避免全局广播，是规模化多核/多插槽服务器的必备方案。

7.2 一致性粒度与代价

一致性粒度为 Cache Line（64B），而非单个变量。这是伪共享问题的根源：粒度越粗，误伤越多；粒度越细，目录/标签开销越大。一致性还要求提供原子性（同一行内操作的串行化）与写序（所有核看到一致的写顺序）。

8. 伪共享与性能优化

8.1 伪共享（False Sharing）现象

伪共享：两个线程各自频繁修改不同的变量，但这两个变量恰好落在同一条 64 字节缓存行上。每次任一线程写入，都会使整条行失效并强制对方重新同步——明明没有真正的数据竞争，却像竞争一样互相拖慢。

共享同一 Cache Line：
|  thread A 的变量 x  |  thread B 的变量 y  |   (同一 64B 行)
   A 写 x → Invalidate 整行 → B 重新读取整行 → B 写 y → Invalidate → A 重读 ...
   → 行在核间"乒乓"传递，性能骤降

/* 伪共享示例：两个计数器挨着放，写密集场景互相拖慢 */
struct counters {
    long a;                          /* 线程 0 写 */
    long b;                          /* 线程 1 写 */   /* 相邻 → 伪共享 */
};

/* 修复 1：padding 填充到不同缓存行 */
struct padded_counters {
    long a;
    char pad[56];                    /* 填充到 64 字节边界 */
    long b;
};

/* 修复 2：C++11/C17 alignas 对齐到缓存行 */
struct alignas(64) counters2 {
    long a;
    long b;                          /* b 与 a 天然不同行 */
};

8.2 优化手段汇总

/* 每线程私有副本示例：避免原子操作与伪共享的双重代价 */
#include <pthread.h>

typedef struct { long sum; char pad[56]; } ThreadLocalSum;

void *worker(void *arg) {
    ThreadLocalSum *local = arg;         /* 每线程独立对象，天然不同行 */
    for (int i = 0; i < 1000000; i++)
        local->sum += 1;                 /* 无锁、无伪共享 */
    return NULL;
}
/* 最后把各线程 local->sum 汇总 */

判据：先用 perf c2c 或 VTune 确认**确实存在 Cache Line 乒乓（cross-node false sharing）**再优化，不要无脑 padding——过度 padding 会浪费宝贵的缓存空间。

9. 性能测量与分析工具

9.1 用硬件计数器测量

现代 CPU 内置性能监控单元（PMU），可精确统计缓存命中/未命中、行乒乓等事件，无需修改代码。

# 统计程序 cache 行为（Linux perf）
perf stat -e cache-references,cache-misses,cycles,instructions ./app

# 输出示例
#   cache-references  : 2,183,016,482
#   cache-misses      :   118,352,130   （未命中率 ~5.4%）
#   cycles            : 6,020,118,211
#   instructions      : 8,310,402,997

# 检测伪共享/行乒乓
perf c2c record ./app
perf c2c report            # 显示哪些缓存行在多核间竞争

9.2 量化收益的基准方法

/* 简单基准：测量"单线程写私有变量" vs "两个线程写相邻变量" */
// 场景 A：两个线程写不同缓存行（对齐）→ 吞吐 ≈ 单线程 × 2
// 场景 B：两个线程写同一缓存行（伪共享）→ 吞吐可能 < 单线程 × 1.2
double measure(int nthreads, int aligned) {
    double start = now();
    run_workers(nthreads, aligned);
    return elapsed(start);
}

优化路线图：先 perf stat 看 Miss 率 → 若高，检查循环遍历顺序（空间局部性）→ 若存在共享写热点，用 perf c2c 确认伪共享 → 按第 8 节手段修复 → 重新测量验证。

参考文章

• Wikipedia — CPU cache
• Wikipedia — Cache coherence / MESI protocol
• Intel 优化手册 — Memory Hierarchy & Cache
• Ulrich Drepper — What Every Programmer Should Know About Memory
• perf 官方文档 — perf c2c 与硬件计数器