Jeffrey Bosboom's Blog

[blog] [projects] [about]

Java performance gotcha: Collections.min/max and SortedSet

Just a quick note on a performance gotcha that burned me recently.

You’d expect Collections.min and max to be fast when passed a SortedSet. After all, it’s already sorted, and SortedSet (and its refinement NavigableSet) expose first() and last() methods to retrieve the minimum and maximum elements in the set. Unfortunately, at least Oracle’s library writers didn’t think of this; the Collections methods don’t delegate to first() and last() when available and legal. (It’s more than just instanceof SortedSet, since the set may be using a custom Comparator.) The generic methods use the obvious linear-time algorithm, rather than the logarithmic implementation in TreeSet or the constant-time implementation in Google Guava’s ImmutableSortedSet.

Why not make this case fast? Adding the type check would slightly slow down calls passing other collection types, but the cost of a load and predictably not-taken branch isn’t significant in comparison to the comparisons (heh), and JVMs might be able to constant-fold it at a given call site. Backwards compatibility is the greater concern; I’m sure this optimization would break some poorly-written programs depending on min and max touching all elements to generate a ClassCastException or NullPointerException.