How to speed up array intersection in Java? -

arrays below sorted without duplicates (contain unique positive integers) of small size (less 5000) , intersection (see below) called billion of times micro-optimization matter. article nicely describes how speed below code in c language.

int = 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 guess impossible call low-level instructions. mention "it possible improve approach using branchless implementation". how 1 it? using switch? or maybe substitute a[i] < b[j], a[i] > b[j] or a[i] == b[i] comparisons binary operations on integer operands?

binary search approach (with complexity o(la log(lb))) not case because la not << lb. interesting how change if statements.

i don't think there's improve performance of java code. however, note not doing same thing c version. c version putting intersection array preallocated caller. java version allocates array ... , reallocates , copies smaller array when finished.

i guess, change java version make 2 passes on input arrays, first 1 working out how big input array needs ... whether helps or hinders depend on inputs.

there might other special cases optimize for; e.g. if there long runs of numbers in 1 array nothing in range in other array might able "optimistically" try skip multiple numbers in 1 go; i.e. increment i or j larger number 1.

---

but mention "it possible improve approach using branchless implementation". how 1 it? using switch?

not java switch ... or conditional expression because both involve branches when translated native code.

i think referring this: branchless code maps zero, negative, , positive 0, 1, 2

fwiw bad idea try kind of thing in java. problem performance of tricky code sequences dependent on details of hardware architecture, instruction set, clock counts, etc vary 1 platform next. java jit compiler's optimizer can pretty job of optimizing code ... if include tricky sequences:

1. it not @ obvious or predictable how translated native code, and
2. you may find trickiness inhibits useful optimizations jit compiler might otherwise able do.

having said that, not impossible future release of java might include superoptimizer ... along lines of 1 mentioned on linked q&a above ... able generate branchless sequences automatically. bear in mind superoptimization expensive perform.