Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #775 > unrolled thread

basic question about cps

Back to article view | Back to comp.compilers

Contents

  basic question about cps n.oje.bar@gmail.com - 2012-11-12 11:05 -0800
    Re: basic question about cps torbenm@diku.dk (Torben Ægidius Mogensen) - 2012-11-14 11:25 +0100
    Re: basic question about cps Stefan Monnier <monnier@iro.umontreal.ca> - 2012-11-14 11:13 -0500
      Re: basic question about cps n.oje.bar@gmail.com - 2012-11-21 09:27 -0800

#775 — basic question about cps

Hi, I have a basic question about writing a compiler using continuation-passing style
as an intermediate language.

It seems to me that if one performs the cps transformation one is left
with many 'computed' calls (that is call to variables holding
procedure values, namely, the continuation). It seems that compiling
such 'computed' calls would be much slower than compiling 'direct'
calls to known procedures.

Question:

1. Is this assumption valid?
2. If it is, then it seems that cps is not very useful without some
non-trivial control flow analysis...??

Please excuse me if this question is very basic.

Thanks!
Nicolas
[Yes, it assumes a reasonbly good optimizer. -John]

[toc] | [next] | [standalone]

#780

n.oje.bar@gmail.com writes:

> Hi, I have a basic question about writing a compiler using
> continuation-passing style as an intermediate language.
>
> It seems to me that if one performs the cps transformation one is left
> with many 'computed' calls (that is call to variables holding
> procedure values, namely, the continuation). It seems that compiling
> such 'computed' calls would be much slower than compiling 'direct'
> calls to known procedures.
>
> Question:
>
> 1. Is this assumption valid?
> 2. If it is, then it seems that cps is not very useful without some
> non-trivial control flow analysis...??

There are indeed a lot of calls when you do CPS transformation, but
the majority of these are tail-calls, so if you do tail-call
optimisation, you are not so bad off.  Also, while closures in general
need to be heap allocated, continuation closures can be stack
allocated (unless they are captured with call/cc or similar
constructs).

Depending on which formulation of CPS transformation you use, you may
also end up with a lot of so-called "administrative redexes", which
you can reduce at compile time.

With the above "optimisations", the code you get is very similar to
"normal" compiled code that uses a stack of activation records.  The
advantage of using CPS is that inlining and other transformations are
simpler on the CPS form than in traditional intermediate code.  You
also get some of the dataflow-analysis advantages that SSA form gives
you.

A good place to get in-depth coverage of CPS as an intermediate form
is Andrew Appel's book "Compiling with Continuations".  I don't think
it is in print anymore, but you can probably get it at most CS
libraries.

	Torben

[toc] | [prev] | [next] | [standalone]

#781

> It seems to me that if one performs the cps transformation one is left
> with many 'computed' calls (that is call to variables holding
> procedure values, namely, the continuation).

Yes.  Every additional "computed call" (aka indirect call) corresponds
to a "return" in the non-CPS version of the code.

> It seems that compiling such 'computed' calls would be much slower
> than compiling 'direct' calls to known procedures.

That's the wrong comparison: the non-CPS version wouldn't see direct
calls there, but would see `return's instead.

Also, you're talking about "compiling" being "slower": are you really
concerned about the speed of compilation, or the speed of the
generated code?

The performance of "return" versus "indirect call" depends on many
factors, but it's probably important to try and make sure that the
"return-like indirect calls" are compiled to code which the CPU
recognizes as "some sort of return", in order for the
branch-prediction to work better (CPUs keep an internal&hidden stack
to try and predict the destination of return instructions).

        Stefan

[toc] | [prev] | [next] | [standalone]

#782

On Wednesday, November 14, 2012 4:13:52 PM UTC, Stefan Monnier wrote:
> > It seems to me that if one performs the cps transformation one is left
> > with many 'computed' calls (that is call to variables holding
> > procedure values, namely, the continuation).
>
> Yes.  Every additional "computed call" (aka indirect call) corresponds
> to a "return" in the non-CPS version of the code.
>
> > It seems that compiling such 'computed' calls would be much slower
> > than compiling 'direct' calls to known procedures.
>
> That's the wrong comparison: the non-CPS version wouldn't see direct
> calls there, but would see `return's instead.

> Also, you're talking about "compiling" being "slower": are you really
> concerned about the speed of compilation, or the speed of the
> generated code?

> The performance of "return" versus "indirect call" depends on many
> factors, but it's probably important to try and make sure that the
> "return-like indirect calls" are compiled to code which the CPU
> recognizes as "some sort of return", in order for the
> branch-prediction to work better (CPUs keep an internal&hidden stack
> to try and predict the destination of return instructions).

Thanks very much for all your replies!

Best regards,
Nicolas

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web