c++ - 代码重构后 std::vector::clear() 需要更多时间

Question

我有一个过程，它用从另一个数组获取的值填充一些数组。 它看起来类似于以下代码:

// Point 0
ptrlistVector.clear();

// Point 1
ptrlistVector.resize(50);
const size_t s = ptrlistVector.size();

// Point 2
for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
{
    for (UINT i = 0; i < s; ++i) 
    {
        ptrlistVector[i].push_back(&(*j)); 
    }
}
// Point 3

实际上，“push_back”行中有更复杂的代码 - 我将不同的值推送到列表中。这些值取决于某些条件。

声明和定义:

typedef std::list<void*> ObjectPtrList;
typedef std::vector<ObjectPtrList> PtrListVector;
typedef std::list<std::string> ObjectList;

ObjectList objList;
PtrListVector ptrlistVector;

我测量了点之间的时间，平均而言，点 1-0 需要 0.02 秒，点 3-2 需要 0.05 秒。 我尝试重构循环并发现一些奇怪的行为。 我用以下内容替换了上面的循环:

for (UINT i = 0; i < s; ++i)
{
    for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
    {
        ptrlistVector[i].push_back(&(*j)); 
    }
}

之后时间发生了变化。第 3-2 点需要 0.035 秒，但clear() 调用(第 1-0 点)现在需要 0.45(!!!)，这比之前的时间长得多。

我使用MSVC 10.0，在调试和 Release模式下结果大致相同。在 Release模式下，时间差异不是那么显着，但无论如何，第二秒的时间更长。

有人可以解释一下为什么在我更改循环后，clear() 调用需要花费更多时间吗？

下面的代码是我用于性能测试的控制台应用程序。

#include "stdafx.h"
#include <windows.h>
#include <vector>
#include <list>
#include <cstdio>
#include <cassert>
#include <string>

int _tmain(int argc, _TCHAR* argv[])
{
    typedef std::list<void*> ObjectPtrList;
    typedef std::vector<ObjectPtrList> PtrListVector;
    typedef std::list<std::string> ObjectList;

    ObjectList objList;
    objList.insert(objList.begin(), 500, std::string());

    PtrListVector ptrlistVector;

    LARGE_INTEGER __counters[10];
    double __totals[10] = { 0 };
    UINT __counter = 0;
    BOOL bRes;

    LARGE_INTEGER __freq;
    bRes = QueryPerformanceFrequency(&__freq);
    assert(bRes);

    for (int k = 0; k < 500; ++k)
    {
        // Point 0
        bRes = QueryPerformanceCounter(&__counters[0]);
        ptrlistVector.clear();

        // Point 1
        bRes = QueryPerformanceCounter(&__counters[1]);
        ptrlistVector.resize(50);
        const size_t s = ptrlistVector.size();

        // Point 2
        bRes = QueryPerformanceCounter(&__counters[2]);
        /*
        // original
        for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
        {
            for (UINT i = 0; i < s; ++i) 
            {
                ptrlistVector[i].push_back(&(*j)); 
            }
        }
        /*/
        for (UINT i = 0; i < s; ++i) // refactored
        {
            for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
            {
                ptrlistVector[i].push_back(&(*j)); 
            }
        }
        //*/

        // Point 3  
        bRes = QueryPerformanceCounter(&__counters[3]);
        __counter += 1;
        __totals[1] += 1.0 * (__counters[1].QuadPart - __counters[0].QuadPart) / __freq.QuadPart;
        __totals[2] += 1.0 * (__counters[2].QuadPart - __counters[1].QuadPart) / __freq.QuadPart;
        __totals[3] += 1.0 * (__counters[3].QuadPart - __counters[2].QuadPart) / __freq.QuadPart;
        __totals[4] += 1.0 * (__counters[3].QuadPart - __counters[0].QuadPart) / __freq.QuadPart;
        printf("%s: %.4f  %.4f  %.4f = %.4f\n", 
            __FUNCTION__, 
            __totals[1]/__counter, 
            __totals[2]/__counter, 
            __totals[3]/__counter, 
            __totals[4]/__counter);
    }
    return 0;
}

Answer 1

我想在这个答案前加上一个免责声明 - 这是推测，因为我没有运行问题中的代码，也没有查看所涉及的实际库实现。但我认为这概述了问题中描述的时间上任何统计上显着差异的可能解释。但是，请记住，目前这只是猜测。

---

清除列表 vector 所需时间的差异可能是由于堆的使用方式以及堆处理列表元素(列表被销毁时释放的列表元素)时可能进行的工作造成的。我认为当使用第二个循环类型释放列表元素时，堆中可能会进行更多工作。我只能猜测(我还没有逐步完成库代码)。

在第一种循环样式中，每个列表在每次循环迭代时添加一个元素；换句话说，循环迭代 0 在每个列表上放置一个元素，然后循环迭代 1 在每个列表上放置另一个元素，依此类推。

在第二个示例中(其中 clear() 操作需要更长的时间)，每个列表都是单独构建的；换句话说，ptrlistVector[0] 中的列表被填充，然后 ptrlistVector[1] 被填充，依此类推。

我猜想，对于第一个循环样式，特定列表中的每个元素与列表中的其他元素不连续(在地址空间中)。这是因为在特定列表上的任意两个 push_back() 操作之间，发生了 50 次其他分配以将元素添加到其他列表。

但是，我猜测在第二个循环样式中，特定列表中的元素或多或少是连续的，因为这是分配发生的顺序。

现在，让我们考虑一下当列表被销毁时这可能意味着什么(当保存列表的 vector 被清除时会发生这种情况)。对于元素在地址空间中连续的列表，堆可能会花费大量时间来合并那些相邻的空闲 block 。但是，当包含一堆不相邻元素的列表释放其元素时，释放的内存块不相邻，因此不会发生合并。直到我们到达最后一个(或最后几个)列表时，堆才可能开始看到可以合并的相邻空闲内存块。