|
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© 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© 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.
[Prev in Thread] | Current Thread | [Next in Thread] |