[gclist] Fast-allocating non-copying GC's

[Stephen Hooton]

>>>>> "Paul" == Paul R Wilson <wilson@cs.utexas.edu> writes:

    Paul> Our real-time collector allocates by popping blocks off of
    Paul> free lists.  There's an array of free lists for
    Paul> different-sized blocks, and you just index into the array,
    Paul> grab the pointer, dereference it to get the next pointer,
    Paul> and store that back into the array.

We are developing a functional object-oriented language (called
UFO). Initially we had a scheme as described above, but it was found
that the allocation rate was not good enough.

We now have a scheme where all of the free blocks in the store are
either on a "small" free list (there are lists for each size of object
from 1 to N). Or on a "large" free list for blocks over size N.

Allocations are made contiguously from blocks on the large free list
until all large blocks are consumed. Then allocations are made from
the small lists. Normally > 90% of allocations are from the large
free list, which leads to a good allocation rate.

Two steps are used to reduce fragmentation:
i) A fraction of Store is kept in reserve. This "clean" memory can be
introduced for large allocations and/or to help with fragmentation.
ii) Normally GC is a simple mark-sweep but occasionally there is a
compaction phase when fragmentation is deemed to be too high. This
compaction has to be done in the presence of ambiguous pointers so
normally only a small amount of the store can be moved.

Steve.

-- 
   +---------------------- Stephen Hooton ---------------------+
   | Dept. of Computer Science,    Email: hootons@cs.man.ac.uk |
   | Manchester,                   Voice:     +44-161-275-6292 |
   | England.                      Fax  :     +44-161-275-6236 |
   +---- URL: http://www.cs.man.ac.uk/arch/people/s-hooton/ ---+