[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: New GC concept
From: |
Daniel Colascione |
Subject: |
Re: New GC concept |
Date: |
Fri, 4 Jun 2021 02:47:32 -0700 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 |
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.
Re: New GC concept, Andrea Corallo, 2021/06/04
Re: New GC concept, Matt Armstrong, 2021/06/07