I've taken to using Mark-Sweep-Compact, Mark-Sweep (no Compact), and Mark-Compact (no sweep) to describe the variants, because you will find all of them in the wild these days.
The confusion starts with the fact that some algorithms that people often refer to as "Mark-Sweep" are actually Mark-Sweep-Compact, while other are purely Mark- Sweep (with no compaction). Mark-Sweep with no compaction usually means that free memory is recycled in place, with no object movement. A good example of this in practice is the CMS collector in the HotSpot JVM, which tracks unused memory in the oldgen in some form of free lists, but does not move any objects in the oldgen to compact it. Mark-Sweep *with* compaction (Mark-Sweep-Compact) obviously does compact. It usually implies the use of the knowledge established during a sweep (e.g. a list of the empty ranges) to compact the space "in place", It also usually involves a complete fixup of all references in all live objects. E.g. a simplistic description of a common Mark-Sweep-Compact technique would involves: (A) mark the live objects in the heap, (B) sweep the heap to find the empty ranges, (C) move all live objects to one side of the heap (filling in the empty spaces), (D) linearly scan all live objects and fix up any references in them to point to the correct target location. A good example of this in practice is the ParallelGC and SerialGC collectors in the HotSpot JVM. Similarly, more confusion is caused by the fact that some algorithms that people often refer to as "Mark-Compact" are actually "Mark-Sweep-Compact", while other are purely Mark-Compact (no sweep). Again a good example of the first in common use would be ParallelGC in the HotSpot JVM (and the Wikipedia entry https://en.wikipedia.org/wiki/Mark-compact_algorithm). Good examples for the latter in common use can be found in various regional evacuating collectors (like C4, G1, etc.), where there is no sweep per-se (live object are evacuated to outside of the originally marked heap, and there is some mechanism for finding/tracking them to do so, but that mechanism is not the traditional sweep used by Mark-Sweep style of collectors). Fixup behavior in such algorithms can also vary quite a bit (e.g. C4 normally uses the next cycle's Mark to perform fixups for the previous Compact's relocated objects, and as such does not require a scanning fixup pass). Another key difference often pointed to is that with in-place compaction (Mark-Sweep-Compact), no additional empty memory is required to guaranteed full compaction, while regional evacuating collectors need to evacuate into some empty memory, so their ability to compact may be limited by the amount of empty memory available outside of the currently occupied heap regions. However,. several well documented regional collector algorithms (e.g. Pauseless <https://www.usenix.org/legacy/events/vee05/full_papers/p46-click.pdf>, C4 <http://paperhub.s3.amazonaws.com/d14661878f7811e5ee9c43de88414e86.pdf>, Compressor <http://www.cs.technion.ac.il/~erez/Papers/compressor-pldi.pdf>) perform hand-over-hand compaction to guarantee forward progress in evacuation, such that a single empty region is sufficient to achieve full compaction in a single pass. On Sunday, August 13, 2017 at 10:47:01 PM UTC-7, Peter Veentjer wrote: > > I have been improving my gc knowledge and there is some confusion on my > side regarding the 'mark-sweep-compact' algorithm I frequently see > mentioned in posts, articles and some not too formal books on the topic. > E.g. > > > https://plumbr.eu/handbook/garbage-collection-algorithms/removing-unused-objects/compact > https://www.infoq.com/news/2015/12/java-garbage-collection-minibook > > AFAIK mark-sweep-compact is not correct. It is either mark-sweep or > mark-compact where as part of the compacting process the dead objects are > removed. When I check more formal literature like "The Garbage Collection > Handbook: the Art of Automatic Memory Management", then there is no > mentioning of mark-sweep-compact. > > So I guess that when 'mark-sweep-compact' is mentioned, they are actually > referring to 'mark-compact'. Is this assumption correct? > > -- 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]. For more options, visit https://groups.google.com/d/optout.
