9.1 Avoiding Unnecessary Sorting Overhead

The JDK system provides sorting methods in java.util.Arrays (for arrays of objects) and in java.util.Collections (for objects implementing the Collection interfaces). These sorts are usually adequate for all but the most specialized applications. To optimize a sort, you can normally get enough improvement by reimplementing a standard sort (such as quicksort) as a method in the class being sorted. Comparisons of elements can then be made directly, without calling generic comparison methods. Only the most specialized applications usually need to search for specialized sorting algorithms.

As an example, here is a simple class with just an int instance variable, on which you need to sort:

public class Sortable
  implements Comparable
{
  int order;
  public Sortable(int i){order = i;}
  public int compareTo(Object o){return order - ((Sortable) o).order;}
  public int compareToSortable(Sortable o){return order - o.order;}
}

I can use the Arrays.sort( ) to sort this, but as I want to make a direct comparison with exactly the same sorting algorithm as I tune, I use an implementation of a standard quicksort. (This implementation is not shown here; for an example, see the quicksort implementation in Section 11.9.) The only modification to the standard quicksort will be that for each optimization, the quicksort is adjusted to use the appropriate comparison method and data type. For example, a generic quicksort that sorts an array of Comparable objects is implemented as:

public static void quicksort(Comparable[  ] arr, int lo, int hi)
{
  ...
  int mid = ( lo + hi ) / 2;
  Comparable middle = arr[ mid ]; //Comparable data type
  ...
  //uses Comparable.compareTo(Object)
  if(arr[ lo ].compareTo(middle) > 0 )
  ...
}

To start with, I use a quicksort that takes an array of Objects. The comparisons are made using the Comparator.compareTo( ) method, so every Object in the array must implement the Comparable interface. Since every object is a Comparable, why don't I specify a Comparable[ ] instead of an Object[ ] in the quicksort signature? I use an Object[ ] signature initially to illustrate why it is faster to use a Comparable[ ] signature. java.util.Arrays.sort( ) has an Object[ ] as its argument rather than a Comparable[ ] because it needs to support any array type, and Java doesn't let you cast a generic array to a more specific array type. That is, you cannot use:

Object[  ] arr = new Object[10];
... //fill the array with Comparable objects
//The following line does not compile
Arrays.sort( (Comparable[  ]) arr); //NOT valid Java code, invalid cast

This means that if you specify a sort with the signature that accepts only a Comparable[ ] object array, then you actually have to create a new Comparable array and copy all your objects to that array. And it is often the case that your array is already in an Object array, hence the more generic (but slower) support in the JDK. Another option for the JDK would be to have a second copy of the identical sort method in java.util.Arrays, except that the second sort would specify Comparable[ ] in the signature and have no casts in the implementation. This has not been done in java.util.Arrays up to JDK 1.4, but may be in the future.

Back to the example. The first quicksort with the Object[ ] signature gives a baseline at 100%. I am sorting a randomized array of Sortable objects, using the same randomized order for each test. Switching to a quicksort that specifies an array of Comparable objects (which means you avoid casting every object for each comparison) is faster for every VM I tested (see Table 9-1). You can modify the quicksort even further to cater specifically to Sortable objects, so that you call the Sortable.compareToSortable( ) method directly. This avoids yet another cast, the cast in the Sortable.compareTo( ) method, and therefore reduces the time even further.

The last quicksort accepting a Sortable[ ] array looks like:

public static void quicksort(Sortable[  ] arr, int lo, int hi)
{
  ...
  int mid = ( lo + hi ) / 2;
  Sortable middle = arr[ mid ]; //Sortable data type
  ...
  //uses Sortable.compareToSortable(Sortable)
  if(arr[ lo ].compareToSortable(middle) > 0 )
  ...

You can make one further improvement, which is to access the Sortable.order fields directly from the quicksort. The final modified quicksort looks like:

public static void quicksort(Sortable[  ] arr, int lo, int hi)
{
  ...
  int mid = ( lo + hi ) / 2;
  Sortable middle = arr[ mid ]; //Sortable data type
  ...
  //uses Sortable.order field for direct comparison
  //if(arr[ lo ].order - middle.order > 0 ) -- same as next line
  if(arr[ lo ].order > middle.order )
  ...

This last quicksort gives a further improvement in time (see Table 9-1), though clearly the HotSpot server mode inlines the method call, enabling it to achieve the same speed for both the method and field access. Overall, this tuning example shows that by avoiding the casts by implementing a standard sort algorithm and comparison method specifically for a particular class, you can significantly speed up the sort with little effort. For comparison, I have included in Table 9-1 the timings for using the Arrays.sort( ) method, applied to the same randomized list of Sortable objects used in the example. The Arrays.sort( ) method uses a merge sort that performs better on a partially sorted list. Merge sort was chosen for Arrays.sort( ) because, although quicksort provides better performance on average, the merge sort provides sort stability. A stable sort does not alter the order of elements that are equal based on the comparison method used.^[1]

^[1] The standard quicksort algorithm also has very bad worst-case performance. There are quicksort variations that improve the worst-case performance.

For more specialized and optimized sorts, there are books (including Java-specific ones) covering various sort algorithms, and a variety of sort implementations are available on the Web. The computer literature is full of articles providing improved sorting algorithms for specific types of data, and you may need to run a search to find specialized sorts for your particular application. A good place to start is the classic reference The Art of Computer Programming by Donald Knuth (Addison-Wesley).

In the case of nonarray elements such as linked-list structures, a recursive merge sort is the best sorting algorithm and can be faster than a quicksort on arrays with the same dataset. Note that the JDK Collections.sort( ) methods are suboptimal for linked lists. The Collections.sort(List) method converts the list into an array before sorting it, which is the wrong strategy to sort linked lists, as shown in an article by John Boyer.^[2] Boyer also shows that a binary search on a linked list is significantly better than a linear search if the cost of comparisons is more than about two or three node traversals, as is typically the case.

^[2] "Sorting and Searching Linked Lists in Java," Dr. Dobb's Journal, May 1998.

If you need your sort algorithm to run faster, optimizing the comparisons in the sort method is a good place to start. This can be done in several ways:

• Eliminating casts by specifying data types more precisely.

• Modifying the comparison algorithm to be quicker.

• Replacing the objects with wrappers that compare faster (e.g., java.text.CollationKeys). These are best used when the comparison method requires a calculation for each object being compared, and that calculation can be cached.

• Eliminating methods by accessing fields directly.

• Partially presorting the array with a faster partial sort, followed by the full sort.

Only when the performance is still short of your target do you need to start looking for alternatives. Several of the techniques listed here have been applied in the earlier example and also in Section 5.6 in Chapter 5.