Codeforces: Why You Should Avoid Using comparingX or thenComparingX in Java's Comparator Class
Background
Suppose you need to sort an array or have a TreeSet that requires a specific order.
Let's take the following class as an example:
class Node {
int index, value;
public Node(int index, int value) {
this.index = index;
this.value = value;
}
}
When defining a TreeSet for this class, you can use one of the following two approaches:
new TreeSet<>(Comparator.comparingInt((Node o) -> o.value).thenComparingInt(o -> o.index));
new TreeSet<>((o1, o2) -> o1.value != o2.value ? Integer.compare(o1.value, o2.value) : Integer.compare(o1.index, o2.index));
Clearly, the first approach is elegant, but unfortunately, it's slower. It's recommended to use the second approach. In fact, the second approach can still be slow; you can use o1.value - o2.value directly. You could even consider combining two integers into a long for comparison.
Reasons
In short, the Java is highly engineered, with many checks and a deep call stack.
Methods like comparingX often require passing a lambda function, and their source code typically includes null checks. If you also need to use thenComparingX, the call stack becomes even deeper. The call stack for the first approach is approximately as follows:
treeSet -> comparator_2 -> comparator_1 -> lambda_1 -> lambda_2
On the other hand, the call stack for the second approach is simpler:
treeSet -> comparator
In cases where the necessary logic is the same, the first approach results in a lot of additional function calls, making it slower.