8

C に似た配列と C++ のベクトルのパフォーマンスの違いを定量化するために、この小さなプログラムを作成しました。https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

共通の理由でそれらを比較するために、ランダム アクセスとシーケンシャル アクセスの両方をテストすることにしました。それらを比較するためだけにイテレータを追加しました（しかし、それは質問が焦点を当てているものではありません）。

100 万の配列/ベクトル サイズで 7.7 GB RAM を搭載した 64 ビット Linux マシンの結果は次のとおりです。

  • 配列への書き込みにかかった時間。: 12.0378 ミリ秒
  • 配列から順次読み取るのにかかった時間。: 2.48413 ミリ秒
  • 配列からランダムに読み取るのにかかった時間。: 37.3931 ミリ秒
  • 動的配列への書き込みにかかった時間。: 11.7458 ミリ秒
  • 動的配列から順次読み取るのにかかった時間。: 2.85107 ミリ秒
  • 動的配列からランダムに読み取るのにかかった時間。: 36.0579 ミリ秒
  • インデックスを使用してベクトルに書き込むのにかかった時間。: 11.3909 ミリ秒
  • インデックスを使用してベクトルから順番に読み取るのにかかった時間。: 4.09106 ミリ秒
  • インデックスをランダムに使用してベクトルから読み取るのにかかった時間。：39ミリ秒
  • イテレータを使用してベクトルに書き込むのにかかった時間。: 24.9949 ミリ秒
  • イテレータを使用してベクトルから読み取るのにかかった時間。: 18.8049 ミリ秒

ベクトルのサイズは初期化時に設定され、変更されないため、ベクトルのサイズ変更はありません (プログラム内のアサーションはそれを確認するのに役立ちます)。この時間には、静的に割り当てられた配列、動的に割り当てられた配列、またはベクトルの初期化時間は含まれません。

統計によると、Vector への書き込み時間は配列よりも短くなりますが、Vector からの読み取り時間は配列の 2 倍になります。

違いはかなり小さいですが、パフォーマンスの違いがある理由について説明はありますか? テストに何か問題がありますか？どちらも同じ速度で実行されると予想していました。このテストの繰り返しは、同じ傾向を示しています。

コード：

#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 が使用されないため、ベクトル/配列を読み取るステップが完全にスキップまたは削減される可能性があります。最後の割り当てです。少なくともそれは私が理解していることです)。
4

1 に答える 1

4

確かに決定的な答えではありませんが、ループを変数に書き込んでいます。つまり、コンパイラはシーケンシャル読み取りの最終結果を簡単に推測できるため、ループを最適化できます。明らかにこれを行っていないため、反復子アプローチを確実に好まない最適化はないと思います。他の数値は近すぎて結論を出すことができません。

于 2012-06-04T20:25:03.247 に答える