c++ - 为什么迭代 std::set 比迭代 std::vector 慢得多？

Question

在优化性能关键代码时，我注意到迭代 std::set 有点慢。

然后我编写了一个基准测试程序，并测试了迭代器 ( auto it : vector ) 对 vector 的迭代速度，迭代器对集合的迭代速度，以及索引 ( int i = 0; i < vector.size(); ++i ) 对 vector 的迭代速度。

容器的构造相同，有 1024 个随机整数。 (当然，每个 int 都是唯一的，因为我们使用的是集合)。然后，对于每次运行，我们循环遍历容器并将它们的整数相加为一个长整型。每次运行有 1000 次迭代求和，测试是 1000 次运行的平均值。

这是我的结果:

Testing vector by iterator
✓           
Maximum duration: 0.012418
Minimum duration: 0.007971
Average duration: 0.008354

Testing vector by index
✓           
Maximum duration: 0.002881
Minimum duration: 0.002094
Average duration: 0.002179

Testing set by iterator
✓           
Maximum duration: 0.021862
Minimum duration: 0.014278
Average duration: 0.014971

正如我们所见，通过迭代器迭代集合比通过 vector 慢 1.79 倍，比通过索引 vector 慢 6.87 倍之多。

这是怎么回事？集合不只是一个结构化 vector ，用于检查每个项目在插入时是否唯一吗？为什么要慢这么多？

编辑:感谢您的回复!很好的解释。根据要求，这里是基准代码。

#include <chrono>
#include <random>
#include <string>
#include <functional>
#include <set>
#include <vector>

void benchmark(const char* name, int runs, int iterations, std::function<void(int)> func) {
    printf("Testing %s\n", name);

    std::chrono::duration<double> min = std::chrono::duration<double>::max();
    std::chrono::duration<double> max = std::chrono::duration<double>::min();
    std::chrono::duration<double> run = std::chrono::duration<double>::zero();
    std::chrono::duration<double> avg = std::chrono::duration<double>::zero();

    std::chrono::high_resolution_clock::time_point t1;
    std::chrono::high_resolution_clock::time_point t2;

    // [removed] progress bar code
    for (int i = 0; i < runs; ++i) {
        t1 = std::chrono::high_resolution_clock::now();

        func(iterations);

        t2 = std::chrono::high_resolution_clock::now();

        run = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);

        // [removed] progress bar code

        if (run < min) min = run;
        if (run > max) max = run;   
        avg += run / 1000.0;
    }
    // [removed] progress bar code

    printf("Maximum duration: %f\n", max.count());
    printf("Minimum duration: %f\n", min.count());
    printf("Average duration: %f\n", avg.count());

    printf("\n");
}

int main(int argc, char const *argv[]) {
    const unsigned int arrSize = 1024;

    std::vector<int> vector; vector.reserve(arrSize);
    std::set<int> set;

    for (int i = 0; i < arrSize; ++i) {
        while (1) {
            int entry = rand() - (RAND_MAX / 2);
            auto ret = set.insert(entry);
            if (ret.second) {
                vector.push_back(entry);
                break;          
            }
        }
    }

    printf("Created vector of size %lu, set of size %lu\n", vector.size(), set.size());

    benchmark("vector by iterator", 1000, 1000, [vector](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (auto it : vector) {
                sum += it;
            }
        }
    });

    benchmark("vector by index", 1000, 1000, [vector, arrSize](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (int j = 0; j < arrSize; ++j) {
                sum += vector[j];
            }
        }
    });

    benchmark("set by iterator", 1000, 1000, [set](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (auto it : set) {
                sum += it;
            }
        }
    });

    return 0;
}

我正致力于使用 O2 发布结果，但我试图让编译器避免优化总和。

Answer 1

Isn't a set just a structured vector that checks whether each item is unique upon insertion?

不，到目前为止还没有。这些数据结构完全不同，这里的主要区别在于内存布局:std::vector 将其元素放入内存中的连续 位置，而std::set 是一个基于节点的容器，其中每个元素都被单独分配并驻留在内存中的不同位置，可能彼此相距很远，并且绝对不可能预取数据以进行快速遍历处理器。这与 std::vector 完全相反——因为下一个元素总是恰好在内存中当前元素的“旁边”，CPU 会将元素加载到其缓存中，并且在实际处理元素，它只需要去缓存检索值 - 与 RAM 访问相比，这非常快。

请注意，通常需要在内存中连续放置一个经过排序的、唯一的数据集合，而 C++2a 或之后的版本实际上可能附带一个 flat_set，有看看P1222 .

马特·奥斯特恩的 "Why you shouldn't use set (and what you should use instead)"也是一本有趣的读物。