Wie konvertiert man eine boolesche Bedingung in Java in einen Integer-Typ ohne Verzweigung oder Sprung in den kompilierten Bytecode und den JITed-Maschinencode [Duplikat]?

Dec 03 2020

Wie im hier angegebenen Beispiel für C / C ++:

... Dies ist auf eine neue Technik zurückzuführen, die in "BlockQuicksort: Wie Branchenfehlvorhersagen Quicksort nicht beeinflussen" von Stefan Edelkamp und Armin Weiss beschrieben wurde. Kurz gesagt, wir umgehen den Verzweigungsprädiktor, indem wir kleine Puffer (vollständig im L1-Cache) der Indizes der Elemente verwenden, die ausgetauscht werden müssen. Wir füllen diese Puffer auf verzweigungsfreie Weise, die ziemlich elegant ist (im 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);
}

Wie kann das gleiche in Java ohne Verzweigung oder Sprung erreicht werden?

Antworten

WilliamRosenbloom Dec 02 2020 at 23:48

Dies ist in Java leider nicht möglich.

Um zu verstehen, warum, werfen Sie einen Blick auf die nativen Typen hinter Java-Typen in der JVM.

BEACHTEN:

  • Java- intGrundelemente ( jint) werden von 32-Bit- Ganzzahlen mit Vorzeichen unterstützt.
  • Java- booleanGrundelemente ( jboolean) werden durch vorzeichenlose 8-Bit- Ganzzahlen unterstützt.

Der Grund, warum Sie ohne einen Sprung oder eine Verzweigung nicht zwischen den beiden wechseln können, besteht darin, dass die Besetzung notwendigerweise einen Vergleich mit Vorzeichen und Vorzeichen beinhaltet und der Vergleich mit Vorzeichen und Vorzeichen notwendigerweise Sprünge oder Verzweigungen beinhaltet. Die Antwort auf diese Frage liefert eine gute Erklärung dafür, warum.

Grundsätzlich ist der Prozessor selbst auf Hardwareebene nicht in der Lage, einen vorzeichenlosen Vergleich in einem einzigen Vorgang durchzuführen. Der Prozessor muss den Vergleich in Form von Vorzeichen-Vorzeichen- und Vorzeichen-Vorzeichen-Vergleichen durchführen. Dies erfordert einen Logikbaum und erfordert daher auch Sprünge oder Verzweigungen.

TL; DR: int auf booleanUmwandlung kann nicht in der nativen Ebene in Java ohne Sprünge oder Verzweigungen erfolgen, da ist booleannicht signiert und intsigniert und somit eine Umwandlung erfordert unterzeichnet-unsigned Vergleich.