Re: Garbage Collection in Ada

[dewar@merv.cs.nyu.edu (Robert Dewar)]

HJB says

"N log K, where N is the size of live data and K is the size ratio
between largest and smallest bound is the best worst-case bound
acheivable by a general purpose nonmoving allocator.  This is an old
result due to Robson, cited in Knuth  (I don't have the reference
handy).  This means a binary buddy system without
coalescing is asymptotically optimal for the worst case.  It does poorly
if your program allocates 1MB of 5 byte objects, deallocates them, then
allocates 1MB of 9 byte objects, deallocates them, allocates 17 byte
objects, etc.  (It's also less space efficient in the typical case
tah other algorithms with worse worst-case behavior.)"


When I say binary storage allocator, I am referring to the Knowlton paper
(note that Knuth did not invent the algorith, just the term buddy system,
and Knuth is concerned to give the right credit as always!)

The essence of the binary storage allocator is that it DOES coalesce
on return, and that for a given maximum block size, the time to coalesce
is bounded by a constant, as is the time to allocate. And in such a system
it is obvious that you cannot be worse than a factor of 2 inefficient
in use of storage (the worst case occcurs if all your allocations are for
one size of block, that is a power of 2 plus one in size).