为什么调整指向向量*（在向量数组中）的指针比向量（在向量数组中）更快？

Question

调整向量大小可能很慢？迫切需要提高软件速度的解决方案，我尝试调整向量数组中的向量和向量数组中的向量*的大小* 第二个似乎更快。即使我能感觉到原因，我也没有明确的纯理性解释（我不想在数组中为向量使用预留空间，因为真实的向量很大）。有吗？

这是我的测试程序（在另一台装有 debian 8 的 Lenovo ThinkCenter i5 上结果可能不同：另一个我不想停止的任务是运行）：

int main (int argc, char* argv []) {
  const int n = 10;
  const int s2 (10000);
  {
    std::vector<int> tab [n];
    clock_t begt, endt;
    begt = clock ();
    {
      std::vector<int>* pv ((std::vector<int>*) tab);
      for (int i (0); i < n; ++i, ++pv) {
        pv->resize (s2);
      }
    }
    endt = clock ();
    std::cout << "vector resize duration == " << (unsigned int) (endt - begt) <<  " ticks" << std::endl;
  }

  {
    std::vector<int> *tab [n];
    for (int i (0); i != n; ++i) {
      tab [i] = new std::vector<int> ();
    }
    clock_t begt, endt;
    begt = clock ();
    {
      std::vector<int>** pv ((std::vector<int>**) tab);
      for (int i (0); i < n; ++i, ++pv) {
        (*pv)->resize (s2);
      }
    }
    for (int i (0); i != n; ++i) {
      delete tab [i];
    }
    endt = clock ();
    std::cout << "*vector resize duration== " << (unsigned int) (endt - begt) <<  " ticks" << std::endl;
  }
  return 0;
}

和典型结果：

vector resize duration == 114 ticks
*vector resize duration== 78 ticks

Answer 1

我对声称的观察结果很好奇，并且能够自己重现它们。然后我交换了两个替代实现，现在情况发生了翻天覆地的变化。现在第一个执行的 std::vector<int> *tab [n] 版本比现在第二个执行的另一个版本慢得多。

解释很简单。 C++ 库重用分配的内存。当您通过 new 直接自己使用内存，或通过为容器中的值分配内存而间接使用内存，然后释放它时，C++ 库不会将释放的内存释放回操作系统，而是下次需要更多内存时重新使用它，而无需向您的操作系统请求更多内存。没有法律规定这是 C++ 库必须做的，但这是现代 C++ 实现的典型行为。

所以，这是什么，非常简单。您的第一个基准测试包括从操作系统分配一堆内存所需的时间。 C++ 第一次需要这些向量的内存，这需要额外的时间。您的第二个基准代码部分不必这样做，因为该内存已经被第一个基准分配，然后释放；所以第二个基准只是导致你的 C++ 库重用它已经拥有但未使用的内存（这通过查看系统调用跟踪很明显）。

第二次简单地重复第一个基准测试的典型结果：

vector resize duration == 191 ticks
vector resize duration == 48 ticks
*vector resize duration== 63 ticks

为什么调整指向向量*（在向量数组中）的指针比向量（在向量数组中）更快？

why is it faster to resize a pointer to a vector* (in an array of vector*) than a vector (in an array of vector)?

c++

stdvector