Potential Games

I was just perusing the Java source code (because I don’t read the morning newspaper), when I discovered that java.util.LinkedList.clear() is implemented to operate in linear time. The documentation does not specify its order of growth, and I intuitively assumed that a linked list clear implementation would be a constant time operation.

Could this be an artifact of early Java development, leaving a legacy of poor performance? The remainder of this article explores the potential to significantly improve application performance when using the LinkedList.clear() operation.

First consider java.util.ArrayList.clear(). ArrayList allocates an array in memory and tracks how many elements have actually been added to the list. The fastest way to clear the list would be to simply set the size as 0. However, this would leave leftover object references at abandoned indexes, preventing the garbage collector from freeing them. So, ArrayList sweeps through the list and sets each index to null, but retains the allocated array and sets the element count (list size) to 0.

Inspecting java.util.LinkedList.clear() reveals that it also performs a linear sweep, nulling the links between all nodes as well as setting each node’s element to a null reference. I would argue that the implementation should simply cut the chain of nodes loose, with one or two snips. The chain of nodes are now subject to garbage collection since they are no longer reachable. By extension, any former referenced elements of the list may also be unreachable and available for garbage collection. The list is cleared in constant time and no stale references are held.

The existing implementation implies that the developer did not trust the garbage collector to operate efficiently. If the garbage collector takes an inordinate amount of resources to clean up a large tract of linked objects, it could impact runtime performance. However, the garbage collector has the ability to schedule cleanup at opportune moments. Furthermore, different cleanup strategies can be employed based on application needs. A server with plenty of excess memory can allow garbage to accumulate until it can all be deallocated in one fell swoop. In any case, burdening the application code by presupposing the garbage collector’s duties is wrong. The only purpose to this linear operation is to help the garbage collector, which is never an appropriate excuse.

In practice, it could be possible that nulling out all the elements of a LinkedList improves runtime performance. To find out, performance measurements would have to be taken on a variety of platforms under each available garbage collection scheme. Suppose massive garbage collection is actually found to be less efficient at runtime than linearly stalling the application (which I really doubt). This empirical data would only be valid for one version of the garbage collector. Future improvements in the garbage collection routines could overcome such deficiencies. Then, developers are left with legacy cleanup code in their applications, which is now working against them. This may be the very case of the LinkedList.clear() implementation.

Since the LinkedList.clear() implementation is vaguely documented, there is room for improvement. The linear approach could be swapped out for a constant-time snip procedure with no compatibility impact. Until then, consider constructing a new LinkedList() instead of clearing an old one for reuse. This is not as pretty in the code, prevents the use of final member variables, and may not be appropriate if a list reference is exposed. When appropriate, and in cases of large lists, creating a new LinkedList instance would alleviate a linear operation and allow the garbage collector to free up the old list as efficiently as possible.