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

[Stephen Hooton]

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

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

    Paul> Do you have any measurements of fragmentation when doing
    Paul> this?

What is the best way of measuring fragmentation? We measure
fragmentation as the percentage of memory that is on the small free
lists. The amount of fragmentation created varies greatly from program
to program. 

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

    Paul> This seems like a good idea.  I'm curious what a good
    Paul> strategy is for keeping big free blocks around---how much do
    Paul> you want to keep in reserve?  

I don't think we do either. We let the user set this at runtime
because of the different behaviour of programs. The collector keeps
track of the percentage of allocations from the large free list and
then tries to keep it at some constant (by introducing some reserved
memory).

    Paul> The problem with worst fit is that it's too extreme---it
    Paul> systematically whittles away at the largest block until it's
    Paul> not the largest anymore, evening out the block sizes.  Then
    Paul> if you get a few requests for larger sizes, you're out of
    Paul> luck.

Yes. This is why we had to introduce the compaction phase. Users can
set a threshold of the percent of memory on the small free lists to
trigger a compaction, but also specify the minimum number of collects
between compactions.

The compaction phase seems to work best when a large complicated
structure is deallocated. Most of the freed memory ends up initially
on the small free lists, but after a compaction, this memory is moved
back onto the large free list.

Steve.