C++ 变暖 std 向量

为什么第二次填充 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

RESULTS:
118
23
21

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

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

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

^{Note: updated to latest, with reserve() moved to the top and wrapped in its own getrusage call.}

#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 和操作系统而异，但本质是相同的。）操作系统可能将虚拟地址范围指向标记为只读的单个零填充页。

操作系统确实not必须使这些页面立即可供任务使用。相反，操作系统会等待，直到任务实际尝试写入为其分配的内存。此时，操作系统会分配一个物理页来支持分配给该任务的虚拟页。这在 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)                           = ?

正如你所看到的，任务分配的内存是mmap前两个之间的调用getrusage系统调用。然而，这一步只造成了24个小错误。所以，尽管 C++ 是not由于懒惰，Linux 懒于为任务分配内存。

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

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