[plt-scheme] 3m

About Our Current GC Technology
----------------------------------

Our default GC is called a "conservative" garbage collector. The
"conservative" part means "guess a bit about which stack, heap, and
register words represent live pointers --- and make conservative
guesses".

The advantage of conservative garbage collection (CGC) is that it's
relatively easy to interoperate with C. For that reason, CGC was a
reasonable choice for the way that we originally constructed DrScheme,
and it remains extremely useful to those of you who develop C-based
extensions to import C libraries.

Also, the research literature says that CGC works pretty well, and our
experience is generally consistent with that conclusion. There is one
known problem, though, related to linked lists [Boehm,
POPL'02]. Unfortunately, we seem to hit this problem often in
practice, due to the way that threads and continuations are
implemented, and there doesn't seem to be a reliable way around
it. Furthermore, the problem is worse for GUI programs that involve
lots of threads --- such as DrScheme.

Why I Think the GC is the Problem
---------------------------------

After many years of looking at the problem, it's still difficult for
me to pin down where CGC goes wrong and whether the problem is
avoidable. But one bit of experience long ago convinced me that we can
do better with a different GC.

About seven years ago, I abandoned Emacs for e-mail, replacing it with
MrEd-based program called "SirMail". The world doesn't really need
another e-mail client, and I don't recommend that you switch to
SirMail. The point for me is to continuously test our software by using
it for (what seems to be) my main activity.

At first, I had to re-start SirMail every few days to keep memory use
manageable, just many do now for DrScheme. I eventually concluded that
the problem was not a leak in SirMail, but a problem with using CGC.

This experience triggered the "3m" project to replace the current GC
with a better one. 3m fixed SirMail, which is why I still use it (and
can run it for weeks at a time).

What is 3m?
-----------

"3m" stands for "moving memory manager". The "moving" is the important
part; it means that the C code inside MzScheme and MrEd has been
transformed so that the garbage collector can move objects in memory.
A GC can do many things better and more easily when it can move
objects, such as compact the heap and separate long-lived objects from
short-lived objects (so that the long-lived objects can be inspected
less frequently). More importantly, a prerequisite for moving objects
is knowing exactly where all the pointers are, so the 3m collector is
non-conservative.

By default, PLT Scheme builds with CGC. By using `make 3m' and `make
install-3m', you can obtain 3m variants of PLT executables in parallel
to the regular CGC variants; the 3m variants all have a "3m" suffix.
Instead of building from source, you can download the "Full" nightly
build, which includes 3m executables.

Why 3m Isn't Yet the Default
----------------------------

3m definitely works better than CGC for SirMail, and in principle it
should always work at least as well as CGC. Despite having a 3m that
works well enough for SirMail for many years, however, we have not yet
switched to it as the main build.

Two major obstacles have kept 3m out of our main release:

 * The first obstacle is the difficulty of connecting to C-implemented
   libraries and extensions. We use CGC is because it simplifies
   interoperability with C libraries, and dumping CGC means losing
   that advantage.

 * The second obstacle is run-time performance. Cooperating with the
   3m GC requires instrumenting the core MzScheme and MrEd code (which
   is implemented in C). That instrumentation slows MzScheme by as
   much as 20% on an x86, especially in the interpreter loop. The
   performance change is usually worse for PowerPC (because the 3m
   instrumentation interferes with registers, we think).

Why 3m Might Become the Default Before Long
-------------------------------------------

Both of the major obstacles above have recently become much smaller:

 * Using the "foreign.ss" library with 3m is usually not much more
   difficult than with CGC. As our library bindings have migrated to
   "foreign.ss" (instead of writing the glue in C), using 3m has
   become much easier.

   Meanwhile, we also have mzc --xform (and a better tool in the
   pipeline) for transforming C-implemented glue code to work with 3m.

 * The new JIT essentially eliminates the 3m instrumentation cost for
   JITted code, because the JIT can cooperate much more directly with
   the GC than instrumented C code.

   The overhead remains for primitives, such as port operations and
   regexp matching. Nevertheless, the overall performance comparison
   (including GC space and time) has shifted significantly in 3m's
   favor.

Whether we actually shift depends on a couple of factors. First, we
have to make sure that 3m is stable and well-tuned; although I use 3m
most of the time, my tasks form a small subset of what the people on
this list do. We are gradually widening the circle of people who use
3m, and you are certainly welcome to become part of that group.

Second, we need to make sure that most people who deal with low-level
code are ready for the switch --- especially people on this list who
write bindings to C libraries. I am interested in hearing from anyone
who works with C code about whether the switch to 3m is feasible. Of
course, we will never discontinue the CGC build, so those who embed
MzScheme or create extensions for personal use can always continue
using the CGC variant.