From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Daniel Colascione Newsgroups: gmane.emacs.devel Subject: Re: Let's make the GC safe and iterative Date: Thu, 1 Mar 2018 16:05:42 -0800 Message-ID: References: <87inaiss6l.fsf@web.de> <6FCF6ACA-4F29-4B6B-BE9D-D7130C6E9495@gnu.org> <87fu5moe4c.fsf@web.de> <877eqyocro.fsf@web.de> <83zi3uz4nb.fsf@gnu.org> <0b1dd3fa-e0b0-ed20-a256-dd92d1c1826f@dancol.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: blaine.gmane.org 1519949077 24289 195.159.176.226 (2 Mar 2018 00:04:37 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 2 Mar 2018 00:04:37 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 To: Stefan Monnier , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Mar 02 01:04:32 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1erYBa-0005VS-AT for ged-emacs-devel@m.gmane.org; Fri, 02 Mar 2018 01:04:30 +0100 Original-Received: from localhost ([::1]:59826 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1erYDb-0004i0-12 for ged-emacs-devel@m.gmane.org; Thu, 01 Mar 2018 19:06:35 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:39728) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1erYD0-0004hm-Gz for emacs-devel@gnu.org; Thu, 01 Mar 2018 19:05:59 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1erYCw-0006EV-AO for emacs-devel@gnu.org; Thu, 01 Mar 2018 19:05:58 -0500 Original-Received: from dancol.org ([2600:3c01::f03c:91ff:fedf:adf3]:45160) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1erYCv-0006Cs-VK for emacs-devel@gnu.org; Thu, 01 Mar 2018 19:05:54 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=dancol.org; s=x; h=Content-Transfer-Encoding:Content-Type:In-Reply-To:MIME-Version:Date:Message-ID:From:References:To:Subject; bh=Dmj66npHf0QLrV+fycnOzjAbkZEs+luY8KkWEV41D4c=; b=Dq9xrpJuoUHdMUj6FV1kUmz1B8UbykvVo0HP9Qckvpy7VdHaCRsk3MmrpDcQc+WsSWAi42kQjCz6SLszF0zQ4mxcvniryRV6yRRY2ySp7hqQjT3bO8tzvOkQBomD7RroORoB4FuFW3l4UCB45jpqU4CIBjGGjQl7ZRXpJlh+4Si748U2HjTMiYw9a+xqwWN6PdsT9mbEzW0MfbEdB9L1otd3CO3QWTrhMROHYkTVpdMnMll85QXSmTs96nu9/QezxFtCBcytcMCkKyI/s+FD+tjU+rGBKuNQntpFE04KNVN1a4P+7XKgfoxt1A3CQ9VbTmowgBO7cUiGR8oh9k+rsA==; Original-Received: from [172.92.145.124] (helo=[192.168.86.27]) by dancol.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) (envelope-from ) id 1erYCr-0004ne-RE; Thu, 01 Mar 2018 16:05:49 -0800 In-Reply-To: Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2600:3c01::f03c:91ff:fedf:adf3 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:223205 Archived-At: 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.