Why so much allocation on heap for vector with emplace back?

Question

Hi

I have a structure which has one int member. Size of this structure is hence 4 bytes.

Now, when I have vector initialized with 3 objects of test structure, it is expected to allocate 12 bytes on heap. Global new operarator overloaded suggests this as expected.

Now I am doing clear on vector and capacity remains 3 but size reduces back to 0.

With this background, let me ask a query I have on my code snippet below:

Now refer code of trial2 function.

As i have not done shrink to fit yet, capacity does not go back to 0 and remains 3 yet. Now doing emplace_back 3 times and no allocation happens on heap. When at the end function call ends, vector object goes out of scope and de allocates everything from heap.

This is perfectly fine for me to digest.

Now, refer code of trial1 function.

Here , i am just emplacing back 2 elements (obviously less than 3 i.e. capacity) but could observe allocation on heap... Why ?
https://code.sololearn.com/cFRwdX6P4bjp/?ref=app

Answer 1

Ketan Lalcheta In fact i said that the allocation that you refer is made in consequence of shrink_to_fit call because vector have to allocate an array of a new size (2) to shrink the capacity to size.

Or Maybe i have not understand well your question 😅

Answer 2

KrOW

Yup, that seems correct...

I just updated code... cout statement added after emplace_back but before shrink to fit

Wow.. now, allocation is done after that cout stating that re allocation of size 8 happened due to new capacity 2 not matching with 3

BUT

isnt this a very bad implementation of shrink to fit ?

More contigous memory may not be available , but to reduce is not very easy ?

Suppose i have reserved 1000 elements memory, pushed_back 999 elements and then doing shrink to fit... just to save 1 space, shrink to fit does re allocation of 999 elements....

Very bad isnt it ?

Answer 3

Ketan Lalcheta Fiuu, you saved me to write a code example for show the concept 😂.
Anyway, its bad but its good too.. Its a compromise .. Its the price to pay for an access O(1) and, above all, using shrink_to_all presume a conoscence about how work at memory level the the programmer have to understand potential performance implications

Answer 4

Ketan Lalcheta
google "memory thrashing". Maybe it is to prevent that?

https://stackoverflow.com/questions/19031902/what-is-thrashing-why-does-it-occur

Answer 5

Thanks Bob_Li ..it seems different and something at time consumption. But thanks again for sharing... i am not at all aware about this and would definitely have a look.

Answer 6

Ketan Lalcheta
int is 4 bytes, after two emplace operations, 8 bytes is correct, I think....🤔

anyway, I learned something new from this post.
emplace_back.
But it's got its caveats.

https://yasenh.github.io/post/cpp-diary-1-emplace_back/#:~:text=push_back%3A%20Adds%20a%20new%20element,after%20its%20current%20last%20element.

https://www.quora.com/How-does-C-vector-push_back-ensure-address-is-available-and-elements-are-contiguous/answer/V%C3%A1clav-Bla%C5%BEek?ch=10&oid=217274058&share=68bccb89&srid=iSS1x&target_type=answer

Answer 7

Ketan Lalcheta
what you are doing is similar to this YouTube video

https://youtu.be/uwv1uvi1OTU

Answer 8

I am not concerned about emplace back Bob_Li , but thanks for sharing

My issue was with shrink to fit reallocating even though it has to reduce the size

But i could figure out one issue in my code due to you focusing on emplace back

Emplace_back with test() is not helpful to avoid constructor and then copy... it should be ideally

Vector.emplace_back()
Not
Vector.emplace_back(test())

Answer 9

Ketan Lalcheta The allocation of 8 bytes happen because shrink_to_fit calls.
Because of it, the vector have to shrink the vector internal array to real size then, because at that point the size is 2 while the capacity is to 3, the vector have to create a new internal array with only 2 items (here happen the allocation of 8 bytes), copy to it the current 2 items then deallocate the old internal array

Answer 10

I think no

Let me do some analysis of code for trial1

After vector initialization : size 3 and capacity 3

Cleared so size 0 and capacity 3 as still shrink to fit is not called

Now, we are doing first insertion.. size (0) is less than capacity (3). So, allocation should not happen for first emplace_back

Now, we are doing amother insertion.. size (1) is less than capacity (3). So, allocation should not happen for second emplace_back as well

Why it happens ?

Answer 11

If i would have called shrink to fit before emplace back , then i digest 8 byte allocation

But i am doing emplace back just before shrink to fit

Answer 12

I was wondering about the reason for the struct.
I also realized that puts is more efficient than cout.

https://code.sololearn.com/cTmsm147f12e/?ref=app