Vector initializing slower than array...why?

Question

I tried 2 things: (pseudo code below)

int arr[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

and

vector<int> arr(10000);
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

I ran both the programs and timed it using the "time" shell command. Program 1 runs in 5 seconds, program 2 runs in 30 seconds. I ran both programs with compiler optimization turned on, and both programs ran in about the same time (0.38s). I am confused by these results. Can someone please explain to me why this is happening?

Thanks!

Answer 1

For the template, subscripting is done with operator[]. With optimization turned off, that'll usually be generated as a real function call, adding a lot of overhead to something as simple as subscripting into an array. When you turn on optimization, it's generated inline, removing that overhead.

Answer 2

In debugging mode, implementations of std::vector provide a lot of run-time checking for ease of use. This checking is not available for native arrays. For example, in VC2008, if you compile your vector example in debugging mode, there will be range-checking even in the case of operator[].

Answer 3

If your non-optimized vector implementation is performing bounds checking, that would account for the discrepancy.

Answer 4

because when you write vector arr(10000); you create an object, call it's functions... when and it will be slower than whe you create int arr[10000];

Answer 5

In your examples, the array is on the stack. Accessing data in the array involves accessing data on the stack. That's fast.

On the other hand, while the vector is on the stack, the data for a std::vector is allocated somewhere else (by default it's allocated on the heap via std::allocator). Accessing data in the vector involves accessing data on the heap. That's much slower than accessing data on the stack.

You get something for the performance penalty, though. std::vector is growable, while a regular array is not. Also, the size of a std::vector does not have to be compile time constant, while the size of an array on the stack does. A heap-allocated array (via operator new[]) does not have to be a compile-time constant. If you compare a heap allocated array with a std::vector you'll find the performance is much closer.

int* arr = new int[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

delete[] arr; // std::vector does this for you

Answer 6

These are good answers, but there's a quick way you can find out for yourself.

You're seeing a 6-to-1 difference in performance, right? Just run the slow one and hit the "pause" button. Then look at the call stack. The probability is 5 out of 6 (83%) that you will see exactly how it is spending those 25 extra seconds. Do it several times to get as much insight as you want.

For the optimized case, do the same with program 1. Since it is 13 times slower than the optimized program, you will see the reason why on each "pause", with probability 12/13 = 92%.

That is an application of this technique.