Proposal for improving performance of TreeMap and others

[cowwoc]

I noticed that TreeMap (and maybe other classes) require a user to either
pass in a Comparator or ensure that all keys must implement Comparable. The
TreeMap code then uses a utility method whenever it needs to compare two
keys:


/**
 * Compares two keys using the correct comparison method for this TreeMap.
 */
final int compare(Object k1, Object k2) {
  return comparator == null ? ((Comparable<? super  K>) k1)
  .compareTo((K) k2) : comparator.compare((K) k1, (K) k2);
}

The problem with the above method is that it checks whether comparator is
null once per comparison instead of once when the TreeMap is constructed.
Instead I propose that this check only take place once in the constructors
and the rest of the code assume that a comparator exists. If a comparator is
not provided then you can simply define one as follows:

comparator = new Comparator<K>()
    {
      @SuppressWarnings("unchecked")
      public int compare(K first, K second)
      {
        return ((Comparable<K>) first).compareTo(second);
      }
    });

This solution should be backwards compatible while improving performance. At
least, that's my guess. There is always the chance that the JIT is smart
enough to optimize away this comparison but I'd rather not rely on JIT
implementation details. I also believe the resulting code is more readable.

What do you think?
-- 
View this message in context: http://www.nabble.com/Proposal-for-improving-performance-of-TreeMap-and-others-tp14673283p14673283.html
Sent from the OpenJDK Core Libraries mailing list archive at Nabble.com.