[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Imporved cons representatoin in guile
From: |
Stefan Monnier |
Subject: |
Re: Imporved cons representatoin in guile |
Date: |
Fri, 10 Jul 2015 13:31:02 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) |
> 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