Migrating an existing more modern GC to D's gc.d

[Jonathan M Davis]

On Tuesday, April 10, 2018 06:10:10 David Bennett via Digitalmars-d wrote:
> On Tuesday, 10 April 2018 at 05:26:28 UTC, Dmitry Olshansky wrote:
> > On Monday, 9 April 2018 at 19:50:16 UTC, H. S. Teoh wrote:
> >> Last I remembered, you were working on a GC prototype for D?
> >
> > Still there, but my spare time is super limited lately, the
> > other project preempted that for the moment.
> >
> >> Any news on that, or have you basically given it up?
> >
> > Might try to hack to the finish line in one good night, it was
> > pretty close to complete. Debugging would be fun though ;)
>
> I was thinking about messing with the GC in my free time just
> yesterday... how hard would it be:
>
> Add a BlkAttr.THREAD_LOCAL, and set it from the runtime if the
> type or it's members are not shared or __gshared.
>
> Then we could store BlkAttr.THREAD_LOCAL memory in different
> pages (per thread) without having to setting a mutex. (if we need
> to get new page from the global pool we set a mutex for that)
>
> If thats possible we could also Just(TM) scan the current thread
> stack and mark/sweep only those pages. (without a stop the world)
>
> And when a thread ends we could give the pages to the global pool
> without a mark/sweep.
>
> The idea is it works like it does currently unless something is
> invisible to other threads, Or am i missing something obvious?
> (quite likely)

As it stands, it's impossible to have thread-local memory pools. It's quite
legal to construct an object as shared or thread-local and cast it to the
other. In fact, it's _highly_ likely that that's how any shared object of
any complexity is going to be constructed. Similarly, it's extremely common
to allocate an object as mutable and then cast it to immutable (either using
assumeUnique or by using a pure function where the compiler does the cast
implicitly for you if it can guarantee that the return value is unique), and
immutable objects are implicitly shared. At minimum, there would have to be
runtime hooks to do something like move an object between pools when it is
cast to shared or immutable (or back) in order to ensure that an object was
in the right pool, but if that requires copying the object rather than just
moving the memory block, then it can't be done, because every pointer or
reference pointing to that object would have to be rewritten (which isn't
supported by the language).

Also, it would be a disaster for shared, because the typical way to use
shared is to protect the shared object with a mutex, cast away shared so
that it can be operated on as thread-local within that section of code, and
then before the mutex is released, all thread-local references then need to
be gone. e.g.

synchronized(mutex)
{
    auto threadLocal = cast(MyType)mySharedObject;

    // do something with threadLocal...

    // threadLocal leaves scope and is gone without being cast back
}

// all references to the shared object should now be shared

You really _don't_ want the shared object to move between pools
because of that cast (since it would hurt performance), and in such a
situation, you don't usually cast back to shared. Rather, you have a shared
reference, cast it to get a thread-local reference, and then let the
thread-local reference leave scope. So, the same object temporarily has both
a thread-local and a shared reference to it, and if it were moved to the
thread-local pool with the cast, it would never be moved back when the
thread-local references left scope and the mutex was released.

Having synchronized classes as described in TDPL would make the above code
cleaner in the cases where a synchronized class would work, but the basic
concept is the same. It would still be doing a cast underneath the hood, and
it would still have the same problems. It just wouldn't involve explicit
casting. shared's design inherently requires casting away shared, so it just
plain isn't going to play well with anything that doesn't play well with
such casts - such as having thread-local heaps.

Also, IIRC, at one point, Daniel Murphy explained to me some problem with
classes with regards to the virtual table or the TypeInfo that inherently
wouldn't work with trying to move it between threads. Unfortunately, I don't
remember the details now, but I do remember that there's _something_ there
that wouldn't work with thread-local heaps. And if anyone were to seriously
try it, I expect that he could probably come up with the reasons again.

Regardless, I think that it's clear that in order to do anything with
thread-local pools, we'd have to lock down the type system even further to
disallow casts to or from shared or immutable, and that would really be a
big problem given the inherent restrictions on those types and how shared is
intended to be used. So, while it's a common idea as to how the GC could be
improved, and it would be great if we could do it, I think that it goes
right along with all of the other ideas that require stuff like read and
write barriers everywhere and thus will never be in D's GC.

- Jonathan M Davis