在阅读了这篇关于缓存列表有多不友好的博客文章后： http ://www.baptiste-wicht.com/2012/11/cpp-benchmark-vector-vs-list/
...我试图通过将实际对象放入每个节点（从而删除一个间接操作）来使指向对象的指针的 std::list 对缓存更友好，希望当当前节点被缓存时，对象也会. 但是，性能实际上下降了。这是我使用的代码：
源代码和二进制文件： http ://wilcobrouwer.nl/bestanden/ListTest%202013-8-15%20%233.7z
#include <list>
using std::list;
list<Object*> case1;
list<Object> case2;
class Object {
public:
Object(char i);
~Object();
char dump[256];
};
// Should not notice much of a difference here, equal amounts of memory are
// allocated
void Insertion(Test* test) {
// create object, copy pointer
float start1 = clock->GetTimeSec();
for(int i = 0;i < test->size;i++) {
case1.push_back(new Object(i));
}
test->insertion1 = clock->GetTimeSec()-start1;
// create object in place, no temps on stack
float start2 = clock->GetTimeSec();
for(int i = 0;i < test->size;i++) {
case2.emplace_back(i);
}
test->insertion2 = clock->GetTimeSec()-start2;
}
// Case 2 removes one extra layer of derefence, so it should be more cache
// friendly, because when the list node is found in cache, the object should be
// there too
void Iteration(Test* test) {
// faster than case2 for some reason
float start1 = clock->GetTimeSec();
int tmp1 = 0;
for(list<Object*>::iterator i = case1.begin();i != case1.end();i++) {
tmp1 += (**i).dump[128];
}
test->iteration1 = clock->GetTimeSec()-start1;
// why the hell is this slower? I removed a dereference
float start2 = clock->GetTimeSec();
int tmp2 = 0;
for(list<Object>::iterator i = case2.begin();i != case2.end();i++) {
tmp2 += (*i).dump[128]; // is equal to tmp1, so no mistakes...
}
test->iteration2 = clock->GetTimeSec()-start2;
}
// Case 2 removes one extra layer of derefence, so it should be more cache
// friendly, because when the list node is found in cache, the object should be
// there too
void Deletion(Test* test) {
// again, faster than case2 for some reason
float start1 = clock->GetTimeSec();
int size1 = case1.size();
for(list<Object*>::iterator i = case1.begin();i != case1.end();i++) {
delete *i;
}
case1.clear();
test->deletion1 = clock->GetTimeSec()-start1;
// as before: why is this slower? I removed a dereference
float start2 = clock->GetTimeSec();
int size2 = case2.size();
case2.clear();
test->deletion2 = clock->GetTimeSec()-start2;
}
这些函数针对从 1 到 100000 线性变化的 test->size 值运行，并且在计算完成后将clock->GetTimeSec() 之间的时间差保存到磁盘。我的结果图可以在这里找到：
http://wilcobrouwer.nl/bestanden/ListTestFix.png
如您所见，案例 2 在插入和删除时快了大约 10%，但在迭代时慢了大约 10%，这意味着迭代案例 1 所需的额外取消引用使得它快点！
我在这里想念什么？
编辑 1：我的 CPU 是具有 64K/1MB/6MB 缓存的 Phenom II X4 @ 3.5GHz（恒定频率），我正在以这种方式编译（请注意 -m64 是隐含的，这意味着禁止 x87 通过 - mfpmath=ssse):
Compiler: TDM-GCC 4.7.1 64-bit Release
rm -f obj/Clock.o obj/main.o obj/Object.o ListTest.exe
g++.exe -c Clock.cpp -o obj/Clock.o -std=gnu++11
g++.exe -c main.cpp -o obj/main.o -std=gnu++11
g++.exe -c Objecst.cpp -o obj/Object.o -std=gnu++11
g++.exe obj/Clock.o obj/main.o obj/Object.o -o ListTest.exe -static-libgcc
编辑 2：对Dale Wilson的回答：我的意思是一个 std::list。对 Mats Petersson 的回答：图片中添加了摘要。优化检查正在进行中。回答询问更大数据集的人：对不起，我只有 4GiB 的 RAM，从当前最大值到填充的图非常无聊。
编辑 3：我启用了 -O3 （-O2 产生类似的结果），这只会让事情变得更糟：
http://wilcobrouwer.nl/bestanden/ListTestO3Fix.png
这一次，案例 2 在插入和删除时大约快 20%，但这次在迭代时慢了大约 1~5 倍（在更大的测试规模下变得更糟）。同样的结论。
编辑 4：对Maxim Yegorushkin的回答：CPU 频率缩放恰好被禁用（忘了提），我的 CPU 始终以 3.5GHz 运行。此外，基本上也可以从更多测试中挑选平均值或最佳结果，因为 x 轴上有足够多的样本点。也启用了优化：-O3、-m64 和 mfpmath=sse 都已设置。在 std::vector 测试中添加相同的测试（检查源代码）并没有改变任何重要的东西。
编辑5：修复了一些错别字（删除结果没有显示，但迭代结果显示了两次。这已经清除了删除问题，但迭代问题仍然存在。