C++ Array vs Vector 性能测试解释

Question

很难说出这里问的是什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或言辞激烈，无法以目前的形式合理回答。如需帮助澄清此问题以便可以重新打开，visit the help center .




9年前关闭。




为了量化类似 C 的数组和 C++ 中 Vectors 的性能差异，我编写了这个小程序。 https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

为了在共同点上比较它们，我决定测试随机访问和顺序访问。我添加了迭代器，只是为了比较它们(但这不是问题的重点)。

对于具有 7.7 GB RAM 且数组/vector 大小为 100 万的 64 位 Linux 机器，结果如下:-

写入数组所需的时间。 :12.0378 毫秒

顺序读取数组所花费的时间。 :2.48413 毫秒

随机读取数组所花费的时间。 :37.3931 毫秒

写入动态数组所需的时间。 :11.7458 毫秒

顺序读取动态数组所需的时间。 :2.85107 毫秒

随机读取动态数组所需的时间。 :36.0579 毫秒

使用索引写入 vector 所需的时间。 :11.3909 毫秒

使用索引顺序读取 vector 所花费的时间。 :4.09106 毫秒

使用索引从 vector 中随机读取所花费的时间。 :39 毫秒

使用迭代器写入 vector 所需的时间。 :24.9949 毫秒

使用迭代器从 vector 中读取所花费的时间。 :18.8049 毫秒

vector 的大小是在初始化时设置的，不会改变，因此不会调整 vector 的大小(程序中的断言有助于验证这一点)。时间不包括任何静态分配数组、动态分配数组或 vector 的初始化时间。

据统计，写入 Vector 的时间比数组少，但读取 vector 的时间是数组的两倍。

差异很小，但有没有解释为什么会有性能差异？测试有问题吗？我希望两者以相同的速度执行。该测试的重复显示了相同的趋势。

编码:

#include <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
#include <cassert>

#define ARR_SIZE 1000000

using std::string;

void printtime (struct timeval& start, struct timeval& end, string str);   

int main (void)
{
  int arr[ARR_SIZE];
  int tmp;
  struct timeval start, stop;

  srand (time (NULL));

  /* Writing data to array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    arr[i] = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to array."));

  /* Reading data from array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = arr[i];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from array sequentially."));

  /* Reading data from array randomly*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = arr[rand() % ARR_SIZE];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from array randomly."));


  int *darr = (int *) calloc (sizeof (int), ARR_SIZE);  

  /* Writing data to array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    darr[i] = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to dynamic array."));

  /* Reading data from array */
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = darr[i];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from dynamic array sequentially."));

  /* Reading data from dynamic array randomly*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = darr[rand() % ARR_SIZE];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from dynamic array randomly."));

  std::vector<int> v(ARR_SIZE);
  assert (v.capacity() == ARR_SIZE);

  /* Writing to vector using indices*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    v[i] = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to vector using indices."));
  assert (v.capacity() == ARR_SIZE);

  /* Reading from vector using indices*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = v[i];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from vector using indices, sequentially."));

  /* Reading data from dynamic array randomly*/
  gettimeofday (&start, NULL);
  for (int i = 0; i < ARR_SIZE; i++)
  {
    tmp = v[rand() % ARR_SIZE];
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from vector using indices, randomly."));

  std::vector<int> v2(ARR_SIZE);

  /* Writing to vector using iterators*/
  gettimeofday (&start, NULL);
  std::vector<int>::iterator itr, itr_end;
  for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++)
  {
    *itr = rand();
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to write to vector using iterators."));


  /* Reading from vector using iterators*/
  gettimeofday (&start, NULL);
  for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++)
  {
    tmp = *itr;
  }
  gettimeofday (&stop, NULL);
  printtime (start, stop, string ("Time taken to read from vector using iterators."));

  return 0;
}

void printtime (struct timeval& start, struct timeval& end, string str)
{
  double start_time, end_time, diff;

  start_time = ((start.tv_sec) * 1000 + start.tv_usec/1000.0);
  end_time   = ((end.tv_sec) * 1000 + end.tv_usec/1000.0);
  diff = end_time - start_time;

  std::cout << str << " : " << diff << " ms" << std::endl;
}

编辑

正如评论中所建议的，这里有更多信息:-

编译器:- g++ - 4.5.2

标志:- 无(​​即默认值)

优化:- 无(​​我想在通常的设置中测试行为。优化可能会改变程序的行为，例如，由于从未使用变量 tmp，读取 vector/数组的步骤可能会完全跳过或减少到只是最后一个任务。至少我是这么理解的)。

Answer 1

当然不是一个明确的答案，但你正在一个循环中写入一个变量，这意味着编译器可以很容易地猜测顺序读取的最终结果应该是什么，从而优化循环。由于它显然没有这样做，我假设没有优化肯定不利于迭代器方法。其他数字太接近，无法得出结论。