Re: GUILE GC -- Write barrier for vectors

[Han-Wen]

address@hidden writes:
> >     SCM scm_changing_cell()
> >     SCM scm_changing_vector()
> > 
> > They would be allocated from a separate memory pool. Also if we
> > redefine the GC engine to use a different function internally
> > (i.e. scm_gc_internal_mark), then we can distinguish between data
> > cells that may be moved (only pointed to from within the heap), and
> > other cells (marked by scm_gc_mark: conservatively marked entries,
> > pointed to from smobs, etc.).
> > 
> > The copiable cells could be subjected to copying GC, although it would
> > require another scan of the entire heap.
> 
> It's a good idea - unfortunately it is patented.  Don't ask me who has
> this patented, but I also suggested this idea some time ago.  That's the
> bad thing about patents:  Whenever there's a good idea, you can't be sure
> it is patented.
> 
> But, it may make sense to investigate this patent issue again.  Maybe the
> information above is outdated and the idea can actually be used in free
> software?
> 
> In this case, I wouldn't like to have the API extended as you suggest
> above:  Then it would be easy to re-arrange cells in cards such that
> untouched cells are moved into common cards - no need to extend the API.

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).

Interestingly, his techreport
(ftp://gatekeeper.dec.com/pub/DEC/WRL/research-reports/WRL-TR-88.2.ps)
contains C source code for the garbage collector -- but that's no
permission to use it, right, and the "patents" page at DEC doesn't
mention the patent.

(some time later I dug it up anyway: 

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/search-bool.html&r=1&f=G&l=50&co1=AND&d=ft90&s1='digital+equipment'.ASNM.&s2=bartlett.INZZ.&OS=AN/%22digital+equipment%22+AND+IN/bartlett&RS=AN/%22digital+equipment%22+AND+IN/bartlett

)

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.

> This is true if there is code.  As long as there is just a
> conceptual phase, there is no code to comment on.  And, the current
> situation is a counterexample to your suggestion: If we had started
> the workbook idea sooner, we would not have to go around asking for
> things about gc that others have already thought about.

Ok. So how do I go about adding to the workbook? Do I send simply send
patches?

> > > 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.

-- 

Han-Wen Nienhuys   |   address@hidden   |   http://www.cs.uu.nl/~hanwen