Blog

Garbage Collection, Part 2 – Mark and Sweep Algorithms

“Under the Hood” blog series – getting a deeper technical insight like the mobile solutions, JVM, computer languages, scripts, databases and other interesting tools and technologies. Each blog in this series is a result from our experiences, customer projects and gained knowledge through the web community.

The heap space is separated into the young and old generation memory pools. Each pool has its own generational garbage collector. Due to the fact that objects in the young generation keep alive for a very short period and objects in the old generation live longer different collection algorithms are required.

Mark-and-Sweep Algorithm

Garbage collectors in the HotSpot JVM are based on the Mark-and-Sweep algorithm. The algorithm identifies reachable objects (marking) and then assigns unreachable objects as free memory (sweeping):

Mark Objects
Starting from a root reference the algorithm iterates through all linked objects and marks them as live objects. Root references are:

  • local variables defined in a method within a thread stack and
  • global references declared as static variables in a class.

Sweep Objects
In the sweep phase of the Mark-and-Sweep algorithm all unreachable objects are declared as free memory.

Fragmentation

The Mark-and-Sweep algorithm is fast on one hand but on the other hand it creates a fragmented memory. The total free memory is not available in one block but spread between used memory blocks (=objects). The following illustrates the memory with used memory blocks for live objects (marked as X) and free memory (green):

Mark-and-Copy

A variant of Mark-and-Sweep is the Mark-and-Copy algorithm to avoid fragmentation. During the sweep phase all life objects are evacuated into another memory space. In the young generation it is the Survivor space. There are two Survivor spaces: the “From” and “To” space.

All life objects initially created in the Eden space are copied during a garbage collection into the To space. The To space is always empty. Life objects in the From space are also evacuated into the To space. Objects in the Eden and From space being bigger or does not fit into the To space are directly copied to the old generation. The following figure illustrates this:

Source: “Memory Management in the Java HotSpot Virtual Machine” White Paper, Figure 3, page 8

Once a garbage collection is finished the Survivor spaces switches their role:

  • The From space becomes the empty To space and
  • The To space becomes the From space.

The memory looks as follows:

Source: “Memory Management in the Java HotSpot Virtual Machine” White Paper, Figure 4, page 9

Generational Collection

As mentioned in the first blog the heap space is separated into the:

  • Young generation: where short-term objects and
  • Old generation: where long-term (and big) objects live.

In the HotSpot JVM objects are declared as old when they have survived some number of young generation collections. These objects are then copied from the young into the old generation.

Large objects being too big for the Eden or Survivor spaces are also copied into the old generation.

Mark-Sweep-Compact

The old generation compared to the young generation varies in several ways:.

  1. Longer lifecycle: objects in the old generation stays longer alive than in the young generation. Many objects in the young generation are freed in a short time. In the old generation few objects are freed in a much longer time.
  2. Bigger memory size: the old generation requires more memory than the young generation. Here objects resides for a longer period and the amount of objects increases and requires more space.
  3. Fewer allocations: In the young generation all new objects are allocated into the Eden space. Whereas in the old generation only objects are allocated when being copied from the young generation.
  4. Fewer references: references are mostly created during initialization of new objects. Few references are created in the old generation.

Useful Links

Kommentare

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *