Releasing storage of a vector

[jacob navia]

Hi

Vectors allocate a bit more storage than is needed to avoid repeated
reallocations. Is there a way to force the vector to release the extra
storage and keep only what is strictly necessary?

Thanks in advance for your time.

jacob

 

[Miles Bader]

Vectors allocate a bit more storage than is needed to avoid repeated
reallocations. Is there a way to force the vector to release the extra
storage and keep only what is strictly necessary?

In C++11, there's the "shrink_to_fit" method...

http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

-miles

 

[jacob navia]

Le 30/04/12 22:02, Miles Bader a écrit :

In C++11, there's the "shrink_to_fit" method...

http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

-miles

Thanks a lot!

jacob

 

[Nobody]

Vectors allocate a bit more storage than is needed to avoid repeated
reallocations. Is there a way to force the vector to release the extra
storage and keep only what is strictly necessary?

No. Miles mentioned C++11's shrink_to_fit() method, but that's only a
request; it can legitimately be ignored.

 

[jacob navia]

Le 01/05/12 06:31, Nobody a écrit :

No. Miles mentioned C++11's shrink_to_fit() method, but that's only a
request; it can legitimately be ignored.

Ahhh it is only a *request* ???

It looked official enough for me!

Thanks for this clarification. I thought it was in the standard already.

 

[Marcel Müller]

Vectors allocate a bit more storage than is needed to avoid repeated
reallocations. Is there a way to force the vector to release the extra
storage and keep only what is strictly necessary?

This requires a reallocation in general.
Simply create a new vector with the appropriate size and use this one.

vector<int> current;

if (current.size() != current.capacity())
{ vector<int> newvec;
newvec.reserve(current.size);
newvec.assign(current.begin(), current.end());
current.swap(newvec);
}

There is no guarantee that reserve does exactly what you intend, but
calling it on an empty vector usually does what you want. You could
check newvec.capacity() to validate that. But keep in mind, that
allocating a bit more than required could be for free on a certain
platform because the physical allocation size is restricted to multiples
of some value. So I would not care about small differences.


Marcel

 

[Nobody]

Ahhh it is only a *request* ???

It looked official enough for me!

Thanks for this clarification. I thought it was in the standard already.

It is in the standard, but the standard only requires that the method
exists, it doesn't require that it actually minimises the memory used (or
even what that means).

I can't think of any language which treats memory consumption as a
functional requirement.

In C++, vector::reserve() and vector::capacity() were never strictly about
memory consumption per se, but rather about the fact that iterators are
invalidated by reallocation; if v.capacity()-v.size()==N, you can append
up to N elements to the vector without invalidating any iterators on it.

 

[Miles Bader]

Ahhh it is only a *request* ???

It looked official enough for me!
Thanks for this clarification. I thought it was in the standard already.

It is in the standard.

However, like _anything_ in the standard, it's subject to "quality of
implementation": good vendors will make it do what you expect -- this
method is easy to implement in most cases, so there's little reason
not to -- but a crappy vendor may implement it crappily.

[but the same caveat applies to almost everything -- for all you know,
your vendor allocates 1MB for every new vector ... nothing in the
standard forbids it...]

-miles

 

[jacob navia]

Le 01/05/12 10:23, Marcel Müller a écrit :

There is no guarantee that reserve does exactly what you intend, but
calling it on an empty vector usually does what you want. You could
check newvec.capacity() to validate that. But keep in mind, that
allocating a bit more than required could be for free on a certain
platform because the physical allocation size is restricted to multiples
of some value. So I would not care about small differences.

Well, the context is that I am writing a containers library for the C
language. In C, memory management and keeping software small are
important considerations, to the contrary of C++.

I thought that

Vector *vector;
extern iVectorInterface iVector; // The interface table

iVector.Resize(vector,iVector.GetSize(vector));

would be an "idiom" within my library to request the library to shed
any extra storage used. This would arrive when you know that the
vector will never be modified again, for instance.

Simply requesting a resize with the exact number of elements currently
stored would mean that the vector should be shrunk to fit.

I thought that a new method would simply be too heavy.

Within that context, I wanted to add an example of how this is done in
C++, hence my question.

Thanks for your answer.

jacob

 

[Ian Collins]

Le 01/05/12 10:23, Marcel Müller a écrit :

Well, the context is that I am writing a containers library for the C
language. In C, memory management and keeping software small are
important considerations, to the contrary of C++.

Where do you get that idea from?

If the underlying memory subsystem allocates in multiples of say 32
bytes and your vector uses 33, how can you give back the remaining 31?

I thought that

Vector *vector;
extern iVectorInterface iVector; // The interface table

iVector.Resize(vector,iVector.GetSize(vector));

would be an "idiom" within my library to request the library to shed
any extra storage used. This would arrive when you know that the
vector will never be modified again, for instance.

So would it be non-binding like shrink_to_fit, or would the
implementation be obliged to somehow give back those 31 bytes?

Simply requesting a resize with the exact number of elements currently
stored would mean that the vector should be shrunk to fit.

Which is what shrink_to_fit is intended to do - with the sensible note:

"The request is non-binding to allow latitude for implementation
specific optimizations"

 

[Jorgen Grahn]

It is in the standard.

However, like _anything_ in the standard, it's subject to "quality of
implementation": good vendors will make it do what you expect

It's hard to tell what people expect, though. If my vector has a
capacity of 1 000 000 but a size of 999 999, do I really want an
expensive (and possibly fatal) copying and reallocation to happen?

/Jorgen

 

[Jorgen Grahn]

Le 01/05/12 10:23, Marcel Müller a écrit :

Well, the context is that I am writing a containers library for the C
language. In C, memory management and keeping software small are
important considerations, to the contrary of C++.

Memory management is less of a problem in C++, but just as important.

/Jorgen

 

[jacob navia]

Le 02/05/12 12:08, Jorgen Grahn a écrit :

It's hard to tell what people expect, though. If my vector has a
capacity of 1 000 000 but a size of 999 999, do I really want an
expensive (and possibly fatal) copying and reallocation to happen?

/Jorgen

The problem is that if your vector has 999 999 elements and then you
reduce that size to 735 you really would like that the extra memory
allocated is released if you know that vector will not change again.

That is the most common use case.

 

[Miles Bader]

It's hard to tell what people expect, though. If my vector has a
capacity of 1 000 000 but a size of 999 999, do I really want an
expensive (and possibly fatal) copying and reallocation to happen?

Of course -- that's why it's a separate method, and so explicitly
named. I don't think there's really much question about that.

-miles

 

[Jorgen Grahn]

Of course -- that's why it's a separate method, and so explicitly
named. I don't think there's really much question about that.

My point is, I'd expect a quality implementation to apply some
heuristics so that shrink_to_fit() would do nothing in the case above.
It seems we might have different expectations after all.

/Jorgen

 

[Miles Bader]

My point is, I'd expect a quality implementation to apply some
heuristics so that shrink_to_fit() would do nothing in the case above.
It seems we might have different expectations after all.

I don't think your expectation is reasonable, given the very explicit
name of the method.

[Note that it's trivial for user code to do something like:
"if (...) v.shrink_to_fit()", to establish more refined behavior.]

-miles

 

[Miles Bader]

I don't think your expectation is reasonable, given the very
explicit name of the method.

[Note that it's trivial for user code to do something like: "if
(...) v.shrink_to_fit()", to establish more refined behavior.]

But even if an implementation requested that the OS kernel reduce
the allocated memory from 1000000B to 999999B, there's no guarantee
that the kernel will actually do anything to change the mappings in
the background. Any change below granularity of whichever memory
heap/pool is in use is pretty much going to get ignored by the OS.

Of course. But everybody knows that, and such issues affect user code
as well as library code; because these issues are very common, they
are not surprising to most competent programmers. All I'm saying is
that it would be silly for the library author to add _additional_
uncertainties on top of those that everybody already understands. The
library should do what it can within its remit, and leave it at that.

"shrink_to_fit", AFAICT is a very "practical" method; it basically
just adds a convenient way to do something people often wanted to do,
but for which only clumsy methods existed previously . I see no
reason to read anything more into it...

-Miles

 

[Nobody]

[but the same caveat applies to almost everything -- for all you know,
your vendor allocates 1MB for every new vector ... nothing in the
standard forbids it...]

1MB of storage, or 1MB of address space?

It's not completely inconceivable that someone might create an
architecture where every allocation gets a separate "segment" (i.e. an
entire virtual address space), with storage allocated as needed.

The STL semantics were originally supposed to be even more abstract than
they currently are. Every container template has an "allocator" template
parameter, and the allocator defines its own "pointer" and "reference"
types.

AIUI, the idea was to make the concept of storage (or "memory") completely
abstract, but it turned out to be hamstrung by the existing language
semantics, meaning that allocator<T>:ointer and allocator<T>::reference
cannot be other than T* and T& respectively.

 

[Jorgen Grahn]

I don't think your expectation is reasonable, given the very explicit
name of the method.

But upthread people pointed out that the method doesn't have to do
anything /at all/ -- surely that's a strong hint that it is misnamed?

[Note that it's trivial for user code to do something like:
"if (...) v.shrink_to_fit()", to establish more refined behavior.]

In that case I'd prefer a method called unreserve(size_type) or
something -- if I have to do the work myself, I also want the full
control.

/Jorgen

 

[Miles Bader]

But upthread people pointed out that the method doesn't have to do
anything /at all/ -- surely that's a strong hint that it is misnamed?

It's a hint that the standard gives some breathing room for
implementors when warranted (such as the reserved space for vectors,
whose existance isn't directly observable).

That doesn't mean implementors should do dumb things when there's no
reason to -- it seems fairly obvious what behavior is expected in
"conventional" environments.

[Note that it's trivial for user code to do something like:
"if (...) v.shrink_to_fit()", to establish more refined behavior.]

In that case I'd prefer a method called unreserve(size_type) or
something -- if I have to do the work myself, I also want the full
control.

So when you release your standard, it'll be called that... :]

[Though "do the work myself" seems a bit overstated -- a simple "if
(comparison)..." isn't a huge burden...]

As I mentioned elsewhere, this particular method seems to basically be
the committee's "OK, OK" response to complaints that performing this
often-wanted operation ("get rid of all the extra reserved space now
that I've finished filling in my vector") was clumsy in the old
standard.

My impression is that it wasn't really carefully thought out as a
general tool, just as a practical answer to those complaints. No
doubt it's possible to replace it with something more elegant and
general -- but who knows if it's worth the trouble...

-miles