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

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

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


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: More than 2, but less than 3 GiB per process memory?
    ... when it allocates it it only allocates address space. ... > storage only when the storage is actually used. ... I get up to 3058 M; that on a system with 8 GiB swap and on a system ... overcommitting since that much virtual memory is definitely not available. ...
    (Debian-User)
  • Re: Author of Visual C++ 2005 STL ???
    ... In VS6, release, each mallocconsumes 40 bytes ... smaller than 8 bytes, the storage is lost. ... had 100 bytes of free storage I could get 100 allocations? ... by other memory allocations. ...
    (microsoft.public.vc.mfc)
  • Re: REGION=0M and LSQA
    ... At the time, memory was very expensive, and we ... remaining storage and always issued a return code zero. ... programs actually worked in production, ... all of the resources used by the job up until that point ...
    (bit.listserv.ibm-main)
  • Re: Statement on Schildt submitted to wikipedia today
    ... storage is allocated from free ... free memory that is used for dynamic allocation is called the heap. ... storage area, and the stack. ...
    (comp.lang.c.moderated)
  • Re: main memory vs. storage memory on 128 meg samsung 1 730 ppc phone
    ... This type is commonly used in WM devices (and storage cards). ... OS would copy itself to RAM taking out some of it. ... > How fast is the main memory compared to the flash ram memory in ... >> Fake storage card composed of flash is relatively slow, ...
    (microsoft.public.dotnet.framework.compactframework)