From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Re: Imporved cons representatoin in guile Date: Fri, 10 Jul 2015 13:37:53 +0200 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a113634fa72c738051a83cdb4 X-Trace: ger.gmane.org 1436528281 21875 80.91.229.3 (10 Jul 2015 11:38:01 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 10 Jul 2015 11:38:01 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Jul 10 13:38:01 2015 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZDWcy-00049Y-8S for guile-devel@m.gmane.org; Fri, 10 Jul 2015 13:38:00 +0200 Original-Received: from localhost ([::1]:44177 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDWcx-00027o-Bg for guile-devel@m.gmane.org; Fri, 10 Jul 2015 07:37:59 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59277) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDWct-00027i-SJ for guile-devel@gnu.org; Fri, 10 Jul 2015 07:37:57 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZDWcs-0007Uz-LT for guile-devel@gnu.org; Fri, 10 Jul 2015 07:37:55 -0400 Original-Received: from mail-pd0-x22b.google.com ([2607:f8b0:400e:c02::22b]:32823) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDWcs-0007Ur-5o for guile-devel@gnu.org; Fri, 10 Jul 2015 07:37:54 -0400 Original-Received: by pdbqm3 with SMTP id qm3so39296623pdb.0 for ; Fri, 10 Jul 2015 04:37:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=adrzUWEj2LxdrrekQxK3/vG0GynRiNWS7o2TjC0610o=; b=dWwn8fst7649lFQ7EXbbiVEjXGVe/0BT6AfFkhgvlsQU+e8eNxReG9hLjwCHIpPbWn xt5rtBnK5+glkyH5G8eiCck6fDEOZ52i58x9kZiv4Gl5rzWEgm2ZyOYKCGu+TPL2nJZ3 C3IwIy9LMKQEMhQ741Q8N3Tn/vr5OzrFO8/jDWfpl3YBcGuwTdaezpp0XPdGg0xpC5lE gJ8WA0k+QDvwhWB7k1Evn0HAzUdqeYKWSd0To3BUmPaMiZ0KfKtxp0NUo/34E/6mVYcn BRZElIecxIuBGJreVjbVkem/MfW21fUlR+FdOpQpdzjiDYkFL6htm1KUGmxwBFlHrUG6 9uIg== X-Received: by 10.66.65.138 with SMTP id x10mr42004991pas.15.1436528273431; Fri, 10 Jul 2015 04:37:53 -0700 (PDT) Original-Received: by 10.70.78.132 with HTTP; Fri, 10 Jul 2015 04:37:53 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400e:c02::22b X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 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-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:17758 Archived-At: --001a113634fa72c738051a83cdb4 Content-Type: text/plain; charset=UTF-8 I managed to push the send button prematurey, Here is the code i think that would be needed SCM SCM_CAR(SCM x) SCM *pt = GET_REFERENCE(x) scm_t_bits val = SCM_UNPACK(*pt) & SCM/2; (Mask out the first half) if(1 & val == 0) //THIN { if(val & 6 == 0) //non emediate e.g. a pointer { int64 delta = promote_signed_ptr(val); return UNREF(pt + delta); } if(val & 2 == 1) // integer { SCM_PACK(return promote_signed(val)) } return SCM_PACK(val) } fat version of SCM comes here. To note is that indeed we do get a more complex code here. But on the other hand the extra logic is bit twiggelin and compiled using the cpu registers only at most a SCM_CAR will take twice the time. A SCM_CDR on the other hand need to take in two SCM and is probably as fast or faster. On Fri, Jul 10, 2015 at 1:20 PM, Stefan Israelsson Tampe < stefan.itampe@gmail.com> wrote: > Hi, > > I was complentating the cons cells in guile an was wondering if we could > pack our cons cells better than today. So this is some notes about this. > > Currently if x is a cons cell we have the relation > x -> [SCMCAR,SCMCDR] > > This is really neat and makes guiles conses quite compact e.g. a vector y > of two elements is > y -> [SCMTAG,SCMV1,SCMV2], where SCMTAG containes the datatype tag and > length of the > vector. > > To compress even further we need a way to could use > x ->[SCM/2/SCM/2], witt SCM/2 the same tagging half the size as the normal > SCM with the interpretation that if > SCM/2 is a non emediate then it starts with 00 and is then interpreted as > a signed integer i and the real adress is x + i, e.g. a relative adress > regarding. > > We of cause must also add a fat cons cell of the form > x -> [Tag,X,Y] for the case when SCM/2 is not fitting. Currently I can't > see this beeing common. But > if we later makes floating point represented via nan boxing e.g. stored > directly in a 64bit value then > the cons cell will be mostly fat and there would be a speed reduction > using cons cells. On the other hand there has been a considerable speed. > > There is a final sematic case that needs to be fixed. if we do a setcar on > a thin cons cell and the cell > then becomes fat, we need to create the following > > x -> oldthin -> newfat > > e.g. we need to add a pointer type with the meaning of automatically > follow the pointer if we encounter it. then oldthin is also tagging a > variant of a cons cell. It is possible to keep it slim > in the code that all fat cons cells is represented like that. > > How would a SCM_CAR be like? > > SCM SCM_CAR(SCM x) > if(THIN(x)) > { > > } > > > > > > > --001a113634fa72c738051a83cdb4 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I managed to p= ush the send button prematurey,

Here is the cod= e i think that would be needed
SCM SCM_CAR(SCM x)
= =C2=A0 =C2=A0SCM *pt =3D GET_REFERENCE(x)
=C2=A0 =C2=A0scm_t_bits val =3D SCM_UNPACK(*pt) & SCM/2= ; (Mask out the first half)
=C2=A0 =C2=A0if(1 & val =3D=3D 0) //THIN
=C2=A0 =C2=A0 =C2=A0 {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if(val & 6 =3D=3D = 0) //non emediate e.g. a pointer
=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 int64 delta =3D promote_signed_ptr(val);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 return UNREF(pt + delta);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if(val & 2 =3D= =3D 1) =C2=A0 // integer
= =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 S= CM_PACK(return promote_signed(val))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return= SCM_PACK(val)
=C2=A0 =C2= =A0 =C2=A0 }
=C2=A0 =C2=A0=
=C2=A0 =C2=A0 =C2=A0fat v= ersion of SCM comes here.
=
To note is that indee= d we do get a more complex code here. But on the other hand the extra logic= is bit twiggelin and compiled using the cpu registers only at most
a SCM_CAR will take twice the tim= e. A SCM_CDR on the other hand need to take in two SCM and is probably as f= ast or faster.=C2=A0

On Fri, Jul 10, 2015 at 1:20 PM, Stefan Israelsson Tampe <= span dir=3D"ltr"><stefan.itampe@gmail.com> wrote:
Hi,

I was complentating t= he cons cells in guile an was wondering if we could pack our cons cells bet= ter than today. So this is some notes about this.

= Currently if x is a cons cell we have the relation
x -> [SCMCA= R,SCMCDR]

This is really neat and makes guiles con= ses quite compact e.g. a vector y of two elements is
y -> [SCM= TAG,SCMV1,SCMV2], where SCMTAG containes the datatype tag and length of the=
vector.

To compress even further we nee= d a way to could use
x ->[SCM/2/SCM/2], witt SCM/2 the same ta= gging half the size as the normal SCM with the interpretation that if
=
SCM/2 is a non emediate then it starts with 00 and is then interpreted= as a signed integer i and the real adress is x + i, e.g. a relative adress= regarding.

We of cause must also add a fat cons c= ell of the form
x -> [Tag,X,Y] for the case when SCM/2 is not = fitting. Currently I can't see this beeing common. But
if we = later makes floating point represented via nan boxing e.g. stored directly = in a 64bit value then
the cons cell will be mostly fat and there = would be a speed reduction using cons cells. On the other hand there has be= en a considerable speed.

There is a final sematic = case that needs to be fixed. if we do a setcar on a thin cons cell and the = cell
then becomes fat, we need to create the following
=
x -> oldthin -> newfat

e.g. w= e need to add a pointer type with the meaning of automatically follow the p= ointer if we encounter it. then oldthin is also tagging a variant of a cons= cell. It is possible to keep it slim
in the code that all fat co= ns cells is represented like that.

How would a SCM= _CAR be like?

SCM SCM_CAR(SCM x)
=C2=A0 = =C2=A0if(THIN(x))
=C2=A0 =C2=A0 =C2=A0 {

=C2=A0 =C2=A0 =C2=A0 }



<= div>



--001a113634fa72c738051a83cdb4--