Re: Compiling with Continuations/Andrew Appel

In article 92-01-101 (Jonathan Eifrig) writes:
|> Compiling with Continuations, Andrew Appel
|> Cambridge University Press 1992, ISBN 0-521-41695-7
|
| This is indeed a good book, but perhaps not for the reasons you
| suggest. It provides an invaluable explaination of the compilation method
| currently being used for a non-imperative language, ML, in the Standard
| ML/New Jersey compiler (available via ftp from "research.att.com" and


(named sml-nj below)


| However: ... There are good reasons why the methods described may not be
| a good model of compilation for all languages.


A legitimate question is also wether it represents a good model for
the compilation of *any* language. See below.


| The continuation-style method basically converts the source language
| into executable code for a machine model _with_a_heap_. While this is
| OK if the language you are compiling will ...
| Well, I would partially agree with your claim that Appel's book is
| indeed a change from the Dragon book, but I would hesitate to claim that it
| is a "modern compiler text." Rather, I would say it is more like an extended
| tech. note on the SML/NJ compiler, and a good view of how continuations
| might be useful in your current compilation project.


SHORT:




Sorry if I break down a myth for some people, but the fact is that sml-nj
is a real hog, and for that reason, people should be careful before they
suggest that it represents a _model_ that every compiler writer should
follow. As any implementation, it is successful in some respects, and less
successful in others [I give below what I think is the reason for the
overall inefficiency, despite the good quality of the generated code].


Following Mr. Eifrig I suggest that the book be simply taken as
what it was probably meant to be: a research book, useful to understand
the trends of current research in programming languages implementation and
design.


LONGER:


I've read papers by Appel and got convinced that he can generate
good code with his approach: the code is there, it is good. But remember,
good code is not the whole thing when (and here I quote Appel himself),
you "allocate like crazy".


Appel claims that the runtime system he designed, and especially
his garbage collector is powerful enough to reclaim this amount of memory
at virtually no cost. To get things straight, let's recall the argument:
suppose your program has an average (say, constant) amount A of live
objects. Living in a huge amount of memory H will live another huge
amount of free memory H' = H - A at the end of each garbage collection,
allowing for very infrequent triggerings. Since a copying garbage
collector has a cost proportional to the amount of live objects (that is,
a constant cost A), increasing the amount of working memory H decreases
the triggering frequency and the overall cost of garbage collection, even
down to "less than one instruction per object" : this argument was
striking when the article [87] went out.


However, unless you work on a cray or a pc, the real cost of
operations in memory can not be measured in instructions! The huge amount
of memory used by sml-nj puts an enormous burden on the virtual memory
system of the machine it runs on. Appel recommands a ratio H/A of about 7
(15 without the generational version of the GC). Now consider you run a
program asking for, say 20 Mbytes for a certain amount of time. With
SML-NJ, you are really asking for 140 Mbytes of virtual memory. Two
observations must be made:


(1) even supposing that sml-nj uses that virtual memory like god
himself (no page fault, etc) memory (even _virtual_ memory) is a precious
resource. With such a demand, unless you have a very powerful machine your
sml job will ask for *all of it*.
(2) experience shows that even when you run your sml world alone,
the machine pages a lot, and you can get very bad performances (so sml-nj
is not god himself ;-)


It turns out that this serious drawback is related to the overall strategy
of sml-nj compilation : what Appel "allocates like crazy" are essentially
... continuation objects (activation records). In other words, the problem
with sml wasting machine resource comes from a bad pair of memory
management and model of execution.


Finally, I'd like to clarify that despite the appearance I *really* don't
criticize A. Appel's work with sml-nj [more than this: I'd be happy to
have done it in his place, and sign it]. I put the blame on people
reciting that sml-nj is a thunder without having tried it, or worse: even
when they actually tried it, preferring the paradox and *belief* to facts.
It's better to try to understand what's going on, and in that respect, it
should be emphasized that negative results in research work are not a
shame, they are as valuable as other results, and infinitely more valuable
than slogans.


V. Delacour


See:


[87] A. Appel, "Garbage Collection can be Faster than Stack
          Allocation", Information Processing Letters, 1987.


[89] A. Appel, "A Runtime System", Princeton University, 1989.
          Also published in the journal Lisp and Symbolic Computation, in
          1991 I believe.


[89b] A. Appel, "Simple Generational Garbage Collection and Fast
          Allocation", Software Practice and Experience, Feb, 1989.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.