Re: Garbage Collection in Ada

[Hans-Juergen Boehm <boehm@mti.sgi.com>]

Robert Dewar wrote:
> 
> 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.
I believe the version with full coalescing has worst-case allocation
time log N, where N is the heap size.  Consider a heap with only one
large empty block and repeated requests to alternately allocate and
deallocate a 1 byte block.  (I'm referring to the algorithm in Knuth,
vol. 1, 2nd edition, starting at page 442.  Knuth credits it to
Markowitz and Knowlton.)

I mentioned the algorithm without coalescing, since it seems to be
commonly implemented.  Allocation and deallocation is a bit faster, and
worst-case space usage is only worse by a constant (see below).

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

You can do considerably worse than that.  Consider allocating size 1MB
os size 1 blocks.  Deallocate most of them, so that only ever 16th
remains.  Repeat with size 16 blocks.  They will need to go into a new
region of memory.  Leave every 16th.  Repeat with sizes 256, 4096 and
64K.  At most 1.25MB were live at any point.  But 5MB were needed.  This
is in addition to the factor of 2 you get with non-power-of 2 sizes.  So
we have something like a factor of 8.  And this isn't quite the worst
case.  See also exercise 41 on page 455 in Knuth V. 1.

Knuth states (Vol 1, 2nd ed., bottom of page 451):

"J.M. Robson has shown [JACM 18 (1971), pp. 416-423] that dynamic
storage allocation strategies that never reallocate reserved blocks
cannot possibly be guaranteed to use memory efficiently; there will
always be pathological circumstances in which the method breaks down."

He gives details and bounds in the exercises.

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com