0
310
ViewsHow 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
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?
1 answers
Answer question0
Unfortunately, this is not possible in Java.
To understand why, take a look at the native types behind Java types within the JVM.
NOTICE:
- Java
intprimitives (jint) are backed by 32-bit signed integers. - Java
booleanprimitives (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.