[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://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20090522/8af5d59f/attachment.htm>
More information about the Gambit-list
mailing list