Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

reduce c++ vector size

103 views
Skip to first unread message

sukhmeet

unread,
Jun 3, 2012, 1:34:19 PM6/3/12
to
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.

--
sukhmeet

--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---

Paavo Helde

unread,
Jun 3, 2012, 1:46:46 PM6/3/12
to
sukhmeet <suk...@gmail.com> wrote in
news:jqg76r$2r1b$1...@adenine.netfront.net:

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

Calling vector::reserve(10) might work. It is not guaranteed though that
it allocates memory for 10 elements only, so you have to test this with all
your supported platforms and compiler versions.

hth
Paavo

Alain Ketterlin

unread,
Jun 3, 2012, 1:52:08 PM6/3/12
to
sukhmeet <suk...@gmail.com> writes:

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

Look up reserve() or resize() in class vector.

-- Alain.

Rui Maciel

unread,
Jun 3, 2012, 2:28:09 PM6/3/12
to
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

Victor Bazarov

unread,
Jun 3, 2012, 3:49:04 PM6/3/12
to
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

Rui Maciel

unread,
Jun 3, 2012, 4:33:42 PM6/3/12
to
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

sukhmeet

unread,
Jun 3, 2012, 9:18:34 PM6/3/12
to
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.

Paavo Helde

unread,
Jun 4, 2012, 1:21:26 AM6/4/12
to
sukhmeet <suk...@gmail.com> wrote in
news:jqh2da$dam$1...@adenine.netfront.net:

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

It's a bit hard to believe. Reserve() is working fine with MSVC and g++,
at least for avoiding allocation of 32 entries instead of 10. Probably
you are using it wrong.

Coming to think of that, your initial claim that pushing an element into
an empty std::vector jumps its capacity to 32 is also a bit hard to
believe. What C++ implementation is doing this?

If you wan't to get rid of any excess reserved memory at any time point,
you can always construct a new vector of the right size, once you know
it. This will cost an extra copy of the data though.

#include <iostream>
#include <vector>

int main() {

std::vector<int> v;
v.reserve(10);
for(int i=0; i<3; ++i) {
v.push_back(i);
}
std::cout << "size==" << v.size() <<
", capacity==" << v.capacity() << "\n";


std::vector<int> w(v.begin(), v.end());
v.swap(w);

std::cout << "size==" << v.size() << ",
capacity==" << v.capacity() << "\n";

}

Output:
size==3, capacity==10
size==3, capacity==3





Juha Nieminen

unread,
Jun 4, 2012, 3:17:58 AM6/4/12
to
Rui Maciel <rui.m...@gmail.com> 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.

bartek szurgot

unread,
Jun 4, 2012, 4:02:12 AM6/4/12
to
On 06/03/2012 07:34 PM, 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.

hi,

the best way is to use vector::reserve(). if it is not an option, C++11
has vector::shrink_to_fit() method. it is very convenient, though it is
not guaranteed to resize a container; it does so on gcc-4.[567], so
check your compiler.

--
pozdrawiam serdecznie / best regards,
bartek szurgot
/* http://www.baszerr.eu */

bartek szurgot

unread,
Jun 4, 2012, 4:06:27 AM6/4/12
to
On 06/04/2012 09:17 AM, Juha Nieminen wrote:
> A list of 10 elements might well take more memory than a vector or 32
> elements.

for the list not only the memory footprint will be much larger, but
accessing elements will be WAY slower too (compared to the vector).

Rui Maciel

unread,
Jun 4, 2012, 4:43:00 AM6/4/12
to
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

Ian Collins

unread,
Jun 4, 2012, 4:47:23 AM6/4/12
to
On 06/ 4/12 05:34 AM, 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.

You could store pointers to the objects so the "waste" won't be so big.

--
Ian Collins

Luca Risolia

unread,
Jun 4, 2012, 5:33:03 AM6/4/12
to
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.

Fraser Ross

unread,
Jun 4, 2012, 6:45:07 AM6/4/12
to
vector<A> a;

fill a.

vector<A>(a).swap(a); I have taken this from a well known book.

Fraser.


Rui Maciel

unread,
Jun 4, 2012, 6:54:57 AM6/4/12
to
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

Juha Nieminen

unread,
Jun 4, 2012, 11:27:52 AM6/4/12
to
Rui Maciel <rui.m...@gmail.com> 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.)

Andy Champ

unread,
Jun 4, 2012, 11:38:57 AM6/4/12
to
In his case the overhead for the vector is 22 times the size of the
object stored in the vector. The overhead for the list is 10 times (2
pointers plus a memory allocation overhead).

Which is smaller will depend on the objects stored.

Sukhmeet,

I too am very surprised that reserve didn't work. You could try
constructing it with 10 dummy elements, then resize-ing it back to zero
before using it (or overwriting the elements)

Andy

Rui Maciel

unread,
Jun 4, 2012, 12:47:49 PM6/4/12
to
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

sukhmeet

unread,
Jun 4, 2012, 12:56:50 PM6/4/12
to
Hi Guys,
Thanks all for your responses. I found a workaround to do this at compile
time.
The compiler I use is aCC ( hp-ux ). It worked by defining below in my
program. I am able to downsize my program considerably.
#define _RWSTD_MINIMUM_NEW_CAPACITY 10

Christian Gollwitzer

unread,
Jun 4, 2012, 1:34:22 PM6/4/12
to
Am 04.06.12 07:21, schrieb Paavo Helde:
> sukhmeet<suk...@gmail.com> wrote in
> news:jqh2da$dam$1...@adenine.netfront.net:
>
>> 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.
>
> It's a bit hard to believe. Reserve() is working fine with MSVC and g++,
> at least for avoiding allocation of 32 entries instead of 10. Probably
> you are using it wrong.
>
> Coming to think of that, your initial claim that pushing an element into
> an empty std::vector jumps its capacity to 32 is also a bit hard to
> believe. What C++ implementation is doing this?

He might be talking about vector<bool> ... in this case not he doesn't
have simple options to improve on that, besides using one big
vector<bool> and doing index arithmetics.

Christian

Luca Risolia

unread,
Jun 4, 2012, 1:58:55 PM6/4/12
to
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.

Scott Lurndal

unread,
Jun 4, 2012, 3:00:53 PM6/4/12
to
bartek szurgot <ba...@no.spam> writes:
>On 06/03/2012 07:34 PM, 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.
>
>hi,
>
>the best way is to use vector::reserve(). if it is not an option, C++11
>has vector::shrink_to_fit() method. it is very convenient, though it is
>not guaranteed to resize a container; it does so on gcc-4.[567], so
>check your compiler.
>

It's not really up to the compiler. It's up to the run-time library and
the operating system to reduce the physical memory footprint of an application. Once
memory has been allocated to the heap, it is quite difficult to
give it back to the OS (unix heaps allocated with sbrk(2) can only return
memory to the OS if the unused memory is (a) contiguous and (b) at the
end of the heap). If using mmap(2) to allocate heap, the amount returned
must be page-aligned and multiples of a page and must not contain other
allocations (which is common in a heap implementations).

If the application doesn't access whole pages in the heap, and the system is
under memory pressure, the OS will move the unaccessed pages to backing storage
and allow another application to use the physical memory pages, but this
is independent of any standard library interface such as vector::shrink_to_fit.

At best, ::shrink_to_fit is a hint to the library which may result in a
spurious copy as it mallocs a smaller chunk, copies it, and free's the
larger (which still remains as part of the process heap).

If std::vector uses operator::new to allocate, then all other callers
of new will get elements from the same heap, which will make it difficult
to find sufficient contiguous regions of heap to return any storage to the system.

Far better not to allocate too much in the first place, or to control large
allocations by explicitly using ::mmap(2) (or the windows equivalent) in a
customer operator::new.

scott

Juha Nieminen

unread,
Jun 5, 2012, 1:33:54 AM6/5/12
to
Rui Maciel <rui.m...@gmail.com> 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.)

Andy Champ

unread,
Jun 5, 2012, 3:46:57 PM6/5/12
to
On 04/06/2012 17:56, sukhmeet wrote:
>
> Hi Guys,
> Thanks all for your responses. I found a workaround to do this at compile
> time.
> The compiler I use is aCC ( hp-ux ). It worked by defining below in my
> program. I am able to downsize my program considerably.
> #define _RWSTD_MINIMUM_NEW_CAPACITY 10

Thanks for letting us know the solution. It may help someone else one day.

Andy

bartek szurgot

unread,
Jun 6, 2012, 10:17:52 AM6/6/12
to
i've made a though-shortcut, when saying it "depends on the compiler",
since quite often nowadays you get standard library as a part of the
compiler environment. to be precise, it is of course the library's
implementation to handle vector's shrink_to_fit() method.

when talking about OS-side of memory handling implementation, many
things can happen, just to mention lazy allocation mechanism. custom
allocators can be used in user's program as well. i believe this was not
the scope of the original question, though.
0 new messages