One Shot Continuations

Guile has adjustable stacks and one thing that struck me when implementing generators in python on guile with the help of delimited continuations are that the overhead is pretty high as one need to tear down store, reload and tear up the stack for it. If you apply the continuation only once this should not needed if we allow the stack to be a list of stacks with clear interfaces between them, where we hock in a new "thread". This means that when starting a continuation we create an interface on the stack and then grow the stack from there just as before. When we leave the stack but want to store it to reload it later we do not copy any stack at all but just unwind the stack object. This process works excellently for python's generators as those are just of this "one shot" kind. To use these we need to change guile quite a lot and I have done a small effort to at least get to the level where I can demo it's usefulness and as a result I sped up generator iteration by a factor of 7X for a small trivial iterator. This means that if the stack is larger we would expect even greater speed up. Another application is fibers and increase the speed for that project. Fibers also make use of one shot continuations and I expect a similar speed increase there if the actual reinstating uninstating is the bottle neck. Finally prolog program compilation can be greatly simplified and also most likely a speed increase is quite possible. To really get this into guile means more work than just copy my approach. There are multiple possibilities to implement one shot continuations and it is not trivial. Look at this offer as a way to argue that one of the best spent time to improve guile is to implement one shot continuations (in some way). Anyhow the code is private atm as I do not want to put up a whole clone of the guile project on gitlab and would prefer to work in a wip branch of guile proper if possible in order to share.

Work left is to make these one shot continuations work well with ordinary (delimited) continuations.

Anyhow here is the high level interface,

;; Make a generator out of a function (define (f yield) code ...)
;; the initiation of the new stack is done when the returned thunk
;; is called and then the iterator can start
(define (make-generator f)
  (lambda ()
    ;; make the passable stack (one shot continuation) that will be
    ;; link on the current stack
    (let ((x (mk-pause-stack)))
      ;; start is will return differently
      ;; much like UNIX forks
      (let ((k (start x)))
        (if (eq? k (i-child))
            ;; We are in the child process
              ;; we just return from here as the initiation is just to set
              ;; up the new stack and wait for the iteration to start

              ;; kludge to be able to unwind the stack without
              ;; bugging crashes in case off an error
                (lambda () (values))
                (lambda ()
                  ;; call the iteration function
                  (f x)
                  (return x 'finished))
                (lambda ()                
                  (leave x))))

And a simple example to use this generator framework (I am now are testing this out in python-on-guiles generators)

(define G
    (lambda (I)
      (let lp ((i 0))
        (when (< i 100000000)
          (return I i)
          (lp (+ i 1)))))))

(define (test)
  (let ((I (G)))
    (let lp ((s 0))
      (let ((ret (next I)))
        (if (eq? ret 'finished)
             (lp (+ s ret)))))))

time (test)  
$1 = 4999999950000000
;; 1.590144s real time, 1.589888s run time.  0.000000s spent in GC.

We see that we can do 75M iterations per seconds around 2.5X-3X slower than the fastest way to run this loop in guile which is pretty fast (faster than CPython's generators) Expect that using delimited continuations you would end up around 7X slower.

I plan to see if these can by used in my guile-log projectand if it will speed up both execution and compilation.