每周性能技巧 #83：减少内存间接访问

本文翻译自 Abseil 官网的 Performance Tip of the Week #83: Reducing memory indirections。

原文发布于 2024 年 6 月 17 日，作者 Chris Kennelly，更新于 2025 年 8 月 23 日。

内存间接访问是延迟和内存带宽瓶颈的常见原因。当处理器必须沿着指针寻找真正需要的数据时，程序会变慢，也会比更高效布局需要更多内存带宽。本篇讨论如何识别低效数据结构并改进它们。

延迟与吞吐量

在 Google fleet 中，处理器有 40% 到 50% 的时间在等待来自缓存或主内存的数据。内存访问延迟和吞吐量紧密相关：

• 软件访问次数越多，每次都相当于掷骰子，可能遇到 cache miss。并且，当单位时间访问率提高时，由于内存带宽饱和，核心会看到更高访问延迟。
• 每次访问时，如果处理器需要访问最外层缓存或主内存，程序都会付出更多延迟。

思考程序数据布局时，可以同时处理这两个因素。我们可以减少访问次数，或选择更可能复用已有数据的布局。改善这一点能让我们用更少 CPU 做更多有用工作。

帮助硬件帮助我们

PMU 事件是用于理解访问并识别缓存层次友好改动的代理指标。考虑一个链表：单个节点通常不是物理连续的，因为它们在堆上分配。没有这种相关性，硬件 prefetcher 无法帮我们隐藏访问延迟，最好情况也只是无能为力，坏时还可能访问逻辑上无关的相邻 cacheline，浪费带宽。

Arena 是非常有用的工具，但最好在优化数据结构之后再使用。一个更曲折但 Arena 分配的数据结构，很可能比一开始就使用最佳数据结构更差。

调查数据结构

考虑在 std::list、std::set、absl::node_hash_set 或 absl::flat_hash_set 中查找元素。可以用两种方式构造 benchmark：一种是连续做互不依赖的查找，另一种把一次查找的输出串到下一次输入中，以探测延迟特征。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

template<typename T>
void BM_LookupSpeed(benchmark::State& state) {
  using ValueType = T::value_type;
  const int size = std::max<int>(1, state.range(0) / sizeof(ValueType));
  // 选择 size 个随机整数，然后填充容器。
  absl::BitGen rng;
  std::vector<std::remove_cv_t<typename ValueType::first_type>> v;
  v.reserve(size);
  for (int i = 0; i < size; ++i) {
    v.push_back(absl::Uniform(
        rng,
        std::numeric_limits<typename ValueType::first_type>::min(),
        std::numeric_limits<typename ValueType::first_type>::max()));
  }
  T container;
  for (auto u : v) {
    if constexpr (std::is_same<T, std::list<ValueType>>::value) {
      container.emplace_back(u, u);
    } else {
      container.emplace(u, u);
    }
  }

  const auto begin = container.begin();
  const auto end = container.end();
  // 使用小状态 PRNG 选择索引，避免较大状态 RNG
  // 可能引入的访问计数混杂因素。
  std::minstd_rand lcg;
  uint32_t last = 0;
  uint64_t sum = 0;
  for (auto _ : state) {
    const size_t index = (lcg() + last) % size;
    const auto value = v[index];
    typename T::const_iterator it;
    if constexpr (std::is_same<T, std::list<ValueType>>::value) {
      it = std::find(begin, end, std::make_pair(value, value));
    } else {
      it = container.find(value);
    }
    ABSL_DCHECK(it != end);
    auto found = it->second;
    sum += found;

    // 为下一次查找的 key 引入对本次查找的有意依赖。
    last = found;
  }

  ABSL_CHECK_NE(sum, 0);
}

可以在运行 benchmark 时同时收集 PMU counter。完整输出显示：随着数据规模增长，std::list 因线性扫描和指针追踪急剧变慢；std::map 受树结构间接访问影响；absl::flat_hash_map 通常比 absl::node_hash_map 更少加载、更少 L1 miss。

这些容器因渐进复杂度而有明显差异，内存子系统也给它们的性能增加了可观缩放因子。

• 微基准中的 ALL_LOADS 数据符合预期。一个 256KB 的 uint32_t list 有 64K 个元素。查找平均要扫描一半元素，并且扫描还要读取指向下一个节点的指针，访问次数翻倍。这些控制数据会被缓存，但对程序并没有内在用处。不同数据结构每次查找需要的内存访问次数不同。
• L1_MISS 让我们从“程序访问多少 cacheline”的角度区分访问效率。许多加载落在同一个 cacheline 上，例如既访问 next 指针元数据又访问值，或者最终查找值时同时访问 key 和 mapped value。

寻找不必要的间接访问

要找不必要的间接访问，我们关注堆分配及其访问模式，因为很多访问都发生在这些数据结构上。全局对象往往没那么复杂：保存一个值的命令行 flag 很常见，但复杂且无分配的数据结构相对少见。

我们也寻找被频繁访问的分配。这是定性而非定量阈值，取决于上下文。扁平化一个太冷的数据结构，可能因 RAM 成本过高而不值得，甚至伤害缓存效率。

结合这两个因素，我们常寻找“一个对象生命周期是另一个对象超集”的位置。例如，std::unique_ptr 成员变量可能在构造时初始化，在析构时释放。相比之下，std::shared_ptr 持有的东西生命周期不确定，较不适合耦合。

分配

小而频繁的分配是很好的优化候选：

• 小分配 cacheline 效率低，因为我们既需要存储指向分配的指针，也需要存储对象本身，还可能触碰无关相邻数据。
• 短生命周期限制了没使用所有数据时的误差。它也提供访问频率的粗略代理：每次分配的字节一般都应该至少被触碰一次，否则可以让分配更小。像 std::vector 这样的摊销增长容器可能比需要略大一个小常数因子，通常是 2 倍；很大的常数因子通常说明 reserve 参数太大。

可以用 TCMalloc 的 deallocation profiler 显式按生命周期过滤，或把 allocation profile 和 heap profile 结合起来寻找它们。

检查频繁分配也能帮助发现完全消除分配的机会：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

rpc::StreamStatsInfo* stats_info = new rpc::StreamStatsInfo;
// ...填充 stats_info...
data.stats_info = stats_info;
// ...填充 data...
GetStreamMultiplexer()->HandleBytes(&data);
delete stats_info;

rpc::StreamStatsInfo stats_info;
// ...填充 stats_info...
data.stats_info = &stats_info;
// ...填充 data...
GetStreamMultiplexer()->HandleBytes(&data);
// stats_info 在离开作用域时销毁

stats_info 只有 120 字节，因此通过 data.stats_info 访问字段可能涉及 4 个 cacheline：data.stats_info 本身，以及 *stats_info 的 2 到 3 个 cacheline，取决于对齐。使用栈不会让对象缓存足迹归零，但这些 cacheline 更可能已经驻留，并且连续性让它更容易被 prefetch。

结语

减少不必要的内存间接访问，可以同时改善延迟和内存带宽。关键是从真实 profile 出发，找出频繁访问、生命周期适合合并、且扁平化不会带来过大 RAM 成本的数据结构。