Heap Fragmentation

[Mike Haertel]

In article <11161 at smoke.BRL.MIL> gwyn at brl.arpa (Doug Gwyn) writes:
>In article <35076 at apple.Apple.COM> mikes at Apple.COM (Mike Shannon) writes:
>>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.

Not true.  GNU malloc(), of which I am the author, can shrink the heap.
(This is a new and different malloc(), distinct from the ancient Caltech
malloc() we have previously distributed.)  Callers can freely mix sbrk()
calls.  The algorithm is:

	if (sbrk(0) == mallocs_notion_of_top_of_heap)
		sbrk(negative_amount);

>>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.

If you want to be absolutely sure of avoiding heap fragmentation, don't
trust any allocator (even mine :-) and write a dedicated allocator as
a front end to malloc(), that malloc()s huge and parcels them out as
needed, and later free()s them in a batch when appropriate.  The GNU
obstack macros implement one such allocation discipline.

>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.

Yes.  If you know the types and roots of all your data structures,
this is straightforward.  Even if you don't you can write a
(nonportable) "conservative" garbage collector that scans all
variables, heap, stack, and registers looking for possible references.
Empirically such conservative allocators have been observed to
do a reasonably good job of reclaiming dead storage.
-- 
Mike Haertel <mike at stolaf.edu>
``There's nothing remarkable about it.  All one has to do is hit the right
  keys at the right time and the instrument plays itself.'' -- J. S. Bach