[Top][All Lists]

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

Re: Let's make the GC safe and iterative

From: Daniel Colascione
Subject: Re: Let's make the GC safe and iterative
Date: Thu, 1 Mar 2018 16:05:42 -0800
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0

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.

reply via email to

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