3

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?

Suminda Sirinath S. Dharmasena
  • 1,831
  • 3
  • 26
  • 35
  • Why is this important? – Thorbjørn Ravn Andersen Dec 02 '20 at 16:17
  • 1
    Is it really necessary that there isn't a jump in the bytecode? Such a jump could be optimized away by the JIT, should it be determined to be beneficial. – Andy Turner Dec 02 '20 at 16:17
  • The main thing is to bypass the branch predictor as described here: `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)` – Suminda Sirinath S. Dharmasena Dec 02 '20 at 16:19
  • "in a branch-free way that's quite elegant" Are you sure that the branching form won't be optimized to a branch-free form by the JIT? Perhaps it would be if the two forms were actually equivalent (e.g. put the `buffer[buffer_num] = i;` outside the condition). – Andy Turner Dec 02 '20 at 16:21
  • According to [BlockQuicksort: How Branch Mispredictions don't affect Quicksort](https://arxiv.org/abs/1604.06697): `Our experimental results are promising: when sorting random integer data, we achieve an increase in speed of 80% over the GCC implementation of C++ std::sort. Also for many other types of data and non-random inputs, there is still a significant speedup over std::sort.` – Suminda Sirinath S. Dharmasena Dec 02 '20 at 16:24

1 Answers1

0

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.

William Rosenbloom
  • 2,506
  • 1
  • 14
  • 37
  • 1
    OP isn't asking about int to boolean conversion, but boolean to int. And [this answer](https://stackoverflow.com/a/16868321/3788176) demonstrates that it is possible to do without a jump. – Andy Turner Dec 02 '20 at 16:57
  • Additionally, [according to the JVM spec](https://docs.oracle.com/javase/specs/jvms/se14/html/jvms-2.html#jvms-2.3.4): " expressions in the Java programming language that operate on boolean values are compiled to use values of the Java Virtual Machine int data type". – Andy Turner Dec 02 '20 at 16:59
  • @AndyTurner I don't totally understand the question you linked to. That assembly doesn't look like Java byte-code, but it doesn't make sense that Java would compile to native assembly. Also, I agree within the JVM. But the virtual machine must at some level be implemented by the real machine. The branching or jumping would happen on the real processors. – William Rosenbloom Dec 02 '20 at 17:13