> 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