C++内存局部性优化与基准测试设计

1. 局部性基准测试的设计思想解析

在现代C++性能优化中，内存访问模式对程序性能的影响往往比算法复杂度更为关键。这个基准测试的核心目标是通过精心设计的数据结构和访问模式，让"访问局部性"成为决定性能的主导因素，从而量化评估不同内存分配策略对程序性能的影响。

1.1 局部性的两种类型

1.1.1 时间局部性(Temporal Locality)

时间局部性指的是如果一个数据项被访问过，那么它在短时间内很可能再次被访问。从概率角度可以表示为：

P(在t+Δt时刻访问 | 在t时刻访问)

当Δt很小时，这个条件概率会显著增大。在实际程序中，循环结构中的变量访问、频繁调用的函数参数等都表现出强时间局部性。

1.1.2 空间局部性(Spatial Locality)

空间局部性指的是如果访问了某个内存地址x，那么地址x±k（k很小）的位置也很可能被访问。典型场景包括：

• 数组顺序访问
• 结构体字段访问
• 指令顺序执行

数学上可以表示为|k| ≪ 内存总量，这意味着连续的内存访问更容易命中CPU缓存。

1.2 基准测试的设计目标

这个基准测试的设计包含以下几个关键考量点：

1. 研究访问局部性：重点考察cache行为、TLB和内存层级的影响，而非算法复杂度
2. 时空双重观察：同时测量空间局部性和时间局部性的影响
3. 并发子系统模拟：使用多个独立数据块而非单一数组
4. 变量独立控制：子系统数量和大小可以独立调整
5. 确保局部性主导：消除malloc开销、线程创建等干扰因素
6. 长时间数据访问：访问时间要足够长（小时级）以减少setup时间的影响

2. 测试数据结构设计与分析

2.1 vector<list>的选择

测试采用vector<list>作为核心数据结构，这种设计有意制造了"坏局部性"的场景：

cpp复制std::vector<std::list<int>> systems(N);  // N个子系统
for(auto& s : systems) {
    for(int i=0; i<M; ++i) {
        s.push_back(i);  // 每个节点独立分配
    }
}