Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Re: reduce c++ vector size

Reply
Thread Tools

Re: reduce c++ vector size

 
 
Rui Maciel
Guest
Posts: n/a
 
      06-03-2012
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
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      06-03-2012
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
 
Reply With Quote
 
 
 
 
Rui Maciel
Guest
Posts: n/a
 
      06-03-2012
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
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      06-04-2012
Rui Maciel <(E-Mail Removed)> 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.
 
Reply With Quote
 
Rui Maciel
Guest
Posts: n/a
 
      06-04-2012
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
 
Reply With Quote
 
Luca Risolia
Guest
Posts: n/a
 
      06-04-2012
On 04/06/2012 09:17, Juha Nieminen wrote:
> Rui Maciel<(E-Mail Removed)> 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.
 
Reply With Quote
 
Rui Maciel
Guest
Posts: n/a
 
      06-04-2012
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
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      06-04-2012
Rui Maciel <(E-Mail Removed)> 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.)
 
Reply With Quote
 
Rui Maciel
Guest
Posts: n/a
 
      06-04-2012
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

 
Reply With Quote
 
Luca Risolia
Guest
Posts: n/a
 
      06-04-2012
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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: reduce c++ vector size Fraser Ross C++ 0 06-04-2012 10:45 AM
Re: reduce c++ vector size Ian Collins C++ 0 06-04-2012 08:47 AM
Re: reduce c++ vector size Alain Ketterlin C++ 0 06-03-2012 05:52 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
better to compress the jpeg or reduce resolution or reduce pixel size? Mr.Will Digital Photography 8 10-08-2004 03:16 PM



Advertisments