[gambit-list] Viewing CPS expansion?

D.McClain dbm at asyrmatos.com
Fri May 22 15:18:49 EDT 2009


Very interesting... I would like to see your claims backed up by  
actual measurements.

Dr. David McClain
Sr. VP, Embedded Systems
Asyrmatos Inc.
Boston & Tucson
phone: 	520-529-2437
cell: 	520-390-3995
web: 	www.asyrmatos.com
e-mail:	dbm at asyrmatos.com




On May 22, 2009, at 12:10, Taylor R Campbell wrote:

>    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.
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://webmail.iro.umontreal.ca/pipermail/gambit-list/attachments/20090522/8af5d59f/attachment.html 


More information about the Gambit-list mailing list