使用thread_local缓存加速C++函数

在大型代码库中，我们常常会遇到设计不佳但影响性能的接口。有时我们需要寻找非侵入式的方法来提升性能，比如不改变函数签名的情况下进行优化。

问题场景

考虑一个具体例子：某个编程接口要求通过索引从映射中获取值。原始代码如下：

1
2
3
4
5
6
7
8
9


auto at_index(map_like auto& index_map, size_t idx) {
  size_t count = 0;
  for (const auto &[key, value] : index_map) {
    if(count == idx)
      return value;
    count++;
  }
  throw std::out_of_range("Index out of range");
}

这段代码需要遍历映射键idx次，通常涉及某种链表遍历。如果被迫使用这个接口，遍历所有值可能需要重复调用at_index函数：

1
2
3


for (size_t i = 0; i < input_size; ++i) {
    at_index(index_map, i);
}

这导致了二次复杂度问题：如果映射大小翻倍，运行时间可能变为四倍。对于2或4个元素可能还能接受，但对于400个元素就不可行了。

解决方案

理想方案是避免这种设计，直接迭代映射：

1
2
3


for (auto& [key, value] : index_map) {
   sum += value;
}

但如果无法修改接口呢？假设映射在实践中不会被修改，可以使用static或thread_local缓存。关键思路是在缓存中保存映射中的位置，从该位置开始下一次查询。

 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


auto at_index_thread_local_cache(map_like auto& index_map, size_t idx) {
  using iterator = decltype(index_map.begin());
  struct Cache {
    iterator last_iterator;
    size_t last_index = -1;
    decltype(&index_map) map_ptr = nullptr;
  };
  thread_local Cache cache;
  
  if (cache.map_ptr == &index_map
      && idx == cache.last_index + 1
      && cache.last_iterator != index_map.end()) {
    cache.last_iterator++;
    cache.last_index = idx;
    if (cache.last_iterator != index_map.end()) {
      return cache.last_iterator->second;
    } else {
      throw std::out_of_range("Index out of range");
    }
  } else {
    cache.last_iterator = index_map.begin();
    cache.last_index = -1;
    cache.map_ptr = &index_map;
    size_t count = 0;
    for (auto it = index_map.begin(); it != index_map.end(); ++it) {
      if (count == idx) {
        cache.last_iterator = it;
        cache.last_index = idx;
        return it->second;
      }
      count++;
    }
    throw std::out_of_range("Index out of range");
  }
}

技术细节

在C++中，thread_local变量在同一线程内的所有函数调用间共享单个实例。如果想在整个程序中只有一个实例，可以使用static，但在这种情况下thread_local是最佳选择。

缓存变量记住每个线程最后访问的迭代器和索引。如果请求下一个索引，只需递增迭代器并返回。如果访问是非顺序的或是第一次调用，则回退到从头开始的线性扫描，并在此过程中重建缓存。

性能对比

对包含400个元素的映射进行基准测试：

方法	纳秒/键	指令数/键
原始方法	300	2000
缓存方法	2	20

在此案例中，缓存将性能提高了150倍。

注意事项

代码变得更复杂，如果不是按顺序访问键，可能会更慢。此外，需要确保映射在缓存使用期间不被修改，否则会导致未定义行为。