Potential GSoC project - GC improvements

[Adam Wilson via Digitalmars-d]

Chris Wright wrote:
> On Sat, 12 Mar 2016 13:23:35 -0800, Adam Wilson wrote:
>
> To start off, let's talk terminology. You seem to be using nonstandard
> terminology and possibly misunderstanding standard terminology.
>
> A GC scan is the mark phase of a mark/sweep collector (and specifically
> the part where the GC examines roots and allocated memory, if that
> matters). The GC searches for pointers to GC memory. Simple GCs only need
> to record whether there is a pointer to a given allocation, not where
> those pointers are coming from.
>
> A conservative GC is one that will encounter some things that aren't
> pointers but must be scanned as if they were pointers. In D, for
> instance, a union between a pointer and a size_t forces collectors to be
> conservative.
>
> A false pointer is something that a conservative GC must treat as a
> pointer and appears to point to an object allocated by that GC. For
> instance, unions in D allow us to create false pointers.
>
> A precise GC is a GC that never mistakes a non-pointer for a pointer.
>
> A moving GC is a GC that can relocate objects.
>
> A generational GC is one that can perform a collection on part of the
> heap without dealing with the full heap. Those parts tend to be organized
> by how long an object has survived. This does not require a precise or
> moving GC, though it works better with a precise, moving GC.
>

I didn't intend to confuse, but I was not writing to neophyte's, and I 
used linguistic shortcuts.

> A write barrier is a way to record which sections of memory have been
> altered since the last GC collection. This lets the GC scan only the
> changed data -- useful to any GC, especially useful to generational ones.
>
> A "partially moving" GC does not exist, as far as I know.
>

Yep, it's a Bad Idea.

>> Jeremy DeHaan wrote:
>>> On Saturday, 12 March 2016 at 08:50:06 UTC, Adam Wilson wrote:
>>>> If I may make a suggestion. The lock free work is unlikely to require
>>>> the entirety of GSoC. And the precise GC is the next most important
>>>> thing on your list and will have the biggest impact on GC performance.
>>>
>>> Rainer has two different precise GC's in pull requests right now and
>>> both are slower than the current one unless there are false pointers.
>>> I would expect anything I come up with to largely act the same. The
>>> reason I keep pushing for a generational garbage collector is because I
>>> think it would be where we would see the most benefit in terms of
>>> general performance.
>>>
>>>
>> I would contend that it's not quite that simple. Of course the precise
>> GC is slower, it's scanning more stuff.
>
> Precise GCs are slower because they must reference some data telling them
> which items on the stack and in allocations represent pointers and which
> do not. This data takes up cache space, and having less cache for memory
> being scanned slows things down. Correlating two pieces of data takes
> extra time, too.
>

Yep the data is usually held with the object in a header. Hence the 
"scanning more stuff".

> The hope with a precise GC is to avoid false pointers. A false pointer to
> an object that holds references to many other objects can be costly, both
> in GC time and in excess memory usage.
>
> In D, we have a tiny bit of type information surfaced to the GC to reduce
> the incidence of false pointers. We could additionally take advantage of
> the fact that numbers tend to be small and people tend to use 4 to 8 byte
> numbers: we could arrange our address space to avoid ranges where false
> pointers are likely. But that's probably unnecessary.
>

We are not limited by what we currently have. Most of Rainer's work 
involved surfacing more data to the GC.

>> The current conservative GC by
>> definition can't figure out large chunks of memory so it won't even
>> bother scanning them.
>
> It must scan anything that might be a pointer. A precise GC reduces the
> number of things that might be pointers but aren't to zero. Therefore a
> precise GC scans less.
>

Yep, precise GC's aren't totally perf-negative.

> If a conservative GC didn't scan something that might be a pointer, it
> would sometimes free an object that still had live references to it. This
> would result in memory corruption or segmentation faults.
>
>> What it does to those things it can't scan. And
>> what it can't scan it has to pin, which means the memory can't be moved.
>
> If a moving GC cannot precisely identify all pointers to an object, it is
> not allowed to move that object. If it can, it is allowed to move that
> object.
>
> A conservative GC can be a moving GC. It must classify things as
> "definitely pointer", "maybe pointer", and "not pointer". It cannot move
> an object with a "maybe pointer" pointing to it, but it can move an
> object with several "definitely pointers" pointing to it.
>
> In D, thanks to unions, we can never create a fully precise collector,
> but we can create a moving collector. Objects pointed to from a union
> can't be moved, but few objects will be pointed to from a union.
>

Actually, we probably could with modifications to the compiler. A little 
metadata goes a long way. And I know that Walter would accept that PR. I 
don't know for sure if it can be done, but I've seen precious little 
evidence one way or the other. Let's investigate before making absolute 
statements about what we can do. I know from discussions with Walter 
that the compiler's AST contains a wealth of information, and that more 
can be added.

>> You can't build a fully generational GC until you can move everything.
>
> You can build a more efficient generational GC if you can move objects.
> However, it's not impossible to build a non-moving generational GC.
> Instead of having large blocks of address space for each generation, you
> would have each Pool indicate its generation. Then you have to find the
> Pool for a pointer and check that flag.
>
> That's comparatively slow, but it'd still be faster to do a Gen 0 scan
> that way than to do a full scan with D's current collector (assuming you
> implement write barriers).
>

My apologies I didn't intend to state that it was impossible. I was 
attempting to emphatically question the wisdom of doing so, particular 
when the potential performance benefits are dubious at best. My point is 
that we should do this right, if we keep blindly pursuing performance 
without taking a considered approach to achieving it, we'll never get 
there. The GC will just become an ever larger pile of hacks that 
increase performance in specific cases.

>> They talk about this problem in the books. However, once you have a
>> precise GC, a fully moving GC becomes possible and only then do the
>> performance benefits of a generational GC become realized.
>
> The performance benefit of a moving and generational GC over a non-moving
> generational GC is that you can have a contiguous section of address
> space for each generation, allocated densely. You get this with less
> overhead.
>

That's actually pretty important. Precision enables moving, moving has 
clear and enumerable performance benefits. QED.

> However, a moving GC can be a pessimization for user code. If you
> allocate several objects in sequence, with many GCs you'll get memory
> allocated for them that is contiguous or nearly contiguous. For small
> objects, this is probably going to be on the same page of memory. But a
> moving GC is free to move them to different pages. So you need to
> exercise caution.
>

Yes ... and this is also dealt with in the books, including basic 
algorithms to help combat these problems. Additionally, as evidenced by 
the fact that every major GC (JVM, CLR, et al.) system implements a 
moving GC, I'd argue that the benefits greatly outweigh any potential 
risks. And we have pull requests to further optimize the algorithms. We 
don't have a system at all yet, let's build it first, then we can work 
on optimizing it.

>>> I have concerns about doing any compaction
>>> though, mostly because D can have both references and pointers to
>>> objects, and I don't know how we would want to go about updating
>>> pointers. Especially since pointers to D objects can exists in C and
>>> C++
>>> code.
>>>
>>>
>> Erm, a generational GC is, in practice, a moving GC as it must move the
>> blobs around from the various heaps.
>
> The Boehm collector is generational, conservative, and not moving. You
> probably conflate "moving" and "generational" because of the JVM.
>

Ok, yes, but lets be honest, it's what we actually want, and more 
importantly, expect. Precision makes it happen, efficiently. Even the 
C++ community doesn't take the Boehm GC very seriously. We have an 
opportunity to prove the C-style language can have a performant GC.

>> As for the C/C++ code problem various solutions have been proposed here.
>> For one, D knows the difference between the two, so pinning is possible
>> there.
>
> There's nothing in the type system that says whether you can pass a
> variable to a C/C++ function. So, no, D *doesn't* know the difference
> between them. And there's no GC.pin function, so people aren't currently
> telling your GC when something's accessible to C/C++ code.
>

D does differentiate between a GC reference and pointer. Pin the 
pointers. Yes, you can create get pointer from a reference, and doing so 
is a pinning operation. We'd have to add a GC.pin function, so long as 
the compiler emits it for us. :)

> That means a moving collector in D will produce segmentation faults and
> memory corruption in existing, currently working code.
>
>> AFIAK each OS allows you to specify multiple heaps
>
> You get one address space. You get to use mmap to ask for memory at a
> given address. There's no heap_t data structure to provide to malloc or
> mmap.
>
> You might have been confused by literature referring to multiple heaps.
> That's just a single allocator deciding to divide its address space
> logically. There's no OS-level enforcement.
>

Windows has that concept via HeapCreate shown here: 
https://msdn.microsoft.com/en-us/library/windows/desktop/aa366599(v=vs.85).aspx
I'd be surprised if it's not available on other OS's, and yes, it is OS 
enforced. It might not work exactly how you like it, but that's a far 
cry from "not provided".

>> A concurrent GC without precision is mostly useless
>
> The Boehm collector is not precise. It is concurrent. Its concurrency
> reduces the amount of time a GC collection takes. This is mostly
> orthogonal to the benefits of a precise collector in reducing the amount
> of memory a process uses.
>
>> because the GC roots
>> are primarily derived from the stack which the thread was spawned and
>> the stack roots are not scanned in a conservative GC.
>
> They *are* scanned in a conservative GC. If you don't scan memory that
> might contain pointers (such as the stack), your GC will inevitably cause
> segmentation faults and memory corruption. D's GC is conservative and
> does not cause segmentation faults or memory corruption, therefore it
> must scan the stack.
>

I may have been confusing any precise GC with Rainer's precise GC which 
only did precise Heap scans. Apologies for the confusion.

I will admit that I've done better work with my wording than what is in 
my last message. However, my fundamental point is sound, precision has 
benefits across all GC workloads and enables scenarios beyond the GC 
itself. Extending the compiler can work around many of the issues with 
false pointers.

And let's engage the elephant in the room. One of Rainer's main 
learning's was the precision permeates the compiler and GC, you have to 
deal with it everywhere. So you end up rebuilding the GC from the ground 
up when you add it. What you are proposing is building a 
conservative-generational GC that will have to be jettisoned and 
rewritten *again* once precision is added for a performance boost that, 
by your own admission, may not actually happen. How is this a good use 
of time?

My statement stands. Precision is the basis from which all high-order GC 
functions flow. Yes, you can work around not having it, but such 
workarounds tend to be just that. More importantly you are inevitably 
going to end up doing a half-implementation of precision anyways because 
each of the high-order functions need parts of that information.

I know precision isn't fun. But it's extremely important work that needs 
to get done. And once we have it, the world of GC algorithms opens 
before us. Until then we are intentionally limiting ourselves. One of 
the biggest complaints about D is the GC, fine, so instead of doing yet 
another hack-job on something that may not actually improve GC 
performance, let's do it right and lay the groundwork for a modern GC 
that allows us to really compete with JVM/CLR.

-- 
// Adam Wilson
// quiet.dlang.dev