Dynamically allocated arrays or std::vector

Question

I'm trying to optimize my C++ code. I've searched the internet on using dynamically allocated C++ arrays vs using std::vector and have generally seen a recommendation in favor of std::vector and that the difference in performance between the two is negligible. For instance here - Using arrays or std::vectors in C++, what's the performance gap?.

However, I wrote some code to test the performance of iterating through an array/vector and assigning values to the elements and I generally found that using dynamically allocated arrays was nearly 3 times faster than using vectors (I did specify a size for the vectors beforehand). I used g++-4.3.2.

However I feel that my test may have ignored issues I don't know about so I would appreciate any advice on this issue.

Thanks

Code used -

#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

I agree with 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 2

Your code provides an unfair comparison between the two cases since you're doing far more work in the vector test than the array test.

With the vector, you're incrementing both the iterator (vecIT) and a separate variable (i) for generating the assignment values.

With the array, you're only incrementing the variable i and using it for dual purpose.

Answer 3

I think the answer here is obvious: it doesn't matter. Like jalf said the code will end up being about the same, but even if it wasn't, look at the numbers. The code you posted creates a huge array of 10 MILLION items, yet iterating over the entire array takes only a few hundredths of a second.

Even if your application really is working with that much data, whatever it is you're actually doing with that data is likely to take much more time than iterating over your array. Just use whichever data structure you prefer, and focus your time on the rest of your code.

To prove my point, here's the code with one change: the assignment of i to the array item is replaced with an assignment of sqrt(i). On my machine using -O2, the execution time triples from .02 to .06 seconds.

#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 4

One reason you're code might not be performing quite the same is because on your std::vector version, you are incrimenting two values, the integer i and the std::vector::iterator vecIt. To really be equivalent, you could refactor to

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 5

The issue seems to be that you compiled your code with optimizations turned off. On my machine, OS X 10.5.7 with g++ 4.0.1 I actually see that the vector is faster than primitive arrays by a factor of 2.5.

With gcc try to pass -O2 to the compiler and see if there's any improvement.

Answer 6

The reason that your array iterating is faster is that the the number of iteration is constant, and compiler is able to unroll the loop. Try to use rand to generate a number, and multiple it to be a big number you wanted so that compiler wont be able to figure it out at compile time. Then try it again, you will see similar runtime results.