问题详细信息
我正在开发一个 C++ 项目，其中我使用std::list<TestElement*>来存储指向动态分配对象的指针。每个TestElement对象都有一个附加字段，用于使用 来存储其在列表中的位置std::list::iterator。该类如下所示：
class TestElement {
public:
int value;
std::list<TestElement*>::iterator listIterator; // Stores iterator to its position in the list
};
我std::list用 200 万个TestElement对象填充了这两个对象。在初始化期间，我将iterator每个对象的存储在其listIterator 字段中。
问题是，当listIterator中存在该字段时TestElement，pop_back()对 的操作std::list会变得明显变慢。具体来说：
- 使用
listIterator字段：pop_back+delete需要 289.316 毫秒。 - 无该
listIterator字段：相同操作仅需0.0043毫秒。
由于pop_back()应该是的恒定时间操作std::list，这种减速似乎是出乎意料的。
我做了什么？
我创建了一个std::list<TestElement*>，其中列表中的每个元素都是指向的指针TestElement。
我iterator为每个字段添加了一个字段TestElement来存储其在中的位置std::list。
pop_back()我测量了有和没有字段listIterator时操作所花费的时间TestElement。
这是我使用的测试程序：
#include <iostream>
#include <list>
#include <chrono>
class TestElement {
public:
int value;
std::list<TestElement*>::iterator listIterator;
};
int main() {
const int numElements = 2000000;
const int testIterations = 10;
std::list<TestElement*> testList;
for (int i = 0; i < numElements; ++i) {
testList.push_front(new TestElement());
testList.front()->listIterator = testList.begin();
}
double totalDuration = 0.0;
for (int t = 0; t < testIterations; ++t) {
auto start = std::chrono::high_resolution_clock::now();
delete testList.back();
testList.pop_back();
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> duration = end - start;
totalDuration += duration.count();
}
std::cout << "Average time for pop_back and delete operations: "
<< (totalDuration / testIterations) << " ms" << std::endl;
return 0;
}
pop_back()我预计和 的性能delete不会受到该listIterator字段的影响。由于pop_back()是 的常量时间操作，因此我预计在 中std::list添加一个字段不会导致任何显著的性能下降。然而，添加该字段导致和耗时 289.316 毫秒，而没有该字段时仅耗时 0.0043 毫秒。iteratorTestElementlistIteratorpop_back()delete
6
最佳答案
2
您的测量方法不正确。std::chrono本身可能无法提供准确的结果，并且每次迭代都会累积错误totalDuration += duration.count();。请记住，在现代 PC 上，您的单次迭代需要几纳秒。
为了更好地测量，请编写基准，例如使用库：
#include <list>
#include <benchmark/benchmark.h>
class TestElement1 {
public:
int value;
};
class TestElement2 {
public:
int value;
std::list<TestElement2 *>::iterator listIterator;
};
constexpr int numElements = 2000000;
constexpr int testIterations = 1000;
static void pop1(benchmark::State &state) {
std::list<TestElement1 *> testList;
for (int i = 0; i < numElements; ++i) {
testList.push_front(new TestElement1());
}
for (auto _ : state) {
delete testList.back();
testList.pop_back();
}
}
BENCHMARK(pop1)->Iterations(testIterations);
static void pop2(benchmark::State &state) {
std::list<TestElement2 *> testList;
for (int i = 0; i < numElements; ++i) {
testList.push_front(new TestElement2());
testList.front()->listIterator = testList.begin();
}
for (auto _ : state) {
delete testList.back();
testList.pop_back();
}
}
BENCHMARK(pop2)->Iterations(testIterations);
尝试在您的机器上运行它并比较结果。如果结果仍然不稳定，请增加迭代次数和/或元素。始终对优化的发布版本进行基准测试。
|
我尝试使用 Windows 11 和 Intel Core I7-14700K 上的 Visual Studio 2022 运行您的测试程序。
发布版本，x64 代码：
- 使用迭代器：0.00016 毫秒
- 无迭代器：0.00015 毫秒
发布版本，x86 代码：
- 使用迭代器：0.00028 毫秒
- 无迭代器：0.00022 毫秒
调试版本，x64 代码：
- 使用迭代器：132.247 毫秒
- 无迭代器：0.00085 毫秒
调试版本，x86 代码：
- 使用迭代器：37.3472 毫秒
- 无迭代器：0.00092 毫秒
您的里程将根据您使用的编译器和环境而有所不同。
是否启用优化很重要。此外，调试版本和调试运行时库在生成的代码中还有额外的正确性检查
列表元素应从堆中分配，并且编译器/C++ 运行时可能对分配不同大小的对象有不同的策略。Visual C++ 调试运行时库还具有额外的检查和核算功能，以便检测内存正确性错误。
最后，根据我的经验，在 Visual C++ 的情况下，如果您在未附加调试器的情况下运行代码，即使对于发布版本，堆操作也往往会更快。
3
-
4这是因为 MSVC 默认在 Debug 版本中使用已检查的迭代器，这些迭代器很胖（不同的 ABI）而且很慢，你可以关闭它们：
– -
1@Gene 但你为什么要这么做（在调试版本中）。已检查的迭代器会捕获错误。
–
-
@john——我不记得他们曾经发现过任何一个错误，但是从实际考虑，检查的迭代器太慢了，所以您可能无法轻松地调试，另一个大问题是，正如我提到的，它们与常规迭代器二进制不兼容，所以您不能混合调试和发布代码。
–
|
–
std::list比差std::vector，现代处理器不喜欢链表–
–
–
TestElement时listIterator也std::list必须调用析构函数。–
|