Practical Garbage Collection

Basic stop-the-world, mark, sweep, resume

A very simple tracing garbage collector works using the following process:

1. Pause the application completely.
2. Mark all objects that are reachable (from the root set, see above) by tracing the object graph (i.e., following references recursively).
3. Free all objects that were not reachable.
4. Resume the application.

In a single-threaded world, this is pretty easy to imagine: The call that is responsible for allocating a new object will either return the new object immediately, or, if the heap is full, initiate the above process to free up space, followed by completing the allocation and returning the object.
None of the JVM garbage collectors work like this. However, it is good to understand this basic form of a garbage collector, as the available garbage collectors are essentially optimizations of the above process.
The two main reasons why the JVM does not implement garbage collection like this are:

• Every single garbage collection pause will be long enough to collect the entire heap; in other words, it has very poor latency.
• For almost all real-world applications, it is by far not the most efficient way to perform garbage

Practical Garbage Collection

Tracing vs. reference counting

You may have heard of reference counting being used (for example, cPython uses a reference counting scheme for most of it’s garbage collection work). I am not going to talk much about it because it is not relevant to JVM:s, except to say two things:

• One property that reference counting garbage collection has is that an object will be known to be unreachable immediately at the point where the last reference is removed.
• Reference counting will not detect as unreachable cyclic data structures, and has some other problems that cause it to not be the end-all be-all garbage collection choice.

The JVM instead uses what is known as a tracing garbage collector. It is called tracing because, at least at an abstract level, the process of identifying garbage involves taking the root set (things like your local variables on your stack or global variables) and tracing a path from those objects to all objects that are directly or indirectly reachable from said root set. Once all reachable (live) objects have been identified, the objects eligible for being freed by the garbage collector have been identified by a proces of elimination.

Practical Garbage Collection

Why should anyone have to care about the garbage collector?

That is a good question. The perfect garbage collector would do its job without a human ever noticing that it exists. Unfortunately, there exists no known perfect (whatever perfection means) garbage collection algorithm. Further, the selection of garbage collectors practically available to most people is additionally limited to a subset of garbage collection algorithms that are in fact implemented. (Similarly, malloc is not perfect either and has its issues, with multiple implementations available with different characteristics. However, this post is not trying to contrast automatic and explicit memory management, although that is an interesting topic.)

The reality is that, as with many technical problems, there are some trade-offs involved. As a rule of thumb, if you’re using the freely available Hotspot based JVM:s (Oracle/Sun, OpenJDK), you mostly notice the garbage collector if you care about latency. If you do not, chances are the garbage collector will not be a bother – other than possibly to select a maximum heap size different from the default.

By latency, in the context of garbage collection, I mean pause times. The garbage collector needs to pause the application sometimes in order to do some of its work; this is often referred to as a stop-the-world pause (the “world” being the observable universe from the perspective of the Java application, or mutator in GC speak (because it is mutating the heap while the garbage collector is trying to collect it). It is important to note that while all practically available garbage collectors impose stop-the-world pauses on the application, the frequency and duration of these pauses vary greatly with the choice of garbage collector, garbage collector settings, and application behavior.

As we shall see, there exists garbage collection algorithms that attempt to avoid the need to ever collect the entire heap in a stop-the-world pause. The reason this is an important property is that if at any point (even if infrequent), you stop the application for a complete collection of the heap, the pause times suffered by the application scale proportionally to the heap size. This is typically the main thing you want to avoid when you care about latency. There are other concerns as well, but this is usually the big one.

Practical Garbage Collection

This is the first part of a series of blog posts I intend to write, whose aim will be to explain how garbage collection works in the real world (in particular, with the JVM). I will cover some theory that I believe is necessary to understand garbage collection enough for practical purposes, but will keep it to a minimum.

The motivation is that garbage collection related questions keeps coming up in variety of circumstances, including (for example) on the Cassandra mailing list. The problem when trying to help is that explaining the nuances of garbage collection is too much of an effort to do ad-hoc in a mailing list reply tailored to that specific situation, and you rarely have enough information about the situation to tell someone what their particular problem is caused by.

I hope that this guide will be something I can point to in answering these questions. I hope that it will be detailed enough to be useful, yet easy to digest and non-academic enough for a broad audience.  I very much appreciate any feedback on what I need to clarify, improve, rip out completely, etc.Much of the information here is not specific to Java. However, in order to avoid constantly invoking generic and abstract terminology, I am going to speak in concrete terms of the Hotspot JVM wherever possible.

Functional Programming on the JVM

Java8 Lambda Expression
Java has finally realized the power of writing code in functional style and is going to support the concept of closures starting from Java8. JSR 335 - Lambda Expressions for the JavaTM Programming Language aims to support programming in a multicore environment by adding closures and related features to the Java language. So it will finally be possible to pass around functions similar to variables in pure Java code.
Currently if someone wants to try out and play around lambda expressions, Project Lambda of OpenJDK provides prototype implementation of JSR-335. Following code snippet should run fine with OpenJDK Project Lambda compiler.

ExecutorService executor = Executors.newCachedThreadPool();

executor.submit(() -> {System.out.println("I am running")})

As can be seen above, a closure(function) has been passed to executor's submit method. It does not take any argument and hence empty brackets () have been placed. This function just prints "I am running" when executed. Just as we can pass functions to function, it will also be possible to create closure within functions and return closure from function. I would recommend to try out OpenJDK to get a feel of lambda expressions which is going to be part of Java8.

Conclusion

So this was all about functional programming, it's concepts, benefits and options available on JVM to write function code. Functional programming requires a different mind-set and can be very useful if used correctly. Functional Programming along with Object Oriented Programming can be a jewel in crown. As discussed there are various options available to write code in functional style that can be executed on JVM. Choice depends on various factors and there is no one language that can be considered best in all aspects. However one thing is for sure, going forward we are going to see more and more usage of functional programming.

Functional Programming on the JVM

Groovy
Groovy is again a dynamic language with some support for functional programming. Amongst the 3 languages, Groovy can be considered weakest in terms of functional programming features. However because of it's dynamic nature and close resemblance to Java, it has been widely accepted and considered good alternative to Java. Groovy does not provide immutable objects out of the box but has excellent support for higher order functions. Immutable objects can be created with annotation @Immutation, but it's far less flexible than immutablity support in Scala and Clojure. In Groovy functions can be passed around just as any other variable in the form of Closures. The same example in Groovy can be written as follows

def numbers = [1,2,3,4,5,6,7,8,9,10]

def total = numbers.inject(0){a,b ->

    a+b
}

However the point to be noted is that variables "numbers" and "total" are not immutable and can be modified at any point of time. Hence writing multithreaded code can be a bit challenging. But Groovy does provide the concept of Actors, Agents and DataFlow variables via library called GPars(Groovy Parallel System) which reduces the challenges associated with multithreaded code to a greater extent.

Functional Programming on the JVM

Clojure

Clojure is a dynamic language with an excellent support for writing code in functional style. It is a dialect of "lisp" programming language with an efficient and robust infrastructure for multithreaded programming. Clojure is predominantly a functional programming language, and features a rich set of immutable, persistent data structures. When mutable state is needed, Clojure offers a software transactional memory system and reactive Agent system that ensure clean, correct multithreaded designs. Apart from this since Clojure is a dynamic language, it allows to modify class definition at run time by adding new methods or modifying existing one at run time. This makes it different from Scala which is a statically typed language.
Immutability is in the root of Clojure. To create immutable list just following needs to be done. By default list in Clojure is immutable, so does not require any extra effort.

(def numbers (list 1 2 3 4 5 6 7 8 9 10))

To add numbers without maintaining state, reduce function can be used as mentioned below

(reduce + 0 '(1 2 3 4 5 6 7 8 9 10))

As can be seen, adding list of numbers just requires one line of code without mutating any state. This is the beauty about functional programming languages and plays an important role for parallel execution.