stl_vector allocation

[Afra Zomorodian]

Hi,

I have not coded in C++ for some years, but generic programming is
bringing me back to it. Unfortunately, some of strange behavior is still
disconcerting. I'd like to know what my language does, so I appreciate
any help regarding this from C++ gods and goddesses...

I have the following riddle regarding STL vector's allocation policy. In
the following code, I'm allocating a vector of size 1:

#include<vector>
int main() {
std::vector<int> v(1);
return 0;
}

I compile this with g++ (gcc version 3.2.2.)

Now, running valgrind (latest version) on it, I get that (snip):

still reachable: 320 bytes in 1 blocks.

In the backtrace, you can see that it's a 'new' from stl_vector. So, I
assume it's doing some sort of specialized allocation for future. I can
show this to be true by allocating any number of vectors of size 1, and I
always get 320. In fact, the later vectors can be of larger size.

Changing the size of the vector to 10 instead of 1, I get:

still reachable: 1600 bytes in 1 blocks.

OK, this is strange, but still, maybe explainable. Let's change the size
of the vector to 100. Running valgrind, I get (and here's a bigger snip):

==14455== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 19 from 1)
==14455== malloc/free: in use at exit: 0 bytes in 0 blocks.
==14455== malloc/free: 1 allocs, 1 frees, 400 bytes allocated.
==14455== For counts of detected errors, rerun with: -v
==14455== No malloc'd blocks -- no leaks are possible.

So, somehow, the policy changes. It's all on the stack and now, I
don't have any "reachable" allocation left.

I'd appreciate if anyone can explain how the vector allocation results in
this behavior.

Thank you. Please CC your post to me.

Afra

[Mike Wahler]

"Afra Zomorodian" <af**@cs.stanford.edu> wrote in message
news:Pi**************************************@xeno n.Stanford.EDU...

Hi,

I have not coded in C++ for some years, but generic programming is
bringing me back to it. Unfortunately, some of strange behavior is still
disconcerting. I'd like to know what my language does, so I appreciate
any help regarding this from C++ gods and goddesses...

I have the following riddle regarding STL vector's allocation policy. In
the following code, I'm allocating a vector of size 1:

#include<vector>
int main() {
std::vector<int> v(1);
return 0;
}

I compile this with g++ (gcc version 3.2.2.)

Now, running valgrind (latest version) on it, I get that (snip):

still reachable: 320 bytes in 1 blocks.

In the backtrace, you can see that it's a 'new' from stl_vector. So, I
assume it's doing some sort of specialized allocation for future. I can
show this to be true by allocating any number of vectors of size 1, and I
always get 320. In fact, the later vectors can be of larger size.

Changing the size of the vector to 10 instead of 1, I get:

still reachable: 1600 bytes in 1 blocks.

OK, this is strange, but still, maybe explainable. Let's change the size
of the vector to 100. Running valgrind, I get (and here's a bigger snip):

==14455== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 19 from 1)
==14455== malloc/free: in use at exit: 0 bytes in 0 blocks.
==14455== malloc/free: 1 allocs, 1 frees, 400 bytes allocated.
==14455== For counts of detected errors, rerun with: -v
==14455== No malloc'd blocks -- no leaks are possible.

So, somehow, the policy changes. It's all on the stack and now, I
don't have any "reachable" allocation left.

I'd appreciate if anyone can explain how the vector allocation results in
this behavior.

Most if not all implementations of std::vector do indeed allocate more
space than is immediately needed. This is in the interest of performance.
Exactly how much is initially allocated and subsequently allocated when
more memory is needed is left to the implementation. All the performance
requirements made by the standard are formulaic, not specified in actual
time or space.

-Mike

[Afra Zomorodian]

Hi again,

Of course, I understand the difference between "standard" and
"implementation".

So, let me be more precise: Can someone explain the behavior of _this_
implementation?

The question is still valid as this implementation is widely used. I'd
like to know the rationale behind the strange behavior.

Afra

[Mike Wahler]

"Afra Zomorodian" <af**@cs.stanford.edu> wrote in message
news:Pi**************************************@xeno n.Stanford.EDU...

Hi again,

Of course, I understand the difference between "standard" and
"implementation".

So, let me be more precise: Can someone explain the behavior of _this_
implementation?
Someone probably can, but not here. Here we only discuss
standard C++, not specific implementations.

The question is still valid
Not valid for comp.lang.c++
as this implementation is widely used.
That's not what dictates topicality here.
I'd
like to know the rationale behind the strange behavior.

Try a newsgroup, mailing list, web site, etc. dedicated
to your implementation.

Purpose of comp.lang.c++ :
http://www.slack.net/~shiva/welcome.txt

-Mike

[Artie Gold]

Afra Zomorodian wrote:

Hi again,

Of course, I understand the difference between "standard" and
"implementation".

So, let me be more precise: Can someone explain the behavior of _this_
implementation?

The question is still valid as this implementation is widely used. I'd
like to know the rationale behind the strange behavior.

Afra

Though the implementation is indeed off topic, there's a simple
solution: Read. The. Code.

HTH,
--ag

--
Artie Gold -- Austin, Texas
http://it-matters.blogspot.com (new post 12/5)
http://www.cafepress.com/goldsays