Re: sizeof([ALLOCATED MEMORY])

Howard Hinnant <howard.hinnant@xxxxxxxxx> writes:
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.

No, you couldn't necessarily avoid the realloc altogether, unless the
extra memory is actually reserved. There might happen to be another
two shorts worth of storage available immediately after your allocated
space, but the system might later choose to use it for another
allocation.

More generally, if I call, say, malloc(300), the system might reserve
512 bytes for me, and might (internally) guarantee that it won't use
any of it for anything else until I call free() -- or it might
allocate 512 bytes, but remember that I only asked for 300, and later
carve out the last 128 bytes for another allocation. Or another call
to free() might result in my 300-byte allocation being at the
beginning of a contiguous chunk of 1024 bytes.

In other words, the number of bytes that are *really* reserved for a
given malloc() call isn't necessarily a meaningful question, and may
vary over time depending on things outside the program's control.

If I were going to suggest a new feature to address this (perhaps
straying off-topic a bit), I'd probably propose a new function similar
to realloc(), except that it's guaranteed not to relocate the object.
Let's call it xrealloc() (not a great name, but it will do for now).
If realloc() would have expanded or contracted the object in place,
xrealloc() is equivalent to realloc(). If realloc() would have
relocated the object, xrealloc() fails. (We wouldn't require
xrealloc() to succeed in *exactly* the same circumstances where
realloc() would expand or shrink the object in place, but it would
usually work out that way.)

If I've allocated space for 300 bytes, and I find that I need 302
bytes, I can call xrealloc(), asking for just 302 bytes. If this
succeeds, I'm done, and the call was probably very cheap. If it
fails, I can then do a more expensive realloc() call, requesting 400
or 500 bytes to leave room for future growth. And of course existing
code can ignore xrealloc() and continue to work as it always has.

This would allow an implementation to allocate more memory than you
ask for, while still permitting it to take back some of the extra
space if it needs it.

--
Keith Thompson (The_Other_Keith) kst-u@xxxxxxx <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
.

Relevant Pages

  • Re: Buffer growing strategy?
    ... Oin terms of memory copy performance. ...  Is it possible for a compiler vendor to implement a realloc ... developer to work around the system's implementation. ... tight allocation strategies, which are the norm, you can never know. ...
    (comp.lang.c)
  • Re: malloc
    ... If I use both the calls ie. malloc and realloc together, how the allocated memory will be ... Again, an old pointer value, valid for the first allocation of p, will ...
    (comp.lang.c)
  • Re: realloc, copy and VM
    ... > When you realloc for more size, it may be necessary to allocate a new block, ... > copy memory and deallocate the old, for example if there is not enough free ... That *is* extending the original block. ... via lazy allocation and copy-on-write.) ...
    (comp.lang.c)
  • Re: when can realloc fail?
    ... will the allocation of ptr be freed? ... about what the Standard requires/allows. ... memory pointed to by p, basing the claim on the deallocation ... Don't call realloc() with the second ...
    (comp.lang.c)
  • Re: Proposed addition of malloc_size_np()
    ... for future realloc(), etc. ... are other uses such as for having a debug malloc wrap the real one, ... We can store that information, ... getting the size of each allocation, I don't know how much to subtract ...
    (freebsd-arch)