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

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

铛版本7.0.1

海湾合作委员会8.2.0

的Python 3.7.2

i7-7700 CPU @ 3.60 GHz

$ 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。

这篇文章有两个问题：

问：如何提高std::set_intersectionC ++的性能？

使用sorted std::vector而不是set，这对缓存更友好。由于相交是在单遍中按顺序完成的，因此它将尽可能快。在我的系统上，我的运行时间为0.04 s。如果这是您需要的，请在这里停止。

问：... Python如何如此快地完成呢？

换句话说，“ 为什么Python的设置比C ++的设置快？ ”。在余下的文章中，我将重点讨论这个问题。

首先，Python set是一个哈希表，并且std::set是一个二叉树。因此，用于std::unordered_set将苹果与苹果进行比较（基于O（logN）查找复杂度，我们此时拒绝二叉树）。

还要注意，这std::set_intersection只是一个两指针算法；它遍历两个排序的集合，仅保留匹配的值。除了它的名称之外，它与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使用类似于PHP哈希表（通常是开放式寻址哈希表的类）的特殊形式的“密集哈希表”，而C ++ 通常是幼稚的或列表向量的哈希表。密集结构对缓存更友好，因此速度更快。有关实现的详细信息，请参见dictobject.c和setobject.c。std::unordered_set

对于std::hash要生成的已经独特的输入数据集，内置的C ++ 太复杂了。另一方面，Python使用标识（无操作）哈希函数来存储最大为2 ^30的整数（请参阅参考资料long_hash）。冲突由其哈希表实现中内置的LCG摊销。您无法将其与C ++标准库功能相匹配；不幸的是，此处的身份哈希将再次导致哈希表太稀疏。

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

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std::chrono_literals;

void elapsed(std::function f, const std::string& s)
{
    auto start = std::chrono::steady_clock::now();
    f();
    auto end = std::chrono::steady_clock::now();
    std::cout <
struct myhash {
    size_t operator()(T x) const {
        return x / 5; // cheating to improve data locality
    }
};

template 
using myset = std::unordered_set>;

template 
void fill_set(myset& s, T start, T end, T step)
{
    s.reserve((end - start) / step + 1);
    for (T i = start; i 
void intersect(const myset& s1, const myset& s2, myset& 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 s1;
    myset s2;
    myset s3;

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

    std::cout <<"s1 length = " <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