C++ `std::flat_map` / `flat_set` (C++23) 的缓存局部性与性能优势

哈喽，各位好！今天咱们来聊聊C++23标准库里新来的小伙伴：std::flat_map 和 std::flat_set。这俩家伙，说白了，就是想在缓存局部性上做文章，试图在特定场景下榨干CPU的最后一滴性能。

一、为啥要关注缓存局部性？

在深入 flat_map 和 flat_set 之前，咱们先得搞清楚一个问题：缓存局部性到底是个啥玩意儿？简单来说，CPU访问内存的速度比访问缓存快得多。当CPU需要数据时，它首先会检查缓存里有没有。如果有（命中），那就万事大吉，速度飞快。如果没有（未命中），就得去内存里取，然后再放到缓存里。缓存未命中的代价很高，会严重影响程序的性能。

缓存局部性指的是CPU访问内存的模式。如果CPU访问的数据在内存中是连续存储的，那么缓存命中的概率就会很高。反之，如果数据分散在内存的各个角落，那缓存就得频繁地从内存里搬运数据，性能自然就下来了。

想象一下，你是个图书馆管理员，需要从书架上找书。如果你要找的书都在同一排书架上，那效率肯定很高。但如果书分散在不同的楼层，那你就得跑上跑下，累个半死。

二、std::map 和 std::set 的痛点

传统的 std::map 和 std::set 是基于红黑树实现的。红黑树的特点是动态平衡，插入和删除操作的时间复杂度是O(log n)。但是，红黑树的节点在内存中是分散存储的，彼此之间通过指针连接。

这意味着什么呢？当你遍历 std::map 或 std::set 时，CPU需要不断地通过指针跳转到不同的内存地址，这会导致大量的缓存未命中。特别是当数据量很大时，这种影响会更加明显。

举个例子，假设你有一个 std::map<int, string>，存储了100万个键值对。当你遍历这个 map 时，CPU可能需要访问100万个不同的内存地址。如果这些地址分散在内存的各个角落，那缓存未命中的概率就会非常高。

三、std::flat_map 和 std::flat_set 的解决方案

std::flat_map 和 std::flat_set 的核心思想是：将数据存储在一个连续的数组中。这样，当你遍历数据时，CPU就可以顺序地访问内存，从而提高缓存命中的概率。

std::flat_map 和 std::flat_set 的实现方式通常是：

使用 std::vector 存储数据。 std::vector 保证了数据的连续存储。
保持数据排序。 插入和删除操作需要维护数据的排序，可以使用二分查找等算法来提高效率。

这种方式的优点是：

缓存局部性好。 数据在内存中是连续存储的，可以提高缓存命中的概率。
遍历速度快。 顺序访问内存的速度很快。

当然，这种方式也有缺点：

插入和删除操作的时间复杂度较高。 由于需要维护数据的排序，插入和删除操作的时间复杂度是O(n)。这比红黑树的O(log n)要慢。
需要预先分配内存。 std::flat_map 和 std::flat_set 需要预先分配内存，可能会造成一定的内存浪费。

四、代码示例

下面是一些代码示例，展示了如何使用 std::flat_map 和 std::flat_set。

#include <iostream>
#include <flat_map>
#include <flat_set>
#include <map>
#include <set>
#include <chrono>
#include <random>

using namespace std;
using namespace std::chrono;

int main() {
  // 初始化随机数生成器
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> distrib(1, 1000000);

  // 数据量
  size_t data_size = 10000;

  // 测试 std::map
  map<int, int> my_map;
  auto start = high_resolution_clock::now();
  for (size_t i = 0; i < data_size; ++i) {
    my_map[distrib(gen)] = i;
  }
  auto end = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(end - start);
  cout << "std::map insertion time: " << duration.count() << " microseconds" << endl;

  start = high_resolution_clock::now();
  for (auto const& [key, val] : my_map) {
     // 迭代
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::map iteration time: " << duration.count() << " microseconds" << endl;

  // 测试 std::flat_map
  flat_map<int, int> my_flat_map;
  start = high_resolution_clock::now();
  for (size_t i = 0; i < data_size; ++i) {
    my_flat_map[distrib(gen)] = i;
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::flat_map insertion time: " << duration.count() << " microseconds" << endl;

  start = high_resolution_clock::now();
  for (auto const& [key, val] : my_flat_map) {
    // 迭代
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::flat_map iteration time: " << duration.count() << " microseconds" << endl;

  // 测试 std::set
  set<int> my_set;
  start = high_resolution_clock::now();
  for (size_t i = 0; i < data_size; ++i) {
    my_set.insert(distrib(gen));
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::set insertion time: " << duration.count() << " microseconds" << endl;

    start = high_resolution_clock::now();
  for (auto const& val : my_set) {
    // 迭代
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::set iteration time: " << duration.count() << " microseconds" << endl;

  // 测试 std::flat_set
  flat_set<int> my_flat_set;
  start = high_resolution_clock::now();
  for (size_t i = 0; i < data_size; ++i) {
    my_flat_set.insert(distrib(gen));
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::flat_set insertion time: " << duration.count() << " microseconds" << endl;

  start = high_resolution_clock::now();
  for (auto const& val : my_flat_set) {
    // 迭代
  }
  end = high_resolution_clock::now();
  duration = duration_cast<microseconds>(end - start);
  cout << "std::flat_set iteration time: " << duration.count() << " microseconds" << endl;

  return 0;
}

五、性能对比

理论上，std::flat_map 和 std::flat_set 在遍历操作上应该比 std::map 和 std::set 更快。但是，在插入和删除操作上，std::flat_map 和 std::flat_set 可能会更慢。

为了更直观地了解它们的性能差异，我们可以进行一些简单的测试。比如，我们可以测试插入、查找和遍历操作的时间。

六、适用场景

那么，在什么情况下应该使用 std::flat_map 和 std::flat_set 呢？

一般来说，以下情况可以考虑使用 std::flat_map 和 std::flat_set：

数据量不大。 如果数据量很小，那么缓存局部性的优势可能不明显。
插入和删除操作较少。 如果插入和删除操作很频繁，那么 std::flat_map 和 std::flat_set 的性能可能会下降。
遍历操作较多。 如果需要频繁地遍历数据，那么 std::flat_map 和 std::flat_set 可以提高性能。
对内存占用不敏感。 std::flat_map 和 std::flat_set 需要预先分配内存，可能会造成一定的内存浪费。

总而言之，std::flat_map 和 std::flat_set 是一种以空间换时间的策略。它们通过将数据存储在一个连续的数组中，来提高缓存局部性，从而提高遍历速度。但是，它们在插入和删除操作上的性能可能会下降。

七、总结

std::flat_map 和 std::flat_set 是C++23标准库中新增的两个容器，它们通过提高缓存局部性来优化性能。它们适用于数据量不大、插入和删除操作较少、遍历操作较多的场景。

简单来说：

特性	`std::map` / `std::set`	`std::flat_map` / `std::flat_set`
实现	红黑树	排序的 `std::vector`
缓存局部性	较差	较好
插入/删除	O(log n)	O(n)
查找	O(log n)	O(log n) (二分查找)
遍历	较慢	较快
内存占用	动态分配，更灵活	预先分配，可能浪费
适用场景	频繁插入/删除，数据量大	频繁遍历，数据量不大

希望今天的讲解对大家有所帮助！记住，选择合适的容器要根据具体的应用场景来决定。别一上来就盲目追求“新”技术，要结合实际情况，权衡利弊。

最后，祝大家编程愉快！

发表回复 取消回复

发表回复取消回复