This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: gc notes available


> I actually think that memory protection will be much slower than doing it
> all in software.  Here are the steps involved in handling a page
> fault:
> 
>     1) The kernel gets the page fault, puts together a signal context,
>        and invokes the handler.
>     2) The handler does the bookkeeping which is the real point of the
>        exercise.
>     3) Now the handler has to actually do the write.  In order for
>        that write to succeed without causing yet another page fault,
>        you have to somehow:
> 	a) unprotect the page
> 	b) do the write
> 	c) re-protect the page, to catch the next write
> 
> So you're talking signal handling overhead, and at least two system
> calls.  Notice also that the handler can't really find the SCM object
> being modified; it only gets the address being written to, and
> probably the value being written to it.  But you can't find the cell
> at the head of the vector, given the address of some word in the
> malloc'ed array of elements.

Using memory protection is a bit messy though I think that the above
description is over the top. The idea of memory protection is really just to
bound off areas that have been written to rather than to chase down and
classify every single write operation. Thus, when you do get a page fault,
you make a few notes in some unprotected global variables and shrink the area
that you are still protecting. When you do some garbage protection you
have to rescan whichever areas you are no longer protecting but you know
that the protected areas have not changed.

Based on some reasonable assumptions:

	* most changes occur in clusters
	* large areas of live data stay unchanged for long periods of time

Your protected regions adjust themselves to covering the older generations
and you don't actually get many page faults. The newer generations become
a free-for-all that gets scanned often (but scans are quick because there
isn't much data here).

Well, that is the hand-waving explanation anyhow...

> Suppose we tell people that they must call SCM_WRITE_BARRIER (obj,
> new) after changing any field in OBJ to point to NEW.  So, for
> example:
> 
> 	SCM_VELTS (vector)[5] = some_object;
> 	scm_write_barrier (vector, some_object);
> 
> The thing is, they *know* when they write the code that they're going to
> do a write, so they might as well call the write barrier directly.
> Then you've got function call overhead (which is less than signal
> dispatch overhead) and bookkeeping.  No system calls.  And you also
> get the information you actually want: the object being modified.  So
> you can check the generations of the objects, and if vector is older
> than some_object, then you stick vector in a list of objects to be
> used as roots when collecting younger generations.

Why bother with conservating GC then? Requiring the user to declare
every write is surely no more difficult than requiring them to declare
every use of a SCM variable. Worse, your method gives overhead to every
single write, memory protection gives overhead to only writes that cause
page faults (hopefully a small percentage).

> The only weirdness here is: what if someone doesn't know they're
> mutating an object?  What if they've just got a pointer to an SCM, and
> they're storing something in it?  What if they've just got a void *,
> and they're copying bytes from another void * into it?  I think the
> answer here is that whoever gave them that pointer must have had the
> real SCM, and it's the SCM holder's job to make sure the write barrier
> gets called appropriately.  Thus:
> 
> 	frob (SCM_CDRLOC (pair));
> 	scm_write_barrier (pair, SCM_NEWEST);
> 
> SCM_NEWEST would be a magic value which tells the write barrier, "I
> don't know what I stored; I may or may not have pointers to younger
> objects now."

bleah!

	- Tel