在优化性能关键代码时,我注意到迭代 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 发布结果,但我试图让编译器避免优化总和。
最佳答案
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)"也是一本有趣的读物。
关于c++ - 为什么迭代 std::set 比迭代 std::vector 慢得多?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56832563/