c++ - 如何提高 C++ 中的 std::set_intersection 性能？

Question

在尝试使用 C++ 中的 std::set 和 Python 中的 set() 期间，我遇到了无法解释的性能问题。在 C++ 中设置交集至少比 Python 慢 3 倍。

那么有人能指出我可以对 C++ 代码进行的优化和/或解释 Python 如何更快地做到这一点吗？

我希望他们都使用类似的算法，复杂度为 O(n)，而 set 是有序的。但可能 Python 做了一些优化，所以它达到了更小的系数。

set_bench.cc

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <chrono>
#include <functional>
#include <thread>

void elapsed(std::function<void()> f, const std::string& s)
{
    auto start = std::chrono::steady_clock::now();
    f();
    std::chrono::duration<double> elapsed = std::chrono::steady_clock::now() - start;
    std::cout << s << " " << elapsed.count() << " seconds" << std::endl;
}

template <typename T>
void fill_set(std::set<T>& s, T start, T end, T step)
{
    for (T i = start; i < end; i += step) {
        s.emplace(i);
    }
}

template <typename T>
void intersect(const std::set<T>& s1, const std::set<T>& s2, std::set<T>& result)
{
    std::set_intersection(s1.begin(), s1.end(),
                            s2.begin(), s2.end(),
                            std::inserter(result, result.begin()));
}

int main()
{
    std::set<int64_t> s1;
    std::set<int64_t> s2;
    std::set<int64_t> s3;

    elapsed(std::bind(fill_set<int64_t>, std::ref(s1), 8, 1000*1000*100, 13), "fill s1 took");
    elapsed(std::bind(fill_set<int64_t>, std::ref(s2), 0, 1000*1000*100, 7), "fill s2 took");

    std::cout << "s1 length = " << s1.size() << ", s2 length = " << s2.size() << std::endl;

    elapsed(std::bind(intersect<int64_t>, std::ref(s1), std::ref(s2), std::ref(s3)), "intersect s1 and s2 took");

    std::cout << "s3 length = " << s3.size() << std::endl;

    // sleep to let check memory consumption
    // while (true) std::this_thread::sleep_for(std::chrono::milliseconds(1000));
}

set_bench.py

#!/usr/bin/env python3

import time

def elapsed(f, s):
    start = time.monotonic()
    f()
    elapsed = time.monotonic() - start
    print(f'{s} {elapsed} seconds')

def fill_set(s, start, end, step=1):
    for i in range(start, end, step):
        s.add(i)

def intersect(s1, s2, result):
    result.update(s1 & s2)

s1 = set()
s2 = set()

elapsed(lambda : fill_set(s1, 8, 1000*1000*100, 13), 'fill s1 took')
elapsed(lambda : fill_set(s2, 0, 1000*1000*100, 7), 'fill s2 took')

print(f's1 length = {len(s1)}, s2 length = {len(s2)}')


s3 = set()

elapsed(lambda: intersect(s1, s2, s3), 'intersect s1 and s2 took')

print(f's3 length = {len(s3)}')

# sleep to let check memory consumption
# while True: time.sleep(1)

以下是在下一个环境中运行此程序的结果:

叮当版 7.0.1

gcc 8.2.0

Python 3.7.2

i7-7700 CPU @ 3.60GHz

$ clang -lstdc++ -O0 set_bench.cc -o set_bench && ./set_bench
fill s1 took 5.38646 seconds
fill s2 took 10.5762 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 1.48387 seconds
s3 length = 1098901

$ clang -lstdc++ -O1 set_bench.cc -o set_bench && ./set_bench
fill s1 took 3.31435 seconds
fill s2 took 6.41415 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 1.01276 seconds
s3 length = 1098901

$ clang -lstdc++ -O2 set_bench.cc -o set_bench && ./set_bench
fill s1 took 1.90269 seconds
fill s2 took 3.85651 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.512727 seconds
s3 length = 1098901

$ clang -lstdc++ -O3 set_bench.cc -o set_bench && ./set_bench
fill s1 took 1.92473 seconds
fill s2 took 3.72621 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.523683 seconds
s3 length = 1098901

$ gcc -lstdc++ -O3 set_bench.cc -o set_bench && time ./set_bench
fill s1 took 1.72481 seconds
fill s2 took 3.3846 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.516702 seconds
s3 length = 1098901

$ python3.7 ./set_bench.py 
fill s1 took 0.9404696229612455 seconds
fill s2 took 1.082577683031559 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.17995300807524472 seconds
s3 length = 1098901

正如你所看到的结果是相等的，所以我假设两个程序都做相同的计算。

顺便说一句 - C++ 程序的 RSS 是 1084896 kB，而 Python 的 RSS 是 1590400 kB。

Answer 1

这篇文章有两个问题:

Q: How to improve std::set_intersection performance in C++?

使用排序的 std::vector s 而不是集合，这对缓存更友好。由于交叉是在单次通过中顺序完成的，因此它将尽可能快。
在我的系统上，我得到了 0.04 s 运行时间。
如果这就是您所需要的，请停在这里。

Q: ... how [does] Python do this so much faster?

或者换句话说“ 为什么 Python 的 set 比 C++ 的 set 快？”。我将在我的帖子的其余部分关注这个问题。

首先，Python 的 set 是 hash table ， std::set 是 binary tree 。因此，使用 std::unordered_set 将苹果与苹果进行比较(此时我们根据其 O(logN) 查找复杂度拒绝二叉树)。

还要注意 std::set_intersection 只是一个 two-pointer algorithm ；它迭代两个排序的集合，只保留匹配的值。
除了它的名字之外，与 Python 的 set_intersection 没有任何共同之处，它本身只是一个简单的循环:

迭代较小的哈希表

对于每个元素，如果它存在于另一个哈希表中，则将其添加到结果中

所以我们不能对未排序的数据使用std::set_intersection，需要实现循环:

    for (auto& v : set1) {
        if (set2.find(v) != set2.end()) {
            result.insert(v);
        }
    }

这里没什么好看的。不幸的是，尽管这个算法在 std::unordered_set 上的直接应用是 仍然比 慢了 3 倍。这怎么可能？

我们观察到输入数据集的大小 > 100MB。这无法容纳 i7-7700 的 8MB 缓存，这意味着在 8MB 的范围内可以容纳的工作越多，程序执行的速度就越快。

Python 使用一种类似于 "dense hash table" 的特殊形式的 PHP hash table(通常是一类 open addressing 哈希表)，而 C++ std::unordered_set 通常是一个简单的或列表 vector 哈希表。密集结构对缓存更友好，因此速度更快。有关实现细节，请参阅 dictobject.c 和 setobject.c 。

内置的 C++ std::hash<long> 对于您正在生成的已经唯一的输入数据集来说太复杂了。另一方面，Python 对高达 230 的整数使用身份(无操作)散列函数(请参阅 long_hash )。冲突由内置在其哈希表实现中的 LCG 摊销。您无法将其与 C++ 标准库功能相匹配；不幸的是，这里的身份哈希将再次导致过于稀疏的哈希表。

Python 使用自定义内存分配器 pymalloc ，它类似于 jemalloc 并针对数据局部性进行了优化。它通常优于内置的 Linux tcmalloc，这是 C++ 程序通常使用的。

有了这些知识，我们可以设计一个类似性能的 C++ 版本，以证明技术可行性:

#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <iterator>
#include <chrono>
#include <functional>
#include <thread>
#include <tuple>
#include <string>

using namespace std::chrono_literals;

void elapsed(std::function<void()> f, const std::string& s)
{
    auto start = std::chrono::steady_clock::now();
    f();
    auto end = std::chrono::steady_clock::now();
    std::cout << s << " " << (end - start) / 1.0s << " seconds" << std::endl;
}

template <typename T>
struct myhash {
    size_t operator()(T x) const {
        return x / 5; // cheating to improve data locality
    }
};

template <typename T>
using myset = std::unordered_set<T, myhash<T>>;

template <typename T>
void fill_set(myset<T>& s, T start, T end, T step)
{
    s.reserve((end - start) / step + 1);
    for (T i = start; i < end; i += step) {
        s.emplace(i);
    }
}

template <typename T>
void intersect(const myset<T>& s1, const myset<T>& s2, myset<T>& result)
{
    result.reserve(s1.size() / 4); // cheating to compete with a better memory allocator
    for (auto& v : s1)
    {
        if (s2.find(v) != s2.end())
            result.insert(v);
    }
}

int main()
{
    myset<int64_t> s1;
    myset<int64_t> s2;
    myset<int64_t> s3;

    elapsed(std::bind(fill_set<int64_t>, std::ref(s1), 8, 1000 * 1000 * 100, 13), "fill s1 took");
    elapsed(std::bind(fill_set<int64_t>, std::ref(s2), 0, 1000 * 1000 * 100, 7), "fill s2 took");

    std::cout << "s1 length = " << s1.size() << ", s2 length = " << s2.size() << std::endl;

    elapsed(std::bind(intersect<int64_t>, std::ref(s1), std::ref(s2), std::ref(s3)), "intersect s1 and s2 took");

    std::cout << "s3 length = " << s3.size() << std::endl;
}

使用此代码，我在 C++ 和 Python 版本中都获得了 0.28 秒的运行时间。

现在，如果我们想击败 Python 的设置性能，我们可以删除所有作弊并使用 Google 的 dense_hash_set ，它通过二次探测实现 open addressing ，作为替代品(只需要调用 set_empty_object(0) )。

使用 google::dense_hash_set 和无操作散列函数，我们得到:

fill s1 took 0.321397 seconds
fill s2 took 0.529518 seconds
s1 length = 7692308, s2 length = 14285714
intersect s1 and s2 took 0.0974416 seconds
s3 length = 1098901

或者比 Python 快 2.8 倍，同时保持哈希集功能!

附言有人会想 - 为什么 C++ 标准库要实现这么慢的哈希表？
无免费午餐定理在这里也适用:基于探测的解决方案并不总是很快；作为一种机会主义的解决方案，它有时会遇到“聚集”(无休止地探索被占用的空间)。
当这种情况发生时，性能会呈指数级下降。
标准库实现背后的想法是保证所有可能输入的可预测性能。不幸的是，尽管缓存对现代硬件的影响太大而不容忽视，正如 Chandler Carruth 在 his talk 中解释的那样。