Parallel GC and Concurrent GC

Parallel GC and Concurrent GC

Parallel GC

Goal

Utilize multicore power to speed up GC

TradeOff

• Need to sync works between different process(reside on different cpu), collector thread can have local work list and global work list and steal work from global list or other collector's list(thus requires sync)
• Different architecture provide different memory model, need to implement with memory fences

Incremental GC

One GC cycle will be separated into multiple increments(smaller portion of work). Mutator and Collector will work one after another but not parallel.(When collector works mutator will stop).

Goal

Reduce duration of single GC pause

TradeOff

• More work should be done such as record keeping(which objects are mark but not yet collected)
• More head room required since heap will be fully collected several(or more) GC cycle later

Concurrent GC

Mutator and Collector and work at the same time(in parallel)

Goal

Reduce duration of single GC pause, or even erase GC pasu.

On the fly concurrent GC:

Different round GC cycle can run parallel, so Marking phase mutator of round 1st may work parallel with a marking phase mutator of round 2nd. Therefore must distinguish white obj from past round and current round. Solution: introduce purple color, etc

Note

Actually short period of stop the world will happened, like mark the roots for one collector thread and defer other GC thread's roots scan Total wait-free algo is possible but actually more costly than pause for a short while, otherwise multi phase hand shake can be used to sync all mutator into same phase(mark).

TradeOff

To let mutator and collector have a consistent view of heap, write and read barrier is required(more work added to mutator) For moving collectors, need read barrier since mutator may reading an obj being moved partially

Tricolor GC Model

GC works like DFS - White Objects: Not yet scanned(before scanned starts) or Unreachable(after scan finished), will be reclaimed - Grey: scanned with neighbors not fully scanned - Black: scanned with all neighbors scanned. Under concurrent GC, mutator may 1. let black obj ref a grey directly reachable white obj -> a reachable obj will be reclaimed wrongly 2. let black obj ref a white directly object but grey indirectly reachable, * ref means delete pointer from old obj and assign to new obj

General barriers

• Insertion barriers: when insert a white obj to black obj, shade the white obj(black to defer to next round, grey for near rescan)
• Deletion barriers: when deletion ref of a white/grey obj from white/grey obj, shade it or mark it, etc.

  Feeling

  deletion b' is wider than insertion b'

  Allocation

  Besides mutator, allocator also need to color obj based on specific strategy when allocating obj in mark/collect phase.