动态分配的数组或 std::vector

Question

我正在尝试优化我的 C++ 代码。 我在互联网上搜索过使用动态分配的 C++ 数组与使用 std::vector 的比较，并且通常看到有利于 std::vector 的建议，并且两者之间的性能差异可以忽略不计。 例如这里 - 在中使用数组或 std::vectors C++，性能差距是多少？。

然而，我编写了一些代码来测试迭代数组/向量并向元素赋值的性能，我通常发现使用动态分配的数组比使用向量快近 3 倍（我确实事先指定了向量的大小） ）。 我用的是g++-4.3.2。

不过，我觉得我的测试可能忽略了我不知道的问题，因此我将不胜感激有关此问题的任何建议。

感谢

使用代码 -

#include <time.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i;
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
}

Answer 1

对 C++ 容器进行基准测试时，启用大多数编译器优化非常重要。 我自己对 SO 的几个答案都违反了这一点 - 例如，当像operator[]这样的东西没有内联时，函数调用的开销可能非常大。

Answer 2

只是为了好玩，尝试使用指针而不是整数索引来迭代普通数组（代码应该看起来像向量迭代，因为 STL 迭代器的要点是对于大多数操作来说看起来像指针算术）。 我敢打赌在这种情况下速度将完全相同。 这当然意味着您应该选择向量，因为它可以让您免去手动管理数组的麻烦。

Answer 3

关于标准库类（例如 std::vector）的问题是，是的，天真地说，它比原始数组要多得多的代码。 但所有这些都可以由编译器轻松内联，这意味着如果启用优化，它基本上会变成与使用原始数组相同的代码。 那么速度差异不是可以忽略不计的，而是不存在的。 所有开销都在编译时消除。

但这需要启用编译器优化。

Answer 4

我想你发现迭代和添加到 std::vector 比普通数组慢 3 倍的原因是迭代向量和进行分配的成本的组合。

编辑：

这是我在测试用例之前的最初假设； 然而运行测试用例（用 -O3 编译）显示相反的情况 - std::vector 实际上快了 3 倍，这让我感到惊讶。

我看不出 std::vector 如何比普通数组副本更快（当然不是快 3 倍） - 我认为对 std::vector 编译的代码应用了一些优化，而数组版本则没有发生这种情况。

原始基准测试结果：

$ ./array
array:  0.059375
vector: 0.021209

• std::vector 速度提高了 3 倍。 再次进行相同的基准测试，除了添加一个额外的外循环来运行测试迭代器循环 1000 次：

  $ ./数组
  数组：21.7129
  矢量：21.6413

• std::vector 现在〜与数组的速度相同。

编辑2

找到了！ 因此，您的测试用例的问题在于，在向量情况下，保存数据的内存似乎已经在 CPU 缓存中 - 要么是通过初始化的方式，要么是由于调用 vec.end()< /代码>。 如果我在每次计时测试之前“预热”CPU 缓存，我会得到相同的数组和向量数字：

#include <time.h>
#include <iostream>
#include <vector>

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  // get vec into CPU cache.
  for (int i = 0; vecIt != vecEnd; i++) { *(vecIt++) = i; }
  vecIt = vec.begin();
  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i;
  }
  end = clock();
  std::cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<std::endl;

  int* arr = new int[9999999];

  // get arr into CPU cache.
  for (int i = 0; i < 9999999; i++) { arr[i] = i; }
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  std::cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<std::endl;
}

这给出了以下结果：

$ ./array
vector: 0.020875
array: 0.020695

Answer 5

我同意rmeador的观点，

  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i; // <-- quick offset calculation
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i; // <-- not fair play :) - offset = arr + i*size(int)
  }

Answer 6

我认为这里的答案很明显：没关系。 就像 jalf 所说的那样，代码最终将大致相同，但即使不是，请查看数字。 您发布的代码创建了一个包含 1000 万个项目的巨大数组，但迭代整个数组只需要百分之几秒。

即使您的应用程序确实正在处理这么多数据，无论您实际对这些数据执行什么操作，都可能比迭代数组花费更多的时间。 只需使用您喜欢的数据结构，然后将时间集中在其余代码上。

为了证明我的观点，这里的代码做了一个更改：对数组项的 i 赋值被 sqrt(i) 的赋值替换。 在我使用 -O2 的机器上，执行时间增加了三倍，从 0.02 秒增加到 0.06 秒。

#include <time.h>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = sqrt(i);
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
}

Answer 7

问题似乎是您在关闭优化的情况下编译了代码。 在我的机器上，OS X 10.5.7 和 g++ 4.0.1 我实际上发现向量比原始数组快 2.5 倍。

使用 gcc 尝试将 -O2 传递给编译器，看看是否有任何改进。

Answer 8

数组迭代速度更快的原因是迭代次数是恒定的，并且编译器能够展开循环。 尝试使用 rand 生成一个数字，并将其乘以一个您想要的大数字，这样编译器将无法在编译时算出它。 然后再试一次，你会看到类似的运行结果。

Answer 9

您的代码执行效果可能不完全相同的原因之一是，在您的 std::vector 版本上，您增加了两个值，即整数 i 和 std::vector::iterator vecIt。 为了真正等效，你可以重构为

start = clock();
for (int i = 0; i < vec.size(); i++) {
  vec[i] = i;
}
end = clock();
cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

Answer 10

您的代码在两种情况之间提供了不公平的比较，因为您在向量测试中所做的工作比数组测试要多得多。

使用向量，您可以增加迭代器 (vecIT) 和单独的变量 (i) 来生成赋值。

对于数组，您只需递增变量 i 并将其用于双重目的。