Garbage Collection and Scope

Garbage collection (GC) is one of those programming language features that you are supposed to not have to think about, but anyone who has tried to optimize the performance of Java applications will know that managing memory is often the most effective way of speeding things up. The less time the garbage collector has to spend running, the more time your program can have to run. I recently came across an aspect of code design that turns out to have a significant impact on memory performance. Consider the following program:


It is a toy program, but it is designed the emulate the following sequence of events (both the handle1 and handle2 methods):

• you receive a raw stream of bytes from somewhere, e.g. the network;
• you deserialize the bytes into something meaningful, e.g. a web request; and
• you do some processing with the deserialized data, e.g. handling a web request by doing some database operations and returning a response.

Here we are getting the bytes by just allocating a 256MB array and then "deserializing" the bytes into integers. And lastly, the "processing" consists of just repeatedly allocating 1MB arrays until we hit an error (in particular, we are expecting an OutOfMemoryError). The idea is that the handleInts method figures out roughly how much free memory the JVM has at the point at which it is called (forcing GC as necessary) in order to evaluate the relative efficiency of the two versions of code.

It turns out that handle2 is about 256MB more efficient than handle1 as measured by the number of allocations done in handleInts, despite the fact that the two methods are functionally identical. The reason is scope, although not quite in the traditional programming language sense. We have two representations of the data in the code, one as an array of bytes and the other as an array of integers, each of which is about 256MB in size. Conceptually, once we have deserialized the bytes as integers, we can discard the array of bytes, i.e. allow it to be garbage collected. And that is exactly what happens in handle2; the scope of the array of bytes is limited to the time during which it is being deserialized. In handle1, however, we are passing the array of bytes as a method parameter to the method which eventually ends up calling handleInts. That means, in particular, that a reference to the array is living on the call stack, which is a GC root, so it cannot be garbage collected while the method is running.

In my mind, this example raises some interesting questions about how code should be designed and the impact of different design patterns on GC performance. Specifically, we know that having a very deep call stacks, especially when methods do transformations on the data, can lead to larger retained sets of objects (those that cannot be collected) than intended. In an ideal world, a programmer using a language with built-in memory management should not have to be concerned with this, though, so it would be even better if the compiler or JVM could identify this type of situation and make the correct optimization.

Multithreading is Hard

Over the last few years, I have repeatedly found myself working with complex, multithreaded Java applications that produce all sorts of bugs that are extremely difficult to identify, reproduce, and fix. And in doing so, I have learned a great deal about the Java memory model, the various synchronization primitives (e.g. locks, semaphores, atomic references), and useful concurrent abstractions (e.g. blocking queues, executor services). With enough knowledge and experience with multithreaded programming in Java, it is possible to design and implement complex systems that, after some time, you have modest confidence in. But not only does it take a very long time to get to that point (typically on the order of years for large projects), I would also guess that most programmers have less confidence in their programs than they wish they could. It is also not uncommon for mature projects to still be littered with minor race conditions and rare deadlocks that pop up over time when some poor engineer has to debug why their production system failed. To some degree we have just accepted that the systems we build and the libraries we write will inevitably suffer from bugs that we cannot preemptively identify and fix. I recently came across this technical report by Professor Lee from Berkeley that I feel very clearly identifies the problem, which is the concept of threads and how they are materialized in today's languages.

The main argument, which I have seen formulated in a number of ways, is that because the execution of a multithreaded program is nondeterministic, we cannot efficiently reason about correctness. In a single-threaded program, you only need to guarantee that the single, deterministic execution of the program produces the correct result; even then it can be difficult to convince yourself of correctness (since the space of possible inputs is often exponential in the size of the input), but people have become reasonably proficient at doing so. Once you introduce multithreading, the number of potential executions from interleaving operations is exponential in the size of the program, and correctness depends on all of those executions producing the correct result. So, without any structure to reduce the problem, it is exponentially harder to guarantee the correctness of a multithreaded program than a single-threaded program. The tools in Java that I mentioned are designed to "prune away [the] nondeterminism" introduced by multithreading, namely by reducing the space of potential executions and, specifically, preventing those that are known to be incorrect. But this is very difficult to do given that there are so many possible executions to reason about, not to mention the fact that only one such execution manifests itself each time the code is run. To quote Professor Lee, "A folk definition of insanity is to do the same thing over and over again and to expect the results to be different. By this definition, we in fact require that programmers of multithreaded systems be insane. Were they sane, they could not understand their programs."

At a high level, there are a number of different ways to get around the fundamental problem of nondeterminism in multithreaded programs. One is the use of immutable objects, which amounts to just never having mutable state. If there is no mutable state, then different interleavings will always read the same values and produce the same results. Functional programming emphasizes immutability and, in many cases, not having state altogether, which can make it a very natural paradigm for multithreaded programs (though it comes with its own set of concerns). Clojure is a good example of how the functional paradigm can present a distinct way of leveraging multiple processors without directly manipulating threads. Besides immutable objects, another option for managing multithreaded interactions is to assume all threads touch only local state and use a specific system for passing messages between threads. The actor model is an abstraction based on these principles which has been implemented in languages such as Erlang and Scala with some success. Unfortunately, these paradigms and abstractions have not seen the same popularity as threads, quite possibly because threads have the closest resemblance to sequential programming in popular languages. In the end, everything comes down to getting rid of shared, mutable state; if the state is not shared or is immutable, then the nondeterminism of executions becomes a non-issue, but as long as you are using shared, mutable state, multithreaded programming will be difficult.

Regarding the situation in Java, Professor Lee argues that "the mechanisms (such as semaphores) still require considerable sophistication to use, and very likely will still result in incomprehensible programs with subtle lurking bugs" and that "software engineering process improvements alone will not do the job." We can do the best we can to improve the design, review, implementation, and testing processes around building these applications, but it seems impossible to program in this way and confidently believe that there are no synchronization bugs. Given what we know about threads and the nondeterminism they introduce, it is worth considering whether it is the right programming model to build on and if there is an alternative to be found in functional programming, actors, or something completely different.

Static Initialization Deadlock

Time some more fun with static initialization in the JVM. I previously wrote about how static initializers are not hotspot-optimized, which can lead to some interesting performance issues, but this time we see something more scary in seemingly innocent code. Take a look:


Here we have a class MyClass (it is an inner class here for simplicity only) which has a static inner class MySubClass. MyClass also has a static field of type MySubClass; that field will be initialized when MyClass is. Then in the main method we have a thread that creates an instance of MySubClass, and we directly reference the static field on MyClass. We aren't really doing a whole lot here; in particular, there is no explicit synchronization, which is usually good enough to rule out things like race conditions and deadlocks. Well, if you run this a few times, you will in fact notice that this program sometimes fails to terminate. Putting jstack to work, we see the following stack traces:


Well, that's interesting; the thread we created is just stuck on the line trying to create the instance of MySubClass while the main thread is trying to initialize MyClass. As it turns out, static initialization in the JVM is thread-safe which is good, but the synchronization introduced used can cause a deadlock. If you recall the necessary conditions for deadlock, one of them is circular wait; that is, threads acquiring locks in a potentially cyclic order. In this case, the two classes MyClass and MySubClass have individual locks guarding their loading and initialization, but initializing one in turn triggers the initialization of the other (hence the possibility of circular wait). Initializing MySubClass naturally has to initialize the superclass, while the presence of the static field in MyClass causes the reverse dependency, so both of our threads get stuck during the class initialization process.

This is quite unfortunate because deadlocks are extremely hard to reproduce and track down, especially when you do not suspect your code of having such problems. And while my example may seem a bit contrived (although less so than they typically are), it is based on a real bug we encountered in a production environment. If a bug exists in the JVM, there is enough Java code out there that someone will almost certainly run into it.

HashCode "Randomness"

The basis of this post is a very confusing bug I ran into recently involving what appeared to be nondeterministic behavior in a program that has no explicit randomness. Consider the following example:


It looks innocent enough, but when you run it there is a very good chance it will not print out the same number all three times. Set data structures generally do not give you any guarantees as to the ordering of the elements, but Scala's HashSet also does not have any randomness, so the question remains as to why the head of the set would be different each time. Java veterans should be cringing by now at the fact that we are putting an object that does not override the equals() and hashCode() methods into a hash data structure, one of the basic rules of Java collections. And that is indeed the reason for the "nondeterministic" behavior we observe; the JVM's default hash code implementation can return basically anything (but tries to return unique numbers), so depending on the values of the hash codes for each instance of Foo that we create, the set may (and does) order them differently.

As it does with many confusing things in Java, Scala has ways of helping you out here. In the above code example, if we turn Foo into a case class, the same value will be printed every time. This is because case classes automatically have equals() and hashCode() implemented so you do not have to worry about doing it yourself, which is a good argument for making simple value wrapper classes always be case classes (not to mention the nice pattern matching functionality you get). For reference, the automatically generated hash code for case classes can be found here; it is an implementation of the MurmurHash algorithm using the hash codes for each of the fields in the class. So the hash code of the Foo case class is stable across different instances of the JVM as long as Scala does not change the implementation (which they could very well do).

In the end, this turned out to be just a lesson in Java basics brought to light by some old, convoluted code that I came across. It does make me wonder whether the Java and/or Scala compilers could emit a warning when they detect objects being put into a hash data structure without overriding equals() and hashCode() because I am sure that would save a lot of headaches. There is definitely a limit to how much can be done through static analysis, but perhaps a combination of that and runtime checks could do the trick.

String.format

Most of the time when you are dealing with strings, you want to construct them dynamically from some variables, whether they are integers, objects, or strings themselves. You might end up with code that kind of looks like this:

To most people, this is not the nicest looking code, and it can be hard to parse while reading and easy to mess up while writing. Java offers an alternative that behaves like good old printf which is the String.format method. Instead of inlining the variables as in the above example, you can put format specifiers in their place and specify the variables at the end. This additionally has the benefit of allowing you to render strings in different ways (e.g. leading zeros). For example:

In many cases, this is preferable because it is easier to see what the string should look like. There are some disadvantages such as the increased difficulty in identifying which variable is associated with which format specifier, but as we can see that might be overcome through good naming conventions. Now that I've introduced (or reintroduced) to you this handy feature of Java, let me tell you why you should be wary of using it. The reason is, of course, performance. Let's take a look at a quick benchmark program:

This benchmark compares String.format to appending when there are between 0 and 10 format specifiers (all "%d" for simplicity). The output of the second run (to avoid the impact of JVM warm-up) is as follows, with the columns representing number of format specifiers, time taken by String.format, and time taken by appending, respectively:

Needless to say, the append method blows String.format out of the water, especially with a small number of format specifiers. As it turns out, String.format calls down into Java's regular expression library to parse the format string, and that has a lot of overhead, especially in simple cases. That's not to say String.format doesn't have its uses. The whole point of this discussion came from the fact that it can make your code more readable, which is a great thing and sometimes more important than performance. But if you ever need to manipulate strings in the innermost loop of your application, please just stick with appending.

Memory-Mapped Binary Search

Following up on my last post, I looked into implementing a simple proof-of-concept application using FileChannels. I settled on the following use case: suppose you have a very large file which is a sorted list of strings and you want to perform binary search on it. As mentioned last time, the Sorted String Table data structure, which is roughly a generalization of this, is often manipulated through memory-mapped files. The reason why its convenient to do so is because, regardless of how large the file is, we can map its contents to (virtual) memory and treat it as a big in-memory array, letting the OS take care of paging. Then we can easily perform binary search to test membership in the list.

Let's start by formalizing the data structure. We have two files, the index file and the data file with the actual strings. The former is a list of offsets where strings start (and correspondingly end) in the data file, while the latter is a concatenation of all the strings in sorted order. We will assume we can read the entire index into memory, but we could just as easily memory-map that file as well. When doing the binary search, the index will tell us where in the data file to read strings from to do the comparisons. Here's the code in Scala:


We start off by mapping the data file into memory, from which we obtain a MappedByteBuffer that operates as our in-memory array. The bulk of the work happens in the findString() method which does the binary search; to read from the memory-mapped file, we position the buffer at the location specified by the index and read the string from that position. From there, it is as if we just had a String in memory, and we do the necessary comparisons for the binary search logic.

Again, the biggest win is that we can manipulate very large files without doing any complex memory management to make sure we do not exceed our heap size or the machine's memory. You may notice that there are a few limitations of the above code due to the Java ByteBuffer API. A single ByteBuffer can only represent up to 2GB because it uses integers everywhere instead of longs, so the code will only work for files less than 2GB in size (in which case you often do not exceed the machine's memory). Fortunately, it is not too hard to chunk the file into 2GB blocks and map each chunk to its own ByteBuffer; the code changes slightly, but mostly in additional implementation details.

This proof-of-concept binary search shows how FileChannels and MappedByteBuffers can be leveraged to efficiently solve problems in which your data exceeds your memory limit without adding enormous amounts of complexity to your code.

Memory-Mapped Files

Using memory-mapped files is a common technique for improving I/O performance. The concept is pretty simple: take a portion of a file (usually a page worth, or 4KB) and map its contents to a segment of virtual memory so that your program can access that segment as if were normal memory. The mapping is managed by the operating system, and the actual physical memory used is typically the OS page cache. The OS then naturally handles syncing the page back to disk after writes. There are a couple of key benefits you get when you do this:

• reading from a file no longer requires a system call or a copy from kernel space to user space;
• you can perform random access and updates to the contents of the file;
• memory can be shared between multiple processes that need to read the same file;
• you can manipulate contents of extremely large files in memory; and
• if your process dies, the OS will usually still flush the written contents to disk.

As such, there are often performance benefits from using memory-mapped files over traditional I/O when used in the correct situations. So all of the above you would typically learn in an operating systems course, but when might you want to use a memory-mapped file outside of writing operating systems?

First, let me introduce the Java interface to memory-mapped files. Since as a Java programmer you don't have access to most low-level operations like mapping files into memory, the functionality has to be built into the language itself. It is done so in the form of the FileChannel, which is part of the new I/O (nio) package. Here's an example of how you might map a portion of a file into memory and write some bytes using a FileChannel:

When we map a file into memory, we are given a MappedByteBuffer which we can then read from and write to assuming we have opened the file in the proper mode. In the example, we set the position to 100 and write four bytes; this only touches memory, but the changes will be flushed to disk by the OS (a flush can also be triggered manually from the FileChannel). The size  You can check out this stack overflow question and this blog post for details about FileChannel performance relative to normal Java I/O and even C.

One neat use for memory-mapped files is taking data structures on disk and manipulating them in memory. For example, suppose you have an extremely large bloom filter that you cannot or do not want to load into the JVM heap. Since a bloom filter is a compact and regular data structure, using memory-mapped files to access it is simply a matter of figuring out the offset at which you want to read or write in the MappedByteBuffer. This is especially useful if you are ingesting a lot of data into the bloom filter as you will be doing many writes to different portions of the large file, so it's best to leave the complex memory management to the OS. As another example, Cassandra, a popular NoSQL data store, also uses memory-mapped files for the caching behavior to handle their Sorted String Table data structures.

Memory-mapped files are a convenient feature provided by operating systems in order to simplify the management of resources on disk and improve I/O performance. Even in Java, when you might think such low-level I/O management is not necessary or possible, there are standard libraries to take advantage of memory-mapped files because they are that useful. So if you ever have to write an I/O-intensive application, consider whether you can leverage the OS to simplify your own system.

Dependency Management

Managing dependencies properly in software is a problem that I've run into time and time again regardless of what project I'm working on. By dependency management, I mean specifying which internal and third-party dependencies your code needs. There are many systems for doing this, such as Ivy and Maven in the Java world and SBT in the Scala world (I'm sure other languages have equivalent facilities). These work pretty well in general; for example, if I'm using Maven as my build tool and I need to depend on Google's Guava library, I can find it in Maven Central, add it to my configuration file, and be done with it. The existence of such repositories is one of the greatest developments in software engineering and has probably reduced the amount of code that you need to write by a few orders of magnitude. Inevitably, however, I always encounter situations in which dependency management causes major headaches, in particular due to inconsistent version requirements.

For example, suppose you are working on a project that requires third-party libraries A and B. Both of them are on Maven Central, so you happily put them into your build configuration and are on your way. Well, not quite. Maven is smart in that it recursively pulls dependencies so that you actually have all of the JARs that you need to run your application. But it turns out that library B was last updated five years ago while library A is brand new, and they both depend on a third library C which has had several releases over the last five years. So B specifies version 1.1 of C as a dependency while A uses the latest-and-greatest version 2.0-alpha. To make things even better, the authors of library C decided to break backwards-compatibility with the major version change from 1.x to 2.x, so now you're stuck with two incompatible versions of the same library on your classpath. Maven will most likely complain because of this, but even if you can coerce it to compile your application (which technically will work), upon running the code you will see scary things like NoSuchMethodErrors and IllegalAccessErrors.

So if you find yourself in such a situation, what can you do? One course of action is to decide on either version 1.1 or 2.0-alpha of library C, find the source of A or B, and build your own version of it after changing the dependency on C. This is quite error-prone because you are not familiar with the third-party code and consequently don't have a full understanding of the scope of the dependency on C. It is also time-consuming to dive into the details of implementations that are supposed to be abstracted away from you and mess with bits and pieces of the internals. I have gone through this process a couple of times (when dealing with ubiquitous libraries like Apache HttpClient and Apache Commons), and it's never been fun.

The problem is that there is nobody who is at fault here; the authors of the libraries are all handling their releases in reasonable ways, and you may very well be the first one who has wanted both libraries A and B in the same application. When nobody does anything wrong and you end up with such a nasty situation, something seems wrong. I recently came across a practice that somewhat mitigates the pain: the authors of the Apache Commons Math library used unique package names when they went from version 2 to 3 (org.apache.commons.math vs org.apache.commons.math3) which means that you can safely have them both on your classpath and think of them as completely separate libraries. But it's not clear whether the generic problem of dependency management is actually "solvable" without having all developers adhere to some rigorous backwards-compatibility standard -- certainly an impossible task.

P.S. There are a few other things that I may as well complain about while I'm on this topic. If you run your own continuous integration system and your code is modular to any degree, you'll most likely run into incompatible versions of your own JARs when certain builds break. This is very annoying and a big killer of developer productivity. Additionally, Scala takes dependency management to a whole new level by having libraries be associated with a specific version of the language, so Maven will complain if you have some dependencies built against Scala 2.10.0 while others are built against Scala 2.9.2. Since people don't always update their libraries in a timely fashion, the process of upgrading your own version of Scala can be painful.

Beware of Autoboxing

Autoboxing is a feature of Java which allows the compiler to automatically translate between primitives and their boxed object forms, e.g. from ints to Integers and vice versa. Since Java generics can only parametrize  on real classes, autoboxing is convenient when you want to use collections like List<Integer>. Instead of having to wrap all values with the Integer class, the Java compiler will do that for you. While autoboxing is known to have performance issues in some cases (constantly creating objects as you call methods with primitives will have some overhead), there are even more subtle dangers that you should be aware of. Consider the following code:


It puts two values into a map, removes one, and then prints the content of the map. Simple enough, but here's the output:


Well that's interesting; somehow "foo" did not get removed from the map. Looking closely at the Java API for Map, we see that the remove method takes an Object as its parameter (the reasons for this are subtle and discussed in various places). So when we call remove on the map, the value 1 gets autoboxed to... an Integer. Unfortunately, the map uses Longs for keys, and the Integer 1 is not equal to the Long 1, so remove does not find the key and does nothing. But since the argument to remove has type Object, the code compiles fine and you are blissfully unaware of the impending doom until your system crashes and burns horribly (or you catch the mistake with a unit test!). Sad times. And all of this is fixed by writing "1L" (primitive long) instead of just "1" (primitive int).

This subtle interaction between the collection APIs and autoboxing should make any Java programmer very anxious. It is difficult to spot such mistakes in code, especially because you expect the compiler to catch this kind of error. The best solution I have for avoiding this problem is being very rigid about passing the correct type of primitive; if a value is an int, don't ever store it in a long, and vice versa. This can be somewhat annoying (personally, "1L" is much uglier to read than "1") but may save you some headaches in the future. Alternatively, don't use boxed primitives in collections, but that seems like an even harder standard to maintain. Regardless, add autoboxing to your list of things in Java that you just have to deal with even though the point is that you shouldn't have to think about it.

Reading InputStreams

The Java InputStream is one of the core I/O classes in the JDK and is used pretty much whenever you want to do I/O in your Java programs, e.g. reading from the disk or network. It has a variety of read methods that allow you to read a single byte or many bytes at a time, which are typically called in some sort of loop until you get a return value of -1 indicating the end of the stream. Consider the following example:


Here, we write 256MB worth of data into a ByteArrayOutputStream, which just allocates a byte array to store all of those bytes, and then read it back all at once using a ByteArrayInputStream, which just wraps a byte array with the InputStream API. Unsurprisingly, this program results in the message: "Read 268435456 bytes." Simple enough, but let's see what happens when you decide you want to compress the bytes when writing them out and decompress them when reading them back (this is common when you have to write large amount of easily-compressible data to the disk or network).


Now we're wrapping the ByteArrayOutputStream with a DeflaterOutputStream, which compresses the data as its written out, and the ByteArrayInputStream with an InflaterInputStream, which decompresses the data as its read in. These streams do indeed invert each other correctly, but now this programs prints: "Read 512132 bytes." That's strange, because we expected to get the same number of bytes back after compression followed by decompression. Digging into the contract provided by the InputStream API. you can find the following statement: "Reads some number of bytes from the input stream and stores them into the buffer array b. The number of bytes actually read is returned as an integer. This method blocks until input data is available, end of file is detected, or an exception is thrown." What that means is that InputStreams do not provided any guarantees on how many bytes it will read, even if, as in this case, all of the data is "available" in memory. The InflaterInputStream is most likely designed to inflate data in chunks and be efficient regardless of the underlying InputStream it is reading from. Taking this fact into account, the final example produces the expected output:


The great thing about all of this is that, if your data is small enough, the second example will actually work properly. Thus even testing may not catch the bug, which can lead to a lot of unfortunate situations. So the lesson to be learned is to always wrap InputStream reads in a loop and only consider it done once you see that -1!

Covariant Return Types

The topic of this post is covariant return types in the context of the builder pattern and how you can use the builder pattern with inheritance in Java. To illustrate what the concept of covariant return types is, consider the following example (roughly taken from Wikipedia):



Here the D class overrides the foo method of C, but it doesn't return the same type (B versus A). Since B is a subclass of A, however, this satisfies the property of the return type being covariant, as we are still guaranteed that the return type of foo is "an A." So why is this useful? Suppose you have a Resource class. The builder pattern gives you some nice syntax like this to chain methods together when constructing an object:



It's especially useful when the list of fields is large and you often only want to assign a subset of them. In that case constructors don't cut it (you'd need exponentially many of them to cover all cases...) so the builder pattern provides a convenient alternative that avoids having to pass in a bunch of null values. The key to making this work is having the setters return the "this object" and thus enable chaining. Simple enough, but when you introduce inheritance it gets a bit tricky.



Now we have a subclass ExpiringResource which is just a Resource with an expiration time. Although this code looks natural, it doesn't compile because the withName method returns a Resource and not an ExpiringResource, which doesn't have the withExpirationTime method. Fortunately, we can leverage covariant return types to make this work:



We are overriding the withName method so that it returns an ExpiringResource instead of a normal Resource (a covariant return type). Then we can successfully chain the methods together and make our example compile. It's not shown here, but you'd typically do the same with the other two methods on Resource as well. For these simple setters, it's a bit unfortunate that we have to add so much code in the subclasses, but you can imagine if those methods had other side effects or validation that it would be worthwhile to share that code. To wrap up, Java's support for covariant return types allows us to use the builder pattern while maintaining a sensible inheritance hierarchy.

Mockito (Part 2)

Last time, I briefly introduced Mockito, which is a Java/Scala mocking framework that uses a bytecode generation library cglib to create a very simple and natural way of describing mocking behavior. We saw that we could use cglib to create dynamic subclasses and intercept their methods in ways that seemed to be close to how something like Mockito might work. This time I'll provide a full implementation of what I am calling MiniMockito, which allows straightforward when/thenReturn mocking behavior seen here (same example as last time):



Let's take a look at a few method interceptors we'll use to get there (apologies for the large chunk of code):



Here, the MockIntercepted trait is what we'll mix in to the return of methods, e.g. the value of someClass.foo, the first time they are called (or until a stub return value is provided). Because this trait is mixed into a dynamically-generated class, the methods don't actually have implementations anywhere. That's where the StubInterceptor comes in; for the two methods on the MockIntercepted trait, we have predefined return values that give context about which MockInterceptor we're using and which method was stubbed out. These two pieces of information are necessary for thenReturn to set the stub return value.

Lastly, the most important piece is the MockInterceptor itself, which is the method interceptor for the actual mock object. When there is no stub return value set yet, the MockInterceptor will dynamically generate a subclass which mixes in MockIntercepted and uses the StubInterceptor. The subclass carries the context of the method call so we know which method to stub later. The one piece remaining is when the methodReturns map is updated with the stub return values; once it is populated, future calls to the method will always return the stored value! So here's the rest:



The Stubbing object is what actually takes the method and the stub return value and puts them in the methodReturns map. It is returned by the call to when and has context about the mock interceptor and stubbed method because of the MockIntercepted trait we mixed in earlier. The remaining pieces of the implementation are relatively straightforward and included for completeness.

So, to summarize, what does all this code do?

• The mock method dynamically generates a subclass of the mocked class (SomeClass) which uses the MockInterceptor.
• The MockInterceptor dynamically generates a subclass of the return class (StringInt) that mixes in the MockIntercepted trait and uses the StubInterceptor to implement those methods.
• A call to when uses the MockIntercepted trait that was mixed in to create a Stubbing that knows about the corresponding MockInterceptor and the method that was stubbed (foo).
• Calling thenReturn on the Stubbing populates the map maintained by the MockInterceptor to intercept future calls to the method and return the stub value.

As a final note, this implementation is naturally really hacked together in order to keep it short (sort of, anyway). There are numerous details left out and assumptions made that Mockito naturally does a much better job of handling (e.g. I didn't really figure out a robust way to deal with the lack of no-arg constructors in the mocked class), but it touches upon the basic building blocks offered by cglib that Mockito leverages to achieve its magical behavior. Hope this provided some insight into how this awesome library works!

Mockito (Part 1)

Mockito is a really neat Java/Scala mocking framework that I recently came across. I'm familiar with mocking frameworks that use dynamic proxies to mock interfaces, which are already pretty magical in their use of reflection to intercept method calls. They also have many uses beyond testing and are a good tool to understand. Mockito goes beyond that in its magic, in ways that I previously thought impossible in the Java language. Consider the following example:



This code outputs "bar 2" as you might expect from reading it (it's not quite the same semantics as Mockito, but very close). The interesting things to note here are the fact that SomeClass is just a normal class, not an interface, and the when/thenReturn paradigm (these are static methods in Mockito, along with mock). Looking at the code, it's clear that the call to foo is intercepted/overridden to return something more than just a StringInt object. Otherwise, calling when on it would not be able to accomplish what this code does.

But we are in a type-safe language, so mock needs to return an object which is a subclass of SomeClass that intercepts the foo method call to return an object which is a subclass of StringInt that contains enough information to mock out future calls to foo (e.g. which method was called and what the mocked return value should be). In other words, to not break type safety, we need to create subclasses of these classes that can add on the extra required functionality. Because these subclasses don't exist at compile-time, their bytecode needs to be generated at run-time, which turns out to be possible. The dynamic nature in which this happens is the reason that we can take (almost) any class and create a mock for it with very few assumptions about the original class.

cglib is a bytecode manipulation library whose purpose is to "extend Java classes and implement interfaces at run-time." The Enhancer in particular allows you to create an instance of a dynamically-generated class which can:

• subclass any non-final class,
• have callbacks for method interception, and
• implement additional interfaces.

For example:

Using SomeClass from the previous example, we dynamically generate a subclass for it that uses a method interceptor to return a different object. This code also outputs "bar 2" and gives us a little bit of insight into how these dynamically-generated subclasses can be used to get the mocking behavior in Mockito. If we can create a method interceptor that somehow keeps track of the when/thenReturn calls, we should be able to substitute the return value in place of invoking the actual method.

Stay tuned for part 2 which will demonstrate how this is done and a very minimal implementation of Mockito functionality.

Edit: Part 2 is here.

Static Initializers and HotSpot Optimization

HotSpot optimization is one of the core features of the Java Virtual Machine (JVM) that allows JVM-based languages like Java and Scala to have great performance even in comparison to languages that compile directly to machine code. It enables dynamic, run-time optimization of bytecode in various ways, including "true" compilation into machine code, called just-in-time (JIT) compilation. As a result, writing code that is more conducive to HotSpot optimization can lead to huge performance gains; conversely, not doing so can produce unexpectedly slow code. Consider the following two simple Java programs:





They are almost identical, except that the former has the body in the main method while the latter has it in a static initialization block. Running the two programs produces the same result. The key difference, however, is performance: executing the first program takes about 5 ms, while executing the second takes over 40 seconds. With a performance gap of over 1000 times for two pieces of nearly identical code, this is surely worth investigating a bit.

Thanks to this blog post, I discovered two interesting flags you can pass to the JVM called -XX:+PrintCompilation and -XX:+LogCompilation which will cause it to print out all sorts of information regarding the JIT compiler, such as when methods are JIT compiled and when they are recompiled. Here is a snippet of the output for the second program (from log compilation):



I verified that in both cases the JVM tried to JIT compile the main method and the static initializer in the two examples, respectively. Furthermore, in both cases, the compiler performed the key optimization of inlining the call to run(). The discrepancy lies in the snippet, which is repeated in the log for the second program's execution many times. In short, it says that it successfully compiled the static initializer and then hit a trap because the class had not yet been initialized, which forced it to reinterpret the method rather than using the compiled version. This means that the call to run() is not inlined, leading to significantly worse performance.

Since the static initializer is executed at classloading time, it is indeed true that a class has not yet been initialized before static initialization happens. Why this means you have to reinterpret the method is unclear to me, but I'm sure the JVM writers have a good reason for it. So where does this leave us? It seems that in general static initializers cannot be JIT compiled since by definition the enclosing class has not been initialized yet. This, among other reasons, is why you should never perform expensive operations in static initializers.

Finally, I'll provide a Scala example of why this is not a completely trivial case to worry about.





Scala makes it look very natural to put code into the body of an object. Unfortunately, these examples compile into bytecode that closely resembles that of the Java examples above. The for-comprehension is not implemented by a simple for loop but rather by a call to foreach, which takes a closure and calls a method on it (like the Runnable). Most importantly, the body of the second example is run in a static initializer, which causes the same problem that we discussed and the same abysmal performance.