Re: Opportunistic GC

[Pip Cet]

On Mon, Mar 8, 2021 at 11:37 AM martin rudalics <rudalics@gmx.at> wrote:
>  >> And short-lived objects have to
>  >> wait for the next cycle to get recovered.
>  >
>  > I'm not aware of any GC algorithm that recovers objects allocated
>  > after the GC cycle started :-)
>
> In the early phase of a collection cycle most objects are unmarked so it
> would make sense to give a new object the mark status of the first
> object referencing it.  But that's admittedly hard to do with ambiguous
> roots.

Perhaps it's worth keeping in mind that this is a relatively simple
change, not a complete GC rewrite.

>  > Mostly that there should not be a doubling of memory usage. With the
>  > mark bits fixed, memory usage would grow by, at most, 1/64th the heap
>  > size on 64-bit systems, plus a constant. I think we can live with a
>  > 1.5% increase in memory usage if we get (effectively) zero-cost (or
>  > zero latency) GC in exchange. (I'm assuming there'll be an unused CPU
>  > core, which is usually true for me (unless I'm compiling something)).
>  > With the mark bits not fixed, memory usage would increase by
>  > approximately the size of the surviving heap, but not the size of the
>  > discarded heap pages.
>
> But doesn't that depend on how many writes the Lisp thread performs in
> the heap?

You're right, it does. Thanks for correcting me on this point.

I don't think it's going to matter in practice, though. GC, after all,
does not take that long, and the retained working set of most Lisp
programs is small, memory is cheap, and it is a factor of two in the
absolute worst conceivable case.

> Each such write causes its associated page getting written
> out to avoid that an old link gets lost.  And if the action was to drop
> an old link, writing the page out doesn't even make sense.

I'm not sure what you mean by "drop an old link".

>  > Note that none of this is "real" GC: we still mark and sweep, just in
>  > a slightly smarter way.
>
> If with "real" you meant "real-time", then it might qualify as such.

No, I meant "real" as opposed to mark-and-sweep style algorithms.
Generational would have been a better (but possibly slightly
narrower?) term.

Pip