3

Arrays below are sorted without duplicates (contain unique positive integers) of small size (less than 5000) and intersection (see below) is called billion of times so any micro-optimization does matter. This article nicely describes how to speed up the below code in C language.

int i = 0, j = 0, c = 0, la = a.length, lb = b.length;
intersection = new int[Math.min(la, lb)];
while (i < la && j < lb) {
    if (a[i] < b[j]) i++;
    else if (a[i] > b[j]) j++;
    else {
        intersection[c] = a[i];
        i++; j++; c++;
    }
}
int[] intersectionZip = new int[c];
System.arraycopy(intersection, 0, intersectionZip, 0, c);

In Java I guess it is impossible to call those low-level instructions. But they mention that "it is possible to improve this approach using branchless implementation". How one would do it? Using switch? Or maybe substitute a[i] < b[j], a[i] > b[j] or a[i] == b[i] comparisons with binary operations on integer operands?

Binary search approach (with complexity O(la log(lb))) is not the case because la is not << than lb. Interesting how to change the if statements.

Sophie Sperner
  • 4,428
  • 8
  • 35
  • 55

2 Answers2

1

I don't think there's much you could do to improve that performance of that Java code. However, I would note that it is not doing the same thing as the C version. The C version is putting the intersection into an array that was preallocated by the caller. The Java version allocates the array itself ... and then reallocates and copies to a smaller array when it is finished.

I guess, you could change the Java version to make two passes over the input arrays, with the first one working out how big the input array needs to be ... but whether it helps or hinders will depend on the inputs.

There might be other special cases you could optimize for; e.g. if there were likely to be long runs of numbers in one array with nothing in that range in the other array you might be able to "optimistically" try to skip multiple numbers in one go; i.e. increment i or j by a larger number than 1.

But they mention that "it is possible to improve this approach using branchless implementation". How one would do it? Using switch?

Not a Java switch ... or a conditional expression because they both involve branches when translated to the native code.

I think he is referring to something like this: Branchless code that maps zero, negative, and positive to 0, 1, 2

FWIW it is a bad idea to try to do this kind of thing in Java. The problem is that the performance of tricky code sequences like that is dependent on details of the hardware architecture, instruction set, clock counts, etc that vary from one platform to the next. The Java JIT compiler's optimizer can do a pretty good job of optimizing your code ... but if you include tricky sequences:

  1. it is not at all obvious or predictable how they will be translated to native code, and
  2. you may well find that the trickiness actually inhibits useful optimizations that the JIT compiler might otherwise be able to do.

Having said that, it is not impossible that some future release of Java might include a superoptimizer ... along the lines of the one mentioned on the linked Q&A above ... that would be able to generate branchless sequences automatically. But bear in mind that superoptimization is very expensive to perform.

Community
  • 1
  • 1
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
0

Maybe using ? : operator: 

  (a[i] < b[j]) ? i++ : ((a[i] > b[j]) ? j++ : ....
hamid
  • 2,033
  • 4
  • 22
  • 42