unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
To: guile-devel <guile-devel@gnu.org>
Subject: Re: Pausable continuations
Date: Sun, 13 Feb 2022 10:34:43 +0100	[thread overview]
Message-ID: <CAGua6m2uCKzJPspJb=iR7CAgq_QxSWE7QJFg74tDO6t7XBciMQ@mail.gmail.com> (raw)
In-Reply-To: <CAGua6m2XA_ezy0RKXja4FqdUD5-VdQjW=wM4Y9VGZrm1-_GwOA@mail.gmail.com>

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

The case with A simple loop of 20M operations are now down to 0.3 s that's
almost 20X improvements over
the best delimited continuation example (6s). Cpython takes 0.5s!

On Fri, Feb 11, 2022 at 1:10 PM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> Hmm, I can improve the delimited continuation speed slightly by doing the
> below code
>
>
> (define prompt (list 1))
> (define (f2)
>   (let lp ((i 0))
>     (when (< i 20000000)
>       (begin
>         (abort-to-prompt prompt)
>         (lp (+ i 1)))))
>   #f)
>
>  ; 5.906402s real time, 12.297234s run time.  8.894807s spent in GC.
>
> So we are actually around 12X faster.
>
> (define (test2)
>   (let lp ((k f2))
>     (let ((k (call-with-prompt prompt k (lambda (k) k))))
>       (if k (lp k) #f))))
>
>
> On Fri, Feb 11, 2022 at 1:06 PM Stefan Israelsson Tampe <
> stefan.itampe@gmail.com> wrote:
>
>> 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: 9256 bytes --]

  parent reply	other threads:[~2022-02-13  9:34 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-02-10 13:07 Pausable continuations Stefan Israelsson Tampe
2022-02-10 15:19 ` Stefan Israelsson Tampe
2022-02-11 12:06   ` Stefan Israelsson Tampe
2022-02-11 12:10     ` Stefan Israelsson Tampe
2022-02-11 18:56       ` Vijay Marupudi
     [not found]         ` <CAGua6m24aa+goaczoX-UaDCsGnKEAE6sBfH8Xx-2ks0UjOyvUQ@mail.gmail.com>
2022-02-13  9:34           ` Fwd: " Stefan Israelsson Tampe
2022-02-13  9:34       ` Stefan Israelsson Tampe [this message]
2022-02-13 10:27 ` Mikael Djurfeldt
2022-02-13 10:31   ` Stefan Israelsson Tampe
2022-02-17  6:07     ` Stefan Israelsson Tampe
2022-02-17 16:37       ` Vijay Marupudi

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/guile/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAGua6m2uCKzJPspJb=iR7CAgq_QxSWE7QJFg74tDO6t7XBciMQ@mail.gmail.com' \
    --to=stefan.itampe@gmail.com \
    --cc=guile-devel@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).