为什么这些结果表明不需要在 vector 中使用 reserve？

Question

我编写了下面的代码来测量推回整数 1000k 次而不使用保留和保留所花费的时间。结果不是我想要的。

所有测试都是在我的三星 ativtap7 上执行的，它具有核心 i5 @1.8 Ghz 处理器、4 GB RAM 和 VS2018 C++ 编译器运行 Windows 10。

#include <iostream>
#include <vector>
#include "Stopwatch.h"
using namespace std;

int main()
{
    Stopwatch myWatch;
    //pushback 1000k times without reserve
    for (int i = 0; i < 10; i++)
    {
        cout << "try " << i + 1 << endl;
        myWatch.Start();
        vector<int> vec1;
        for (int i = 0; i < 1000000; i++)
        {
            vec1.push_back(i);
        }
        myWatch.End();
        myWatch.LookElapsedTime();

        //pushback 1000k times with reserve
        myWatch.Start();
        vector<int> vec2(1000000);
        for (int i = 0; i < 1000000; i++)
        {
            vec2.push_back(i);
        }

        myWatch.End();
        myWatch.LookElapsedTime();
        cout << endl;
    }
    return 0;
}

我希望结果显示使用储备和不使用储备之间的有意义的差异，但实际结果与我的预期不符。

下面是结果。

try 1
1.51118(sec)
1.46981(sec)

try 2 
1.43074(sec)
1.4381(sec)

try 3
1.4428(sec)
1.46196(sec)

try 4
1.41903(sec)
1.43688(sec)

try 5
1.47544(sec)
1.558(sec)

try 6
1.47474(sec)
1.45484(sec)

try 7
1.47731(sec)
1.5908(sec)

try 8
1.77192(sec)
1.72018(sec)

try 9
1.56832(sec)
1.447(sec)

try 10
1.43659(sec)
1.43572(sec)

我想知道为什么会这样。

Answer 1

你根本没有reserv记忆。在你的第二个向量中

vector<int> vec2(1000000);

这意味着，用 0 分配和初始化 1000000 个整数。你需要

vector<int> vec2;
vec2.reserve(1000000);

查看使用 quick-bench.com 完成的基准测试。现在很清楚保留很重要。

(See online)

Answer 2

因为两个vector都没有为push_backs

预分配内存

在 vec2 中，您创建了一个包含 1000000 个元素的向量，然后压入另外 1000000 个元素。

如果您检查两个向量的 size()，您会看到 vec1.size() == 1000000 和 vec2.size() == 2000000

如果你想使用reserve机制，你应该执行以下操作：

vector<int> vec2;
vec2.reserve(1000000);
for (int i = 0; i < 1000000; i++)
{
    vec2.push_back(i);
}

或者

vector<int> vec2(1000000);
for (int i = 0; i < 1000000; i++)
{
    vec2[i] = i;
}

Answer 3

正如 JeJo 所提到的，您没有使用储备。您正在分配一个包含 1000000 个整数的向量，然后继续向它添加更多的 1000000 个整数。

但即使修复了代码并使用 reserve，事情也没有想象中的那么好：

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;

int main()
{

  //pushback 1000k times without reserve
  for (int i = 0; i < 10; i++)
    {
      cout << "try " << i+1 << endl;
      auto start = chrono::high_resolution_clock::now();
      vector<int> vec1;
      for (int i = 0; i < 1000000; i++)
        {
          vec1.push_back(i);
        }

      auto finish = chrono::high_resolution_clock::now();
      auto passed = chrono::duration_cast<chrono::microseconds>(finish-start);
      cout << passed.count() << " us\n";
      start = chrono::high_resolution_clock::now();

      //pushback 1000k times with reserve
      vector<int> vec2;
      vec2.reserve(1000000);
      for (int i = 0; i < 1000000; i++)
        {
          vec2.push_back(i);
        }

      finish = chrono::high_resolution_clock::now();
      passed = chrono::duration_cast<chrono::microseconds>(finish-start);
      cout << passed.count() << " us\n";
      cout << endl;
    }

  return 0;
}

结果：

try 1
6313 us
3478 us

try 2
1775 us
1412 us

try 3
1996 us
1551 us

try 4
2054 us
1579 us

try 5
1936 us
1427 us

try 6
1647 us
1504 us

try 7
1902 us
1754 us

try 8
1893 us
1952 us

try 9
1655 us
1874 us

try 10
2019 us
1736 us

第一次尝试有一个 x2 speed-up 保留，但其他尝试并没有显示出很大的差异。原因是一旦分配了适当大小的内存块，它们就会被 C++ 缓存。这样，这些块可以在下一次尝试中快速重用。大多数 C++ 实现将缓存这些块（通过 malloc 的实现或其他方式），因此下次需要该块时，它会很快被重用。

这种 new/delete 块的简单缓存在现实世界中不如在 micro-benchmarks 中有效。实际上，堆还有很多事情要做，使得缓存对 reserve-less 向量的效率降低。

为什么这些结果表明不需要在 vector 中使用 reserve？

Why these results show there is no need to using reserve in vector?

c++

performance

stdvector

c++11