Why does ANSI not define a function to determine the size of (m)allocatedmem? (like _msize)

[Keith Thompson]

How do you think C programming has survived for many decades without it?
It obviously isn't essential, it isn't even in C++ (where it could have
been added easily if they had wanted to do so).

That argument could be used against adding any new feature. (Not that
it's invalid; any new feature needs to overcome this argument.)

Does any language actually allow you to allocate something anf find
out how big it is later?

In a language with a typed allocator (rather than one that returns an
untyped chunk of raw memory), you can generally get the size because
you know the type. Ada is one example. (That's the size of the
object, not the (possibly larger) size allocated by the underlying
system.)

 

[websnarf]

Ok, first, obviously, the length might not be explicitely stored -- it
might need to be derived. But the point of a byte_allocated() function
is not dictate an implementation, but rather to simply duplicate
whatever action free() or realloc() performs in implicitely working out
the length of the allocation. Most reasonable performance
implementations, just store the length, though.

The point is, since I am arguing that it doesn't really cost any more
to implement such a function, that it should always be there as an
assist to debugging. Writing wrapper functions, or using things like
dmalloc() *DOES* cost you something. I'm a big believer in built-in
error logging and recovery mechanisms such as are discussed here:
http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=233 .
(There is this great dillusion that developers have that they can root
out all problems before a project ships -- but any realistic appraisal
of real world software should tell us that this is not the case.) In
the case of programming in C, one of the big problems with late term
debugging (i.e., dealing with problems only seen after the product
ships) is that there are no language tools for auditing the heap that
don't negatively impact performance. But my own analysis of the
problem indicates to me that there is no reason for this. MSVC++, for
example, does come with a well instrumented heap, but its tied
specifically to its debugger and thus is kind of useless for diagnosing
problems that show up in the field.

How do you think C programming has survived for many decades without
it?

Simple -- it *HASN'T*. That's why developers are leaving C behind.
The C language just doesn't scale with the complexity of applications,
and so the simplest thing, such as the implicit constructor destructor
paradigm of C++, which mitigates a lot of memory problems, are enough
for people to abandon ship.

I would also like to point out that in fact there are *C* compilers
that *DO* implement a bytes_allocated() function. Namely, WATCOM C/C++
implements _msize() which does exactly this. WATCOM also implements a
number of other interesting heap analysis functionality -- and it
remains available even for release builds.

 

[Howard Hinnant]

Very interesting discussion. I wish I had noticed it earlier.

I also advocate something like _msize, and several other key additions
to the malloc interface.

I can speak as an author of a few commercial implementations of malloc:
Not one of the implementations I've done actually keeps track of the
size the user requested. And they all keep track of the size of the
block of memory returned to the client. When realloc is called, the
latter number of bytes is copied. Imho, it is faster to do that than to
track both the client requested size, and the client supplied size.
Although the former is definitely useful in a debug build.

A few people have given the main motivation for the existence of this
functionality: To delay the realloc-ing of a dynamically sized array:
If the memory is sitting there anyway, locked out of otherwise being
utilized, one might as well use it.

Yes, I would like to see this functionality in C++ as well. If it
exists at the C level first, it will be easier to bring it to C++'s
allocator concept, and C++ containers can then use it.

There is a proposal in the post-Redmond C mailing which addresses this
subject:

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm

This is all about being able to write potentially higher performance
code and yet remain portable. It also includes "expand-in-place"
functionality to potentially further delay the need to realloc a growing
block of memory to a new location.

The latest Metrowerks products (on some platforms) contain the proposed
interface, although with alternate names in the C library, and a "malloc
allocator" in the C++ library which the std::vector knows how to make
good use of.

-Howard

 

[Keith Thompson]

I would also like to point out that in fact there are *C* compilers
that *DO* implement a bytes_allocated() function. Namely, WATCOM C/C++
implements _msize() which does exactly this. WATCOM also implements a
number of other interesting heap analysis functionality -- and it
remains available even for release builds.

Does _msize() return the number of bytes requested, or the number of
bytes actaully allocated? If the latter, it would probably require
realloc() to copy more bytes than it really needs to.

 

[Howard Hinnant]

Does _msize() return the number of bytes requested, or the number of
bytes actaully allocated? If the latter, it would probably require
realloc() to copy more bytes than it really needs to.

Copying more bytes than it needs to can be faster than not. Consider a
malloc on the PPC architecture which returns 16 byte aligned blocks (the
largest alignment required for PPC vector objects). If the client
requests 75 bytes and malloc returns 80, it is much faster to move the
80 bytes with 5 vector load-stores rather than move 75 bytes with 4
vector load-stores, 1 floating point register load-store, and 3 byte
load-stores.

-Howard

 

[Goran Larsson]

A few people have given the main motivation for the existence of this
functionality: To delay the realloc-ing of a dynamically sized array:
If the memory is sitting there anyway, locked out of otherwise being
utilized, one might as well use it.

This motivation is very weak.

I am quite sure that implementors of malloc routines implement the
simple optimization of avoiding the copy and returning the original
pointer if the new size is smaller that the size of the memory area
malloc used.

Example:

p = malloc(30); /* Returns a pointer to a area */
/* from the 64 byte memory pool. */
. . .
p = realloc(p,40); /* As the new size is less than 64 */
/* no copy and same ptr is returned. */

vs.

p = malloc(30); /* Returns a pointer to a area */
/* from the 64 byte memory pool. */
. . .
if ( _msize(p) < 40 ) { /* _msize returns 64. */
p = realloc(p,40);
}

The cost of calling _msize can't be any different than the cost of
calling a realloc that doesn't need to do a copy.

What can be done with a _msize that isn't provided automatically with,
probably most (if not all), of todays malloc implementations?

 

[websnarf]

Does _msize() return the number of bytes requested, or the number of

bytes actaully allocated?

The bytes actually allocated.

[...] If the latter, it would probably require
realloc() to copy more bytes than it really needs to.

Depending on what you mean by "really needs to". I didn't implement
WATCOM C/C++ heap, and I can tell you, that they have far worse
problems than possible over-copying. The highest impact on realloc()
performance is actually the probability that it can consume adjacent
memory. Using _msize() you can deterministically avoid some small
increases, or just intrinsically avoid them because you've got the
extra space in the allocation anyway. The "extra space" should just be
a round up to the next alignment size -- implementations that try to
round up to powers of 2 or other oversized fixed block sizes (rather
than just alignment) end up paying a price in decreased locality (a
potentially far worse problem) and just plain worse memory utilization.
So I have no sympathy for these claims/concerns -- there are better
ways of designing heaps which are all around better and which don't
suffer any negative performance for exposing a bytes_allocated()
function.

 

[Howard Hinnant]

This motivation is very weak.

Not really, unless we are designing a new language from scratch (see
below).

I am quite sure that implementors of malloc routines implement the
simple optimization of avoiding the copy and returning the original
pointer if the new size is smaller that the size of the memory area
malloc used.

Sure, such as the example realloc implementation in the proposal:

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm

Example:

p = malloc(30); /* Returns a pointer to a area */
/* from the 64 byte memory pool. */
. . .
p = realloc(p,40); /* As the new size is less than 64 */
/* no copy and same ptr is returned. */

vs.

p = malloc(30); /* Returns a pointer to a area */
/* from the 64 byte memory pool. */
. . .
if ( _msize(p) < 40 ) { /* _msize returns 64. */
p = realloc(p,40);
}

The cost of calling _msize can't be any different than the cost of
calling a realloc that doesn't need to do a copy.

What can be done with a _msize that isn't provided automatically with,
probably most (if not all), of todays malloc implementations?

Some clients do not want the expense of a copy and are willing settle
for less memory than the requested size in a realloc. Other clients can
not tolerate a copy, no matter what the expense. For example some
clients may have structs that are self-referencing:

struct MyType
{
struct MyType* head; // head and tail may point to this
struct MyType* tail;
};
....
MyType* p = realloc(p, newsize*sizeof(MyType));

Self-referencing structs can not be memcpy'd, and thus arrays of them
can not be realloc'd (at least not without post detection of address
change and fix up). And so it is beneficial to see if such arrays can
be expanded in place (the real thrust of the proposal).

The proposed sizeof_alloc(void*) is a minor player in this paper,
present mainly for transitional code. If you receive a malloc'd pointer
from a legacy server, you can find out the size of the allocated block
with sizeof_alloc. A non-legacy server would simply use request_malloc
instead of malloc, and thus receive the memory block and its allocated
size at the same time (if that information is useful). So in a newly
built system today, sizeof_alloc(void*) is somewhat redundant, and thus
would have weak motivation. But in today's context, where you might be
dealing with the transfer of memory ownership from legacy code, the
motivation for sizeof_alloc(void*) is significantly stronger.

But the above is really just a subtlety. To really answer your question
head on: Some clients can only expand their array in-place, and can not
use memcpy when placing the array into a larger block. Thus realloc is
inconvenient at best, and completely wrong at worst. To be able to
discover the true size of your allocated block of memory, and to also
discover if it can be expanded in-place, and by how much, can be very a
significant optimization.

A potential pitfall: clients must not (portably) assume that
sizeof_alloc(void*) is O(1) time complexity. While all malloc systems I
can think of can return this information, some of them may not do it in
constant time. Indeed, one of the malloc implementations I've written
for a very tight embedded system returns this information in O(log)
time. And so I advise clients that need this information to cache it,
instead of recomputing it on each need, unless it is known that the
underlying implementation can deliver in O(1) time.

-Howard

 

[websnarf]

p = malloc (30);
...
p = realloc (p, 40);

vs.

p = malloc(30);
. . .
if ( _msize(p) < 40 ) {
p = realloc(p,40);
}

You misunderstand the purpose of the idea. Try the following:

.. p = malloc (30);
.. ...
.. if (_msize (p) < 40) {
.. t = realloc (p, 80); /* Double the allocation size */
.. p = t ? t : realloc (p, 40);
.. if (NULL == p) fail ("Out of memory");
.. }

See, if there is enough space, the memory is not resized. If not, we
try to actively attempt to postpone future reallocs to other size
increases by *doubling* the memory. Even linear increases in size will
only call realloc a logarithmic number of times. But in more common
situations of just doing a few small resizes attempts, knowing the
exact size can save a constant factor number of allocations.

I can't do this for http://bstring.sf.net/ because there is no portable
_msize(), so I use other strategies, which on average slightly increase
the average amount of memory used, and slightly increases the number of
calls to realloc(). Howard Hinnant's proposal would be fine for the
purposes of Bstrlib, however, if you go that far, there is a lot more
that can be done.

 

[CBFalconer]

.... snip ...

I would also like to point out that in fact there are *C* compilers
that *DO* implement a bytes_allocated() function. Namely, WATCOM
C/C++ implements _msize() which does exactly this. WATCOM also
implements a number of other interesting heap analysis
functionality -- and it remains available even for release builds.

No compiler provides this. Some library implementations do. The
approach I took in my nmalloc module for DJGPP (which should be
easily adapted to most POSIX like systems) is to supply a routine
in system name space which returns a record describing the internal
memory layout, together with a header describing the fields in that
record. As long as accessory routines are built using this
facilities, they can be implemented without worrying about the
actual malloc implementation details.

nmalloc.zip is available on my pages below, download section.

 

[Flash Gordon]

The implementation may well have to use more memory to store the
length, thus wasting resources in the more common cases (on some
machines quite possibly wasting 16 bytes or more in order to get the
alignment for the worst case). Or it might have to spend time looking
for the length in some implementations (for instance ones using
garbage collection where separate lists of pointers and lengths are
kept). There's also one common one where the last block allocated on
a 'heap' has an allocated size of "the rest of the heap" until another
block has to be allocated after it.

The implementation logically must have some internal track of how much
space is allocated so that it can:

a) Copy the data on realloc if required.
b) Allocate the next block so that it does not overlap with what the
user requested for the last block on the heap.

Therefor the bytes_allocated() function could be implemented to return
the smallest number it has that

a) will be copied by realloc if realloc has to move the block
b) does not extend in to space that might be allocated by some
subsequent call to *alloc

So, as far as I can see the implementation must have some number which
it knows which is only bigger than what you requested if realloc would
copy the extra space on moving the block and is not so big that it will
lead you to use space that will get used else where.

If you want it for debugging you can implement it on top of the
existing functions (as debuggng libraries such as dmalloc do), or your
debugger can interface with the allocation libraries at low level
(since debuggers are inherently system dependent).

How do you think C programming has survived for many decades without
it? It obviously isn't essential, it isn't even in C++ (where it could
have been added easily if they had wanted to do so).

Obviously it is not essential. For loops are not essential since you can
implement them using labels, if and goto.

Does any
language actually allow you to allocate something anf find out how big
it is later?

Before the first assembler was written did any language allow you to
call a function by name rather than address?

I can see that it would be useful for some code. By using such a
function if it was added to the standard a programmer would remove any
chance of failing to track the size of a buffer correctly. I know a
program *can* keep track itself correctly, since I deal with code that
does, however that does not mean it is always the best way to do it if
an alternative can be provided.

I find it hard to conceive of any allocation scheme that would not be
able to calculate an appropriate number to return when bytes_allocated()
was called, i.e. without adding overhead to the existing *alloc routines
or the data structures they use, although it might need a little code in
bytes_allocated() rather than just reading a number from the structure
and returning it.

 

[Dave Thompson]

Does any language actually allow you to allocate something anf find out how
big it is later?

In Java you can allocate an array of objects [and use .length] <snip>

True, you can do it with vectors in C++ as well. C++ ones also allow
you to dynamically extend them (and get both the current length and the
current allocated size), but they are basically just structures with
dedicated functions to access them and are part of the library not of
the syntax.

Fortran 90 and up (F9X) for arrays (bounds), and for character strings
(length) which Fortran like COBOL and PL/I considers a separate type,
not just array of character as in C, Pascal, and Ada (sort of). But it
does so by having fat pointers. Very fat pointers. Obese, even.

IIRC PL/I CONTROLLED also allows DIMENSION (*) and character (or bit)
string length (*) meaning variable at ALLOCATE time, fetchable later
with builtins like HBOUND.

Ada somewhat more generally allows types, in particular subrange
types, to have bounds computed at compile time; and thus also arrays
(including strings) using these index types.

As a related but distinct feature, in all three languages, and also
Pascal, you can (explicitly) declare a parameter aka dummy or formal
which accepts by-reference an array or string (where distinct) of
varying bounds/sizes, and obtain them.

Exactly.

And probably speed penalties as well, if it uses it for length checking
on access (which Java does, I believe and C== STL vectors generally
don't).

C was designed to be lean & mean, if you don't know what you're doing
use some other language with more protection...

Chris C

- David.Thompson1 at worldnet.att.net