为什么第二次填充 std::vector 更快？即使从一开始就预留了空间？

int total = 1000000;

struct BaseClass {
  float m[16];
  int id;

  BaseClass(int _id) { id = _id; }
};

int main() {

  std::vector<BaseClass> ar;
  ar.reserve(total);

  {
    auto t_start = std::chrono::high_resolution_clock::now();
    for (int var = 0; var < total; ++var) {
      ar.emplace_back(var);
    }
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
                     t_end - t_start).count() << "\n";
    ar.clear();
  }

  {
    auto t_start = std::chrono::high_resolution_clock::now();
    for (int var = 0; var < total; ++var) {
      ar.emplace_back(var);
    }
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
                     t_end - t_start).count() << "\n";
    ar.clear();
  }

  {
    auto t_start = std::chrono::high_resolution_clock::now();
    for (int var = 0; var < total; ++var) {
      ar.emplace_back(var);
    }
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
                     t_end - t_start).count() << "\n";
    ar.clear();
  }

  return 0;
}

在线预览: http://coliru.stacked-crooked.com/a/229e4ba47adddb1a

结果:
118
23
21

附言我问的是，如果 vector 减速的唯一原因是分配/重新分配，为什么它会变得更快。我们在开始之前分配了数组。

最佳答案

第一次运行比其他两次慢的原因是运行时尚未从操作系统获取内存页面。

我对您的程序进行了检测，以输出任务在开始时以及在上述三个阶段中的每一个阶段之后发生的主要和次要页面错误的数量。 (注意:这适用于 Linux。不知道它是否适用于您使用的任何操作系统。)代码:

^{注意:更新到最新版本，reserve() 移到顶部并包含在它自己的 getrusage 调用中。}

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

#include <sys/time.h>
#include <sys/resource.h>

using namespace std;

int total = 1000000;

struct BaseClass {
  float m[16];
  int id;

  BaseClass(int _id) { id = _id; }
};

int main() {

  std::vector<BaseClass> ar;
  struct rusage r;
  {
    auto t_start = std::chrono::high_resolution_clock::now();
     }

  getrusage(RUSAGE_SELF, &r);
  cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl;

  ar.reserve(total);

  getrusage(RUSAGE_SELF, &r);
  cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl;

  {
    auto t_start = std::chrono::high_resolution_clock::now();
    for (int var = 0; var < total; ++var) {
      ar.emplace_back(var);
    }
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
                     t_end - t_start).count() << "\n";
    ar.clear();
  }

  getrusage(RUSAGE_SELF, &r);
  cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl;

  {
    auto t_start = std::chrono::high_resolution_clock::now();
    for (int var = 0; var < total; ++var) {
      ar.emplace_back(var);
    }
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
                     t_end - t_start).count() << "\n";
    ar.clear();
  }

  getrusage(RUSAGE_SELF, &r);
  cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl;

  {
    auto t_start = std::chrono::high_resolution_clock::now();
    for (int var = 0; var < total; ++var) {
      ar.emplace_back(var);
    }
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
                     t_end - t_start).count() << "\n";
    ar.clear();
  }

  getrusage(RUSAGE_SELF, &r);
  cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl;

  return 0;
}

然后我在我的盒子上运行它。结果很有启发性:

minflt: 343 majflt: 0
minflt: 367 majflt: 0
48    minflt: 16968 majflt: 0
16
minflt: 16968 majflt: 0
15
minflt: 16968 majflt: 0

请注意，第一个测量的 for 循环出现了超过 16,000 个小错误。这些故障使应用程序可以使用内存并导致运行时间变慢。此后不会再发生其他故障。相比之下，reserve() 调用本身只发生了 24 个小错误。

在大多数现代虚拟内存操作系统中，操作系统实现了惰性内存分配，即使在其上运行的软件并未实现。当运行时从操作系统请求额外的内存时，操作系统会记录该请求。如果请求成功，运行时现在有一个新的可用虚拟地址范围。 (细节因调用的 API 和操作系统而异，但本质是相同的。)操作系统可能会将虚拟地址范围指向标记为只读的单个零填充页面。

操作系统不一定必须使这些页面立即可供任务使用。相反，操作系统会一直等到任务实际尝试写入分配给它的内存。此时，操作系统分配一个物理页面来支持分配给任务的虚拟页面。这在 UNIX 术语中被称为“小故障”。这个过程可能很昂贵。

这是您的任务正在测量的惰性分配。

为了证明这一点，我还对该应用程序进行了 strace。有意义的部分如下。

getrusage(RUSAGE_SELF, {ru_utime={0, 0}, ru_stime={0, 0}, ...}) = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fe3aa339000
write(1, "minflt: 328 majflt: 0\n", 22) = 22
mmap(NULL, 68001792, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fe3a551c000
getrusage(RUSAGE_SELF, {ru_utime={0, 0}, ru_stime={0, 0}, ...}) = 0
write(1, "minflt: 352 majflt: 0\n", 22) = 22
write(1, "52\n", 3)                     = 3
getrusage(RUSAGE_SELF, {ru_utime={0, 30000}, ru_stime={0, 20000}, ...}) = 0
write(1, "minflt: 16953 majflt: 0\n", 24) = 24
write(1, "20\n", 3)                     = 3
getrusage(RUSAGE_SELF, {ru_utime={0, 50000}, ru_stime={0, 20000}, ...}) = 0
write(1, "minflt: 16953 majflt: 0\n", 24) = 24
write(1, "15\n", 3)                     = 3
getrusage(RUSAGE_SELF, {ru_utime={0, 70000}, ru_stime={0, 20000}, ...}) = 0
write(1, "minflt: 16953 majflt: 0\n", 24) = 24
munmap(0x7fe3a551c000, 68001792)        = 0
exit_group(0)                           = ?

如您所见，任务在前两个 getrusage 系统调用之间通过 mmap 调用分配了内存。然而，这一步只招致了 24 个小错误。因此，尽管 C++ 不懒惰，但 Linux 在为任务提供内存方面是懒惰的。

具体来说，第一个 mmap 调用似乎是为第一个 write 消息分配一个 I/O 缓冲区。第二次 mmap 调用(分配 68001792 字节)发生在第二次 getrusage 调用之前。然而，您可以看到在这次运行中两者之间只发生了 24 个额外故障。

眼尖的人会注意到这次运行的数字与我上面显示的数字略有不同。我已经多次运行这个可执行文件，每次数字都略有变化。但是，它们总是在同一个大致范围内。

关于C++ 变暖标准 vector ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20591821/