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

3 Dec 2017

      Hi Eliot, Clement,
On 7 July 2017 at 00:41, Eliot Miranda eliot.miranda@gmail.com wrote:
...
...

Better support for large heaps (GC tuning API, incremental GC).

Pharo 64 bit is now able to manage large heap. However better
performance can be proposed by offering better settings for the
different GC zone.
The most important thing here is the incremental GC.  Spur has a generation
scavenger that collects garbage in newly created objects (new space),
and a mark-compact collector that collects and compacts garbage in old space.
Right now on my 2.3GHz MacMini doing normal development, the generation
scavenger causes pauses of 1ms or less, and the mark-compact collector
than causes pauses of around 200ms.  Both account for about 0.75% of
entire execution time (1.5% total), so the scavenger is invoked frequently
and the pauses that it creates are not noticeable.  But the occasional
pauses created by the mark-compact collector /are/ noticeable,
especially in games and music.
The idea for the incremental collector is to implement a mark-sweep or
mark-sweep-compact collector for old space that works incrementally,
doing a little bit of work on each invocation, probably immediately after a scavenge.
It is intended to avoid the long pauses caused by the non-incremental
mark-compact collector and make the system more suitable for games, music, etc.
Reading http://www.mirandabanda.org/cogblog/2013/09/13/lazy-become-and-a-partial-rea...
  "An alternative implementation, oft-used in Lisp systems, is to add a
  read barrier to all object access, and mark objects as forwarders.
  This can be used to implement a >>>lazy copying garbage collection<<<<
  where objects are copied from one semi-space to another in parallel to the
  main program (the “mutator”).  To become, or move an object one replaces the
  object’s header or first field with a forwarding pointer to the desired target
  or copy in a new location, marking the “corpse” as forwarded.  The program
  checks the forwarded flag on each access.  If there is hardware support,
  as in a Lisp machine, this can work well.  But without hardware support,
  and like the object table representation, it has costs, slowing down
  program execution due to the scattering of forwarding checks and
  forwarding pointer follows throughout program execution."
I'm curious... Given we now have forwarders with Spur, are we
already sufficiently paying the cost of forwarding checks that a lazy copying
garbage collector might be a feasible form of incremental garbage collection?
I presume "parallel to the main program" means garbage collection occuring
in a separate thread to the main vm thread, potentially resulting in
very low main program pause times for garbage collection.
I found this a useful summary of the terminology...
* https://www.dynatrace.com/resources/ebooks/javabook/reduce-garbage-collectio...
and I'm curious how our planned Incremental CG fits those categories.
That article got me contemplating our performance constraint of the VM only
operating in only in a single native thread. Even though GC is a only
a few percent of performance, I wondered what a concurrent GC might
look like for us.
I found this video describing concurrent GC in Go (ignore first 11:20
and the second half was not so interesting)
* https://pusher.com/sessions/meetup/the-realtime-guild/golangs-realtime-garba...
where they present some interesting charts of their concern with latency pauses.
(btw they reference a multi-language GC latency benchmark
  https://github.com/WillSewell/gc-latency-experiment)
And for balance of that I found...
https://blog.plan99.net/modern-garbage-collection-911ef4f8bd8e
And then my mind wandered around implementation details of concurrent
garbage collection.
To organise and quiet my thoughts I needed to put pen to paper, so I
thought sharing that
might stir thoughts for others.  Probably naive and please excuse the
brain dump format...
Considering two threads...
* Main program thread "MP"
* Garbage collection thread "GC"
with object-space shared between them, consisting of objects split in
object-header & object-body...
1. Only "MP" mutates the object-body, updating slots creating new edges
   in the object-graph, and relocating objects in memory using forwarders.
   This rule avoids potential race conditions without needing to add
   synchronisation code affecting performance of "MP".
2. Concurrently "GC" performs a Marking Phase by following the object-graph
   tricolour tagging objects gray & black. it needs to mutate the object-header,
   in a synchronised way something like...
     a. Load object-header from shared object-space into local variable
          H <== object-header
     b. Modify header into another local variable
          H' <== H + updated GC color bits
     c. Atomic compare-and-swap H' back into object-space
          object-header <== if H then H'
     "MP" gets priority. Conflicts presumed rare.
Then considering object mutation by "MP" concurrent/overlapped with
"GC" marking...
3. TLDR; see 4.
   In old-space if 'mutated' object is linked to a 'target' object
     a. if 'mutated' isBlack, "MP" marks 'target' gray (to be later
processed by "GC").
b. if 'mutated' isGray, overlapped 'mutated' gray->black by "GC"
while 'target'
        remains white would break tricolor invariant (is it a credible
case?), options...
          i. mark 'target' gray, the state anyway in case 'mutated'
gray -> black
          ii. re-mark 'mutated' gray, i.e. normally gray->gray, and
rarely black->gray
          iii. optimisticly just check after mutation if color changed
(cached reads
               cheaper than writes and conflicts presumed rare) then
set color to gray.
c. if 'mutated' isWhite, options...
          i. do nothing and let "GC" reach 'target' normally, as long
as overlapped white->black cannot occur
          ii. if white->black possible, do same as (3.b) "MP" marks
'target' gray, to be later processed by "GC".
4. Overall simplification of (3.) might be...
     "MP" checks for any color change during mutation, and only then
marks 'mutated' object gray.
     How expensive would such a check be?  Presumed marking is infrequent and
     can be done safely like (2.)
5. Eden/survivor space is ignored by "GC" thread. No point in adding
work to the gray set
    until survivors filtered. Stop the world scavenging done as normal by "MP",
    only marking objects gray when they are moved to old-space.
Post scavenging options...
       a. Resume the world and leave it for "GC" to process these
recently grayed objects.
b. Keep world stopped for "MP" to complete marking, emptying gray set to
           transition to Sweep Phase, at which point "MP" resumes the world.
           It doesn't matter if subsequently objects are added to the gray set,
           since existing white objects can never again be referenced by "MP".
6. Sweeping can be safely done by "GC" since white-objects are
unreachable from "MP".
   "GC" can also take time to determine an optimum page P to compact and
   then (per 1.) passes to "MP" via a relocation-queue the objects to be
   relocated using forwarding pointers. "GC" could even spend extra time
   to determine the optimum relocation-destination without impacting the
   performance of "MP".  When "MP" empties the relocation-queue, "GC" starts
   on the next Marking Phase.
7. Now a question remains about multi-threaded flattening of
forwarding pointers.
    If two threads simultaneously perform an identical transform from...
       someObject-slot --> forwarder-b --> finalObject-c
    to...
       someObject-slot --> finalObject-c
    does it matter that these operation may be done twice overlapping?
Options...
a. One mitigation could be for "GC" to identify forwarders to be flattened
        and queue them for "MP" to process (reuse the compaction-queue).  This
        is work that "MP" would need to do anyway, but brings it forward to be
        dealt with at a convenient time.
b. I guess "MP" and "GC" could play nice together if when encountering
        a slot containing with a forwarding pointer they both do
something similar to (2.) like...
          i. Load object-slot from shared object-space into local
variable S <== slot
         ii. Set local variable S' <== flattened/followed pointer
        iii. Atomic compare-and-swap S' back into object-space,
(object-slot <== if S then S')
             - "MP" gets priority but presume conflicts rare anyway.
             - While this violates rule (1.) the presumed frequency of
               encountering forwarding pointers is low for "MP", so performance
               should not be affected. Indeed by "GC" pre-emptively
flattening forwarders
               the frequency "MP" sees reduces.
8. The release of the compacted page back to the OS is held up by
forwarding pointers.
   Forwarders are part of the graph followed in the Marking Phase they get
   marked gray/black just like objects if they are referenced.  After
forwarders are
   fully flattened they are skipped by Marking and end up marked white
and released
   just like any other object. Once all forwarders are released, the
page is released
   to the OS.   If "GC" can effectively flatten pointers concurrently
with "MP" during its
   normal Marking Phase, then pages would be released back to the OS
in a timely manner.
Now one thing I am curious about how the GC tri-color marking is implemented.
At https://clementbera.wordpress.com/2014/01/16/spurs-new-object-format
it describes how Spur's object header has three bits for GC.
* isGray
* isRemembered
* isMarked  (I presume this means marked "black")
Do the bits imply the gray set is not stored in a separate data
structure on the heap, but rather distributed in-place, which I guess
would require multiple passes through memory to grow the gray set?
So this is not an area I'm set up to seriously work on, but I remain curious
and hopefully its a useful seed discussion for others.
cheers -ben
P.S. At https://clementbera.wordpress.com/2017/09/19/vm-learning-memory-management/
nice to hear that you have Sophie (I presume) continuing with the VM.