Date: Fri, 22 May 2009 08:07:26 -0700 From: "D.McClain" dbm@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.