[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Fixing guardians

From: Michael Livshin
Subject: Re: Fixing guardians
Date: 11 Dec 2000 01:27:23 +0200
User-agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (20 Minutes to Nikko)

Marius Vollmer <address@hidden> writes:

> Ok, let me talk out of my *bleep* here. I haven't read the guardian
> code in Guile, nor did I read any paper.  I'd like to just write down
> what I have in my mind right now, maybe it makes sense.  If it doesn't
> make sense, don't bother to explain it to me in great detail.  Just
> tell me to RTFC.

no need to RTFC, since what you describe doesn't match the current
reality.  so I'll comment, if you don't mind.

> I imagine guardians for the Guile mark/sweep collector to be
> implemented like this:
> A guardian has two lists: one list of `guarded' objects and one list
> of `caught' objects.  The `guarded' objects are those that have been
> added to the guardian and not yet moved to the `caught' list.  The
> `caught' list contains those objects that will be returned when asking
> the guardian for objects to finalize.
> These two lists are _not_ visible to the GC, that is, objects on them
> are not automatically marked.  Maintaining these lists does not
> trigger the GC either.

what do you mean by the last sentence?

> After the mark phase of the GC:
>     For every guardian:
>       For every object on the `guarded' list:
>         If the object is unmarked:
>           Call scm_gc_mark on it.
>           Unset its mark bit afterwards.
>     Then, for every guardian:
>       Move all unmarked objects on the `guarded' list to
>       the `caught' list and set their mark bit.
> Then do the sweep phase.  This may delete some guardians and we might
> have superfluously marked some objects that these guardians have on
> their `caught' list.  These objects will not be deleted this time, but
> on the next GC pass.  I don't think it is important to avoid this
> behaviour and it might be tricky to do because guardians might be
> guarded themselves and thus can go from unmarked to marked during the
> process above.

yes, it's tricky and the current implementation doesn't fuss about it
(too much) either.

> This process should take care of guarded objects referencing other
> guarded objects and of cycles among guarded objects.  The cycle will
> be broken at an arbitrary link, but that's OK.

the point about cycles is actually the only one that I find debatable.
I (apparently in a fine company of Hans Boehm, Dirk Herrmann and maybe
others) think that it's preferable to leave cycles "guarded" (not
"caught", that is) and warn the user about them, because finalizing
things in some wrong order is worse than not finalizing them at all.
and breaking cycles is not hard and shouldn't be a frequent need in
practice anyway.

> For example, take two cons cells
> [...]
> Ok, what's wrong with this simple algorithm?

nothing, in the acyclic case.

You question the worthiness of my code? I should kill you where you
                                        -- Klingon Programmer

reply via email to

[Prev in Thread] Current Thread [Next in Thread]