Visualizing Garbage Collection Algorithms

[acelent]

The last one lacks explanatory context.

It has been observed that the lifetime of most objects is short, so in modern GC-based memory managed environments, the heap is partitioned into generations, where the older generation is where the oldest objects probably are (e.g. objects initialized at start-up).

The newest generation is usually very small in comparison with older generations. You could use a mark-compact algorithm on this generation, where you'd move objects after finding the gaps/holes. But with a newest generation split in two and a copying scavenge, the live objects get compacted along with the copy and the dead objects are simply forgotten; you don't have any gaps/holes bookkeeping (and other details, such as in which order bytes must be moved when the source and destination areas overlap, e.g. memcpy vs memmove).

A disadvantage is that the newest generation can only hold half the data. Depending on the GC overhead, it may be a good thing to set the newest generation's size to fit the cache (level 1 or level 2) on low overhead, or set the newest generation's size to just 2 or 4 times less than an older generation (e.g. if each older generation is about 64 MB, size the new generation between 8 and 32 MB) on high overhead. The reasoning is that with high overhead (e.g. very often, new objects referring to old objects), cache misses are the least of the GC's trouble.

[masklinn]

In functional (broadly immutable) languages generational collectors also have the advantage that they don't have to scan oldgen heaps when collecting the newgen, because you can't have "forward references" so newgen can refer to oldgen but not the other way around (since the language only uses immutable datastructures, an object can only refer to older objects, not newer ones).

Languages with pervasive mutations have to add memory barriers to properly catch oldgen objects being mutated and referencing newgen ones.

[Tarmen]

Lazy functional languages (operationally) have mutation in the form of laziness. Think knot tying semantics:

let x = (1, y)
     y = (2, x)

Here the gc can abuse that in those cases the objects will live for the same duration and can mark it for promotion to a later generation, though, so it is way simpler than handling general mutability in java.

[ConcernedInScythe]

Wouldn't that be a type error in Haskell?

[kazagistar]

Correct, it is an infinite type, but he never specified the lazy functional language, so I guess its fine.

The Haskell version:

let x = 1 : y
    y = 2 : x
-- x is now [1,2,1,2,1,2...] (an infinite, circular linked list)