Why is an array so much faster than a vector?

Question

Is this a fair test for comparing a vector with an array? The difference in speed seems too large. My test suggests the array is 10 to 100 times faster!

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <windows.h>
#include <stdint.h>

using namespace std;

double PCFreq = 0.0;
__int64 CounterStart = 0;

using namespace std;

void StartCounter()
{
    LARGE_INTEGER li;
    if(!QueryPerformanceFrequency(&li))
    std:cout << "QueryPerformanceFrequency failed!\n";

    PCFreq = double(li.QuadPart)/1000000000;

    QueryPerformanceCounter(&li);
    CounterStart = li.QuadPart;
}
double GetCounter()
{
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return double(li.QuadPart-CounterStart)/PCFreq;
}

int _tmain(int argc, _TCHAR* argv[])
{
    //Can do 100,000 but not 1,000,000
    const int vectorsize = 100000;
    cout.precision(10);

    StartCounter();
    vector<int> test1(vectorsize);
    for(int i=0; i<vectorsize; i++){
        test1[i] = 5;
    }
    cout << GetCounter() << endl << endl;


    StartCounter();
    int test2[vectorsize];
    for(int i=0; i<vectorsize; i++){
        test2[i] = 5;
    }
    cout << GetCounter() << endl << endl;

    cout << test2[0];

    int t = 0;
    cin >> t;
    return 0;
}

Answer 1

It depends on what you are comparing.

Your benchmark measures both setup time and access times together. It's doubtless that std::vector has a more expensive setup time. This is because it needs to allocate memory, and then (by necessity of the standard) call default constructors on all the elements. Which for a POD type, means zeroing.

So if you're trying to measure access times, then no your benchmark isn't accurate.

Here's some numbers to digest:

Original Code:

StartCounter();
vector<int> test1(vectorsize);

for(int i=0; i<vectorsize; i++){
    test1[i] = 5;
}
cout << GetCounter() << endl << endl;

Time: 444353.5206

---

Start timing after declaring and initializing the vector:

vector<int> test1(vectorsize);

StartCounter();
for(int i=0; i<vectorsize; i++){
    test1[i] = 5;
}
cout << GetCounter() << endl << endl;

Time: 15031.76101

---

And for the array:

StartCounter();
int test2[vectorsize];
for(int i=0; i<vectorsize; i++){
    test2[i] = 5;
}
cout << GetCounter() << endl << endl;

Time: 38129.345

The times are about the same regardless of whether the declaration is timed. This is likely because stack allocation is done all at once upon entry to the function.

---

Basically, the vector memory allocation and initialization is taking a disproportionate amount of time. But the actual loop is fast.

I'll also note that your current benchmark framework is still sightly flawed. You only make one pass over each array. So cache-effects and lazy-allocation will be significant.

The reason why the array is now slower is likely due to lazy-allocation. The array is allocated, but it hasn't been committed yet. Lazy allocation means that it is committed upon first access - which involves a page-fault and a context-switch to the kernel.

---

Here's a fairer test with an outer loop to increase the benchmark time:

vector<int> test1(vectorsize);

StartCounter();
for (int c = 0; c < 10000; c++){
    for(int i=0; i<vectorsize; i++){
        test1[i] = 5;
    }
}
cout << GetCounter() << endl << endl;

Time: 227330454.6

int test2[vectorsize];
memset(test2,0,sizeof(test2));

StartCounter();
for (int c = 0; c < 10000; c++){
    for(int i=0; i<vectorsize; i++){
        test2[i] = 5;
    }
}
cout << GetCounter() << endl << endl;
cout << test2[0];

Time: 212286228.2

So no an array is NOT faster than a vector for steady-state access. It's just tricky to benchmark properly.