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

[David Ungar]

At 9:46 AM 3/15/96, David Chase wrote:
...
>
>> BTW, I tried a "customizing allocator" (aka multiple free lists)
>> in the first version of Berkeley Smalltalk.
>> My experience with it was so different from Paul and David Chase's that
>> I think context (e.g. St vs. C, interactive vs. real-time)
>> must play a very important role.
>
>This is weird.  I have gone out and measured this myself, and friends
>of mine have measured it as well in other applications, and what
>we've always discovered is that something like 90% of the objects
>allocated fall into two or three (smallish-object-size) lists.
>This supports your assertion that header size matters, because an
>8-byte header is a big deal if the user only request 16 bytes of
>memory for data.  (And this is why I like to use BIBOP whenever
>possible, and why I think that the language's type system and
>GC headers should be integrated whenever possible.)


I agree about the lists working w.r.t. object sizes.
What led me away from the free-list allocator towards the
contiguous allocator was the speed issue.

With a contiguous allocator, you can keep the
allocation pointer in a register, and even put its
limit in either a register or an immediate field of an instruction.
The new, hot stuff, is all contigous in memory, which helps VM
and caching behavior--yes I know you can blow the cache anyway,
but it still seems better than following lists.

Then, when it's time to free those dead young objects,
you just reuse the space, without overhead for
doubly-linked lists.

I guess my disaffection for free lists comes as much
from a look at reclamation as from the free list part,
and pertains to a ST/Self/Friendly-compiler
context.