From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Daniel Colascione Newsgroups: gmane.emacs.devel Subject: Re: New GC concept Date: Fri, 4 Jun 2021 02:47:32 -0700 Message-ID: <06073468-e016-52af-9a84-99ef4cf00d78@dancol.org> References: <1658db95-d513-7f21-8751-0e2ea38946cb@daniel-mendler.de> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="4274"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 To: Daniel Mendler , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Jun 04 11:50:29 2021 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lp6TC-0000xG-HR for ged-emacs-devel@m.gmane-mx.org; Fri, 04 Jun 2021 11:50:28 +0200 Original-Received: from localhost ([::1]:39172 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lp6TB-0005iz-F5 for ged-emacs-devel@m.gmane-mx.org; Fri, 04 Jun 2021 05:50:25 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:46338) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lp6QW-0004sE-BJ for emacs-devel@gnu.org; Fri, 04 Jun 2021 05:47:40 -0400 Original-Received: from dancol.org ([96.126.100.184]:58016) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lp6QQ-00069Z-FL for emacs-devel@gnu.org; Fri, 04 Jun 2021 05:47:39 -0400 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:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=hDX0eNlPohQuufHTB4ahEbOv8VhDQockmmwLVppZUx0=; b=QxZR4H4QgrBK6M85FcZYR3nMys 1waatylw/+ltsUVl2JFLkm5WjMe3X1P86xYLTF7Fhadrg4+lCAJ6Sql+hNQp9XrW+m62gB6Rpbtlz NH8nDzh2fyWTlfPz3u+QbXhUkB6rLrnvCymAyrXg0vvNieh4RSGkVws5T4+d04BZDTnUTlvVK6SQ9 tUKRp3w4wscjGb+b86RGLXwlYgSn6EP6eBqyLCyeBwNYqLn/q8lz6R6XALBYXn6Ow/2pJ3gSYPgyZ 90/iHKutVmiSXFbBhFifB56c/Z2jmjSQ0gy45B04gsC5gn/+PNiVFD/qxhF59DeDfiQ20Uu3vpXC6 c/UccZXg==; Original-Received: from [172.92.145.124] (port=56372 helo=[192.168.86.185]) by dancol.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.89) (envelope-from ) id 1lp6QP-0001wc-4b; Fri, 04 Jun 2021 02:47:33 -0700 In-Reply-To: <1658db95-d513-7f21-8751-0e2ea38946cb@daniel-mendler.de> Content-Language: en-US Received-SPF: pass client-ip=96.126.100.184; envelope-from=dancol@dancol.org; helo=dancol.org X-Spam_score_int: -26 X-Spam_score: -2.7 X-Spam_bar: -- X-Spam_report: (-2.7 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, NICE_REPLY_A=-0.603, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 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-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:270365 Archived-At: On 6/4/21 1:00 AM, Daniel Mendler wrote: > Interesting, thank you for working on this! > > I had hoped that a new GC would surface at some point given the recent > improvements regarding native compilation. As you say this can bring > Emacs on par with modern managed language runtimes. Can you elaborate a > bit more of some of your concepts? Thanks for taking a look. >> * fully copying and compacting > How do you ensure that compaction works together with the conservative > stack scanning? You pin memory blocks, which are potentially referenced > by the stack? Yes, pinning is how we combine conservative stack scanning with a copying collector. We don't pin whole memory blocks though. We pin at object granularity. (Things like Hosking's "mostly copying collector" use block pinning IIRC, but we can do much better these days.) Just as each object has a mark bit, each object has a pin bit. We pin only those specific objects that conservative scanning flags as potentially referenced from native code. We still copy pinned objects from the from-space to the to-space actually --- it's important copy pinned objects because it's during copying that we update all the pointers that a pinned object might contain. Pinning just ensures that we copy in a specific way such that after we're done with GC and swap the to-space and from-space, each pinned object ends up at the same virtual address it had before GC started. This way, although we *do* copy pinned objects, the mutator never observes a pinned object changing position. The pin bits end up using very little memory because they're stored contiguously in side arrays and almost entirely zero, and each zero page shares the same backing RAM until something makes it non-zero. Like I mentioned in the new alloc.c, address space is abundant. >> * generational > Do you rely on the OS memory protection as a write barrier to separate > the different generations, similar to how the bdwgc does that? Correct. IMHO, it's not practical to retrofit write barriers or read barriers into Emacs. >> * specialized GC spaces for conses, strings, arrays, and so on: no > stupid header word for cons cells bloating memory use by 50%! > > Avoiding the headers is a good idea. You are using a first fit strategy > to find the next free space for a new object. How do you use the > headerless approach for objects of different sizes? We don't. :-) In the new GC, the overall Emacs heap is divided into "heaps" for various object types; each heap has its own list of blocks and its own heap memory format. The heaps for fixed-size objects like cons cells and intervals don't have headers. The heaps for variable-sized objects like strings and vectorlikes *do* use conventional object headers. > Isn't it the case > that every block should then contain objects of only a single type and > of a single size? Some heaps (most importantly, the vectorlike heap) do support variable-sized objects, and blocks belonging to these heap types contain a mixture of object types. > Probably most of the objects fall in a few size > classes, so it may be possible to do better than first fit? First-fit is better than it sounds in the context of a compacting collector. First-fit allocation always (except in two cases described below) succeeds on the first try: because each GC pass compacts all the objects at the "start" of the heap, and we start first-fit allocation from the end of the last compacted object. That's why I wrote that the first-fit allocation scheme is equivalent in practice to bump-pointer allocation. The two cases where we fail first-fit allocation are: 1) we're in a heap that supports variable-sized objects and there's not enough space in the current block to hold the object we're allocating, and 2) there's a pinned object "in the way" of where we want to place the object via first-fit allocation. #1 isn't a problem in practice: if we're trying to allocate an object that's too big to place in the tail of the object's heap's current block, we allocate a new block and put the new object there instead. The new object is guaranteed to fit in the new block because we allocate larger-than-block objects in a separate storage area, as is traditional in GCs of this sort. (See the large vector list.) When we move to a new block this way, we don't commit the memory of the tail of the previous block, so moving to the next block is practically free, modulo page-tail wastage. #2 isn't a problem either: pinned objects are rare, and when we do encounter one, we can "skip over" it efficiently using the free-object bitmap. Modern machines are really good at streaming analysis of bit arrays: we don't even need a freelist embedded in the heap, like Emacs currently has for conses. Scanning a bitmap is both simpler and kinder to the cache. Because pinned objects are rare, because pins are transient, and because each GC pass is a compacting pass, first-fit doesn't lead to the fragmentation that it normally causes in things like malloc implementations. > Overall is your design similar to the approach of the bdwgc plus that a > memory/object layout tailored to the needs of Emacs and the compaction? > How well does such a GC hold up to a GC which is precise and does not > rely on the OS facilities for barriers? It appears such a precise GC is > impossible to retrofit on the existing Elisp runtime, so I assume your > approach is the right way to go. Most other GCs use software barriers, true. But even that's changing. Relying on OS facilities for barriers has an important advantage: it reduces code size. If we used the non-OS-level facility in a native compilation world, we'd have to emit a write barrier before *every* mutator write (~6 instructions). These barriers add up and bloat the generated code. If we use OS memory protection instead, the generated code can be a lot smaller. Plus, using OS facilities, we don't have to change the rest of the Emacs C core.