Effective compareTo() for primitive long

Question

Working on a sorted list I came to a point I needed to implement a compareTo() function for primitive long values.

I'm not looking for the obvious naive implementation, but was wondering if there's an elegant one-liner code to do that (without creating a new Long(value)).

Maybe something like this:

@Override public int compareTo(MyClass that) {
    return (int) ((value - that.value) >>> 32);
}

Can anyone verify that would work and/or suggest another implementation?

Transitory

Answer 1

One liner code to that:

int res = Long.compare(long x, long y) 

Your code wont work correctly for all values, try it for Integer.MIN_VALUE - Integer.MAX_VALUE and you will get +1

Expostulatory

That's basically the naive implementation which translates to (x < y) ? -1 : ((x == y) ? 0 : 1) right? I'm wondering if there's something that wouldn't require 2 internal if-then calls, assuming it would be more efficient. – Transitory

@Transitory I would say correctness over performance. Besides, the method might already be optimized by the JDK anyway. – Wingfooted

@Wingfooted I agree in general, but for argument's sake let's assume it's a special case where performance is crucial. – Transitory

I am not sure calling the JDK implementation naive is fair. I for one can not think of a more efficient correct implementation. – Trusteeship

@Transitory I'll keep both my points on that. The JDK implementation can rely on a few tricks to make the operation fast enough, without crippling correctness. And since you haven't shown any form of benchmarks proving its relevance in execution speed, it does sound like premature optimization. – Wingfooted

@Transitory Something like this is very unlikely to be the cause of a performance problem, so it is most likely not worth it to try to find some "clever" trick instead of just using an obvious and correct solution. – Pretypify

+1 - As a general rule, use built-in JDK functions for common tasks, because they're more likely to be intrinsified. – Festivity

No argument there. I was just wondering if there was a different way to do it. – Transitory

Answer 2

Your algorithm is incorrect, as it returns 0 when asked to compare 1 and 0:

(1 - 0) >>> 32
1 >>> 32
0

In general, I am not sure it is possible to compare longs without branch instructions, because the difference of two longs may not fit in a long without overflowing, which would change the sign of the difference.

I therefore agree with Evgeniy's answer that using the JDK implementation is likely the best approach.

Trusteeship

Answer 3

I found this alternative solution similar to what you suggested:

public static int signum(long i) {
  return (int) ((i >> 63) | (-i >>> 63));
}

I can't take credit for the solution, it's the implementation of: https://docs.oracle.com/javase/7/docs/api/java/lang/Long.html#signum(long)

Based on your example, I will use it as:

@Override public int compareTo(MyClass that) {
    return Long.signum(value - that.value);
}

As one of the comments mentioned, is a good idea to start with the built-in JDK functions for common tasks.

Arciniega