Re: Pausable continuations

[Stefan Israelsson Tampe <stefan.itampe@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4788 bytes --]

I managed to make jitted code work for an example, speeds up the code up
2x. So in 1s ther is 40M ops per s
overhead in the generator construct, that's essentially 4x slower the
fastest it can do in a very simple loop. And matches
pythons generators and are 15x faster than the example code I have above.

On Thu, Feb 10, 2022 at 4:19 PM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> I did some benchmark, consider this code below. Let's turn off the jit.
> Then
> a 20M loop using normal delimited continuations yields,
>
> ;; 7.866898s real time, 14.809225s run time.  9.652291s spent in GC
>
> With a pausing continuation or generator we end up with,
> ;; 0.965947s real time, 0.965588s run time.  0.000000s spent in GC.
>
> python 3's similar generator example is executing at 0.5s for the same
> looop.
> so using delimited continuations to model pythons generators we have an
> overhead of around 15X.
>
> With jit,
> ;; 6.678504s real time, 13.589789s run time.  9.560317s spent in GC.
>
> So we can't really get any speedup help from guile's jit here. The paused
> jit version is not available as I have not figured out how to do this jet.
>
> (define prompt (list 1))
> (define (f)
>   (let lp ((i 0))
>     (when (< i 20000000)
>       (begin
>         (abort-to-prompt prompt)
>         (lp (+ i 1))))))
>
> (define (test2)
>   (let lp ((k f))
>     (call-with-prompt prompt k lp)))
>
>
>
> On Thu, Feb 10, 2022 at 2:07 PM Stefan Israelsson Tampe <
> stefan.itampe@gmail.com> wrote:
>
>> Consider a memory barrier idiom constructed from
>> 0, (mk-stack)
>> 1. (enter x)
>> 2. (pause x)
>> 3. (leave x)
>>
>> The idea is that we create a separate stack object and when entering it,
>> we will swap the current stack with the one in the argument saving the
>> current stack in x  and be in the 'child' state and move to a paused
>> position in case of a pause, when pausing stack x, we will return to where
>> after where entered saving the current position in stack and ip, and be in
>> state 'pause' and when we leave we will be in the state 'leave and move
>> to the old stack, using the current
>> ip. At first encounter the function stack frame is copied over hence
>> there will be a fork limited to the function only.
>>
>> This means that we essentially can define a generator as
>> (define (g x)
>>   (let lp ((n 0))
>>     (if (< n 10)
>>         (begin
>>            (pause x)
>>            (lp (+ n 1))))))
>>
>> And use it as
>> (define (test)
>>     (let ((x (mk-stack)))
>>         (let lp ()
>>            (case (enter x)
>>                ((pause)
>>                    (pk 'pause)
>>                    (lp))
>>                 ((child)
>>                  (g x)
>>                  (leave x))))))))
>>
>> A paused or leaved stack cannot be paused, an entered stack cannot be
>> entered and one cannot leave a paused stack, but enter a leaved stack.
>>
>> Anyhow this idea is modeled like a fork command instead of functional and
>> have the benefit over delimited continuations that one does not need to
>> copy the whole stack and potentially speed up generator like constructs.
>> But not only this, writing efficient prolog code is possible as well. We
>> could simplify a lot of the generation of prolog code, speed it up and also
>> improve compiler speed of prolog code significantly.
>>
>> How would we approach the  prolog code. The simplest system is to use
>> return the
>> alternate pause stack when succeeding things becomes very simple,
>>
>> x   = stack to pause to in case of failure
>> cc = the continuation
>>
>> (<and> (x cc)  goal1 goal2)
>>      :: (cc (goal1 (goal2 x))
>>
>> (<or >   (x cc)  goal1 goal2)
>>     ::  (let ((xx (mkstack)))
>>              (case (enter xx)
>>                  ((child)
>>                   (cc (goal2 xx)))
>>
>>                 ((pause)
>>                  (cc (goal2 x)))))
>>
>> Very elegant, and we also can use some heuristics to store already made
>> stacks when
>> leaving a stack and reuse at the next enter which is a common theme in
>> prolog,
>>
>> Anyhow we have an issue, consider the case where everythings
>> succeds forever. Then we will blow the stack . There is no concept of tail
>> calls here. So what you can do is the following for an <and>,
>>
>> (let ((xx (mk-stack)))
>>     (case (enter xx)
>>       ((child)
>>        (goal1 x (lambda (xxx) (pause xx xxx)))
>>
>>       ((pause xxx)
>>          (goal2 xxx cc))))
>>
>> This enable cuts so that a cutted and (and!) in kanren lingo will use
>> (goal2 x cc)
>>
>> And we have tail calls!
>>
>>
>> I have a non jitted version guile working as a proof of concept.
>>
>> The drawback with this is if a function uses a lot of stack, it will be a
>> memory hog.
>>
>> WDYT?
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> .
>>
>>
>>
>

[-- Attachment #2: Type: text/html, Size: 7354 bytes --]