From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Re: Pausable continuations Date: Thu, 10 Feb 2022 16:19:16 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000db7c3e05d7ab796d" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="33952"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Thu Feb 10 18:36:08 2022 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nIDMV-0008dx-Sm for guile-devel@m.gmane-mx.org; Thu, 10 Feb 2022 18:36:07 +0100 Original-Received: from localhost ([::1]:41266 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nIDMU-0001ex-S1 for guile-devel@m.gmane-mx.org; Thu, 10 Feb 2022 12:36:06 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:48128) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nIBEL-0001Xa-4k for guile-devel@gnu.org; Thu, 10 Feb 2022 10:19:36 -0500 Original-Received: from [2607:f8b0:4864:20::432] (port=44015 helo=mail-pf1-x432.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nIBEH-00036C-4n for guile-devel@gnu.org; Thu, 10 Feb 2022 10:19:30 -0500 Original-Received: by mail-pf1-x432.google.com with SMTP id d187so10773763pfa.10 for ; Thu, 10 Feb 2022 07:19:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=Ziu4xyac5O608d8VvEe+qF34EJF0PfeVsVKuD/1uSII=; b=ADFDVAUXVk4aLmVqY6g4FiEW3WJEE+1xkFHjFyH0HXh6wLq/61czGTo2ihYb8x2Qui bgOrtCZdMboI1gibHXL86IPx2STFovJyn5TwdyGqbIvq7EHp1IlgUjsH9/vbBga5JouK 97hGtqDCH9TkuNbKhMh2oR2X8jvhmam8Q3iEaHNfSvWO2nc5aJShFV3cAE/ck+6amdZp UMheiXe3bzd0WpAp3SBOhsZ2qp8sX+klYwOv7Via/nzh4UFpcGUKahtlMaKzjn0zQnRA 7ZOKxYxkhqDlla6tN7Waj7Y+V46lY7xyjrOnpYE2QTfhM1ff4/TaeFIKYMgzpXNZQ532 iw7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=Ziu4xyac5O608d8VvEe+qF34EJF0PfeVsVKuD/1uSII=; b=0YtPbaElEQb/ydESKYvV+Ue4QIpxwnxNYNItF/+SezMxSrrqus1UzCdlbdJEnurulm 5dR+Larhp0ZgMdLJHwTZUnN2y3IzJBsEPdiXUjZBN7aMhAs2Y+uXj0mGSA05z7b0wOCj cinjCsfWhS9I2hadomGvIfvnZgtDWsNd0iIXOSX1TAjHGMiNHBVGQEga0nNWmbNDhEGl EBh3M2hncwJd534QDW5UTWz4mDBDLCPAuP0TTug9zaapCJaelVXtvvwHDhMBxVt+/o3Z nTQchT2hoMLBwV8etZr+MxBCaO8GjQ1pz9lbIKfLGTV9LBBno463x6vOsUaLAF84tT/f stFw== X-Gm-Message-State: AOAM531EOv80VdkrxGmT3PeBDGK3MlTnBec9+vHpg0M92+qBZVBH2ttg Qps/w5X2KNubS4KKKnASFMfvZqM5TYf9W7joxdZ0ANkY/Ak= X-Google-Smtp-Source: ABdhPJyGqK0HWzLl3puKyUJKcZYsGsRMULEHCnk2huXzdKbXkyE5prEA9HcDt9jAESlFEp/7k43b7Z/tfBzcOdD9Lh4= X-Received: by 2002:a63:6c88:: with SMTP id h130mr6546662pgc.357.1644506367358; Thu, 10 Feb 2022 07:19:27 -0800 (PST) In-Reply-To: X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::432 (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::432; envelope-from=stefan.itampe@gmail.com; helo=mail-pf1-x432.google.com X-Spam_score_int: -12 X-Spam_score: -1.3 X-Spam_bar: - X-Spam_report: (-1.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, PDS_HP_HELO_NORDNS=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:21088 Archived-At: --000000000000db7c3e05d7ab796d Content-Type: text/plain; charset="UTF-8" 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 > > ( (x cc) goal1 goal2) > :: (cc (goal1 (goal2 x)) > > ( (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 , > > (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? > > > > > > > > > > > > . > > > --000000000000db7c3e05d7ab796d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I did some benchmark, consider this code below. Let's = turn off the jit. Then
a 20M loop using normal delimited=C2=A0continuat= ions yields,

;; 7.866898s real time, 14.8092= 25s run time. =C2=A09.652291s spent in GC

With a pausing continuation or generator we end up with,
;; 0.965947s real time, 0.965588s run time. =C2=A00.00000= 0s 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. =C2=A09.560317s spent in GC.

So we can't really get a= ny speedup help from guile's jit here. The paused jit version is not av= ailable as I have not figured out how to do this jet.

(define prompt (list 1))
(define (f)
=C2=A0 (let lp ((i 0= ))
=C2=A0 =C2=A0 (when (< i 20000000)
=C2=A0 =C2=A0 =C2=A0 (begin<= br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 (abort-to-prompt prompt)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 (lp (+ i 1))))))
=C2=A0
(define (test2)
=C2=A0 (let= lp ((k f))
=C2=A0 =C2=A0 (call-with-prompt prompt k lp)))



On Thu, Feb 10, 2022 at 2:07 PM Stefan Isra= elsson Tampe <stefan.itampe@g= mail.com> wrote:
Consider a memory barrier=C2=A0idiom constructed f= rom=C2=A0
0, (mk-stack)
1. (enter x)
2. (pause x)
3. (leave x)

The idea is that we crea= te a separate stack object and when entering it, we will swap the current s= tack with the one in the argument saving the current stack in x=C2=A0 and b= e in the 'child' state and move to a paused position in case of a p= ause, when pausing stack x, we=C2=A0will return to where after where entere= d saving the current position in stack and ip, and be in state 'pause&#= 39; and when we leave we will be in the state=C2=A0'leave and move to= =C2=A0the old stack, using the current
ip. At first encounter the= function=C2=A0stack frame is copied over hence there will be a fork limite= d to the function=C2=A0only.

This means that we es= sentially can define a generator as
(define (g x)
=C2= =A0 (let lp ((n 0))
=C2=A0 =C2=A0 (if (< n 10)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 (begin
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0(pause x)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lp = (+ n 1))))))

And use it as
(define (test= )
=C2=A0 =C2=A0 (let ((x (mk-stack)))
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 (let lp ()
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(c= ase (enter x)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0((pause)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0(pk 'pause)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lp))
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ((child)
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(g x)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(leave x))))))))
=
A paused or leaved stack cannot be paused, an entered=C2=A0s= tack cannot be entered and one cannot leave a paused stack, but enter a lea= ved stack.

Anyhow this idea is modeled like a fork= command instead=C2=A0of functional and have the benefit over delimited con= tinuations that one does not need to copy the whole stack and potentially s= peed up generator=C2=A0like constructs. But not only this,=C2=A0writing eff= icient prolog code is possible as well. We could simplify a lot of the gene= ration of prolog code, speed it up and also improve compiler speed of prolo= g code significantly.

How would we approach the=C2= =A0 prolog code.=C2=A0The simplest system is to use return the=C2=A0
<= div>alternate pause stack when succeeding things becomes very simple,
=

x=C2=A0 =C2=A0=3D stack to pause to in case of failure<= /div>
cc =3D the continuation

(<and> (x = cc)=C2=A0 goal1 goal2)=C2=A0=C2=A0
=C2=A0 =C2=A0 =C2=A0:: (cc (go= al1 (goal2 x))

(<or >=C2=A0 =C2=A0(x cc)=C2= =A0 goal1 goal2)=C2=A0=C2=A0
=C2=A0 =C2=A0 ::=C2=A0 (let ((xx (mk= stack)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(case (e= nter xx)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0((child)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 (cc (goal2 xx)))

=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ((pause)
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(cc (goal2 x)))))
Very elegant, and we also can use some heuristics to store alr= eady made stacks when=C2=A0
leaving a stack and reuse at the next= enter which is a common theme in prolog,

Anyhow w= e have an issue, consider the case where everythings succeds=C2=A0forever. = Then we will blow the stack . There is no concept=C2=A0of tail calls here. = So what you can do is the following for an <and>,

(let ((xx (mk-stack)))
=C2=A0 =C2=A0 (case (enter xx)
=
=C2=A0 =C2=A0 =C2=A0 ((child)
=C2=A0 =C2=A0 =C2=A0 =C2=A0(go= al1 x (lambda (xxx) (pause xx xxx)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0<= /div>
=C2=A0 =C2=A0 =C2=A0 ((pause xxx)
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0(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 concep= t.=C2=A0

The drawback with this is if a function u= ses a lot of stack, it will be a memory hog.

WDYT?=





=





=

.

=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0=C2=A0
--000000000000db7c3e05d7ab796d--