[Gcl-devel] GCL and GC

[Camm Maguire]

Greetings!  Recent developments in ACL2 have uncovered some modest GC
performance weakness in GCL at the moment.  

Traditionally, GCL GC has been strictly mark/sweep with one exception,
i.e. all cells containing pointers never move, requiring free-lists to
be maintained, which in turn requires walking the entire live+garbage
heap at collection time.  

Pointerless data (i.e. leaf data) lies in two regions, 'contiguous,
which is also static, and 'relocatable, which is the aforementioned
exception as its GC is basically a copy collector with twice the used
space reserved at all times.  

As in all systems, the contiguous data is slow to allocate and free, but
quick to mark and thus maintain, while the relocatable data is quick to
allocate and free, but more expensive to mark and maintain as live data
must be copied.  Thus the latter is more suitable for ephemeral data,
and the former for more permanent data.  GCL arrays have always had the
:static keyword, which would select contiguous memory over the default
relocatable, but beyond this, the allocation has been hardwired and
permanent, i.e. no automatic 'promotion' is implemented on objects which
survive a number of gc's, and e.g. hashtables are always relocatable.

Relocating leaf data is the simplest, and is all that is currently
supported.  Relocating cell data containing pointers is significantly
more complicated, as the moved pointer must be modified in all
locations, requiring the marker to keep track of the pointer address.
In a conservative strategy used by GCL, where the C stack is marked when
it contains any plausible pointer, this means modifying the stack, and
flushing the setjmp buffers back to register on mark exit.  Relocating
code is the hardest of all, especially as we throw away the relocation
data when loading at present.  I am not proposing making code
multi-relocatable at the moment.

I have a rudimentary working collector which can relocate cell data.
This immediately suggests allocating a static array and using it as a
copy collection area for cells, and then moving old cells to the
traditional pages with free-lists as required.  This also suggests the
possibility of keeping all contiguous data adjacent to the end of .text,
and moving the cells when required, so that code addresses are low, and
providing the possibility to copy/compress everything else e.g. at image
save time.  Finally it suggests turning on sgc automatically on old
pages when no data is freed.  SGC, originally designed to minimize swap,
is barely effective at present, as frequently the read-only set becomes
minuscule.

Thus, cell data and leaf data might always begin in relocatable areas,
and be automatically moved to static areas with age.  :static keywords
*might* be obsolete.

Right now, the copy collector area for cells can be allocated and
resized via a variable si::*static-relocatable-buffer*.  Not sure if
this should be exposed to the user or not.

If anyone has suggestions, wish-lists, thoughts, etc., I'd be most
appreciative. 

Take care,
-- 
Camm Maguire                                        address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah