Comparing pushing data (1 million numbers) with and without prior resizing in std::vector

Question

Comparing pushing data (1 million numbers) with and without prior resizing into std::vector. To my amusement , I found the later ( without resizing) to be faster , which is contrary to expectation. What happened ? I am using MS VC++ 2017 compiler.

double times = 1000000;

vector<double> vec1;
auto tp_start = chrono::high_resolution_clock::now();
for (double i=0; i < times; i++)
{
    vec1.push_back(i);
}
auto lapse = chrono::high_resolution_clock::now() - tp_start;
cout << chrono::duration_cast<chrono::milliseconds>(lapse).count() << " ms : push without prior resize  \n"; // 501 ms

vector<double> vec2;
vec2.resize(times);  // resizing
tp_start = chrono::high_resolution_clock::now();    
for (double i = 0; i < times; i++)
{     
       vec2[i]  = i; //fastest
      // vec2.push_back(i); //slower
}
lapse = chrono::high_resolution_clock::now() - tp_start;
cout << chrono::duration_cast<chrono::milliseconds>(lapse).count() << " ms : push with prior resizing  \n"; // 518 ms , shouldn't this be faster theoritically

Edited:

After this change: vec2.resize(times); it works faster

After this change: vec2.reserve(times); it works even faster

After this change: vec2[i] = i; becomes super fast

Any advise what is the best practice?

Edited 2 ( compiler in optimized mode)

10 million data :

 120ms : 41ms   reserve & pushback

 121ms : 35ms   resize & vec[i]

100 million data :

 1356ms : 427ms   reserve & pushback

 1345ms : 364ms   resize & vec[i]

vec[i] still wins

You want .reserve(), not .resize(). Your second vector ends up containing two million elements. Also; what are your compiler flags/options? Make sure you are testing an optimized build, not a debug build. — Jesper Juhl
As for the argument to the resize (or reserve) calls, it's the number of elements, not the size in bytes. If the size of double is 8 (which is common) then you will (with your current code) have nine million elements in the vector, of which the first eight million will all be zero. — Some programmer dude
You should also reserve times amount of items, not 4-8x as much. — Aki Suihkonen
With a corrected example, I get expected results: quick-bench.com/HLMeKeT0G67VgUYsMgyb1jU2vsE — Stephen Newell

scottxiao scottxiao · Accepted Answer · 2018-04-08T05:34:25

After this change: vec2.resize(times); it works faster

I think maybe that's because after the resize the vec2 actually holds 2*times space,so it does not need reallocating in later push_back.

After this change: vec2.reserve(times); it works even faster

this version does not need reallocating,so it's better than the first one.

After this change: vec2[i] = i; becomes super fast

this directly place the element on its position,without any redundant operations compared with push_back

origin answer

You should do like:

vector<double> vec2;
vec2.resize(sizeof(double)* times);  // this directly chage the size(),with capacity() also changed.
tp_start = chrono::high_resolution_clock::now();    
for (double i = 0; i < times; i++)
{
    vec2[i]=i;//not push_back
}

If you still use push_back in this situation,it does not have any efficiency.

And in your example with resize,the size of vec2 is larger than vec1,which needs more time to reallocate its memory,and takes more time to do push_back.By the way it's better to do reserve(n) in your case.

Comparing pushing data (1 million numbers) with and without prior resizing in std::vector

1 Answers

origin answer