• Garbage: anything reachable, not just variables, but temporary in-expression objects, etc.

• malloc implementations

  • ptmalloc: standard system malloc from glibc
    • uses sbrk
  • Apple has libmalloc
  • mimalloc
    • fast, same mem efficiency as ptmalloc
  • jemalloc
    • fast, better mem efficiency
    • favors mmap over sbrk
    • uses a number of arenas, for different alloc sizes; limits fragmentation
      • e.g. if you allocate big then small, then free big, you will free RSS
    • was main allocator in Rust before they defaulted to standard system

• GC design axes

  • moving (compacting) vs non-moving
    • moving: no extra work to reclaim dead space; fast subseq allocs; survivor locality
    • non-moving: no need to copy; no need to update refs
  • copying vs mark-and-sweep vs mark-and-don't-sweep
    • copying: switch btwn 2 regions; copy while traversing; requires 2x space
    • mark-sweep: mark while traversing; sweep separately; sweep can be either moving or non-moving depending on avail mem
  • stop-the-world vs incremental vs concurrent
    • generational aka ephemeral: particular case of incremental
      • inspect younger gens more frequently
      • promote multi-cycle survivors to old gen
      • cross-gen links are perf problem
      • still need to do full GCs at some point
  • precise vs conservative
    • internal ptrs: ptrs to fields in objects (C)

• Generational

  • Generational hypothesis
    • Most objects die young
    • Old objects rarely reference young objects
  • Particular case of incremental

  

• boehm: conservative, incremental, mark-sweep; competitive speed

• hybrids in Java/.NET: generational with occasional mark-and-sweep and rarer full-copying

• great big FAQ: http://www.iecc.com/gclist/GC-faq.html

• tricolor algorithm

  • introduce a gray color, which means “processing its subgraph”
  • As long as there exists gray, don’t collect!
  • Use write barrier on pointers to maintain invariant that black can only point to black/gray, and gray can only point to gray/white
  • Example: say A → B. Mark them black or gray. If C → D is created and A → C (→ D), then mark it C gray (via write barrier).
    • Won’t collect D because there are gray.
    • B is still black but that’s OK, just conservatively won’t collect, will be white next time.

• implementations

  • Go: tricolor, non-compacting, sub-1ms (source)
  • JVM
    • Oracle ZGC: compacting, max pause <1ms, avg 50us
    • Red Hat Shenandoah: similar

Azul's pauseless GC (managed runtime initiative aka MRI)

• GC pauses: biggest pain point in modern JVMs
  • every other GC delays moving objects around
• azul is different: the only way it collects is by compaction
• single pass marking of live objs; no need to revisit refs
  • special read barrier: ea time read ref, VM intercepts to ensure obj is marked if it isn't already
  • GC thus insensitive to ref mutation rate
• concurrent compaction: move an object without updating all its refs
  • self healing: read barriers also allow refs to be updated as they're deref'd
• massive and rapid manipulation of virtual mem mappings, at rate of allocation
  • requires changes to OS kernels
  • "quick release": once relocated/compacted objs out of a page, keep forwarding info outside the page, so can immediately release the physical page behind the physical mapping (refs are all intercepted) and recycle it at a diff virt addr for allocation/app use again
• slightly lower all-around perf
• http://www.artima.com/lejava/articles/azul_pauseless_gc.html

Hotspot GC

• generational GC
  • objs count number of GCs they survived; big counts promote them to older generation