> "Ed Brey" <brey@afd.mke.etn.com> writes:
> >Even though a heap manager never needs to move a block to shrink it, [...]

In article <7ejf95$i3i$1@mulga.cs.mu.OZ.AU>,
  fjh@cs.mu.OZ.AU (Fergus Henderson) wrote:
> This is not true.  Some heap managers do need to move a block to shrink it.
> In particular, some heap managers avoid storing a header at the start
> of each block; instead of storing the size of the block in the header,
> the size can be deduced from the block's address, because each page
> of memory is only used to allocate things of one particular size.

Such schemes are designed to increase speed at the expense of higher
memory consumption. The implementation of shrink() on such a system
simply returns a success code. The extra memory is not available for
other purposes, but it will be reclaimed eventually (when the
newly-sized memory block is finally freed), and in the mean time the
reallocation was done in constant time. Further, if the block later
needs to grow back to it's original size, this too is constant time.

----
Allan_W@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern <austern@sgi.com> writes:

>There's a cute trick for shrink-to-fit, though, that requires no
>changes to vector's interface:
>  std::vector<T>(v.begin(), v.end()).swap(v);
>
>(I thought of this one-liner after my book came out.  The example of
>shrink-to-fit in my book is slightly more complicated.)

If you want conciseness, why not just

 std::vector<T>(v).swap(v);

?

Of course if you want robustness too it should be something like

 try { std::vector<T>(v).swap(v); } catch (...) {}

And if you want readability too then you should define a function
called shrink_to_fit() or something like that, and then just use
that function:

 shrink_to_fit(v);

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern <austern@sgi.com> wrote in message
news:fxtsoac4bgm.fsf@isolde.engr.sgi.com...
>
> No.  The committee discussed changing the semantics of
> vector<>::reserve() so that v.reserve(n), for n < v.capacity(), could
> be taken as a hint to shrink the capacity.  It was argued, though,
> that changing the semantics was a bad idea: the standard clearly
> guarantees that v.reserve(n) has no effect if n < v.capacity(), and
> there may well be code that relies on that fact.  A change like this
> would not be compatible.

This is a good point.  Additionally, the C++ spec appears to guarantee that
following a call to v.reserve(n), v for the rest of its existence will
always have capacity greater than or equal to n.  However, the C++ spec does
allow shrinking, so long as capacity doesn't go below the maximum of all
previous n's.  This makes an auto-shrinking implementation expensive, since
the vector needs to keep track of the size, capacity, and minimum guaranteed
capacity.

Are there any vector implementations that implement auto-shrinking?  I don't
know of any, which is reasonable, due to the extra space (for minimum
guaranteed capacity) and time (for deciding whether to shrink) cost.
Unfortunately, the space cost of not auto-shrinking can be high: A
long-lived vector adapted into a stack can be very big for a small duration,
but then be stuck reserving unused space for a long time.  Of course, an
application can do a kind of garbase collection and manually shrink the
stack's capacity occasionally, if a lot of space is wasted.

This of course, leads us right back to the original point.  Even though
manual shrinking can be done in a small amount of pretty code, e.g.

> There's a cute trick for shrink-to-fit, though, that requires no
> changes to vector's interface:
>   std::vector<T>(v.begin(), v.end()).swap(v);

there still is the substantial time penalty of the copy.  The fact that a
linear-time operation is required where a constant-time is feasible via a
more rich interface to vector seems to depart from C++'s goal of efficiency.

To be efficient and complete, vector would require to more functions (or
something equivilent to get the job done as efficiently):

void shrink();  // container contents can be moved
void shrink_no_invalidation();  // container contents may not be moved

Even though a heap manager never needs to move a block to shrink it,
sometimes it is desireable for heap management purposes, even though it is
linear time instead of contant time.  Having two functions allows the
application to give the heap manager the flexibility to move the block only
if the application can tolarate a move.

Even with better names for the functions, adding these functions muddies up
the simplicty of vector.  Unfortunately, given reserve()'s semantics, vector
as it stands now is not complete and efficient.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Ed Brey" <brey@afd.mke.etn.com> writes:

>Even though manual shrinking can be done in a small amount of pretty code,
>there still is the substantial time penalty of the copy.  The fact that a
>linear-time operation is required where a constant-time is feasible via a
>more rich interface to vector seems to depart from C++'s goal of efficiency.
>
>To be efficient and complete, vector would require to more functions (or
>something equivilent to get the job done as efficiently):
>
>void shrink();  // container contents can be moved
>void shrink_no_invalidation();  // container contents may not be moved
>
>Even though a heap manager never needs to move a block to shrink it, [...]

This is not true.  Some heap managers do need to move a block to shrink it.
In particular, some heap managers avoid storing a header at the start
of each block; instead of storing the size of the block in the header,
the size can be deduced from the block's address, because each page
of memory is only used to allocate things of one particular size.
(Often this scheme is only used for small block sizes, with a
different allocation scheme used for large block sizes.)
The advantage of this kind of scheme is that by avoiding the headers
you reduce memory usage and increase locality.  With this kind of
allocation scheme, changing the size of a block often does inherently
require moving it, and so many shrink-to-fit requests must either be
ignored or must take linear time.

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Fergus Henderson wrote:

> And if you want readability too then you should define a function
> called shrink_to_fit() or something like that, and then just use
> that function:
>
>         shrink_to_fit(v);

I think that the real question is: where isn't there such a
function in vector interface ? This should be a reasonably
common operation.

--

Valentin Bonnard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

A common case of filling a vector occurs when you don't know initially how
many items you will be putting in, but after some point you know that you
are done putting items into the vector, at least for a while, possibly
forever.

Does the standard define a convention to hint to a vector that it can
reclaim space that it has overcommitted?

The following would seem like a reasonable approach, (but it is just a
convention I made up):

vector<int> v;
int i;
while (get_next_value(i))
    v.push_back(i);
v.reserve(v.size());

The vector could reasonably see "reserve" as a hint to shrink its size if it
has overcommitted.  Having a standard for such a convention of what a
container _should_ do (i.e. implement this way unless there is a good reason
not to) seems important to prevent ambiguity about how to help a container
be efficient, since I'm sure other people can think of other ways to issue
such a hint.

On a related note: I expect that the issue was raised in the committee as to
whether there should be a member with the explicit purpose of reclaiming
overcommitted memory.  What was the rational behind not making such a member
part of the standard.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ed Brey wrote:

> A common case of filling a vector occurs when you don't know initially how
> many items you will be putting in, but after some point you know that you
> are done putting items into the vector, at least for a while, possibly
> forever.

Yes

> Does the standard define a convention to hint to a vector that it can
> reclaim space that it has overcommitted?

void reserve0 (vector<T>& v) // complexity: O(v.size ())
{
    vector<T> v2 = v;
    swap (v, v2);
}

> The following would seem like a reasonable approach, (but it is just a
> convention I made up):
>
> vector<int> v;
> int i;
> while (get_next_value(i))
>     v.push_back(i);
> v.reserve(v.size());

This last statement has no effect.

> The vector could reasonably see "reserve" as a hint to shrink its size if it
> has overcommitted.

But it doesn't.

> since I'm sure other people can think of other ways to issue
> such a hint.

It isn't just a hint. It has side effects.

> On a related note: I expect that the issue was raised in the committee as to
> whether there should be a member with the explicit purpose of reclaiming
> overcommitted memory.

Yes

> What was the rational behind not making such a member
> part of the standard.

You can do it yourself (see above)

--

Valentin Bonnard


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard wrote:
>
> Ed Brey wrote:
...
> > Does the standard define a convention to hint to a vector that it can
> > reclaim space that it has overcommitted?
>
> void reserve0 (vector<T>& v) // complexity: O(v.size ())
> {
>     vector<T> v2 = v;
>     swap (v, v2);
> }

That's no more (or less) of a hint than the reserve() approach.

...
> > The vector could reasonably see "reserve" as a hint to shrink its size if it
> > has overcommitted.
>
> But it doesn't.

The standard doesn't specify that it should shrink to fit, but I hope
that any decent-quality implementation would do so. The complexity
requirements allow it. One common complaint I've heard is that certain
implementations of vector<> always allocate enough space for at least
100 objects, regardless of how many are actually there, and that's just
not necessary. There are places where the complexity requirements
implicitly require overallocation, and places where shrink-to-fit
behavior would be inappropriate, but there are several member functions
of vector<> that can shrink-to-fit, and IMHO they should.
vector<>::reserve() is one of them (in the sense of shrinking to fit the
reservation).
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Ed Brey" <brey@afd.mke.etn.com> writes:

> Does the standard define a convention to hint to a vector that it can
> reclaim space that it has overcommitted?
>
> The following would seem like a reasonable approach, (but it is just a
> convention I made up):
>
> vector<int> v;
> int i;
> while (get_next_value(i))
>     v.push_back(i);
> v.reserve(v.size());
>
> The vector could reasonably see "reserve" as a hint to shrink its size if it
> has overcommitted.  Having a standard for such a convention of what a
> container _should_ do (i.e. implement this way unless there is a good reason
> not to) seems important to prevent ambiguity about how to help a container
> be efficient, since I'm sure other people can think of other ways to issue
> such a hint.

No.  The committee discussed changing the semantics of
vector<>::reserve() so that v.reserve(n), for n < v.capacity(), could
be taken as a hint to shrink the capacity.  It was argued, though,
that changing the semantics was a bad idea: the standard clearly
guarantees that v.reserve(n) has no effect if n < v.capacity(), and
there may well be code that relies on that fact.  A change like this
would not be compatible.

There's a cute trick for shrink-to-fit, though, that requires no
changes to vector's interface:
  std::vector<T>(v.begin(), v.end()).swap(v);

(I thought of this one-liner after my book came out.  The example of
shrink-to-fit in my book is slightly more complicated.)
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <Bonnard.V@wanadoo.fr> wrote in message
news:370B8B6A.5919@wanadoo.fr...
>
> void reserve0 (vector<T>& v) // complexity: O(v.size ())
> {
>     vector<T> v2 = v;
>     swap (v, v2);
> }

This works, but the linear time of the copy is expensive.  Also, the copy
may fail due to lack of memory.  Accounting for the exception may make the
application more expensive.  If eliminating wasted pace is taken into
account as part of the design of a vector, the elimination can easily be
guaranteed to complete successfully in constant time.

> > v.reserve(v.size());
> [...]
> It isn't just a hint. It has side effects.

I used the term "hint" since vector isn't required to shrink the allocated
space when presented with reserve, but it could if it wanted to.  The side
effect I'm looking for is to recover wasted space.  As far as I know is the
only allowed side effect.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

>Valentin Bonnard wrote:
>>
>> Ed Brey wrote:
>...
>> > Does the standard define a convention to hint to a vector that it can
>> > reclaim space that it has overcommitted?
...
>> > The vector could reasonably see "reserve" as a hint to shrink its size
>> > if it has overcommitted.
>>
>> But it doesn't.
>
>The standard doesn't specify that it should shrink to fit, but I hope
>that any decent-quality implementation would do so. The complexity
>requirements allow it.

The complexity requirements may allow it, but the behaviour requirements
do not.  The standard guarantees that reserve() will not invalidate
iterators if the current capacity is greater than or equal to the
requested capacity.  A shrink-to-fit operation would in general require
moving the array (even realloc() does not guarantee that the pointer
returned will be the same as the one passed in), which will cause
iterators to be invalidated.

That's what Valentin meant when he said "It isn't just a hint.
It has side effects."  The side effect is invaliding all references,
pointers, and iterators that point to the vector elements.

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Fergus Henderson wrote:
...
> do not.  The standard guarantees that reserve() will not invalidate
> iterators if the current capacity is greater than or equal to the
> requested capacity.  A shrink-to-fit operation would in general require
> moving the array (even realloc() does not guarantee that the pointer
> returned will be the same as the one passed in), which will cause
> iterators to be invalidated.

You're right - I got mixed up. That's what happens when I post from
work, when my copy of the standard is at home. The behaviour I was
incorrectly thinking about should be called expand-to-fit, and only
occurs when the reservation is larger than the current size. In that
case, while other behavior is allowed, I think that a decent quality
implementation should allocate exactly the reserved amount, and not one
element more, just in case the reserve() is meant as a hint that this is
the final size. It's another side of the same concept, but not directly
relevant to this thread.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]