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”行复杂的代码 - 我把不同的值的列表。这些值取决于某些条件。

宣言S和定义：

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，调试和发布模式下的结果大致相同。在发布模式中，时间差异并不那么显着，但无论如何，第二个时间更长。

任何人都可以请解释我为什么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

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

---

在需要明确列出的载体可能是时间量因堆的使用情况以及工作可能当堆正在处理被释放时，列表元素上会的区别该列表被销毁。我认为当列表元素被第二个循环类型取消分配时，堆中可能会有更多工作要做。我只能猜测（我没有通过库代码）。

在循环的第一个样式中，每个列表在每个循环迭代中都会添加一个元素;换句话说，循环迭代0提出一种元素的每个列表中，则循环迭代1把每个列表上的另一元件等

在第二个例子中（其中clear()操作花费更长的时间），每个列表被分别建立起来;换句话说，ptrlistVector[0]中的列表被填充，然后ptrlistVector[1]被填充等等。

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

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

现在，我们来考虑一下当列表被销毁时（当清除了列表的向量时会发生），这可能意味着什么。对于地址空间中元素连续的列表，堆可能花费了一堆时间来合并那些相邻的空闲块。但是，如果列表中有一堆不相邻的元素释放其元素，则释放的内存块不会相邻，因此不会发生合并。直到我们到达最后（或最后几个）列表时，堆才会开始看到可以合并的相邻空闲块的内存。