[gclist] Memory cheats and VM (was Counting on one thumb)

[Henry G. Baker]

David Chase wrote:

> 1. This stuff has been studied before in other contexts; there's 
> Stoye's 1-bit hardware reference counts, for instance, and the SETL 
> project produced a number of papers on analysis and optimization 
> of copying and reference-counting. 

Most people who reference Collins's original 1960 paper on reference
counts haven't read it.  If you do read it, you will find that his
actual scheme was more clever than others' reports of it.  Objects
that are uniquely referenced (count=1) do _not_ have a reference count
field allocated, but the pointer points 'directly' to the object.
Only when the reference count is incremented is a 'header' node with
space for a reference count allocated, and the object is _indirectly_
referenced after this.  While this scheme would appear to be expensive
without hardware help, modern languages with 'unique' types, and
compilers with the ability to determine unique types could get much of
the advantage from this scheme.

Collins's scheme clearly saves mucho memory in a system where most
objects are singly (uniquely) referenced, and allows for multiply
referenced objects to have 'full' (non-sticky) reference counts.

-- 
Henry Baker
www/ftp directory:
ftp.netcom.com:/pub/hb/hbaker/home.html