About deleting extra memory from std::vector

[JiiPee]

We all know the vector class does not have a function to delete extra
memory from the vector. So my first question is that why is it not
there? :) Is there a good reason, as I think its many times needed.

Secondly, we can do it ouselves, and everybody recommends:

(deleting extra memory from a)
vector<int> a{3,4,7,5,8,7};
a.push_back(55);

vector<int> temp(a);
a.swap(temp);

so now a has capacity 7. But I was just thinking, that can't we just do
a move:
vector<int> temp(a);
a = std::move(temp);

becouse move will now make sure a is excatcly temp. Why we would like to
copy stuff from a to temp (with swap) bce temp is not needed anyway ...
kind of extra work? What is the reason behind swap here?

[JiiPee]

does anybody know in what situation shrink_to_fit would not do the job
of taking off the extra memory exactly like asked? I tested, and it
always did take off the extra memory. But we know its not guaranteed, so
in what situation it would not do it?

[Paavo Helde]

On 28.02.2016 15:27, JiiPee wrote:
> We all know the vector class does not have a function to delete extra
> memory from the vector.

You mean shrink_to_fit() is not guaranteed to work? I bet when it does
not then it has good reasons not to.

> So my first question is that why is it not
> there? :) Is there a good reason, as I think its many times needed.

For example? It most probably means an extra copy of the whole array for
no obvious benefit.

If one is working in tight environment where every byte is counted, then
one does not over-allocate arrays in the first place, so there will be
no need to shrink them. Instead, one would use e.g. reserve() to
allocate the correct amount beforehand.

>
> Secondly, we can do it ouselves, and everybody recommends:
>
> (deleting extra memory from a)
> vector<int> a{3,4,7,5,8,7};
> a.push_back(55);
>
> vector<int> temp(a);
> a.swap(temp);
>
> so now a has capacity 7. But I was just thinking, that can't we just do
> a move:
> vector<int> temp(a);
> a = std::move(temp);

That's basically just as good. The swap idiom just predates the C++11
move. And if you have C++11 then you will have shrink_to_fit() which
most probably does the same in a more direct way, so there is no need to
use move.

>
> becouse move will now make sure a is excatcly temp. Why we would like to
> copy stuff from a to temp (with swap) bce temp is not needed anyway ...
> kind of extra work? What is the reason behind swap here?

Swap was a workaround to *avoid* extra copy and extra work in pre-C+11
when there was no move.

[Öö Tiib]

On Sunday, 28 February 2016 16:38:55 UTC+2, JiiPee wrote:
> does anybody know in what situation shrink_to_fit would not do the job
> of taking off the extra memory exactly like asked? I tested, and it
> always did take off the extra memory. But we know its not guaranteed, so
> in what situation it would not do it?

Implementations are allowed to ignore it for sake of optimizations.

Imagine memory management that actually allocates only as multiples
of 32 bytes or the like. In reality most implementations have memory
management with such constraints.

As result the 'std::vector<char> hi{'H','e','l','l','o',0};' has
two choices:
1) to claim that its capacity is 6 (despite it got 32 bytes)
2) to put extra effort into telling honestly that the capacity is 32.
Most implementations have chosen to ignore the extra and to
do 1). It is simpler to implement and less stupid questions and
who really cares that it is less optimal.

[Juha Nieminen]

JiiPee <n...@notvalid.com> wrote:
> We all know the vector class does not have a function to delete extra
> memory from the vector. So my first question is that why is it not
> there? :) Is there a good reason, as I think its many times needed.

std::vector::shrink_to_fit() does exactly that, if the underlying
memory management system supports reducing the size of an alloction.
(If the underlying memory management system does not support it, which
is sometimes the case, then that function does nothing.)

The reason why it's optional is, obviously, because historically not
all systems support resizing of allocated blocks of memory (either
larger or smaller). The only way was/is to allocate a new block and
copy all the values there.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Alf P. Steinbach]

On 28.02.2016 19:32, Juha Nieminen wrote:
> JiiPee <n...@notvalid.com> wrote:
>> We all know the vector class does not have a function to delete extra
>> memory from the vector. So my first question is that why is it not
>> there? :) Is there a good reason, as I think its many times needed.
>
> std::vector::shrink_to_fit() does exactly that, if the underlying
> memory management system supports reducing the size of an alloction.

No no.

shrink_to_fit can and will in general allocate a new buffer, when the
original capacity is way too large.

> (If the underlying memory management system does not support it, which
> is sometimes the case, then that function does nothing.)

No no.

> The reason why it's optional is, obviously, because historically not
> all systems support resizing of allocated blocks of memory (either
> larger or smaller). The only way was/is to allocate a new block and
> copy all the values there.

Yes, I agree. :)


Cheers!,

- Alf

[Juha Nieminen]

Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
> On 28.02.2016 19:32, Juha Nieminen wrote:
>> JiiPee <n...@notvalid.com> wrote:
>>> We all know the vector class does not have a function to delete extra
>>> memory from the vector. So my first question is that why is it not
>>> there? :) Is there a good reason, as I think its many times needed.
>>
>> std::vector::shrink_to_fit() does exactly that, if the underlying
>> memory management system supports reducing the size of an alloction.
>
> No no.
>
> shrink_to_fit can and will in general allocate a new buffer, when the
> original capacity is way too large.

"The request is non-binding, and the container implementation is free
to optimize otherwise and leave the vector with a capacity greater than
its size."

If it's non-binding, I interpret that as the implementation just
having an empty shrink_to_fit() function as being valid.

[Alf P. Steinbach]

Yes, formally.

The reason that it's non-binding is that it can be inefficient,
completely no-win, to reduce capacity in some situations.

And so the easy to use function has a safety catch, while those who are
bent on reducing the capacity no matter what, and know what they're
doing, can easily accomplish that via e.g. the swap idiom.

Note that this has only very peripherally to do with shrinking an
allocation itself.

Unlike std::string, a std::vector can't use the short buffer
optimization, and can't be generally based on e.g. `malloc` and
`realloc`. Experiments (I think e.g. Howard Hinnant tried this) have
shown that it can be significantly faster with `realloc`. So I think it
ideally should be done as an optimization for the case of built-in type
as item type, but unfortunately it can't be done for the general case.


Cheers & hth.,

- Alf

[Juha Nieminen]

Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
> Unlike std::string, a std::vector can't use the short buffer
> optimization

Why not? I don't think there's anything in the specification of
std::vector to stop it from doing that.

The boost small_vector is, in fact, exactly this. (I haven't checked
if it's 100% std::vector-compliant in terms of the C++ standard, but
I don't see why it couldn't be.)

[Alf P. Steinbach]

On 03.03.2016 15:35, Juha Nieminen wrote:
> Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
>> Unlike std::string, a std::vector can't use the short buffer
>> optimization
>
> Why not? I don't think there's anything in the specification of
> std::vector to stop it from doing that.

You can swap two std::vector instances and keep item references valid.

That's only possible when it's the buffers themselves that are swapped.

The small buffer optimization is where storage in the vector object
itself is used as buffer: it can't be swapped around.

> The boost small_vector is, in fact, exactly this. (I haven't checked
> if it's 100% std::vector-compliant in terms of the C++ standard, but
> I don't see why it couldn't be.)

Presumably the Boost small vector doesn't claim to conform to the full
`std::vector` requirements. Thanks for pointing me in that direction! :)
I didn't know about it.

[Juha Nieminen]

Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
> You can swap two std::vector instances and keep item references valid.

Fair enough. That's probably the only requirement that would be broken
with a "small vector optimization".

[woodb...@gmail.com]

I think calling that "small" when it can become huge is
goofy. Maybe it should be called array_vector. And like
std::list, whatever that thing is called, it's rarely needed.

This reminds me of my rabbi's teaching to "chew the meat
and spit the bones." Some of Boost is great, but other
parts are lame.

Brian
Ebenezer Enterprises - "Real development is not leaving
things behind, as on a road, but drawing life from
them, as from a root." G. K. Chesterton
I'd add the word "software" before the word "development."

http://webEbenezer.net