Heap Fragmentation
Mike Haertel
mike at thor.acc.stolaf.edu
Fri Sep 29 02:55:05 AEST 1989
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
More information about the Comp.lang.c
mailing list