Releasing storage of a vector

Discussion in 'C++' started by jacob navia, Apr 30, 2012.

  1. jacob navia

    jacob navia Guest

    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
    jacob navia, Apr 30, 2012
    #1
    1. Advertising

  2. jacob navia

    Miles Bader Guest

    jacob navia <> writes:
    > 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

    --
    "Most attacks seem to take place at night, during a rainstorm, uphill,
    where four map sheets join." -- Anon. British Officer in WW I
    Miles Bader, Apr 30, 2012
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    jacob navia, Apr 30, 2012
    #3
  4. jacob navia

    Nobody Guest

    On Mon, 30 Apr 2012 21:55:28 +0200, jacob navia wrote:

    > 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.
    Nobody, May 1, 2012
    #4
  5. jacob navia

    jacob navia Guest

    Le 01/05/12 06:31, Nobody a écrit :
    > On Mon, 30 Apr 2012 21:55:28 +0200, jacob navia wrote:
    >
    >> 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.
    >

    Ahhh it is only a *request* ???

    It looked official enough for me!

    Thanks for this clarification. I thought it was in the standard already.
    jacob navia, May 1, 2012
    #5
  6. On 30.04.12 21.55, jacob navia wrote:
    > 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
    Marcel Müller, May 1, 2012
    #6
  7. jacob navia

    Nobody Guest

    On Tue, 01 May 2012 08:46:11 +0200, jacob navia wrote:

    >> 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.


    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.
    Nobody, May 1, 2012
    #7
  8. jacob navia

    Miles Bader Guest

    jacob navia <> writes:
    >>> 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.
    >>

    > 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

    --
    We have met the enemy, and he is us. -- Pogo
    Miles Bader, May 2, 2012
    #8
  9. jacob navia

    jacob navia Guest

    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
    jacob navia, May 2, 2012
    #9
  10. jacob navia

    Ian Collins Guest

    On 05/ 2/12 08:46 PM, jacob navia wrote:
    > 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++.


    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"

    --
    Ian Collins
    Ian Collins, May 2, 2012
    #10
  11. jacob navia

    Jorgen Grahn Guest

    On Tue, 2012-05-01, Miles Bader wrote:
    > jacob navia <> writes:
    >>>> 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.
    >>>

    >> 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


    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 <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 2, 2012
    #11
  12. jacob navia

    Jorgen Grahn Guest

    On Wed, 2012-05-02, jacob navia wrote:
    > 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++.


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

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 2, 2012
    #12
  13. jacob navia

    jacob navia Guest

    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.
    jacob navia, May 2, 2012
    #13
  14. jacob navia

    Miles Bader Guest

    Jorgen Grahn <> writes:
    >> 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?


    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

    --
    Conservative, n. A statesman enamored of existing evils, as opposed to a
    Liberal, who wants to replace them with new ones.
    Miles Bader, May 2, 2012
    #14
  15. jacob navia

    Jorgen Grahn Guest

    On Wed, 2012-05-02, Miles Bader wrote:
    > Jorgen Grahn <> writes:
    >>> 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?

    >
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 2, 2012
    #15
  16. jacob navia

    Miles Bader Guest

    Jorgen Grahn <> writes:
    >>> 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.

    >
    > 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

    --
    Philosophy, n. A route of many roads leading from nowhere to nothing.
    Miles Bader, May 3, 2012
    #16
  17. jacob navia

    Miles Bader Guest

    Gareth Owen <> writes:
    >> 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

    --
    Advice, n. The smallest current coin.
    Miles Bader, May 3, 2012
    #17
  18. jacob navia

    Nobody Guest

    On Wed, 02 May 2012 08:57:52 +0900, Miles Bader wrote:

    > [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>::pointer and allocator<T>::reference
    cannot be other than T* and T& respectively.
    Nobody, May 3, 2012
    #18
  19. jacob navia

    Jorgen Grahn Guest

    On Thu, 2012-05-03, Miles Bader wrote:
    > Jorgen Grahn <> writes:
    >>>> 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.

    >>
    >> 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.


    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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 3, 2012
    #19
  20. jacob navia

    Miles Bader Guest

    Jorgen Grahn <> writes:
    >>> 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.

    >
    > 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

    --
    `The suburb is an obsolete and contradictory form of human settlement'
    Miles Bader, May 3, 2012
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    23,789
  2. sarathy
    Replies:
    2
    Views:
    661
    sarathy
    Jul 17, 2006
  3. Replies:
    8
    Views:
    1,915
    Csaba
    Feb 18, 2006
  4. Javier
    Replies:
    2
    Views:
    561
    James Kanze
    Sep 4, 2007
  5. Rushikesh Joshi
    Replies:
    0
    Views:
    359
    Rushikesh Joshi
    Jul 10, 2004
Loading...

Share This Page