28
$\begingroup$

Generally speaking, higher-level programming languages seem to utilize garbage collection.

As a first example, Python uses reference counting (as well as three-level generational collection that just cleans up container objects.) Another example would be JVM, Java's Virtual Machine, which utilizes five different GC implementations. Specifically, those are:

  • Serial Garbage Collector
  • Parallel Garbage Collector
  • CMS (Concurrent Mark and Sweep) Garbage Collector
  • G1 (Garbage first) Garbage Collector
  • Z Garbage Collector

But I'm clueless about how these all work and which ones provide what benefits.

What are the different approaches to garbage collection, and what are the benefits of each approach?

$\endgroup$
6
  • 2
    $\begingroup$ Please let me know if this is far too broad for the site's scope! $\endgroup$
    – Spevacus
    May 16, 2023 at 17:27
  • $\begingroup$ too broad doesn't really matter that much when a site is new, later it will become more important $\endgroup$
    – mousetail
    May 16, 2023 at 17:28
  • $\begingroup$ @mousetail Quite the contrary! During the first few weeks of a site, it's especially important to avoid broad questions. If you seed the site with broad questions — which so far seems alarmingly to be the case — then you're just reinventing Wikipedia, not creating a site that's likely to attract experts. $\endgroup$ May 20, 2023 at 21:51
  • $\begingroup$ @Gilles'SO-stopbeingevil' Yea we've overdone it a bit but in general a site should go from more broad to more specific over time. We've over-saturated the broad side of the spectrum currently though, but are actively working to rectify that issue $\endgroup$
    – mousetail
    May 21, 2023 at 5:35
  • $\begingroup$ @mousetail “a site should go from more broad to more specific over time” no, absolutely not. Broad questions will come naturally. Seeding the site with broad question during the early beta is a sure fire way to make it boring because it's just rehashing content that you can find elsewhere. $\endgroup$ May 21, 2023 at 10:06

4 Answers 4

13
$\begingroup$

Mark-and-sweep collectors

Simple mark-and-sweep collectors attach a separate boolean to every allocated "object", and somehow keep track of every living object (you can imagine this as a big list of pointers, but they're usually slightly cleverer — it doesn't matter for this description). They also have an idea of what "roots" are accessible directly - these are things like global variables, local scopes that are currently running, whatever is applicable to the language.

The collection phase has four steps:

  1. Stop the world: prevent anything else in the program from happening while the collection runs. Usually the collector runs right before an object would be allocated, and just holds up the rest of the program until it returns, which could be a while.

  2. Go through every living object and set the marker boolean to false. Commonly this property is actually established at creation and reset at the end of the collection, but I'll list it here explicitly.

  3. Starting at each root

    1. Set its marker to true.
    2. For each reference contained in this object (in a field, the surrounding scope, ...), perform step 3 with that object as the root. If the marker is already set, just move on to the next object.

    Once every root has been processed, the "mark" phase is complete.

  4. Go through every object again, and release any object whose marker isn't set. This object wasn't reachable from any of the roots, so we know the program can never access it again.

    If the marker was set, unset it ready for the next collection. This is the "sweep" phase.

This is the model for a single-threaded collector with no optimisations. Slightly smarter mark-and-sweep collectors have multiple levels of marking, move objects around, and so on, but the core approach works like this.

Tri-colour mark and sweep

In particular, a tri-colour system is a smarter mark-and-sweep system with three levels of marker instead of two: grey objects are known to be reachable from the roots, black objects are known to be reachable and have had all of their children marked grey, and white objects haven't been examined yet. These markers can be updated piecewise: pick a grey object, mark it black, and mark every white object it references as grey.

When there are no grey objects left, all the white ones are objects that couldn't be reached from the root, so they are freed and the process starts again.

This process can happen in multiple steps, each only moving a few objects from grey to black, so there doesn't need to be one big pause to look at everything. Every object is inspected at some point, however.

Advantages and Disadvantages

There are two main advantages of this approach:

  1. It is guaranteed to free every unreachable object, even if it's within a reference cycle.
  2. It's fairly straightforward to implement.

For these reasons it's not uncommon for a mark-and-sweep phase to be included within more advanced collectors. The disadvantages tend to outweigh the benefits as the main strategy, however:

  1. It's slow. It has to inspect every object in the system multiple times, every time.

    Tri-colour marking spreads the work out over time, but it still does it. In some situations, like user interfaces, one big pause is unacceptable but many smaller ones are ok, but in others this doesn't make much difference.

  2. It relies on stopping every thread until the collection is done.

  3. It has poor memory locality because it is always jumping between objects.

  4. The naïve releasing strategy I described tends to fragment memory quite badly.

When there is a relatively small number of objects (such as within a nursery of a generational collector), or where the completeness properties are desired (such as for occasionally reclaiming reference cycles left by a more efficient reference-counting collector) it can be useful. For cases where raw performance isn't very important but catching escaped reference cycles is, this is a sensible cheap-to-implement strategy.

$\endgroup$
12
$\begingroup$

Generational Garbage Collection

Generational garbage collection is a great tool in a language where small amounts of data are created and destroyed constantly, such as in a purely functional language (where "slightly modified" versions of data are constantly being constructed). The idea is simple: Most data will either die young or live a very long time, so if we optimize for freeing recently allocated memory, that will handle the most common cases. The popular Haskell compiler GHC uses one of these on the backend.

In its simplest form, a generational garbage collector has two generation: short-term storage and long-term storage, with the former being a much smaller data store. All new data is allocated in short-term storage. When short-term storage gets full, we run a mark-and-sweep garbage collection pass on only that small collection of data, freeing anything that we deem unreachable. If, after that pass, short-term storage is still occupied above some threshold, then we move all of that data to long-term storage and start a new, empty short-term storage region (in practice, this "move" is trivial and simply involves marking that buffer as long-term and creating a new one elsewhere). We monitor the total occupied space of long-term storage and run a full mark-and-sweep pass on all of our memory if it gets too full, but the idea is that this happens very infrequently.

The fundamental invariant of generational garbage collection is: Data can never point to data in a younger generation.

In a language with immutable data such as Haskell, this is a very simple, elegant algorithm, and short-term sweeps are fast. Since data is immutable[1], it's impossible for data to point to anything allocated after it. That is, nothing in long-term storage can ever point to short-term storage, so when we do a short-term sweep, we don't even have to think about long-term storage. Data can be cyclic, so data in short-term can point to other short-term data, if both were allocated at the same time. This can arise when tying the knot, for instance. But cycles can never span generations.

In a language with mutable data, this requires some special handling when a pointer is reassigned. If we take some data in long-term storage and reassign it so that it points to data in short-term storage, we either have to make a global note of that for the mark-and-sweep algorithm, or we have to regress the long-term data back into short-term storage.


[1] With the exception of IORef, which already has special handling.

$\endgroup$
9
$\begingroup$

Pure ARC

This is what Swift uses, and many (but not all) Objective-C projects.

ARC stands for “automated reference counting”. It automatically keeps track of how many references there are to an object, and deallocates the memory when that number hits 0.

Advantages

  • Fast: Because there’s no need for a garbage collector to perform tracing or seek out unreferenced objects, there is significantly less processor and even memory overhead. When Apple introduced GC to Objective-C, they never implemented it for iOS, citing that ARC was more power-friendly on mobile devices.
  • Simple: It’s very straightforward to implement reference counting from scratch.

Disadvantages

  • Reference cycles: ARC by itself will never deallocate two objects that reference each other. Thus, you need the concept of a weak reference: a reference that doesn’t affect the refcount. Knowing when to use weak references puts more burden on the programmer and can be confusing to beginners.
  • Frequency: If two objects pass the same reference back and forth, this can cause a lot of “ARC traffic” for something that won’t be deallocated. Not to say that no other GC system does this, but ime a lot of real-time Swift code goes out of its way to minimize changes to the refcount.
  • Depth: If you delete the root of a very deep object tree, the chain of deallocations can blow the call stack. In some cases it’s possible to avoid this by e.g. scheduling the deallocation to occur on the next cycle of the run loop, but not all ARC languages give you control over this.
$\endgroup$
9
  • $\begingroup$ PHP uses reference counting but it's OK because it's intended for short-running scripts $\endgroup$
    – mousetail
    May 16, 2023 at 18:00
  • $\begingroup$ @mousetail Some garbage collectors use refcount + something else. That’s why I specified “pure ARC” in the title, to distinguish it from RC + other. $\endgroup$
    – Bbrk24
    May 16, 2023 at 18:30
  • $\begingroup$ PHP has pure refcount. I don't know any garbage collector that does not have refcount, it's the basis for pretty much every other system $\endgroup$
    – mousetail
    May 16, 2023 at 18:33
  • $\begingroup$ I don’t know much about how GC works for a lot of modern languages. I’m sure there’s some weird stuff out there I’d never think of. $\endgroup$
    – Bbrk24
    May 16, 2023 at 18:34
  • 2
    $\begingroup$ PHP does have a GC which collects cycles. $\endgroup$
    – kaya3
    May 17, 2023 at 3:45
4
$\begingroup$

Some people argue (to death 😏) Reference Counting is not a Garbage Collection technique, but the GC Handbook lists it, discusses and compares, and that's the definitive reference. 😁

A unified theory of garbage collection paper goes a bit further and shows the duality between ("pure") tracing GC and RC, while collectors used in practice implement some "hybridisation" of both.

So we can establish the first dimension of the GC (design) space: on one side tracing GCs that traverse live objects, and opposite to them RC that traverses dead objects (imaging you have a huge tree with no links to nodes except from a parent node, and now the root of the tree becomes unreachable — reference counter goes 0, you deallocate the node and decrease counters of all it's children, which go 0 too, so you now have to deallocate them too, and so on until you traverse and deallocate all the now-garbage; while tracing GC would evacuate live objects and deallocate the whole region of memory regardless of which objects are dead inside it and how they are interconnected).

Another dimension is concurrency and parallelism, which are different notions. A parallel GC can use several cores at the same time to mark live objects and/or move/copy and/or free/compact memory. While concurrent GC can do that while program does it work and allocates new objects/forgets about the old ones. Concurrent GC might do that in a single thread or in a parallel fashion. There's also a notion of incrementality: incremental GC can do some work, then stop, then resume from the same spot. Some people use "concurrent" and "incremental" as synonyms — obviously, if you have an incremental GC you can turn it into concurrent by running preemptively with mutators.

But these are kinda internal GC properties, from an external point of view, the main characteristics of a GC are throughput, latency and space (overhead).

Throughput (as per usual) is how much garbage a collector can free per (sizeable) unit of time. It's very important if an application works in bursts allocating lots of temporary objects that need to be quickly freed before the next burst. Often Stop-the-World (STW) parallel collectors provide highest throughput.

Most usual throughput conflicts with latency i.e. how long a mutator thread have to wait for the GC to do its work before mutator can continue doing something useful. Modern GCs like the Java's Z and Shenandoha exhibit extremely low latencies.

Finally most GCs (RCs might show a counterexample) incur some memory overhead. The most obvious case is two-space copying collector that requires twice as much memory as the application otherwise would use.

And that's just the general very superficial picture, while there are lots of implementation details and programming language and application and workload specifics.

That said, I'd claim that well-designed and well-optimized tracing GC is overall more performant and beneficial that (general) reference counting. But very hard to implement. Still "serious languages" like Kotlin Native and AssemblyScript went from an RC to a tracing GC (somewhat recently).

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .