在大型代码库中，我们常常会遇到影响性能的不良设计。我们可能正在寻找一种非侵入式的方法来提高性能。例如，您可能不想更改函数签名。
让我们考虑一个具体示例。也许有人设计了编程接口，使得您必须使用索引从映射中访问值。他们可能有如下代码：
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
|
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是最佳选择。您可能担心thread_local变量的性能影响，但通常相当廉价：在访问或修改时我们只添加几条指令。
我们的缓存变量记住每个线程最后访问的迭代器和索引。如果请求下一个索引，我们只需递增迭代器并返回。如果访问是非顺序的或是第一次调用，它会回退到从头开始的线性扫描，并在此过程中重建缓存。
代码更复杂，如果您不按顺序访问键，它可能会更慢。然而，性能提升可能是巨大的。我编写了一个基准测试来测试包含400个元素的映射。
| 方法 |
纳秒/键 |
指令/键 |
| 原始方法 |
300 |
2000 |
| 缓存方法 |
2 |
20 |
在我的测试中，缓存将性能提高了150倍。不错的结果。