Imporved cons representatoin in guile

Imporved cons representatoin in guile

[Stefan Israelsson Tampe]

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

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))
      {

      }

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

Re: Imporved cons representatoin in guile

[Stefan Israelsson Tampe]

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

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))
>       {
>
>       }
>
>
>
>
>
>
>

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

Re: Imporved cons representatoin in guile

[Stefan Monnier]

> 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

Note that this is not specific to cons-cells.  I've been meaning to try
and experiment with such a box-compression scheme for several years, but
it never got high enough on the todo list (tho I did get a student to
look at it, but he gave up his MSc before getting far enough).

Note that because of set-car! and set-cdr! you need those SCM/2 fields
to be able to hold *any* value.  So an SCM/2 field can hold 3 different
things:
- an immediate value.
- a compressed reference, typically using relative addressing, where
  you'll want the GC to know about them, so it tries to keep/bring
  related objects near each other.
- a "proxy reference", which identifies a full SCM cell which contains
  the actual value.  It can be a relative pointer or an index in some
  table.

I imagined it working by dividing the heap into zones whose size
corresponds to the "reachability" of an SCM/2 relative pointer (so an
SCM/2 field can point to any other object within the same zone without
going through a proxy), and have each zone come with an array
of proxies.

I was thinking about this mostly in the context of 64bit boxes where the
SCM/2 references would basically only ever need to go through proxies once
the process size passes the 4GB limit.  But for small-memory systems
using 32bit pointers, the same idea might work as well.

Interestingly, this split into zones+proxies would also allow the GC to
operate on each zone independently (you don't need to trace the objects
in the other zones, only their proxies).


        Stefan

Re: Imporved cons representatoin in guile

[Stefan Israelsson Tampe]

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

I think that getting cons cells to work with this is the easiest. With this
one can try to benchmark the change and investigate.

I think that I know enough of guile internals to make this work in a
branch. I can then post for anybody to try out. If it is a good idea to try
this let me know and I take a stab at it.

I think that getting this to work on more datastructures is a bit tricky.
One could for example use the current markings only on the proxied
datastructures but then one needs a huge commit to make it work.

Maybe you suggested this, But I think that the best would be to use two gc
memory regions one for the current mark system and one for the compressed
data structures where relative references is correctly followed. The
drawback with this is that we need to double the thread caches of lists of
free memory blocks. I know that this works cause I dabbled with multiple
memory types in guile-log when making the prolog variables gc-able. This
approach also enables an incremental development transitions of
datastructures suitable for compression.

> you'll want the GC to know about them, so it tries to keep/bring
> related objects near each other.

does bdw-gc do this on current cons cells?

> I imagined it working by dividing the heap into zones whose size
> corresponds to the "reachability" of an SCM/2 relative pointer (so an
> SCM/2 field can point to any other object within the same zone without
> going through a proxy), and have each zone come with an array
> of proxies.

To make this work in a good way is quite difficult. You need bdw-gc to
group the free memory in relation to ther allocation block in order to
simulate the demon of Maxwell if this is not currently done you need quite
a hack into the bdw-gc code to make it work.

Especially constants are loaded via installing pages and here I suspect
that we can get problems with a lot of references going out of bounds. When
it comes with the heap memory from the gc would that not mostly be within
30 bit relative adresses? anyhow I agree for large programs of aroung 1GB
we would start to see more and more proxied datastructures ending with
somthing that is unoptimal. I imagined that any solution to guile that
incorporated a compresion feature would need the possibility via a
configuration option to use the old uncompressed system. Especially it
would be questionable to have large datastructures like vectors to be
compressed cause the although small but positive probability of referencing
constants.


>I was thinking about this mostly in the context of 64bit boxes where the
>SCM/2 references would basically only ever need to go through proxies once
>the process size passes the 4GB limit.  But for small-memory systems
>using 32bit pointers, the same idea might work as well.

Yeah, the information slack is quite high on these Boxes we need to make
sure not to force this feature on the 32bit ones.

> Interestingly, this split into zones+proxies would also allow the GC to
> operate on each zone independently (you don't need to trace the objects
> in the other zones, only their proxies).

Not sure I follow, but marking a proxy implies marking in the other zone so
I can't see this atm.

What is not too difficult is to be able to have say 10 memory regions and
then when you work with scheme code of large applications you could do,

(with-mem-region 8 thunk)

With the meaning that all allocation comes from region 8. This is a
complexity code wise, but could be something that can be profiled out and
just used on the hot code paths and datastructures. Now I'm not sure how
well bdw-gc handles this but I think that controlling the adress ranges of
allocated blocks is a relative small change to the code base, the issue
here is probably portability.

Ok That's all for now,
Cheers!



On Fri, Jul 10, 2015 at 7:31 PM, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> > 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
>
> Note that this is not specific to cons-cells.  I've been meaning to try
> and experiment with such a box-compression scheme for several years, but
> it never got high enough on the todo list (tho I did get a student to
> look at it, but he gave up his MSc before getting far enough).
>
> Note that because of set-car! and set-cdr! you need those SCM/2 fields
> to be able to hold *any* value.  So an SCM/2 field can hold 3 different
> things:
> - an immediate value.
> - a compressed reference, typically using relative addressing, where
>   you'll want the GC to know about them, so it tries to keep/bring
>   related objects near each other.
> - a "proxy reference", which identifies a full SCM cell which contains
>   the actual value.  It can be a relative pointer or an index in some
>   table.
>
> I imagined it working by dividing the heap into zones whose size
> corresponds to the "reachability" of an SCM/2 relative pointer (so an
> SCM/2 field can point to any other object within the same zone without
> going through a proxy), and have each zone come with an array
> of proxies.
>
> I was thinking about this mostly in the context of 64bit boxes where the
> SCM/2 references would basically only ever need to go through proxies once
> the process size passes the 4GB limit.  But for small-memory systems
> using 32bit pointers, the same idea might work as well.
>
> Interestingly, this split into zones+proxies would also allow the GC to
> operate on each zone independently (you don't need to trace the objects
> in the other zones, only their proxies).
>
>
>         Stefan
>
>
>

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