Re: sizeof([ALLOCATED MEMORY])

In article <445a47c0$0$29357$88260bb3@xxxxxxxxxxxxxxxxx>,
"Stephen Sprunk" <stephen@xxxxxxxxxx> wrote:

"Howard Hinnant" <howard.hinnant@xxxxxxxxx> wrote in message
news:howard.hinnant-EED144.10183104052006@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
No matter what the growth strategy for capacity, its existence is a
major motivation for finding out the amount of memory actually
allocated. create_array_short(N) may request only N*sizeof(short)
bytes, but may receive slightly more than that (for alignment purposes
or whatever). If create_array_short(N) had some way to find out how
much memory it actually received, then it makes perfect sense to set
capacity to size_received/sizeof(short) instead of to N. It makes for
higher performing code in the average case.

You're over-optimizing here. If malloc() returns more memory than you asked
for, when you expand the array, you'll get access to it. On average, you'll
perform the same number of realloc()s with or without this optimization
unless you're expanding by a very small amount each time, in which case a
large fraction of your realloc()s will be no-ops for the implementation.

Let's go through a specific example. I'm going to assume the struct I
showed before:

struct array_of_short
{
short* data;
size_t size;
size_t capacity;
};

Let's say that size == capacity == 100. Now for some reason my
algorithm decides it needs 2 more shorts. What do I do?

Today I call realloc similar to:

data = realloc(data, 3*capacity/2 * sizeof(short));

I.e. I up the capacity by 50% (or whatever growth factor you want to
use). Now under the hood lets say (and this is quite reasonable) that
the heap had already allocated 4 more bytes to data, and had another 64
bytes beyond that which it could have expanded that chunk in place. But
because my code is ignorant of the current heap structure in the
neighborhood of my pointer, the best thing I know to do is blindly ask
for a realloc expanding to 50 more shorts (assuming a 2 byte short for
this example). That in turn will trigger the heap to relocate my 200
byte array to another location.

If I had more access to the current heap structure, I could have known
that there was already room for two extra shorts allocated to me. I
could've avoided a call to realloc altogether.

Continuing along with this example: let's say instead of 2 more shorts,
my algorithm actually needed 10 more shorts. Here's my choices:

1. realloc for 10 more shorts.
2. realloc for a 50% bigger capacity.

Choice 1 risks the poor efficiency of an incremental growth strategy
(known performance problem).

Choice 2 completely wastes the 68 bytes that were sitting beyond my 200
byte buffer but had no way to find out about.

Wouldn't it be nice if I could:

A: Discover those extra 2 shorts that were allocated to me anyway.
B: Discover that I could expand in place by another 32 shorts without
the expense of relocating my array.

?

These seem like significant and obvious optimizations to me.

Indeed, I've coded them up and tested them. Given the right underlying
allocation interface one can achieve very decent performance increases
with very little effort. It won't make your code 10 times faster. But
it sure is an easy way to gain say 15% while minimizing heap
fragmentation and thrashing.

But it is only easy if you have the right allocation interface. Indeed
today the only way to achieve this type of optimization in C is to write
your own malloc/realloc/free functions (adding to the interface as
appropriate). Anyone who's written these functions (I have) knows that
this exercise can't be labeled easy.

-Howard
.

Relevant Pages

  • Re: Whats the difference between the heap and the freestore?
    ... >> In general, when discussing dynamically allocated memory, I hear people ... As of a couple of days ago, I though the heap ... > When you use the term heap in the context of memory allocation it annoys ... > without saying that they have to be allocated on a stack or anything else. ...
    (comp.lang.cpp)
  • Memory problems - WinDbg and SOS: Who recognizes this pattern?
    ... Last night I managed to get a memory dump using ADPlus and I analyzed it ... ephemeral segment allocation context: none ... Large object heap starts at 0x0a0d0030 ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Tip Required on Dynamic Memory Allocation in Server Applications ...
    ... a memory allocation failure after 300 usages of the string ... Suggestions where given to pre-reserve the size of the heap, ... My program works untill 200-300 requests are ...
    (microsoft.public.win32.programmer.kernel)
  • Re: C++ Garbage Collector on VMS?
    ... case of a reference counting system, have a non-zero reference count) as ... to the beginning of the heap, updating the pointers to the objects as it ... (segregating allocation areas by type/size can help a lot there, ... any way with GC-controlled memory). ...
    (comp.os.vms)
  • Re: Wonder why GC has only 2 generations ... here is the answer.
    ... > native allocation, and can help your application improve performance. ... > The GC maintains a list of roots, which point into the GC heap. ... of moving large areas of memory outweighs the amount of memory that would be ...
    (microsoft.public.dotnet.faqs)