Re: Imporved cons representatoin in guile

[Stefan Monnier <monnier@iro.umontreal.ca>]

> 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