Re: guile/guile-core/libguile init.c

[Mikael Djurfeldt <mdj at mdj dot nada dot kth dot se>]

Greg Harvey <Greg.Harvey@thezone.net> writes:

> Mikael Djurfeldt <mdj@mdj.nada.kth.se> writes:
> 
> > Mikael Djurfeldt <mdj@mdj.nada.kth.se> writes:
> > 
> > > I took the Ben Zorn idea to allocated heap when freelist is empty
> > > and GC after N cells (the GC trigger) but added that GC won't happen
> > > if there happens to be yet another N cells on the freelist.
> > 
> > Correction: GC won't happen until the rest of the freelist has been
> > consumed (the point where heap growth normally would occur).
> 
> Umm... so nothing's changed, except getting a new cell is more
> complicated?

Well, "worse is better", right?  ;-)

Actually, the two schemes are more similar than I first realized.
Sorry for being so dense.

But, the new code actually does solve two problems:

1. How to coordinate GC for multiple freelists (1-word, 2-word, ...)

2. How to support pre-emptive multi-threading

It differs from the old GC scheme the way you suggested in a previous
letter: the minimum GC yield is *constant* and the heap is grown with
a factor 1.5 instead of 3.

Also, heap is not allocated directly after GC but when the freelist
has been emptied.  This is an advantage when having multiple freelists
since the latter event may not happen at all for one freelist if GC is
triggered by another freelist.

But, perhaps more importantly, this is a big step towards removing
critical sections for pre-emptive multi-threading.  The new GC scheme
maintains a master list consisting of clusters of cells.  Each thread
has its own freelist which is refilled by calling scm_gc_newcell.
scm_gc_newcell, in turn, fills the list by taking one cluster off the
master list.

SCM_NEWCELL makes the *same* operations as before (except that I've
removed the incrementing of scm_cells_allocated; the intention is to
compute this value in a way which doesn't require incrementing it in
SCM_NEWCELL, but since I haven't yet understood what value I should
compute (I posted a question on the list) I haven't implemented this
yet.

What *is* more complicated is that init_heap_seg and scm_gc_sweep now
creates a list of freelists (clusters) instead of a freelist.

In a way I find the new scheme quite neat: The same mechanism
(clusters) is used both to administrate GC and heap allocation, and,
to ration pools of cells to different users.

The old code could have been modified to behave according to the new
scheme without introducing clusters, but it is not expensive to
produce clusters instead of a simple freelist, and clusters will be
required when POSIX threads are introduced.