From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Mikael Djurfeldt Newsgroups: gmane.lisp.guile.devel Subject: Re: A different stack discipline Date: Sat, 3 Nov 2018 19:49:16 +0100 Message-ID: References: <20181102191524.GB947@STATENS_laptop> Reply-To: mikael@djurfeldt.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000ba1abc0579c71cbf" X-Trace: blaine.gmane.org 1541270877 16969 195.159.176.226 (3 Nov 2018 18:47:57 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 3 Nov 2018 18:47:57 +0000 (UTC) Cc: guile-devel To: hugo@lysator.liu.se Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sat Nov 03 19:47:53 2018 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gJ0xa-0004Fb-Vd for guile-devel@m.gmane.org; Sat, 03 Nov 2018 19:47:51 +0100 Original-Received: from localhost ([::1]:56504 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gJ0zh-0006wf-ET for guile-devel@m.gmane.org; Sat, 03 Nov 2018 14:50:01 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:50044) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gJ0zP-0006wZ-B6 for guile-devel@gnu.org; Sat, 03 Nov 2018 14:49:44 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gJ0zJ-0000Tv-HP for guile-devel@gnu.org; Sat, 03 Nov 2018 14:49:41 -0400 Original-Received: from mail-it1-f174.google.com ([209.85.166.174]:51078) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gJ0zJ-0000DW-5G for guile-devel@gnu.org; Sat, 03 Nov 2018 14:49:37 -0400 Original-Received: by mail-it1-f174.google.com with SMTP id k206-v6so7576933ite.0 for ; Sat, 03 Nov 2018 11:49:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:reply-to :from:date:message-id:subject:to:cc; bh=Nud1cJVXWUtHbD4WihXOJ+j+yEIAUrlRBuV/4aeQ0UA=; b=Q9Gj8JlBFGosCX3N49g2+wptmq57WmtFgSDcuUd6LM+uTLRntvBxcEdiOSBKL9VD7G 1mVMonBflRnU1p7NNkvBKqjHHmwpVBnZ/b1z9BUHeq5jh6a+ikXLUa2LHCwJCe62P7tI akzenYulMRMygjkIjzOxpMP9jksXIrSRNVLww8KA7NqnZWWEWjZ7RPJZ+Fni0b5fYhYE tDpLJDzav81Pu9ReCgFsxWYPLR6RPRo48pOa/KEjjjotknICJa/ll8NnBxC3Fcj0+nj8 laZX8ucDNrQZ/qucotT1TVsPQGwZ4mjKWs6p6gfcqACAcvVAe4sW4MmW7bhsxrwmfrpL J9eA== X-Gm-Message-State: AGRZ1gIV5OnIKcYE0iZs9QYk/SCcwtLTaZP9fT8gboYkfY3yVaVmKYje RdP6Fw9GjGnfQc42vylPWx0qCGFdWcAURBInrLImjA== X-Google-Smtp-Source: AJdET5eirP03N35laakYADmsEmrXJUnQHg3T9fJc3ApzFXxxpheOurLJ0lFyZTQojU6B6DVcRsFCNKQk9QwFQ4LYNuY= X-Received: by 2002:a24:3688:: with SMTP id l130-v6mr1424815itl.88.1541270970963; Sat, 03 Nov 2018 11:49:30 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 209.85.166.174 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.org gmane.lisp.guile.devel:19715 Archived-At: --000000000000ba1abc0579c71cbf Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Den l=C3=B6r 3 nov. 2018 19:16 skrev Mikael Djurfeldt : > On Sat, Nov 3, 2018 at 4:30 PM Hugo H=C3=B6rnquist = wrote: > >> The section, as far as I can see, just describes a machine >> which pushes continuation instead of the PC counter to the >> stack. >> >> Also, while in theory quite nice it has the problem that >> Guile is really slow in restoring continuations, due to the >> fact that we have complete C interoperability. >> > > There's some misunderstanding here. The SICP register machine model is no= t > very different from common register machine models. There's just a > difference in how to handle subroutine calls. A short example: > > Let's first write out all operations involved in a call in a conventional > register machine: > > [...] > ; The following three micro operations consitute "call foo ()" > (sp) <- pc + offset(L1) ; NOTE the external memory access > sp <- sp - 1 > pc <- pc + offset(foo) > L1: [...] > > foo: [...] > ; the following two micro operations constitute "ret" > sp <- sp + 1 > pc <- (sp) ; NOTE the external memory access > > Now look at the call in the SICP register machine: > > [...] > continue <- pc + offset(L1) > pc <- pc + offset(foo) > L1: [...] > > foo: [...] > pc <- continue > > It is fewer operations and every operation is immediate with no memory > access. I *have* cheated since I omit a need to push the continue registe= r > onto the stack, but while this is needed at *every* call for the > conventional machine, this is only required once at the beginning of a > function in the SICP machine *unless* the function has a tail call, in > which case we don't need to push anything. So, while one can say that we > only "push around the pushes", we make gains for every tal call. > (consitute -> constitute; tal -> tail; also, when saying "this is needed" above, I was referring to the *stack pushes*, not the push of the continue register specifically) In addition to not having to push continue in functions with tail calls, we also gain for every function that do not call a subroutine. For C compatibility, we can do an ordinary call when calling C. None of this affects the restoration of continuations. Also, it does not slow down but speeds up! > --000000000000ba1abc0579c71cbf Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


=
Den l=C3=B6r 3 nov. 2018 19:16 skrev Mikael Djurfeldt <= mikael@djurfeldt.= com>:
On Sat, Nov 3, 2018 at 4:30 PM Hugo H=C3=B6rnquist <hugo@l= ysator.liu.se> wrote:
The section, as far as I can see, just de= scribes a machine
which pushes continuation instead of the PC counter to the
stack.

Also, while in theory quite nice it has the problem that
Guile is really slow in restoring continuations, due to the
fact that we have complete C interoperability.

There's some misunderstanding here. The SICP register machine m= odel is not very different from common register machine models. There's= just a difference in how to handle subroutine calls. A short example:

Let's first write out all operations involved in a= call in a conventional register machine:

=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 [...]
=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0 ; The following three micro operations consitute &quo= t;call foo ()"
=C2=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0 (s= p) <- pc + offset(L1) ; NOTE the external memory access
=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 sp <- sp - 1
=C2=A0=C2=A0= =C2=A0 =C2=A0=C2=A0=C2=A0 pc <- pc + offset(foo)
L1: =C2=A0=C2= =A0 [...]
=C2=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0
foo:=C2= =A0=C2=A0 [...]
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; the= following two micro operations constitute "ret"
= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 sp <- sp + 1
= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 pc <- (sp) ; NOTE the externa= l memory access

Now look at the call in the SI= CP register machine:

=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 [...]
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 = continue <- pc + offset(L1)
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0 pc <- pc + offset(foo)
L1:=C2=A0=C2=A0 [...]

foo:=C2=A0 [...]
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0 pc <- continue

It is fewer operati= ons and every operation is immediate with no memory access. I *have* cheate= d since I omit a need to push the continue register onto the stack, but whi= le this is needed at *every* call for the conventional machine, this is onl= y required once at the beginning of a function in the SICP machine *unless*= the function has a tail call, in which case we don't need to push anyt= hing. So, while one can say that we only "push around the pushes"= , we make gains for every tal call.

(consitute ->= constitute; tal -> tail; also, when saying "this is needed" a= bove, I was referring to the *stack pushes*, not the push of the continue r= egister specifically)

In addition to = not having to push continue in functions with tail calls, we also gain for = every function that do not call a subroutine.

For = C compatibility, we can do an ordinary call when calling C.

<= /div>
None of this affects the restoration of continuations. Also, it d= oes not slow down but speeds up!
--000000000000ba1abc0579c71cbf--