[gambit-list] Viewing CPS expansion?

Taylor R Campbell campbell at mumble.net
Fri May 22 15:10:02 EDT 2009

   Date: Fri, 22 May 2009 08:07:26 -0700
   From: "D.McClain" <dbm at asyrmatos.com>

   I have speculated for some time now too, after experiments with CPS  
   based compilers on a number of occasions, that the slowdown must be  
   due to two things:

   1. All functions are now forced to accommodate the continuation  
   parameter, whereas before a large majority of functions where niladic  
   or unary operations,

   2. The creation of the continuation arguments requires the production  
   of a closure, which is inherently somewhat expensive.

   My own work has consistently shown a 30% slowdown, independent of  
   actual language of implementation -- be it Scheme, Lisp, or OCaml.

The use of CPS as an intermediate representation in a compiler is a
red herring.  It doesn't make a general difference in the performance
of programs that the compiler compiles; it makes a difference only in
the convenience of writing the compiler, by putting the compiler data
structures into a simpler form.  Two compilers can produce the same
output for any given input even if one uses CPS as an intermediate
representation and the other uses a completely direct style, or ANF,
or SSA, or what-have-you.  The use of CPS as an intermediate
representation moreover has no bearing on the performance of CWCC or
the representation of reified continuations at run-time.

If you observed a difference in performance between two compilers of
which one uses CPS and the other does not, then you observed a
difference other than the intermediate representation.  For example,
if you start with a compiler C, and then construct a compiler C' that
first CPS-converts a program and then applies compiler C to the CPS
form of the program, it will probably be the case that compiler A'
generates worse code.  Compilers often make stronger assumptions about
continuations than about other procedures, by which continuations can
be made less expensive than ordinary procedures; thus if you give a
compiler a program in which continuations are not distinguished from
user procedures, it can't (easily) make these assumptions, and will be
forced to generate worse code for continuations than it would have
generated for the original direct-style program.

The two points that you observed are inherent in any implementation of
a sequential programming language with nested procedure calls.  Every
procedure must take a continuation and every continuation must be
allocated somewhere; usually this happens in a region of memory called
the stack, because continuations as a data structure behave in a
stack-like manner most of the time.  This is also why it is a trifle
silly to say that a programming language `has continuations' -- any
sequential programming language the concept; what most lack is the
ability of programs to reify continuations.  But this is not a reason
why the compilers you tested performed differently -- every compiler,
whether it use CPS or another intermediate representation, must
conceptually add a continuation parameter to each procedure and
allocate storage for continuation environments for each nested
procedure call.

More information about the Gambit-list mailing list