[Vm-dev] Garbage Collection (was Re: [Pharo-dev] Discussing the roadmap)

[Ben Coman]

On 4 December 2017 at 15:47, Clément Bera <bera.clement at gmail.com> wrote:
>
> Here are some ideas/things to say on the tip of my head:
> - Changing an object to a forwarding object is non atomic (we need to maintain at least stack invariant)

Thats because the whole multiword object has to be copied.
What about the reverse, flattening a forwarding-object back into the
real-object?
I presume only the one word of the object-pointer is updated.
btw, are we safe if competing threads write the *same* data to a slot,


Anyway my idea was the GC-thread would only *identify* objects to be
moved, and queue them
for the Main-thread to chip away at, so only one thread is converting
objects to forwarding objects.


> - To decrease the pauses in full GC I have 2 plans:
> -- incremental marking (split the mark pause in multiple small pauses): Not implemented right now.
> -- selective compaction (compacts only part of the heap instead of all the heap and sweeps the rest, similar to G1, but uses forwarders instead of lots of card marking metadata): I implemented SpurSweeper which only sweeps but works very well.
> - Currently the marking phase removes all forwarders and I would like incremental marking to maintain the same invariant (forwarders are always white).

A concurrent-marking thread could essentially do the same.
         i. From shared memory load forwarder F from object-slot
                    F <== object-slot

         ii. Follow forwarder to real-object, store into temporary R
                    R <== flattened/followed pointer

         iii. Atomic compare-and-swap R back into object-slot,
                    object-slot <== if F then R

When (iii.) fails
* If I'm the Main-thread, then an other-thread already did what I wanted,
   and since thats the *only* mutation other-threads can do to an object-slot.
   I am certain...    "object-slot == R",   so since I'm handling a
failed forwarding-check, just continue with the normal retry.
* If I'm an other-thread, no hurry.  Read the object-slot again and it
"should" be a real-object, otherwise just keep trying until I get one.

So the question is... When using forwarders for compaction,
how often would fail forwarder-check fail...
  * if there was one thread on its own; versus
  * in the Main-thread if an other-thread had already flattened many of them


> - In general, Concurrent marking and sweeping have been implemented everywhere, but no concurrent compaction. For compaction you can make it selective (compact only part of the heap and the part which needs it the most) like I suggest and like in G1, which decreases considerably compaction pause time. Work on concurrent compaction is state of the art and not in production everywhere, see for example

IIUC not many other languages use forwarding pointer like we do, and
these seem like a real advantage
to compact incrementally and concurrently.


> No more time right now.

I recognise it wasn't a great format.
I really appreciate the time you could spare.

cheers -ben