Re: Let's make the GC safe and iterative

[Daniel Colascione]

On 03/01/2018 03:38 PM, Stefan Monnier wrote:
> > We need to fix GC being deeply recursive once and for all. Tweaking stack
> > sizes on various platforms and trying to spot-fix GC for the occasional
> > deeply recursive structure is annoying. Here's my proposal:
>
> I'm OK with making the GC loop without recursing on the C stack, but
> I have two comments:
> 1- Don't use a queue: use a stack.  Mark&sweep naturally work with
>     a stack whereas stop&copy naturally works with a queue, so in most cases
>     the choice is implicit/accidental, but experience shows that if we
>     can choose, the stack is the better option (e.g. there's been
>     various works that try to tweak stop&copy to use a stack rather than
>     a queue), for reasons of locality.

Sure. Using a stack instead of a queue is a minor detail; the basic 
algorithm is the same.

Within blocks, we still need to be queue-based though: we'll scan the 
scan_pending bitmap once; if more bits behind the scan_pending read 
position become set during the scan, we won't know until the next time 
we examine the block. But we *can* make sure that we re-examine this 
block immediately after we finish the scan_pending bit-scan.

> 2- Why do you say "We can't allocate memory to hold the queue during GC"?
>     We very well can, and doing it should make things simpler (and make
>     sure we don't preallocate way too much memory).

We can try, but we need a plan if allocation fails. I don't want Emacs 
to be one of those programs that just aborts if malloc fails. Too many 
other programs get it wrong these days. I don't think the worst-case 
preallocation overhead is severe enough that we have to give up malloc 
robustness.

> If instead of a queue we use a stack and we just push Lisp_Object values
> onto that stack, the resulting space use can't be worse than what we
> have now (it's just going to use our malloc-managed stack instead of the
> C stack).

Sure, except that stack use is ephemeral, and the space we allocate for 
the stack gets used for lisp too. OTOH, we need to preallocate these 
linkage structures and keep them allocated between GCs. But like I said, 
I don't think the overhead is worth worrying about.