Re: Author of Visual C++ 2005 STL ???

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance


"Joseph M. Newcomer" <newcomer@xxxxxxxxxxxx> wrote in
message news:5m2ft497h1rmf2e2actqe17926mcdmhpaq@xxxxxxxxxx
A single byte requires many bytes of storage to hold it,
that is
malloc(1)
or
new BYTE

will, each time, consume some large chunk of bytes. Why?
Because there is a "header
block" for the storage, and the allocator never allocates
less than 8 bytes (it actually
allocates in quanta of 8 bytes).

Running under XP:
In VS6, debug, each malloc(1) consumes 72 bytes
In VS6, release, each malloc(1) consumes 40 bytes

Running under Vista:
In VS2008, debug, each malloc(1) consumes 64 bytes
In VS2008, release, each malloc(1) consumes 32 bytes

Note that "too small to use" means "smaller than the
typical allocation I do". So if you
have a lot of 64-byte holes in your VS2008 debug heap, but
rarely allocate anything
smaller than 8 bytes, the storage is lost. This is "heap
fragmentation"

Did you think that an allocation of 1 byte actually used
only 1 byte of storage? So if I
had 100 bytes of free storage I could get 100 allocations?
Depending on my compilation
mode and version of VS, I'll get somewhere between 1 and 3
1-byte allocations out of a 100
byte block.
joe

That seems pretty wasteful, but, perhaps this degree of
overhead is not easy to circumvent. In any case the original
author's reply must have referred to memory holes that are
wasted in terms of re-allocating space for the original
std::vector. Certainly these holes could be effectively used
by other memory allocations.



On Sat, 4 Apr 2009 09:03:39 -0500, "Peter Olcott"
<NoSpam@xxxxxxxxxxxxx> wrote:


"Bo Persson" <bop@xxxxxx> wrote in message
news:73msp5Fvuce0U1@xxxxxxxxxxxxxxxxxxxxx
Peter Olcott wrote:
"Doug Harrison [MVP]" <dsh@xxxxxxxx> wrote in message
news:ep69t41qd0gplg4nu7fr5eeidk3u4kpfs2@xxxxxxxxxx
On Wed, 1 Apr 2009 20:28:23 -0500, "Peter Olcott"
<NoSpam@xxxxxxxxxxxxx>
wrote:

I wish that there was a way that I could
change the memory growth factor to 2.0.

It's easy to write non-member functions that achieve
this
using the size(),
capacity(), and reserve() member functions. However, I
would need to be
convinced there is a significant difference between
1.5
and 2 in this
context. We're talking 1.7*log(N) reallocation events
vs.
log(N) events for
1.5 vs. 2, respectively, while the real comparison is
against N/M, with M
being the linear growth factor and N the final size.
IOW,
with 1.5, we're
still talking about a series of reallocations numbered
in
the tens vs. the
potentially many thousands that can easily occur with
the
linear policy.
Also, if you assume half of the last size increase is
wasted, the memory
savings of 1.5 vs. 2 can be substantial. So, I can
understand the argument
that "1.5 is good enough for everything, a good
compromise
between
efficiency and memory wastage."

--
Doug Harrison
Visual C++ MVP

It is not the number of re-allocations that is
significant
it is the number of copies that must be made that
determines
the additional cost of a memory growth factor of 1.5 as
opposed to 2.0.

best case memory growth factor 1.5 ---> 2 * N
worst case memory growth factor 1.5 ---> 3 * N

best case memory growth factor 2.0 ---> 1 * N
worst case memory growth factor 2.0 ---> 2 * N

average case memory growth factor 1.5 ---> 2.50 * N
average case memory growth factor 2.0 ---> 1.50 * N

Thus the memory growth factor costs an average of 2/3
more
time to cut wasted memory in half.
So the choice between 1.5 and 2.0 depends upon the
relative
importance of saving space versus saving time.
It would be nice if MemoryGrowthFactor was a template
parameter.

If "wasting" memory isn't a problem, you can reduce the
copying by initially doing a
vec.reserve(very_large_number).


There is another reason for chosing the factor 1.5 - if
the vector is alone, and grows by 2.0, it will leave a
hole behind itself on the heap that is always just too
small to be reused.


I don't see this. If a single byte variable is allocated
there will always be plenty of room in any possible hole
that anything could ever create to allocate this single
byte.



Bo Persson





Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm


.

Relevant Pages

  • Re: Author of Visual C++ 2005 STL ???
    ... A single byte requires many bytes of storage to hold it, ... allocates in quanta of 8 bytes). ... In VS6, release, each mallocconsumes 40 bytes ... change the memory growth factor to 2.0. ...
    (microsoft.public.vc.mfc)
  • Re: automatic vs allocated attempts
    ... allocated storage? ... Why is it ok to code in C as if allocations of automatic ... allocations of allocated storage will never fail, ... storage would be used for large arrays and whole blocks of memory. ...
    (comp.lang.c)
  • Re: Is MFC reusing memory?
    ... Regarding the indication the memory is not freed: ... in the debug version. ... We are talking about allocations in C++, ... Read my essay on storage allocation. ...
    (microsoft.public.vc.mfc)
  • Re: automatic vs allocated attempts
    ... allocations of allocated storage will never fail, ... malloc can potentially give you access to the full memory resources ... whereas stack space is ``artificially'' limited. ...
    (comp.lang.c)
  • RE: 2003 SBS stalling randomly
    ... A memory leak occurs in an application using the Volume Shadow Copy Service ... Poolmon displays data that the ... The data is grouped by pool allocation tag. ... Press P twice to display allocations from only the paged pool. ...
    (microsoft.public.windows.server.sbs)