c++ - 为什么迭代对象列表比迭代对象指针列表慢？

Question

在阅读这篇关于列表缓存有多不友好的博文后: 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 是 Phenom II X4 @ 3.5GHz(恒定频率)，缓存为 64K/1MB/6MB，我是这样编译的(请注意 -m64 是暗示，这意味着通过 -mfpmath=ssse 禁止 x87):

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 内存，而且从当前最大值到填充的图非常无聊。

编辑 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

有点跑题，但这种基准测试方法不会产生正确且可重复的结果，因为它忽略了缓存效应、CPU 频率缩放和进程调度程序。

要正确测量时间，它需要运行每个微基准(即每个循环)几次(比如至少 3 次)并选择最佳时间。最佳时间是 CPU 缓存、TLB 和分支预测器处于热状态时可实现的最佳时间。您需要最好的时间，因为最坏的时间没有上限，因此无法对它们进行有意义的比较。

进行基准测试时，您还需要禁用 CPU 频率缩放，这样它就不会在基准测试过程中切换频率。它还应该以实时优先级运行，以减少因其他进程抢占您的基准测试而产生的调度噪音。

并且不要忘记对其进行优化编译。

接下来，让我们回顾一下您的基准:

• 插入:它主要测量两次内存分配 (list<Object*>) 与一次内存分配 (list<Object>) 的时间。
• 删除:同上，将allocation替换为deallocation。
• 迭代:您的对象大小为 256 字节，即 4x64 字节缓存行。与列表节点大小相比，这样的对象大小太大，因此当它从 256 字节的对象中读取一个字节时，您可能会测量缓存未命中的时间。

您真正想要测量的是在读取对象的所有字节(例如，对对象的所有字节求和)时列表的迭代与数组的迭代。您的假设是，当对象放置在数组中并按顺序访问时，CPU 会将下一个对象预加载到缓存中，这样当您访问它时就不会导致缓存未命中。而当对象存储在其节点在内存中不连续的列表中时，缓存预读不会提高速度，因为下一个对象在内存中与当前对象不相邻，因此当它追逐列表的指针时会招致缓存未命中。