ArrayList

ArrayList is backed by an array that has a fixed size. Entries can be added to the array up to the maximum size of the backing array. When the backing array is full, the class will allocate a new, larger array and copy the old values. The performance-conscious programmer must therefore weigh the cost of the resize operation versus the flexibility of not having to know ahead of time how big the lists will become. An ArrayList is initially backed by an empty array. On the first addition to the ArrayList a backing array of capacity 10 is allocated. We can prevent this resizing behavior by passing our preferred initial capacity value to the constructor. We can also use the ensureCapacity() to increase the capacity of the ArrayList to avoid resizing.

The following is a microbenchmark in JMH (as covered in “Introduction to JMH”) showing this effect:

@Benchmark
public List<String> properlySizedArrayList() {
	List<String> list = new ArrayList<>(1_000_000);
	for(int i=0; i < 1_000_000; i++) {
		list.add(item);
	}
	return list;
}

@Benchmark
public List<String> resizingArrayList() {
	List<String> list = new ArrayList<>();
	for(int i=0; i < 1_000_000; i++) {
		list.add(item);
	}
	return list;
}

This results in the following output:

Benchmark                             Mode  Cnt    Score     Error  Units
ResizingList.properlySizedArrayList  thrpt   10  287.388  ± 7.135   ops/s
ResizingList.resizingArrayList       thrpt   10  189.510  ± 4.530   ops/s

The properlySizedArrayList test is able to perform around 100 extra operations per second when it comes to insertion, as even though the cost of reallocation is amortized there is still an overall cost. Choosing a correctly sized ArrayList is always preferable when possible.

LinkedList

The LinkedList has a more dynamic growth scheme; it is implemented as a doubly linked list and this means (among other things) that appending to the list will always be O(1). Each time an item is added to the list, a new node is created and referenced from the previous item. An example can be seen in Figure 11-2.

Figure 11-2. A LinkedList

ArrayList versus LinkedList

The real decision of whether to use an ArrayList or a LinkedList (or another nonstandard implementation of List) depends on the pattern of access and modification of the data. Inserting at the end of a list in both ArrayList and LinkedList is a constant-time operation (after the resize operations are amortized, in the case of ArrayList).

However, adding at an index in ArrayList requires all other elements to be shifted by one position to the right. LinkedList, on the other hand, has to traverse node references to find the position in the list where the insert is required, but the insert itself simply involves creating a new node and setting two references, one pointing to the node at the beginning of the list (the first reference) and the other to the next node in the list (the next reference). This benchmark shows the difference in performance of inserting at the beginning of each type of list:

Benchmark                     Mode  Cnt    Score    Error   Units
InsertBegin.beginArrayList   thrpt   10    3.402 ±  0.239  ops/ms
InsertBegin.beginLinkedList  thrpt   10  559.570 ± 68.629  ops/ms

List removal has a similar behavior; it is cheaper to remove from a LinkedList, at most two references need to change. In an ArrayList, all items to the right of the deletion need to shift one place to the left.

If the list is mainly accessed randomly ArrayList is the best choice, as any element can be accessed in O(1) time, whereas LinkedList requires navigation from the beginning to the index count. The costs of accessing the different types of list by a specific index are shown in the following simple benchmark:

Benchmark                        Mode  Cnt       Score       Error   Units
AccessingList.accessArrayList   thrpt   10  269568.627 ± 12972.927  ops/ms
AccessingList.accessLinkedList  thrpt   10       0.863 ±     0.030  ops/ms

In general it is recommended to prefer ArrayList unless you require the specific behavior of LinkedList, especially if you are using an algorithm that requires random access. If possible, size the ArrayList correctly ahead of time to avoid the charge of resizing. Collections in modern Java take the view that the developer should incur the synchronization costs for all accesses and should either use the concurrent collections or manually manage synchronization when necessary. In the Collections helper class there is a method called synchronizedList(), which is effectively a decorator that wraps all of the List method invocations in a synchronized block. In Chapter 12 we will discuss in more detail how to use java.util.concurrent for structures that can be used more effectively when you are writing multithreaded applications.

HashMap

In many ways, Java’s HashMap can be seen as a classic introductory computer science hash table, but with a few additional embellishments to make it suitable for modern environments.

A cut-down version of the HashMap (eliding generics and a couple of key features, which we will return to) has some key methods that look like this:

public Object get(Object key) {
    // SIMPLIFY: Null keys are not supported
    if (key == null) return null;

    int hash = key.hashCode();
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }

    return null;
}

private int indexFor(int h, int length) {
    return h & (length-1);
}

// This is a linked list node
static class Node implements Map.Entry {
    final int hash;
    final Object key;
    Object value;
    Node next;

    Node(int h, Object k, Object v, Entry n) {
        hash = h;
        key = k;
        value = v;
        next = n;
    }
}

In this case, the HashMap.Node class is restricted to package access in java.util; that is, it is a classic use case for a static class.

The layout of the HashMap is shown in Figure 11-3.

Figure 11-3. A simple HashMap

Initially the bucket entries will be stored in a list. When it comes to finding a value, the hash of the key is calculated and then the equals() method is used to find the key in the list. Because of the mechanics of hashing the key and using equality to find it in the list, duplicate keys are not permitted in a HashMap. Inserting the same key simply replaces the key currently stored in the HashMap.

In modern Java versions, one of the improvements is that indexFor() has been replaced by code that uses the hashCode() of the key object and applies a mask to spread higher bits in the hash downward.

This has been designed as a tradeoff to ensure that the HashMap takes into account higher bits when calculating which bucket a key hashes to. If this was not done, the higher bits might not be used in computing index calculations. This is problematic for a number of reasons, not least of which is that it violates Shannon’s Strict Avalanche Criteria—the idea that even arbitrarily small changes in input data should produce potentially very large changes in the output of the hash function.

Two important variables impact the performance of a HashMap: initialCapacity and loadFactor, both of which can be set via parameters passed to the constructor. The capacity of a HashMap represents the current number of buckets that have been created, which defaults to 16. The loadFactor represents how full the hash table is allowed to get before the capacity is automatically increased. Increasing the capacity and recalculating hashes is a procedure known as rehashing, which doubles the number of buckets available and redistributes the data stored.

An accurate initialCapacity will avoid the need to automatically rehash as the table grows. It is also possible to tweak loadFactor, but 0.75 (the default) provides a good balance between space and time of access. A loadFactor of higher than 0.75 will reduce the rehashing requirement, but access will become slower as buckets will generally become fuller. Setting the initialCapacity to the maximum number of elements divided by the loadFactor will prevent a rehash operation from occurring.

The HashMap provides constant-time support for get() and put() operations, but iteration can be costly. As mentioned in the JavaDoc, setting the initialCapacity and loadFactor high will severely impact the iteration performance.

Another factor that impacts performance is a process known as treeifying. This relatively recent innovation is an internal implementation detail of HashMap, but is potentially useful for performance engineers.

Consider the case where a bucket becomes highly populated. If the bucket elements are implemented as a LinkedList, traversal to find an element becomes on average more expensive as the list grows.

To counteract this linear effect, modern implementations of HashMap have a new mechanism. Once a bucket reaches a TREEIFY_THRESHOLD, it is converted to a bin of TreeNodes (and behaves similar to a TreeMap).

Why not do this from the beginning? TreeNodes are about double the size of a list node, and therefore a space cost is paid. A well-distributed hashing function will rarely cause buckets to be converted to TreeNodes. Should this occur in your application, it is time to consider revisiting the hash function, initialCapacity, and loadFactor settings for the HashMap.

As with everything else in performance, practical techniques are driven by tradeoffs and pragmatism, and you should adopt a similarly hardheaded and data-driven approach to the analysis of your own code.

TreeMap

The TreeMap is, essentially, a red-black tree implementation. This type of tree is basically a binary tree structure with additional metadata (node coloring) that attempts to prevent trees from becoming overly unbalanced.

The TreeMap is incredibly useful when a range of keys is required, allowing quick access to a submap. The TreeMap can also be used to partition the data from the beginning up to a point, or from a point to the end.

The TreeMap provides log(n) performance for the get(), put(), containsKey(), and remove() operations.

In practice, most of the time HashMap fulfills the Map requirement, but consider one example: the case where it is useful to process portions of a Map using streams or lambdas. Under these circumstances, using an implementation that understands partitioning of data—for example, TreeMap—may make more sense.

Lack of MultiMap

Java does not provide an implementation for MultiMap (a map that allows multiple values to be associated with a single key). The reason given in the documentation is that this is not often required and can be implemented in most cases as Map<K, List<V>>. Several open source implementations exist that provide a MultiMap implementation for Java.

War Story: Forgetting to Clean Up

Like many software war stories, this tale starts with production code that had been working fine for years. It was a service that connected via TCP to another service to establish permissions and entitlements information. The entitlements service was relatively stable and had good load balancing, usually responding instantly to requests. A new TCP connection was opened on each request—far from ideal in design.

One weekend a change happened that caused the entitlements system to be slightly slower in the response time. This caused the TCP connection to occasionally time out, a code path never previously seen in production. A TimeOutException was thrown and caught, nothing was logged, and there was no finally block—the close() function had previously been called from the success path.

Sadly, the problem did not end there. The close() function not being called meant that the TCP connection was left open. Eventually the production machine the application was running on ran out of file handles, which impacted other processes tenanted on that box. The resolution was to rewrite the code to first of all close the TCP connection and immediately patch, and second to pool the connection and not open a new connection for each resource.

Forgetting to call close() is an easy mistake to make, especially when using proprietary libraries.

Why Not Use Finalization to Solve the Problem?

Java initially offered the finalize() method, which lives on Object; by default, it is a no-op (and should usually remain that way). It is, however, possible to override finalize() and provide some behavior. The JavaDoc describes this as follows:

Called by the garbage collector on an object when garbage collection determines that there are no more references to the object. A subclass overrides the finalize() method to dispose of system resources or to perform other cleanup.

The way that this is implemented is to use the JVM’s garbage collector as the subsystem that can definitively say that the object has died. If a finalize() method is provided on a type, then all objects of that type receive special treatment. An object that overrides finalize() is treated specially by the garbage collector. The JVM implements this by registering individual finalizable objects on a successful return from the constructor body of java.lang.Object (which must be called at some point on the creation path of any object).

One detail of HotSpot that we need to be aware of at this point is that the VM has some special implementation-specific bytecodes in addition to the standard Java instructions. These specialist bytecodes are used to rewrite the standard ones in order to cope with certain special circumstances.

A complete list of the bytecode definitions, both standard Java and HotSpot special-case, can be found in hotspot/share/interpreter/bytecodes.cpp. For our purposes, we care about the special-case return_register_finalizer bytecode. This is needed because it is possible for, say, JVMTI to rewrite the bytecode for Object.<init>(). To precisely obey the standard, it is necessary to identify the point at which Object.<init>() completes (without rewriting), and the special-case bytecode is used to mark this point.

The code for actually registering the object as needing finalization can be seen in the HotSpot interpreter. The file src/hotspot/cpu/x86/c1_Runtime.cpp contains the core of the x86-specific port of the HotSpot interpreter. This has to be processor-specific because HotSpot makes heavy use of low-level assembly/machine code. The case register_finalizer_id contains the registration code.

Once the object has been registered as needing finalization, instead of being immediately reclaimed during the garbage collection cycle, the object follows this extended lifecycle:

1. Finalizable objects are moved to a queue.

2. After application threads restart, separate finalization threads drain the queue and run the finalize() method on each object.

3. Once the finalize() method terminates, the object will be ready for actual collection in the next cycle.

Overall, this means that all objects to be finalized must first be recognized as unreachable via a GC mark, then finalized, and then GC must run again in order for the data to be collected. This means that finalizable objects persist for one extra GC cycle at least. In the case of objects that have become Tenured, this can be a significant amount of time. The finalization queue processing can be seen in Figure 11-5.

Figure 11-5. Draining the finalization queue

There are other problems with finalize(); for example, what would happen if the method throws an exception while it is being executed by a finalization thread? There is no context inside the user’s application code at this point, so the exception is simply ignored. There is no way for the developer to know about or recover from a fault caused during finalization.

It is also possible that finalization could contain a blocking operation and therefore require the JVM to spawn a thread to run the finalize() method, with the inherent overhead of creating and running the new thread. Once again, the thread creation and management is outside of the developer’s control but is necessary to avoid locking up the entire JVM subsystem.

The majority of the implementation for finalization actually takes place in Java. The JVM has separate threads to perform finalization that run at the same time as application threads for the majority of the required work. The core functionality is contained in the package-private class java.lang.ref.Finalizer, which should be fairly simple to read.

The class also provides some insight into how certain classes are granted additional privileges by the runtime. For example, it contains code like this:

/* Invoked by VM */
static void register(Object finalizee) {
    new Finalizer(finalizee);
}

Of course, in regular application code this would be nonsensical, as it creates an unused object. Unless the constructor has side effects (usually considered a bad design decision in Java), this would do nothing. In this case, the intent is to “hook” a new finalizable object.

The implementation of finalization also relies heavily on the FinalReference class. This is a subclass of java.lang.ref.Reference, which is a class that the runtime is aware of as a special case. Like the better-known soft and weak references, FinalReference objects are treated specially by the GC subsystem, comprising a mechanism that provides an interesting interaction between the VM and Java code (both platform and user).

However, for all its technical interest the implementation is fatally flawed, due to differences in the memory management schemes of the two languages. In the C++ case, dynamic memory is handled manually, with explicit lifetime management of objects under the control of the programmer. This means that destruction can happen as the object is deleted, and so the acquisition and release of resources is directly tied to the lifetime of the object.

Java’s memory management subsystem is a garbage collector that runs as needed, in response to running out of available memory to allocate. It therefore runs at nondeterministic intervals and so the finalize() method is run only when the object is collected, which will be at an unknown time.

Put another way, finalization does not safely implement automatic resource management, as the garbage collector does not run with any time guarantees. This means that there is nothing in the mechanism that ties resource release to the lifetime of the object, and so it is always possible to exhaust resources.

Finalization is not fit for its originally intended main purpose. The advice given to developers by Oracle (and Sun) has, for many years, been to avoid finalization in ordinary application code, and Object.finalize() has been deprecated in Java 9.

try-with-resources

Prior to Java 7 the responsibility of closing a resource was purely in the hands of the developer. As discussed in “War Story: Forgetting to Clean Up” it is easy to forget and not notice the impact of this kind of omission until there is a production problem bearing down on you. The following code sample shows the responsibilities of a developer prior to Java 7:

    public void readFirstLineOld(File file) throws IOException {
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(file));
            String firstLine = reader.readLine();
            System.out.println(firstLine);
        } finally {
            if (reader != null) {
                reader.close();
            }
        }
    }

The developer must:

1. Create the BufferedReader and initialize it to null to ensure visibility from the finally block.

2. Throw or catch and handle the IOException (and possibly the FileNotFound​Ex⁠ception it hides).

3. Perform the business logic interacting with the external resource.

4. Check that the reader isn’t null, and then close the resource.

This example uses only a single external resource, but the complexity increases dramatically when multiple external resources are handled. If you need a reminder, take a look at raw JDBC calls.

try-with-resources, a language-level construct added in Java 7, allows the creation of a resource to be specified in parentheses following the try keyword. Any object that implements the AutoCloseable interface can be used in the try parentheses. At the end of the scope of the try block, the close() method will be called automatically, rather than the developer having to remember to call the function. The following invocation of the close() method behaves just as in the preceding code example, and is run regardless of an exception being thrown in the business logic:

    public void readFirstLineNew(File file) throws IOException {
        try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
            String firstLine = reader.readLine();
            System.out.println(firstLine);
        }
    }

Using javap we can compare the bytecode generated by the two versions. Here’s the bytecode from the first example:

public void readFirstLineOld(java.io.File) throws java.io.IOException;
  Code:
     0: aconst_null
     1: astore_2
     2: new           #2  // class java/io/BufferedReader
     5: dup
     6: new           #3  // class java/io/FileReader
     9: dup
    10: aload_1
    11: invokespecial #4  // Method java/io/FileReader."<init>":
                          // (Ljava/io/File;)V
    14: invokespecial #5  // Method java/io/BufferedReader."<init>":
                          // (Ljava/io/Reader;)V
    17: astore_2
    18: aload_2
    19: invokevirtual #6  // Method java/io/BufferedReader.readLine:
                          // ()Ljava/lang/String;
    22: astore_3
    23: getstatic     #7  // Field java/lang/System.out:Ljava/io/PrintStream;
    26: aload_3
    27: invokevirtual #8  // Method java/io/PrintStream.println:
                          // (Ljava/lang/String;)V
    30: aload_2
    31: ifnull        54
    34: aload_2
    35: invokevirtual #9  // Method java/io/BufferedReader.close:()V
    38: goto          54
    41: astore        4
    43: aload_2
    44: ifnull        51
    47: aload_2
    48: invokevirtual #9  // Method java/io/BufferedReader.close:()V
    51: aload         4
    53: athrow
    54: return
  Exception table:
     from    to  target type
         2    30    41   any
        41    43    41   any

The equivalent bytecode from the try-with-resources version looks like this:

public void readFirstLineNew(java.io.File) throws java.io.IOException;
  Code:
     0: new           #2  // class java/io/BufferedReader
     3: dup
     4: new           #3  // class java/io/FileReader
     7: dup
     8: aload_1
     9: invokespecial #4  // Method java/io/FileReader."<init>":
                          // (Ljava/io/File;)V
    12: invokespecial #5  // Method java/io/BufferedReader."<init>":
                          // (Ljava/io/Reader;)V
    15: astore_2
    16: aconst_null
    17: astore_3
    18: aload_2
    19: invokevirtual #6  // Method java/io/BufferedReader.readLine:
                          // ()Ljava/lang/String;
    22: astore        4
    24: getstatic     #7  // Field java/lang/System.out:Ljava/io/PrintStream;
    27: aload         4
    29: invokevirtual #8  // Method java/io/PrintStream.println:
                          // (Ljava/lang/String;)V
    32: aload_2
    33: ifnull        108
    36: aload_3
    37: ifnull        58
    40: aload_2
    41: invokevirtual #9  // Method java/io/BufferedReader.close:()V
    44: goto          108
    47: astore        4
    49: aload_3
    50: aload         4
    52: invokevirtual #11 // Method java/lang/Throwable.addSuppressed:
                          // (Ljava/lang/Throwable;)V
    55: goto          108
    58: aload_2
    59: invokevirtual #9  // Method java/io/BufferedReader.close:()V
    62: goto          108
    65: astore        4
    67: aload         4
    69: astore_3
    70: aload         4
    72: athrow
    73: astore        5
    75: aload_2
    76: ifnull        105
    79: aload_3
    80: ifnull        101
    83: aload_2
    84: invokevirtual #9  // Method java/io/BufferedReader.close:()V
    87: goto          105
    90: astore        6
    92: aload_3
    93: aload         6
    95: invokevirtual #11 // Method java/lang/Throwable.addSuppressed:
                          // (Ljava/lang/Throwable;)V
    98: goto          105
   101: aload_2
   102: invokevirtual #9  // Method java/io/BufferedReader.close:()V
   105: aload         5
   107: athrow
   108: return
  Exception table:
     from    to  target type
        40    44    47   Class java/lang/Throwable
        18    32    65   Class java/lang/Throwable
        18    32    73   any
        83    87    90   Class java/lang/Throwable
        65    75    73   any

On the face of it, try-with-resources is simply a compiler mechanism to autogenerate boilerplate. However, when used consistently, it is a very useful simplification and can prevent classes from having to know how to release and clean up other classes. The result is to establish better encapsulation and bug-free code.

The try-with-resources mechanism is the recommended best practice for implementing something similar to the C++ RAII pattern. It does limit the use of the pattern to block-scoped code, but this is due to the Java platform’s lack of low-level visibility into object lifetime. The Java developer must simply exercise discipline when dealing with resource objects and scope them as highly as possible—which is in itself a good design practice.

By now, it should be clear that these two mechanisms (finalization and try-with-resources), despite having the same design intent, are radically different from each other.

Finalization relies on assembly code far inside the runtime to register objects for special-case GC behavior. It then uses the garbage collector to kick off the cleanup using a reference queue and separate dedicated finalization threads. In particular, there is little if any trace of finalization in the bytecode, and the feature is provided by special mechanisms within the VM.

By contrast, try-with-resources is a purely compile-time feature that can be seen as syntactic sugar that simply produces regular bytecode and has no other special runtime behavior. The only possible performance effect of using try-with-resources is that because it leads to a large amount of automatically generated bytecode, it may impact the ability of the JIT compiler to effectively inline or compile methods that use this approach.

However, as with all other potential performance effects, the engineer should measure the effect of using try-with-resources on runtime performance and expend the effort to refactor only if it can be clearly shown that the feature is causing problems.

In summary, for resource management and in almost all other cases, finalization is not fit for purpose. Finalization depends on GC, which is itself a nondeterministic process. This means that anything relying on finalization has no time guarantee as to when the resource will be released.

Whether or not the deprecation of finalization eventually leads to its removal, the advice remains the same: do not write classes that override finalize(), and refactor any classes you find in your own code that do.