颜林林的个人网站

flat_set的性能测试及其实现

2024-01-15 11:22
题图
(题图由AI生成)

之前在《从flat_set管窥C++的价值权衡》中没放代码,今天补上(照惯例,文末“阅读原文”可跳转至GitHub完整源码)。

如前所述,flat_set 的用法与 std::set 几乎完全一样,差别主要在于内存布局和性能。由于 flat_set 能保证所包含的元素按次序存储在连续内存空间中,因此,它(的迭代器)还允许进行随机访问。下面的例子展示了基本用法:

 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
#include <boost/container/flat_set.hpp> // 或 <flat_set>
#include <set>
#include <iostream>

int main()
{
  std::flat_set<int> fs;
  fs.insert(1);
  fs.insert(2);
  fs.insert(3);
  for (int e : fs) {
    std::cout << e << std::endl;
  }
  // 下面是随机访问的示例(迭代器加上一个整数)
  std::cout << "The second: " << *(fs.begin() + 1) << std::endl;

  std::set<int> ss;
  fs.insert(1);
  fs.insert(2);
  fs.insert(3);
  for (int e : fs) {
    std::cout << e << std::endl;
  }
  // 对于std::set,则不允许这样的随机访问,下面的语句会导致编译器报错
  //std::cout << "The second: " << *(ss.begin() + 1) << std::endl;

  return 0;
}

接下来是重点,性能测试,这里只展示主要的部分代码:

1
2
3
4
5
6
#if __cplusplus < 202002L
#include <boost/container/flat_set.hpp>
namespace std {
  using boost::container::flat_set;
}
#endif

上面这几句是为了兼容在正式将 flat_set 引入 C++ 标准之前,使用 boost 库中的相应实现进行代替。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
std::vector<int> generateRandomData(size_t size) {
    std::vector<int> data(size);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000000);

    for (auto& d : data) {
        d = dis(gen);
    }
    return data;
}

上面这个函数用于生成一组随机数,以便将其分别用于 std::set 和 flat_set 的测试。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
template<typename SetType>
void performTest(SetType& testSet, const std::vector<int>& data) {
  // 插入操作
  auto start = std::chrono::high_resolution_clock::now();
  ...
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << "Insert time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " microseconds\n";
 
  // 查找操作
  ...
 
  // 迭代操作
  ...
}

上面的函数是测试主体内容,使用了模板函数,从而可以确保对不同的类型(flat_set 和 std::set)分别进行同样的测试。函数中测试了插入、查找和迭代遍历的操作,分别在操作前后使用 std::chrono::high_resolution_clock::now() 获取精确时间,从而计算并打印出每个操作的执行时间。

主函数中的内容如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int main() {
  const size_t TEST_SIZE = 1000000; // 调整测试数据的大小
  auto data = generateRandomData(TEST_SIZE); // 为公平比较,需确保处理相同的随机数据
 
  std::cout << "Testing flat_set...\n";
  std::flat_set<int> fs;
  performTest(fs, data);
 
  std::cout << "\nTesting std::set...\n";
  std::set<int> ss;
  performTest(ss, data);
 
  ...
  return 0;
}

程序执行的结果如下:

可以看到,flat_set 在查找和迭代遍历的速度,都明显快于 std::set,但相应做出的牺牲,则是在数据插入上,明显慢于 std::set。因此,可以知道,对于修改少但访问频繁的数据(这种场景在现实中应该还是相当常见的),是应该考虑使用 flat_set 来代替 std::set 的。 当然,具体使用哪种容器类,还需要依赖于最终所处理的数据,如果对性能要求较高,则应该选取有代表性的实际数据进行测试,来帮助决定。而 STL 统一了各种容器的常见操作接口,让容器之间选择替换变得非常容易,这也是我们应该优先使用标准库的实现,而如果我们自行实现,也应该尽量遵守标准库的规范来进行的重要原因。 测试代码还同时展示了两个集合类的前五个元素的地址,能看到 flat_set 的地址的确都是连续的,而 std::set 则不是。 最后,再来说说实现(这里可以看看 boost 中的实现):

为方便展示,这里使用了来自ClickHouse的截图。想查看和学习相应实现的,也推荐使用这个网址在线浏览学习代码(https://clickhouse.com/codebrowser/ClickHouse/contrib/boost/boost/container/flat_set.hpp.html)。 从上面的代码中可以看到,flat_set::insert() 调用了其成员变量 tree_t 的 insert_unique() 方法。该成员变量的类型,来自于 boost 库的底层实现支持,之所以这么封装,是因为它还可以同时用于支持其他 flat_xxx 类型(如 flat_map)的实现。

我们继续深入到 flat_tree::insert_unique() 中:

可以看到,该插入其实分为三个步骤:(1) 在容器末尾插入新元素;(2) 快速排序;(3) 将重复元素去掉。这里的步骤二(排序)是最耗时的,也因此使用了通常被认为效率最高的快速排序方法,来确保时间复杂度为 O(n * log(n))。 这个分步骤的做法,看起来很绕,但其实它是 STL / boost 中常见的套路,类似于那个“数学家当消防员”的笑话:

一天,数学家觉得自己受够了数学,于是他跑去消防队当消防员。
消防队长说:“您看上去不错,可是我得先给您一个测试。”
消防队长带数学家到消防队后院小巷,巷子里有一个货栈,一只消防栓和一卷软管。
消防队长问:“假设货栈起火,您怎么办?”
数学家回答:“我把消防栓接到软管上,打开水龙,把火浇灭。”
消防队长说:“完全正确。最后一个问题:假设您走进小巷,而货栈没有起火,您怎么办?”
数学家疑惑地思索了半天,终于答道:“我就把货栈点着。”
消防队长大叫起来:“什么?太可怕了,您为什么要把货栈点着?”
数学家回答:“这样我就把问题化简为一个我已经解决过的问题了。”

在数学中,这种思考方式被称为化归。

STL / boost 常把各种看似复杂的算法,都化归到很少的几个底层算法去。于是,这些底层算法被大量使用和测试,形成了今天稳定的、容错性极好的基础库。这些库对于应付大多数情况而言,是绰绰有余的。而真当性能仍然不足以达到要求时,就得考虑根据自己实际需求进行重新实现了。

--- END ---

注:本文首发表于“不靠谱颜论”公众号,并同步至本站。

相关文章