-
Garbage: anything reachable, not just variables, but temporary in-expression objects, etc.
-
malloc implementations
- ptmalloc: standard system malloc from glibc
- 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
![Untitled](https://prod-files-secure.s3.us-west-2.amazonaws.com/fd0e9e06-47ef-46a5-bfc2-18344b58b466/1d4ee846-a72a-4551-a913-2e35298b8f47/Untitled.png)
-
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