Re: GUILE GC -- Write barrier for vectors

[Dirk Herrmann]

On Tue, 16 Jul 2002, Han-Wen wrote:

> I don't know. Some form of the idea seems to be patented, but I can't
> access the text of the patent, so I'm not sure (it's no. 251554).
> (and even if I could -- you never know: the only person qualified to
> judge wether a patent is applicable are IP lawyers and IP judges. With
> those millions and millions of patents it is unlikely that none of
> them are covering GUILE as it is).

Maybe it would make sense to ask the FSF about the issue:  If the patent
is not actually claimed or if there is an agreement to allow its use in
free software, there wouldn't be any restrictions at all.  Probably Marius
will know about how to contact the FSF legal department to get an official
statement about it.

> I'm reading the patent (gosh, what verbosity) -- but interestingly,
> the claim is only made for not copying entire pages (cards in Scheme
> terms), that are marked conservatively. If you one uses a second set
> of mark bits, you could leave alone exactly those objects that are
> marked conservatively (iso. the whole page). The price is that you
> have another mark-bit vector (1.5 % memory overhead), that the free
> space in the conservatively marked pages is fragmented, and that there
> is more overhead (checking the marked-conservatively-bit) during the
> copy phase.

Interesting.  But:  isn't the conservatively marked page fragmented
anyway?  At some time a few objects in a conservatively marked page will
be collected.  That is, wouldn't we need to keep track of conservatively
marked cells (in contrast to pages) anyway?

> > > > Hmmm?  Where should this be necessary?  Do you want to modify the vector
> > > > cell itself, or are you using this for "speed ups"?  In the "speed-up"
> > > > case:  wouldn't SCM_VECTOR_SET do as well, given that the compiler can
> > > > extract constant expressions from within loops?
> > > 
> > > In some cases no (GC manipulations of weak vectors), and in some cases
> > > yes, but it would introduce lots of redtape: long lists of
> > > SCM_VECTOR_SET calls. I'll review the cases once more. 
> > 
> > GC manipulations of weak vectors?  These shouldn't require any write
> > barrier.  And, even if so, there's already SCM_SET_WVECT_GC_CHAIN.
> 
> No, exactly my point. If you add some kind of GC related code that
> writes header from SCM_VECTOR_SET() (to flag object writes), then you
> shouldn't use it in code that is related to the GC. Also flagging
> object writes is overhead, so you typically want to move it out of
> loops if possible.

Wouldn't the compiler move the code out anyway?  (I don't know how
complicated the flagging code would look like, so it may be that this is
impossible...)

According to the point that during GC there shouldn't be any flagging
done:  We already do have special cell accessing macros for GC:
SCM_GC_CELL_WORD and friends.  The point is, that up to now these have had
a different intention:  They don't check if their cells are actually
cells - even in debug mode.  In contrast, SCM_CELL_WORD and friend do
exhaustive checking in debug mode.

Maybe we could re-define the meaning of SCM_GC_CELL_WORD and friends to
mean the following:  The macros are only to be used in code related to GC.  
The cells are never checked for being cells, and the cells are not flagged
for gengc.  For those cases, where cells are to be modified during GC but
still need to be flagged, there could be a special macro to explicitly
flag the cells - probably such a macro would exist anyway.

Best regards,
Dirk Herrmann