Jak przekonwertować warunek logiczny na typ całkowity w Javie bez rozgałęziania lub przeskoku w skompilowanym kodzie bajtowym i kodzie maszynowym JITed [duplikat]

Dec 03 2020

Jak w przykładzie podanym tutaj dla C / C ++:

... Wynika to z nowej techniki opisanej w artykule „BlockQuicksort: How Branch Mispredictions nie wpływają na Quicksort” Stefana Edelkampa i Armina Weissa. Krótko mówiąc, pomijamy predyktor gałęzi, używając małych buforów (całkowicie w pamięci podręcznej L1) indeksów elementów, które należy zamienić. Wypełniamy te bufory w sposób bez gałęzi, który jest dość elegancki (w pseudokodzie):

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);
}

jak można to samo osiągnąć w Javie bez rozgałęzienia lub skoku?

Odpowiedzi

WilliamRosenbloom Dec 02 2020 at 23:48

Niestety nie jest to możliwe w Javie.

Aby zrozumieć dlaczego, przyjrzyj się typom natywnym stojącym za typami Java w JVM.

OGŁOSZENIE:

  • Java intprymitywy ( jint) są wspierane przez 32-bitowe podpisane liczb całkowitych.
  • booleanPrymitywy Java ( jboolean) są obsługiwane przez 8-bitowe liczby całkowite bez znaku .

Powodem, dla którego nie można rzutować między tymi dwoma bez skoku lub gałęzi jest to, że rzutowanie musi koniecznie obejmować porównanie ze znakiem i bez znaku, a porównanie ze znakiem i bez znaku musi koniecznie obejmować skoki lub rozgałęzienia. Odpowiedź na to pytanie dobrze wyjaśnia, dlaczego.

Zasadniczo na poziomie sprzętowym sam procesor nie jest w stanie wykonać porównania ze znakiem i bez znaku w pojedynczej operacji. Procesor musi przeprowadzić porównanie w kategoriach porównań ze znakiem ze znakiem i bez znaku i bez znaku. To wymaga drzewa logicznego, a więc wymaga również skoki czy rozgałęzienia.

TL; DR: int do booleankonwersji nie można wykonać w Javie bez skoków lub rozgałęzień na poziomie natywnym, ponieważ booleanjest bez znaku i intjest podpisany, dlatego konwersja wymaga porównania ze znakiem i bez znaku.