On 08/01/2012 07:01 PM, Eli Zaretskii wrote:

>> I'm really trying to design some GC bits on top of this.
>
> May I suggest to post some kind of design notes, with some details
> about the above?  I think such preliminary discussions help get all
> the interested parties up to speed, raise some important issues that
> are best discovered sooner rather than later, and generally avoid
> surprises, pleasant or otherwise.

OK. There are some ideas to share now.

1. Be realistic. It's practically impossible to throw away current GC and
redesign everything from scratch. In general, GC theory says that the collector
which is able to move objects should have advantages against non-moving
collector; we can think about compaction methods, but switching to (mostly)
copying collector is not a subject for discussions now. So, let's preserve
basic mark and sweep approach.

2. Do not (re)invent the bicycle. The most common ways to improve simple
mark and sweep collector is to make it generational and/or incremental.
Both approaches usually relies on the ability to trap pointer writes,
which is needed to maintain collector invariants; that's why I'm looking
for the lowest-effort methods to implement write barriers on top of
the existing infrastructure. Next, generational and incremental approaches
may be investigated and designed in parallel.

3. Premature optimization is the root of all evil. For the beginning,
I'm trying to implement a hugely overestimated write barrier (e.g. a lot
of pointer writes are really pointer reads). Of course, it will be notoriously
slow. Next, it should be possible to shrink an overestimation by separating
reads from writes, thus improving the collector speed.

4. Let's group them. Advanced GC usually requires additional information stored
in objects. This may be tricky for some objects (consider struct Lisp_Cons as
an example). But the most of objects are allocated from blocks (that's why I
spent some time to design block-based vector allocator :-), so we can try to
investigate using per-block special fields rather than per-object ones. (Large
vectors and buffers are special). For example, the only XSETCAR (X, Y) "invalidates"
the whole block where X is allocated, thus making this block a subject to
mark and sweep procedure at the next partial collection. LOL? Hold your horses
and re-read 3).

5. Just do it. Now I'm trying to trap each X = Y (remember about it's hugely
overestimated), where both X and Y are Lisp_Objects (not integers, not pure),
mark block contains X as target to mark at next partial collection, and mark
block contains _previous_ value of X (which was in effect before assignment)
as target to sweep at next partial collection. Next, I'm trying to estimate
how much allocated blocks needs marking and sweeping. Attached patch illustrates
this idea.

Dmitry