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

[Stephen Hooton]

Stephen Hooton wrote:
"...
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..."

    Hans> Could you clarify this?  Paul's scheme (which is also our
    Hans> approach) takes something like two memory loads, one store,
    Hans> and a nil-check to allocate. If the free list pointers in
    Hans> your scheme are stored in memory, you seem to get very
    Hans> similar costs, with increased fragmentation problems.

The pointer to the current large block is kept in a register (where
possible), hence reducing the allocation time. Also the counter to
keep track of allocated memory is only updated when the current large
block is exhasted. 

To be fair though, when we allocated from Free Lists we also had to
check if the object was small enough to fit on a free list. Though
this cost could have been compile away in most cases.

    Hans> Furthermore, even if you allow the heap to be twice as big
    Hans> as live memory, you have to mark and perhaps trace an object
    Hans> for every object you allocate, on average.  It seems to me
    Hans> that this is virtually certain to dominate.

But for the same collector the fastest possible allocator would be
nice :-) 

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/ ---+