[gclist] Precise GC's performance

Bill Bill GuillermoJ.Rozas
Wed, 6 Mar 1996 11:05:25 -0800


|   Sender: owner-gclist@iecc.com
|   From: wilson@cs.utexas.edu (Paul R. Wilson)
|   Date: Wed, 6 Mar 1996 11:50:02 -0600
|   X-Mailer: Mail User's Shell (7.2.5 10/14/92)
|   Sender: owner-gclist@iecc.com
|   Precedence: bulk
|   Reply-To: gclist@iecc.com
|   Errors-To: owner-gclist@iecc.com
|
|   >From owner-gclist@iecc.com Wed Mar  6 10:57:10 1996
|   >From: Nick Barnes <nickb@harlequin.co.uk>
|   >Precedence: bulk
|   >Reply-To: gclist@iecc.com
|   >
|   >- SML/NJ uses CPS and does not keep a stack (so it allocates out the
|   >  wazoo). 
|
|   I think it might be a good idea to introduce a terminological distinction
|   here.  Appel uses the term "continuation passing style" to talk both
|   about compiler intermediate representations and runtime representations,
|   and this is very confusing.
|
|   These are very different things.  For example, the T compiler uses
|   CPS as an intermediate representation, but compiles for a stack.  And
|   our RScheme compiler does *not* use a CPS representation, but compiles
|   for a runtime with explicit continuations, much like SML of NJ's.  (We
|   use a stack cache, though, to filter out most of the short-lived
|   continuations and avoid stressing the GC and cache memory so much.)
|
|   CPS in the compiler and "CPS" runtime systems are almost entirely
|   independent.  All four combinations exist in different systems.

I agree completely.  CPS is a source-level code transformation tool
that is sometimes used in compilers to make some implicit state
explicit.  Other compilers keep it implicit until a later point and
never rewrite the code.

How that state is then mapped to memory is largely independent of
whether it is kept implicit or explicit at an early stage in your
compiler.

I have written CPS compilers for languages with and without reified
continuations.

I have written compilers that use heap-allocated control records and
stack-allocated control records.

Which of the four options you choose depends on the characteristics of
the language you are compiling and the tradeoffs you are willing to
make (often cheap reified continuation creation/invocation vs. cheap
 deallocation of most control records).