On 8/14/19 11:30 AM, Gil Tene wrote: > For an easy to follow code example of Mark, Sweep, and Compact, look at the > (ahem...) psMarkSweep.c > code for the compacting OpenJDK ParallelGC oldgen implementation, which does > 4 separate passes ( > http://hg.openjdk.java.net/jdk8u/jdk8u/hotspot/file/7576bbd5a03c/src/share/vm/gc_implementation/parallelScavenge/psMarkSweep.cpp#l201 > ): > > 1. A tracing, pointer chasing pass that marks the live set. > Line 514: // Recursively traverse all live objects and mark them > > 2. A sweeping pass that computes the new object addresses > Line 579: // Now all live objects are marked, compute the new object > addresses. > (new addresses are computed to ”shift everything to one side”, > which, when actually done in pass 4, will compact the heap in place) > > 3. A sweeping pass to adjust references to point to the new object addresses: > Line 598: // Adjust the pointers to reflect the new locations > (this is sometimes referred to as a fixup pass) > > 4. A compact pass that moves the objects to their previously chosen target > locations. > Line 645: // All pointers are now adjusted, move objects accordingly > > This is a classic Mark, Sweep, and Compact collector. Pass 1 only visits > live objects, while passes > 2-4 linearly traverse the entire heap, live or dead), going forward one > object at a time, and > skipping over the dead objects one by one.
I think the descriptions of steps (2) and (3) seriously stretch the definition of "sweep". If we creatively redefine it to mean any (linear) heap walk, then most (all, except for copying?) collectors should be marked as "sweep", which defies the purpose of the definition. This describes Lisp2-style collector, which is listed as (*drumroll*) "Mark-Compact": https://en.wikipedia.org/wiki/Mark-compact_algorithm#LISP2_algorithm GC handbook mentions only "Mark-Compact" and "Mark-Sweep" styles, no "Mark-Sweep-Compact". The MM Glossary [https://www.memorymanagement.org/glossary/s.html#sweeping] says: "Sweeping is the second phase (“the sweep phase”) of the mark-sweep algorithm. It performs a sequential (address-order) pass over memory ***to recycle unmarked blocks.***" (emphasis mine) I would leave "sweep" as something that reclaims the storage of the objects (i.e. "sweeps away" the garbage), which makes M-C and M-S classes more clearly defined and easier to reason about. Introducing the fixup pass is not very relevant here, because it talks about how the heap references are managed, not how the object storage is treated. Regardless of what modern concurrent collector does (separate update-refs phase, piggybacking on next marking, self-fixing barriers) to update the references, the objects are already either copied/compacted away, or the garbage is swept away in (per-object-sized) blocks. -Aleksey -- You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web, visit https://groups.google.com/d/msgid/mechanical-sympathy/74e81f50-2764-af9d-3346-21c4246e91ce%40gmail.com.
signature.asc
Description: OpenPGP digital signature
