[gclist] Allocator algorithms.

[Paul R. Wilson]

>From majordom@iecc.com Mon May 20 16:06:32 1996
>Date: Mon, 20 May 96 16:55:56 -0400
>From: David Chase <chase@centerline.com>
>Precedence: bulk
>Reply-To: gclist@iecc.com
>
>
>> 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
>
>I've never heard of it working well for anyone, actually. I'm pretty 
>poor with remembering the names of these algorithms (another nice 
>thing to summarize for the FAQ, actually) but for big blocks (multiplie 
>of pages size) what intuitively seems right is to always prefer lower 
>addresses.  (What is this called?  Memory-ordered first-fit?) Even 

We call it address-ordered first fit in our survey paper.  In the
literature, people usually just call it "first fit", but there's a fair
amount of ambiguity there.

>You might try Cartesian tree.  If you wish to do a quick-and-sleazy 
>experiment, one (SunOS or Solaris, probably SunOS) of the Sun memory 
>allocators uses Cartesian trees (it's the really slow one that doesn't 
>use much memory -- I've tried to beat it myself in the past, and 
>it is tough).

I'm curious about this.  Is there any evidence that address-ordered first
fit beats best fit?  It's worst case is better, and I wouldn't be surprised
if in is in fact better, but I don't know.  In our experiments, they're
both damned near perfect, but I dunno what happens for long-running
programs with unusual fragmentation-causing behavior.

My guess would be that for most programs, the big win of using a cartesian
tree isn't in implementing a better policy than first fit, but in avoiding
the need for headers to support coalescing.  (The tree encodes adjacency,
so you can use it without boundary tags or whatever.)

I wouldn't think there would be a big win for an allocator that only
handled big blocks.

We've seen one synthetic program for which the Sun allocator is bad
news, at least locality-wise.  I don't know if that means anything.

I'm not sure what to think about cartesian trees.  You can't balance
them, which is bad.  Best-fit looks like it has a better implemenation
(a binary tree of linear lists, with the tree indexed by free block
size, and for each size a linear list of free blocks of that size).
Address-ordered first fit might have an edge fragmentation-wise for
ornery programs, but if anybody's got such a program I'd like a trace
of its allocation behavior.