4

这是比较向量与数组的公平测试吗？速度上的差异似乎太大了。我的测试表明阵列快 10 到 100 倍！

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

1 回答 1

12

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.

于 2012-12-15T18:43:16.500 回答