Fastest way of checking the condition l+1<r for int l,r in Java

Question

What is the fastest way of checking the condition

l + 1 < r

for int l,r in Java?

l and r are not constant and I know that l <= r. The comparison is a stopping condition for a while loop in a binary search implementation. I am of course benchmarking my code, both in a separate test (searching a large array) and in the code which uses it.

What I am looking for, I imagine, is some sort of a bit operation which would be faster than the present condition. But I don't know.

Answer 1

I think that's probably as fast as it's going to get. That'll reduce to very simple bytecode, and the JIT (just-in-time compiler) will probably reduce that to a very simple native implementation.

(Unrelated: interesting to see a 'quant dev' use Java btw. Doesn't happen that often)

Answer 2

This kind of micro-optimization is almost always a bad idea; your performance for such a small bit will be entirely dependent on how the hotspot compiler optimizes your code, and subtle cache effects having to do with the surrounding code.

Answer 3

Well the underlying comparison must either:

add 1 to l, compare the result to r

or

subtract 1 from r and compare the result to l

All modern hardware will have the same raw performance for either operation (where addition and subtraction of any native data type has identical performance in terms of cycles to complete and pipeline side effects).

The only way this will have any effect is if:

one of l or r are known constants at compile time. eg.

l + 1 < 5
5 + 1 < r

in this case a poor optimizing compiler may not realise it can convert the first into l < 4

but all java compilers are required to spot that the second case is 6 < r

The other is if the data types of l and r are different.

The operation of :

1. floating point addition/subtraction then comparison to an int
   verses
2. integral addition/subtraction then comparison with a double may be different.

It is fair to say that the chances of this being a serious issue in your application are negligible since the cycle cost of any of these is tiny compared to the pipeline hit of any branch mispredictions associated with the decision.

Also a decent JIT may do all sorts of optimizations in relation to the surrounding code that outweigh the micro optimization performed.

Answer 4

Have a variable lr1 which always equals (l - r + 1). Whenever you increment or decrement l, do the same to lr1. Similarly for r.

Then your test becomes (lr1 < 0), and the instructions to modify lr1 are executed no more often than necessary.

I feel a little silly giving you a micro-optimization, which in most cases is penny-wise, pound-foolish. Like if you're comparing strings, it will totally swamp that test.

ADDED: Since you're doing binary search, I would mention Jon Bentley's cool unrolling of binary search. First you pad the table A up to a power of 2, like 1024. Then you write something like this:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

and finally test if (X == A[i]). Or, if you don't want to pad it, let the if statements be something like
if (i+512 < N && X >= A[i+512]) i += 512;

Answer 5

What all these guys said. The compiler is going to optimize that away for you. Write it so it looks and reads properly to you and move on.

Answer 6

Your best bet is to tweak the JVM rather than the code - given that this is your bottleneck.

Try starting the jvm with the arguments -server -XX:+AggressiveOpts.

Answer 7

How about moving your equality test outside of the while loop, so you check .equals() only after termination. btw I couldn't find any bit twiddling ways to test whether l+1<r. If your array lengths are known to be less than certain sizes, what if you use a different datatype for indices? char/short/byte?