[gclist] Compiler specialized GC's

[boehm.PARC@xerox.com]

Dave Loyd wrote:

"Algol68 is statically typed, so I know where I'm going from every type. I saw
a 5-fold performance improvement over a table-driven GC where following a
pointer involved a few indirections to find out what was under it (now a direct
call)."

My impression is that this depends heavily on the details.  A few years back I
did one or two simple experiments  with SRC Modula 3.  I arrived at the
conclusion that the mark procedures were probably not a win.  The performance
seems to be influenced by many things:

1. How efficient is the table interpreter?  You shouldn't need more than about
5 instructions per field for the actual interpretation of a bit map, plus some
start up overhead.  How much optimization do you perform on the mark
procedures?  On the table?

2. Do you need to dynamically look up object types?  If your language has
implementation inheritance or some "void *" equivalent presumably the answer is
yes.  In Algol 68, presumably the answer is usually no?  I the answer is no, I
can believe that table interpretation becomes relatively a bit more expensive,
since it needs to store type descriptors, not just bit maps.

3. Is your marker recursive, or does it use an explicit stack?  I would argue
that it should use an explicit stack, since otherwise it's usually very hard to
recover from running out of stack space.  In addition, activation records tend
to be much larger than what you need for a mark stack entry.  If both are
recursive, that helps the mark procedure case, since now even the interpreter
involves procedure calls.  Our marker makes no procedure calls on a per object
basis, except in the case of user specified mark procedures.

Hans