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

[David Chase]

David Ungar writes:
> Paul,
> 
> You seem to be arguing that if a system exhibits a high
> object allocation rate, it must be "broken" and therefore
> it would be better to redesign it that to worry too much about
> allocation efficiency.
>
> But, no matter where you allocate continuations, no matter
> how much to try to be clever in the compiler or whatever,
> some population of your programs by some number of users
> will exhibit high allocation rates.

I'm sure that some population will, but if the relative size
of that population can be sufficiently reduced by clever compiler
tricks, one-bit-reference counts, what have you, then a point is
reached where further efforts to make their allocations rapid are
not worth it.  I'm in this for the engineering, not the religion.

> To quote my patron saint of implementations, L. Peter Deutsch:
> "The revolution won't be complete until users think as little
> of creating new objects as they do of calling a subroutine."

But this is probably already true, at least for me.  The free-list-per-size 
allocators can hand you back memory very quickly -- they make for 
very short subroutines.  A typical-case code path looks something like:

  index = (size + 7) >> 3;
  if (index < threshold) {
    p = freelists[index];
    if (p) {
       freelists[index] = p -> next;
       return (void *) p;
    }
  }

If you've got compiler support, then you can remove some of that 
code, and better schedule what remains.  This is not quite as fast
as bumping a pointer, but in order to get to where you can bump that
pointer, I think you have to make other tradeoffs with respect to
system design and/or optimization and/or compatibility with uncooperative 
code.

I haven't, in my limited experience, been nailed by fragmentation 
with one of these yet.  I've written a couple of variations of malloc/free 
along these lines over the years, and they also seem not to fall 
victim to fragmentation.  I know how to write a program that would
cause fragmentation problems, but in practice, I seem not to write 
such programs.

David Chase