Re: Dybvig's Guardians etc.

[mike@olan.com (Michael N. Livshin)]

Mikael Djurfeldt <mdj@nada.kth.se> writes:

> I've read your code now.  I think it is very good,
Thanks.
> but I have some
> suggestions for improvements:
> 
> 1. You are managing the guardians in a doubly linked list.  But isn't
> the purpose of a garbage collector to do the storage management for
> us?  Here's a suggestion for an alternative implementation which, I
> believe, would have simpler logic and be more efficient:
> 
> Guardians are smobs with two fields in the malloc: `live' and
> `zombies'.  These are ordinary lists, just as in your implementation.
> The smob mark function returns the zombies so that the'll be marked
> but leaves the `live' list.  If the `live' list is non-null, we put
> the guardian in a C array of SCMs, `scm_life_guards', which behaves
> similar to `scm_weak_vectors'.  (The int `scm_n_life_guards' is reset
> in the beginning of the mark phase and the array is successively
> filled during it.)

If we want to be maximally efficient, we should mark the zombies "by
hand" in the smob mark function.  This is because we know it's a
proper list, and so it will spare us the big switch in scm_gc_mark.

> Just before the sweep we call the function `scm_zombify' which loops
> through `scm_life_guards'.  For each guardian we loop through `live'
> and move unmarked objects to zombies.  At the same time we 1. call
> scm_gc_mark on unmarked objects, 2. set the gc mark on the cons pairs
> which we move along with the objects, and, 3. set the gc mark also on
> those conses which contain marked objects.
>
> 2. I think the name space in Guile is unnecessarily cluttered.  Maybe
> you could implement `make-guardian' directly as a primitive, and skip
> the other primitives?  `make-guardian' would return a compiled closure
> (see `scm_makcclo' and gsubr.c) which, in turn, contains the guardian
> smob.

Well, what can I say? I'm lame :).

> 3. Please use the same code formatting conventions as (most of) the
> Guile code.  This may seem silly but, in fact, makes it much easier
> and faster to read the Guile source.  (Our visual parser wants to be
> able to make assumptions about the formatting in order to optimize
> reading!)

While I could do it by hand, I don't like those conventions.  Is there
a set of GNU indent switches that does the right thing?

> > 2. Is there a way to implement a `markedp' function (or macro)
> > better than I did?
> 
> I think so.  Instead of the switch you can test bit 2 of SCM_TYP7 (p).
> If it is 0 you do SCM_GCMARKP, otherwise SCM_GC8MARKP.  This is so
> simple that you could do it directly in the inner loop through
> `live' (for maximum efficiency) if you want.  On the other hand, if we
> want to be really neat, we should put `scm_marked_p' in gc.c

Or, as you say in the followup, in gc.h.  But there also should be
this, if I'm not mistaken:

    case scm_tcs_subrs:
        return SCM_GC8MARKP((SCM)(scm_heap_org + (((unsigned long)SCM_CAR(p)) >> 8)))

BTW is the FIFO part really necessary?  I see two CONs:
1. It'll increase the size of guardian object twofold.
2. Depending on the collection order is losing anyway, so I don't
see any sane use for such feature.

> /mdj

thanks a lot!
mike.