[gclist] Compiler specialized GC's

[Richard Jones]

>I'm curious if there's been any research for compiler supported, GC
>specialization. That is has then been any work on compilers that at compile
>time generate a specialized/GC runtime system to take advantage of program
>specific properties. For example, if you don't mind losing modularity, one
>could imagine a compiler analyzing all the different kind of heap objects a
>program could allocate and hard coding a specialized GC that was specialized
>to collect the object, rather than interpreting bitmaps or other type
>information at runtime, one could also imagine using specialized copying
>routines too, if you're gc scheme need to copy. I guess, my real question is
>are these kind of optimizations going to be swamped by other factors like VM
>interactions or tagging/untagging costs.

Yes there has.
One example is Stephen Thomas' compiler for lazy ML.

@phdthesis{thom93,
author = "Stephen P. Thomas",
title = "The Pragmatics of Closure Reduction",
school = "The Computing Laboratory, University of Kent at Canterbury",
month = oct,
year = 1993
}

The compiler generates code for an abstract machine based on TIM, but much
optimised. In particular, it generates GC routines tailored for each function
defined in the program source.

This is necessary because the TIM is a shared environment closure reducer.
It is possible that different slots in a shared environment may be used by
different functions. For the GC simply to preserve everything reachable from
every slot in the environment would (and does) lead to a space leak.

By tailoring a GC routine to each function definition, we get a precise
collector. As you point out, this means that we do not need to interpret
bitmaps, tags or whatever. Each closure is made up of a pointer to an
infromation table and a pointer to an environment. Mutator execution jumps to
a fixed offset in the information table. The collector jumps through an
indirection in the information table.

As you point out modularity is a problem: there is the risk of replicating
identical collector routines. However this is partially solved by having a
fixed set of "common" collector routines. E.g every possible collector for
functions with upto 6 arguments (there are 2^6 of these) is pre-defined.

The compiler generates SPARC code and seems reasonably quick (see a
forthcoming Journal of Functional Programming article). GC only appears to
account for a tiny fraction of execution time, though this may well be due to
the rather limited set of benchmarks used.

I believe a similar approach has been used in versions of the Glasgow Haskell
compiler.
  

Richard Jones

===============================================================================

Computing Laboratory                           Room SW107
University of Kent at Canterbury               Telephone: 01227 764000 ext.7943
Canterbury,                                               01227 827943 (direct)
CT2 7NF, U.K.                                  FAX: 01227 762811

===============================================================================