Re: reduce c++ vector size

Discussion in 'C++' started by Rui Maciel, Jun 3, 2012.

  1. Rui Maciel

    Rui Maciel Guest

    sukhmeet wrote:

    > Hi,
    > I wrote a program in which I define a vector of some class objects.
    > Initially the vector has size and capacity both set to 0.
    > The moment I add an element to the vector the size is 1 and the capacity
    > jumps to 32 elements.
    > This is causing a huge overhead on my program since I need to use many
    > such vectors to load reference data with max capacity of 10 elements.
    > Is there a way to set the max vector capacity or resize it to fit the
    > vector to its size at any point of time.


    If your main concern is memory overhead then why not use a list instead of a
    vector?


    Rui Maciel
     
    Rui Maciel, Jun 3, 2012
    #1
    1. Advertising

  2. On 6/3/2012 2:28 PM, Rui Maciel wrote:
    > sukhmeet wrote:
    >
    >> Hi,
    >> I wrote a program in which I define a vector of some class objects.
    >> Initially the vector has size and capacity both set to 0.
    >> The moment I add an element to the vector the size is 1 and the capacity
    >> jumps to 32 elements.
    >> This is causing a huge overhead on my program since I need to use many
    >> such vectors to load reference data with max capacity of 10 elements.
    >> Is there a way to set the max vector capacity or resize it to fit the
    >> vector to its size at any point of time.

    >
    > If your main concern is memory overhead then why not use a list instead of a
    > vector?


    You're kidding, undoubtedly. A list with 10 elements will likely have
    more overhead than a vector with 10 elements.

    To the OP:

    Why not use std::array? Is it important to use as little memory as
    possible? What functionality from 'std::vector' do you need? Perhaps
    you need a special implementation that stores all elements in the same
    huge array and keeps track of all "vectors", yet doesn't actually create
    an object of type 'std::vector<yourclass>' unless you need it for
    something...

    V
    --
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jun 3, 2012
    #2
    1. Advertising

  3. Rui Maciel

    Rui Maciel Guest

    Victor Bazarov wrote:

    > You're kidding, undoubtedly. A list with 10 elements will likely have
    > more overhead than a vector with 10 elements.


    The OP said that the container will have at most 10 elements, which means
    that each container will contain any number of elements between zero and 10.
    If memory is at a premium then it makes sense to allocate only the memory
    which is really used, and allocate more memory only when it is trully
    needed.

    In this case, both std::vector and std::array pre-allocate enough memory to
    reserve a certain capacity. If you are in a position where your memory
    needs are so demanding that pre-allocation becomes a serious problem, being
    forced to pre-allocate enough memory for 10 elements when you only need to
    use a fraction of that capacity can also represent a serious problem.

    Hence, in this case std::list might be a far better option than std::vector
    or std::array.


    Rui Maciel
     
    Rui Maciel, Jun 3, 2012
    #3
  4. Rui Maciel <> wrote:
    > If memory is at a premium then it makes sense to allocate only the memory
    > which is really used, and allocate more memory only when it is trully
    > needed.


    In that case using a list is a really poor choice due to the overhead that
    list elements have (two pointers plus whatever the memory allocator needs
    for book-keeping an allocated block of memory, which is typically at least
    the size of one or two pointers).

    A list of 10 elements might well take more memory than a vector or 32
    elements.
     
    Juha Nieminen, Jun 4, 2012
    #4
  5. Rui Maciel

    Rui Maciel Guest

    Juha Nieminen wrote:

    > In that case using a list is a really poor choice due to the overhead that
    > list elements have (two pointers plus whatever the memory allocator needs
    > for book-keeping an allocated block of memory, which is typically at least
    > the size of one or two pointers).
    >
    > A list of 10 elements might well take more memory than a vector or 32
    > elements.


    In order for a 10 element list to take more memory than a vector with a 32-
    element capacity, the overhead for each element in a list should be more
    than twice the size of each element.

    This means that if we assume that the overhead for each list element is two
    pointers then, for your assertion to hold, the size of each element must be
    at most about the size of a single pointer. Do you believe this is a
    reasonable assumption?

    In addition, if we consider that a list imposes an overhead of two pointers
    per element then a list container uses less memory if it stores at most
    between 10 and 32 elements, depending on how much memory each element
    occupies. If you need to store at most 10 elements then, considering this,
    how exactly do you believe that using a list "a really poor choice"?


    Rui Maciel
     
    Rui Maciel, Jun 4, 2012
    #5
  6. Rui Maciel

    Luca Risolia Guest

    On 04/06/2012 09:17, Juha Nieminen wrote:
    > Rui Maciel<> wrote:
    >> If memory is at a premium then it makes sense to allocate only the memory
    >> which is really used, and allocate more memory only when it is trully
    >> needed.

    >
    > In that case using a list is a really poor choice due to the overhead that
    > list elements have (two pointers plus whatever the memory allocator needs
    > for book-keeping an allocated block of memory, which is typically at least
    > the size of one or two pointers).
    >
    > A list of 10 elements might well take more memory than a vector or 32
    > elements.


    It depends on the size of the elements and, as you said, on the
    allocator used. I think simple measurements may tell us the truth.
     
    Luca Risolia, Jun 4, 2012
    #6
  7. Rui Maciel

    Rui Maciel Guest

    sukhmeet wrote:

    > Hi Guys,
    > Thanks for your response.As of now I can not change to list since this
    > (use of vector ) is already implemented in my company's core product.
    > Changing this will have huge impact of all code base.
    > Resize or reserve didn't help either. The problem here is that the program
    > is taking 3 times more memory than needed at any point of time.


    If you rely on a container which pre-allocates memory then naturally your
    program will always take more memory than the amount which is actually
    needed.


    Rui Maciel
     
    Rui Maciel, Jun 4, 2012
    #7
  8. Rui Maciel <> wrote:
    > This means that if we assume that the overhead for each list element is two
    > pointers


    The overhead will be larger because each element is allocated
    separately, and the standard memorly allocator needs extra space for
    each allocated block of memory.

    (For example in a 32-bit linux system the minimum allocation size is
    16 bytes, and every allocation over that will be divisible by 8, with a
    minimum of 4 bytes in addition to what was explicitly requested. I imagine
    that in 64-bit linux this is larger.)
     
    Juha Nieminen, Jun 4, 2012
    #8
  9. Rui Maciel

    Rui Maciel Guest

    Juha Nieminen wrote:

    > The overhead will be larger because each element is allocated
    > separately, and the standard memorly allocator needs extra space for
    > each allocated block of memory.
    >
    > (For example in a 32-bit linux system the minimum allocation size is
    > 16 bytes, and every allocation over that will be divisible by 8, with a
    > minimum of 4 bytes in addition to what was explicitly requested. I imagine
    > that in 64-bit linux this is larger.)


    Even if the overhead is larger, your assumption still doesn't make sense. A
    10-element std::list only starts to require more memory than a 32-element
    std::vector if the overhead of storing each element in a std::list is over
    twice the size of each element.

    This means that if the minimum allocation size is 16 bytes, if an element is
    16 bytes then, for your assertion to hold, the overhead for each element in
    a container must be over 34 bytes. And if the element takes more memory
    than that then, for your assertion to hold, the overhead must increase in a
    directly proportional way.

    And this is for the corner case where the std::list is maxed out, which is a
    corner case.

    So, suffice to say, your assertion is false.


    Rui Maciel
     
    Rui Maciel, Jun 4, 2012
    #9
  10. Rui Maciel

    Luca Risolia Guest

    On 04/06/2012 18:47, Rui Maciel wrote:
    > Juha Nieminen wrote:
    >
    >> The overhead will be larger because each element is allocated
    >> separately, and the standard memorly allocator needs extra space for
    >> each allocated block of memory.
    >>
    >> (For example in a 32-bit linux system the minimum allocation size is
    >> 16 bytes, and every allocation over that will be divisible by 8, with a
    >> minimum of 4 bytes in addition to what was explicitly requested. I imagine
    >> that in 64-bit linux this is larger.)

    >
    > Even if the overhead is larger, your assumption still doesn't make sense. A
    > 10-element std::list only starts to require more memory than a 32-element
    > std::vector if the overhead of storing each element in a std::list is over
    > twice the size of each element.
    >
    > This means that if the minimum allocation size is 16 bytes, if an element is
    > 16 bytes then, for your assertion to hold, the overhead for each element in
    > a container must be over 34 bytes. And if the element takes more memory
    > than that then, for your assertion to hold, the overhead must increase in a
    > directly proportional way.
    >
    > And this is for the corner case where the std::list is maxed out, which is a
    > corner case.
    >
    > So, suffice to say, your assertion is false.


    I have made some measurements on my default implementation:

    Total memory used by std::vector<int>(32) is 152 bytes, where:
    sizeof(int) is 4 bytes
    sizeof(vectorInstance) is 24 bytes
    size == capacity (asserted)

    Total memory used by std::list<int>(10) is 256 bytes, where:
    sizeof(int) is 4 bytes
    sizeof(listInstance) is 16 bytes

    std::vector<int>(32) wins.

    On the other hand:

    Total memory used by std::vector<unsigned long>(32) is 280 bytes, where:
    sizeof(unsigned long) is 8 bytes
    sizeof(vectorInstance) is 24 bytes
    size == capacity (asserted)

    Total memory used by std::list<unsigned long>(10) is 256 bytes, where:
    sizeof(unsigned long) is 8 bytes
    sizeof(listInstance) is 16 bytes

    std::list<unsigned long>(10) wins.
     
    Luca Risolia, Jun 4, 2012
    #10
  11. Rui Maciel <> wrote:
    > Juha Nieminen wrote:
    >> (For example in a 32-bit linux system the minimum allocation size is
    >> 16 bytes, and every allocation over that will be divisible by 8, with a
    >> minimum of 4 bytes in addition to what was explicitly requested. I imagine
    >> that in 64-bit linux this is larger.)

    >
    > Even if the overhead is larger, your assumption still doesn't make sense. A
    > 10-element std::list only starts to require more memory than a 32-element
    > std::vector if the overhead of storing each element in a std::list is over
    > twice the size of each element.


    If the size of the element is, for example, that of one int, then on a
    32-bit Linux system each vector element will take 4 bytes, while each
    list element takes 16 bytes of memory (each list element will have the
    size of the int plus two pointers, ie. 12 bytes, and as said, the minimum
    allocation size using the default allocator is 16 bytes).

    The memory allocation overhead will apply to the vector as well, of course,
    but it applies only once because the vector has only one single block of
    memory allocated. Hence the memory taken by the vector will be 32 times 4
    plus 8 (because, as said, allocation sizes in Linux are always the requested
    amount plus 4, rounded up to the nearest multiple of 8), which would be
    136 bytes.

    A std::list of 10 elements, on the other hand, takes 160 bytes of memory in
    total (because, as said, each element takes 16 bytes). And this assuming no
    memory fragmentation (so that each allocated block is neatly one after
    another in memory).

    Last time I checked 160 is larger than 136. Hence a vector of 32 elements
    *can* take less memory than a list of 10 elements.

    (Also, the memory taken by the list can potentially be even larger if
    there's memory fragmentation so the allocator cannot place all those
    blocks neatly one after another in memory.)
     
    Juha Nieminen, Jun 5, 2012
    #11
    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. Replies:
    8
    Views:
    1,998
    Csaba
    Feb 18, 2006
  2. Alain Ketterlin

    Re: reduce c++ vector size

    Alain Ketterlin, Jun 3, 2012, in forum: C++
    Replies:
    0
    Views:
    343
    Alain Ketterlin
    Jun 3, 2012
  3. Ian Collins

    Re: reduce c++ vector size

    Ian Collins, Jun 4, 2012, in forum: C++
    Replies:
    0
    Views:
    354
    Ian Collins
    Jun 4, 2012
  4. Fraser Ross

    Re: reduce c++ vector size

    Fraser Ross, Jun 4, 2012, in forum: C++
    Replies:
    0
    Views:
    391
    Fraser Ross
    Jun 4, 2012
  5. Replies:
    2
    Views:
    104
    Öö Tiib
    Mar 10, 2014
Loading...

Share This Page