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

[boehm.PARC@xerox.com]

Stephen Hooton wrote:

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

Could you clarify this?  Paul's scheme (which is also our approach) takes
something like two memory loads, one store, and a nil-check to allocate.  (We
also need to increment a counter to keep track of allocated memory for heap
expansion decisions, as would you, I suspect.)  If the free list pointers in
your scheme are stored in memory, you seem to get very similar costs, with
increased fragmentation problems.  (We try fairly hard not to break up large
objects.)

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

Hans