[MIT-Scheme-devel] speeding up CWCC

[Taylor R Campbell]

The attached patch[*] makes the ctak benchmark (v8/src/bench/ctak.scm)
faster by a factor of more than twenty when compiled, by making CWCC
avoid aborting to the interpreter when called from compiled code.  The
patch changes both the microcode and the runtime, although the patched
runtime should run on old microcodes; I changed the runtime only to
make it more tolerant of variation in the microcode's continuation
data structures.  If this looks good, I'll commit it, but not until it
has been reviewed and/or tested more thoroughly -- details below.

[*] Apply cwcc.patch with `patch -p1 < /path/to/cwcc.patch' from the
    top level of the Git repository.



I have only lightly tested this patch, but it works well enough to run
Edwin, ctak, and some other random CWCC craziness.  Here are three
issues that I'm concerned about, because I have focussed more on
making it work in real code than on verifying these properties:

1. I don't know whether the patch keeps the interpreter history data
   structures consistent.  In particular, in making the stack parser a
   little more tolerant of variation in the microcode's data
   structures, I changed its behaviour concerning history a little
   bit, because it was not obvious how to preserve the original
   behaviour.  I seldom use the interpreter history anyway, so I
   shouldn't recognize a change in its behaviour immediately if there
   were one.

2. I don't know whether the patch preserves proper tail recursion.
   The old code had a comment about an `optimization', which was
   actually needed in order to preserve proper tail recursion,
   although when mixing compiled and interpreted code, CWCC failed to
   do so anyway.  For example, the following should be an infinite
   loop that runs in a constant amount of space, bounded by the size
   of the continuation of its caller:

   (let* ((interpreted-receiver (lambda (receiver) (lambda (k) (receiver k))))
          (compiled-receiver (compile-procedure interpreted-receiver)))
     (let loop ()
       (call-with-current-continuation
         (interpreted-receiver
          (lambda (k)
            k
            (call-with-current-continuation
              (compiled-receiver (lambda (k) k (loop)))))))))

   With the old code, running this in the interpreter overflows the
   heap.  With the patch, it doesn't.

3. I am not sure whether the stack parser is still correct, or in fact
   whether it was correct before.  For example, the procedure
   STACK-FRAME/SKIP-NON-SUBPROBLEMS has a funny clause for the case
   when STACK-FRAME is a stack marker frame:

   (let loop ((stack-frame stack-frame))
     (let ((stack-frame (stack-frame/next stack-frame)))
       (and stack-frame
            (if (stack-frame/subproblem? stack-frame)
                (stack-frame/next-subproblem stack-frame)
                (loop stack-frame)))))

   Thus it appears to skip the first subproblem after a stack marker
   frame.  After an earlier version of the patch, the stack parser
   behaved strangely, until I changed the second instance of
   (STACK-FRAME/NEXT-SUBPROBLEM STACK-FRAME) to be simply STACK-FRAME.
   Moreover, making this change caused the frame for the continuation
   of (WITH-INTERRUPT-MASK ...) in

   ((compile-procedure
     (lambda ()
       (foo (bar (with-interrupt-mask interrupt-mask/all
                   (lambda (i)
                     (+ 3 (car i))))))))),

   to appear as expected, while the current version of Scheme omits
   it.

   Also, I'm not sure that conpar.scm's CONTINUATION-RETURN-ADDRESS is
   needed any longer, probably as of the v15 microcode, or perhaps as
   of the elimination of non-reentrant CWCC.  For that matter, it
   appears to be computed specifically under the assumption that CWCC
   is not properly tail-recursive.  Its value in a current version of
   Scheme is some compiled return address internal to conpar.scm which
   will presumably never turn up in any continuation except during the
   cold load when INITIALIZE-SPECIAL-FRAMES! is called.

   (In the process of patching conpar.scm, I removed some vestiges of
   v8 code, which probably doesn't affect anyone.  Interested parties
   may find those vestiges still in v8/src/runtime/conpar.scm.)

cwcc.patch
Description: Text document