Heap Fragmentation

[Doug Gwyn]

In article <35076 at apple.Apple.COM> mikes at Apple.COM (Mike Shannon) writes:
>In article <1989Sep27.045926.12634 at polyslo.CalPoly.EDU> ttwang at polyslo.CalPoly.EDU (Thomas Wang) writes:
>>Is heap fragmentation in C a problem or non-problem?
>Memory management is not part of the C language, it is part of the library
>support in the underlying system.

The modern point of view is that there is no crisp distinction between
the language and the run-time support.  In a hosted implementation, the
forthcoming Standard requires that malloc()/realloc()/free() be supplied.
They could be implemented as language keywords (actually, as macros
defined in terms of reserved-name keywords) as well as library routines.

>It's my understanding that de-allocated memory chunks are never handed
>back to the operating system, ...

In a UNIX context, traditionally applications have mixed sbrk() calls
with (perhaps implicit) use of malloc(), so it would be unsafe for
a UNIX malloc()/free() implementation to shrink the heap in general.
In other contexts, for example in the Apple IIGS/Macintosh desktop
environment, it is desirable for memory no longer in use by active
processes to be immediately returned to the system resource pool.

>In summary, I would say heap fragementation under UNIX is not a problem.

It can be, but unless you're pushing the limits on maximum virtual
data space size it would take a rather unusual memory allocator usage
pattern.

Garbage-collecting equivalents of malloc()/free() have been devised
from time to time.  Rob Pike's Blit terminal (and descendants)
firmware relies very heavily on one, and Rob's "sam" text editor
uses a similar scheme.  If memory is a critical resource (as it is
for the terminals), a garbage-collecting allocator may be worthwhile.