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

[chase@centerline.com]

> Also the statement: "I'm in this for the engineering, not the religion."
> is hard to understand.  Are you trying to denigrate a specific assertion
> by casting it as religion? Which one?

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

The statement above is uninteresting from an engineering point of view
-- there will always be outliers in any population, and some of them
will always be dissatisfied with the biases built into any system.  If
you don't talk numbers, it is true, but so what?  It just doesn't
matter.  Much as people like to promote hedgehog solutions (one thing,
done well, solving all problems), the solutions that I usually see
resemble nibbling at a problem until what remains is not large enough
to matter (the rat solution, I suppose that would be :-).  I view the
attraction of hedgehog solutions as being somewhat religious, or
perhaps esthetic, in nature.  They're pretty, they're complete, and
when I can get one, I like it, but the rat solutions get the job done,
too.

> David Chase makes the points that free list allocation is so fast
> that the allocation overhead does not prevent him from using new
> objects, that the problem of fragmentation does not strike, and that
> the a relocating collector has to make "other tradeoffs with respect
> to system design and/or optimization and/or compatibility with
> uncooperative code."

> David, I would believe that these assertions could obtain for C and C++,
> but would be surprised if they were true for Smalltalk and related languages.
> In which arena does your experience lie?

My engineering expertise, as opposed to my noodling expertise, is
mostly in procedural languages.  I've noodled with things like FFP and
Xlisp, and spent a lot of time reading about implementations of
Smalltalk, ML, and the like.  I'd prefer to use languages of that sort
as much as possible, but the performance often seems to be lacking.  I
spent a lot of time wondering why.  I know, pretty much, what goes
into a compiler and optimizer for a procedural language, so I wonder
what is missing, what is different.  (I know some of the reasons.)

As to the various points:

  optimization -- there's a bunch of low-level optimizations,
  often useful with pointer-valued expressions, that aren't possible
  if objects can move (without extraordinary cooperation between
  compiler and GC).  For C and Fortran, these appear to be worth doing.

  compatibility with uncooperative code -- conservative garbage
  collection does this rather well, I think.  Sometimes that uncooperative
  code has been known to do dumb things like using pointer values
  in the computation of hashes, or using "order" between two pointers
  (less-than, greater-than) to build a data structure.

Optimization at the low level may not be applicable to a Smalltalk
system (why?), so that may not be relevant.

I'm also interested in why fragmentation would plague a Smalltalk
system, but not a C++ or Modula-3 system, if a list-per-size
allocation strategy is used.  The freelists can generate more internal
fragmentation when small things are stuffed into too-big buckets, but
it takes interesting allocation patterns to get external
fragmentation.  I've also had good luck customizing lists on-the-fly
to reduce internal fragmentation as well (I sample the size when
requesting an additional page for a more buckets.  Sounds like a dumb
heuristic, but it often worked, and it keeps the usual case fast.  I
don't recall the exact numbers, but it was fast and compact.  It was
part of an effort to boost some benchmark numbers for a former
employer's compilers.) If you know that you'll be customizing in the
future, then you can start off with a larger granularity, and avoid
populating entire pages with single instances of objects.

I'll try to recreate that customizing allocator one of these days.
It was fun (that is not an engineering statement :-).

David Chase