Re: Let's make the GC safe and iterative

[Stefan Monnier]

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

The point is that a stack will be better locality-wise and (more
importantly) that it should be as good as what we have now w.r.t memory
use (actually, it should be significantly better, because at each
"recursive" step we only push one Lisp_Object on our stack whereas the
current code pushes an activation frame which is at least twice as large
since it also needs a return address).

So I think it does affect the algorithm: I'm not convinced we need to do
anything special for objects allocated from blocks.

>> 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.

We can just abort the GC (only requires resetting the markbits).
It's not like we GC when our memory is full: we just GC on a regular
basis for "prophylactic" reasons.

> I don't think the worst-case preallocation overhead is severe enough
> that we have to give up malloc robustness.

It sounds pretty significant to me.  I could live with it if it were
indispensable but I find it difficult to justify.

> Sure, except that stack use is ephemeral,

Our manually-managed stack can have the same property.

> and the space we allocate for the stack gets used for lisp too.

Yes, that's a downside of such a change w.r.t average use of the
combined stack space, but I don't think it affect the maximal combined
stack space, so I'm not worried.  This said, we could also move the Lisp
stack to that same manually-managed stack (at least for the bytecode
stacks).


        Stefan