为什么迭代一个对象列表比迭代一个对象指针列表慢？

Question

阅读此博客文章后,列表对缓存的不友好程度如下:http: //www.baptiste-wicht.com/2012/11/cpp-benchmark-vector-vs-list/

...我试图通过将实际对象放入每个节点(从而删除一个间接操作)来创建std ::指向对象的指针更多缓存友好列表,希望当当前节点被缓存时,对象也将是.但是,性能实际上下降了.这是我使用的代码:

来源和二进制文件: 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;
}

这些函数运行的test-> size值从1到100000线性变化,clock-> GetTimeSec()之间的时间差在计算完成后保存到磁盘.我的结果图可以在这里找到:

http://wilcobrouwer.nl/bestanden/ListTestFix.png
正如您所看到的,案例2在插入和删除时的速度提高了约10%,但在迭代时速度提高了约10%,这意味着迭代案例1所需的额外解引用使其成为可能快点!

我在这里错过了什么？

编辑1:我的CPU是Phenom II X4 @ 3.5GHz(恒定频率),具有64K/1MB/6MB缓存,我正在编译这种方式(请注意-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:回答戴尔威尔逊:列表我指的是一个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:修复了一些拼写错误(删除结果未显示,但迭代结果显示两次.这清除了删除问题,但迭代问题仍然存在.

Answer 1

我在您的构建命令中没有看到任何优化设置，因此可能您得到的是未优化的构建。完全可信的是，在这样的构建中，额外的间接级别（和/或列表节点较小的事实）实际上通过偶然/库实现提高了性能。

尝试在至少-O2启用的情况下进行编译，看看会发生什么。