How do you convert a boolean condition to an integer type in Java without a branching or jump in the compiled byte-code and JITed machine-code

user_676644 0
Viewed 234

As in the example given here for C/C++:

... This is due to a new technique described in "BlockQuicksort: How Branch Mispredictions don't affect Quicksort" by Stefan Edelkamp and Armin Weiss. In short, we bypass the branch predictor by using small buffers (entirely in L1 cache) of the indices of elements that need to be swapped. We fill these buffers in a branch-free way that's quite elegant (in pseudocode):

buffer_num = 0; buffer_max_size = 64;
for (int i = 0; i < buffer_max_size; ++i) {
    // With branch:
    if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; }
    // Without:
    buffer[buffer_num] = i; buffer_num += (elements[i] < pivot);
}

how can the same be achieved in Java without a branch or jump?

branch-prediction java performance
1 Answers

Unfortunately, this is not possible in Java.

To understand why, take a look at the native types behind Java types within the JVM.

Table of native types mapped to Java types

NOTICE:

  • Java int primitives (jint) are backed by 32-bit signed integers.
  • Java boolean primitives (jboolean) are backed by 8-bit unsigned integers.

The reason you can't cast between the two without a jump or branch is that the cast necessarily involves a signed-unsigned comparison, and signed-unsigned comparison necessarily involves jumps or branches. The answer to this question provides a good explanation of why.

Basically, at the hardware level, the processor itself is not able to perform signed-unsigned comparison in a single operation. The processor has to do the comparison in terms of signed-signed and unsigned-unsigned comparisons. This requires a logic tree, and therefore also requires jumps or branching.

TL;DR: int to boolean conversion cannot be done in Java without jumps or branching at the native level, because boolean is unsigned and int is signed and therefore a conversion requires signed-unsigned comparison.

user_50907580
Related