[gclist] Allocator algorithms.

[Paul R. Wilson]

>From majordom@iecc.com Mon May 20 15:11:04 1996
>
>Under the conservative collector operating at a page level
>is a storage allocation algorithm. By operating at a page
>level I mean that requests smaller than a page are done by
>breaking up a page taken from the allocator.
>
>Anyway we are unhappy with circular first fit. It seems
>to create too much fragmentation. Does anyone have any
>suggestions. We are looking for Cartesian tree agorithms
>and best fit.

The biggest suggestion is don't use LIFO first fit or LIFO next
fit.  (That is, where freed blocks are shoved on the front of the
free list.)

The next is don't use a roving pointer.  It's really bad news.

We recently did some experiments, and these algorithms are not only
bad for allocators in general, but extraordinarily bad for GC's.
The deferred freeing that a GC does exacerbates their fragmentation
problems.

(We did a little experiment where we added deferred freeing to
normal allocation traces---we just buffered the frees for n KB
of allocation, then freed things in batches.  This makes next fit's
fragmentation go through the ceiling---to around 400%.  Best fit
does fine.)