Pohled pod kapotu JVM (9.část - tajemství instrukcí lookupswitch a tableswitch)

7. 2. 2012

Doba čtení: 16 minut

Líbí se vám článek?
Podpořte redakci

V dnešní části seriálu o jazyce Java a JVM se již počtvrté budeme zabývat popisem instrukčního souboru virtuálního stroje Javy. Zaměříme se především na dvojici poměrně komplikovaných instrukcí nazvaných tableswitch a lookupswitch, pomocí nichž se implementují větvení programů realizované příkazy switch.

Obsah

1. Rozvětvení programů realizované sadou příkazů if

2. Rozvětvení programů vytvořené příkazy if-elseif

3. Programová konstrukce switch v Javě

4. Struktura instrukce tableswitch

5. Příklad využití instrukce tableswitch

6. Bajtkód instrukce tableswitch pod lupou hexa editoru

7. Struktura instrukce lookupswitch

8. Příklad využití instrukce lookupswitch

9. Odkazy na Internetu

1. Rozvětvení programů realizované sadou příkazů if

V předchozí části seriálu o programovacím jazyku Java i o vlastnostech JVM jsme si popsali všechny základní instrukce používané pro řízení běhu programu. Jednalo se především o nepodmíněné a podmíněné skoky, pomocí nichž je možné realizovat jak podmíněné příkazy typu if-then-else či výrazy ?:, tak i počítané a nepočítané programové smyčky. Teoreticky je sice možné minule uvedené instrukce použít i pro implementaci příkazu switch, ve skutečnosti je však virtuální stroj Javy vybaven dvojicí poměrně složitých instrukcí nazvaných tableswitch a lookupswitch určených právě pro co nejefektivnější implementaci tohoto příkazu (jehož užitečnost je popravdě řečeno v objektově orientovaném jazyce poněkud diskutabilní, nicméně se poněkud vylepšila v Javě 7).

Začněme jednoduchým demonstračním příkladem – implementací rozvětvení s využitím příkazu if. Následující demonstrační program obsahuje jen jedinou statickou metodu, která na základě hodnoty svého prvního a jediného parametru vrátí celočíselnou hodnotu zjištěnou v sekvenci příkazů if (prozatím ignorujme fakt, že se celá věc dá snadno vyřešit s využitím pole):

class Test1 {
 
    static char ifChain(int x) {
        if (x == 0) return 'a';
        if (x == 1) return 'b';
        if (x == 2) return 'c';
        if (x == 3) return 'd';
        return ' ';
    }
 
}

Přeložený bajtkód je celkem snadno pochopitelný a vyskytují se v něm pouze ty instrukce, které jsme si již popsali dříve (poznámky a šipky podmíněných skoků jsou samozřejmě dopsány ručně):

static char ifChain(int);
  Code:
   0:   iload_0
   1:   ifne          7   -------+
   4:   bipush  97   // 'a'      |
   6:   ireturn                  |
                                 |
   7:   iload_0     <------------+
   8:   iconst_1
   9:   if_icmpne     15  -------+
   12:  bipush  98   // 'b'      |
   14:  ireturn                  |
                                 |
   15:  iload_0     <------------+
   16:  iconst_2
   17:  if_icmpne     23  -------+
   20:  bipush  99   // 'c'      |
   22:  ireturn                  |
                                 |
   23:  iload_0     <------------+
   24:  iconst_3
   25:  if_icmpne     31  -------+
   28:  bipush  100  // 'd'      |
   30:  ireturn                  |
                                 |
   31:  bipush  32  <------------+
   33:  ireturn
}

2. Rozvětvení programů vytvořené příkazy if-elseif

Zajímavé je, že prakticky stejný bajtkód je vygenerován i v případě, že se namísto sekvence izolovaných příkazů if použije schéma if-elseif-elseif-…. Je to vlastně vcelku pochopitelné, protože se v našem demonstračním příkazu nachází za každou podmínkou pouze příkaz return, který v případě splnění podmínky ukončí běh testovací metody:

class Test2 {
 
    static char ifElseChain(int x) {
        if (x == 0) return 'a';
        else if (x == 1) return 'b';
        else if (x == 2) return 'c';
        else if (x == 3) return 'd';
        return ' ';
    }
 
}

Vygenerovaný bajtkód je zcela stejný jako u příkladu z první kapitoly:

static char ifElseChain(int);
  Code:
   0:   iload_0
   1:   ifne          7   -------+
   4:   bipush  97   // 'a'      |
   6:   ireturn                  |
                                 |
   7:   iload_0     <------------+
   8:   iconst_1
   9:   if_icmpne     15  -------+
   12:  bipush  98   // 'b'      |
   14:  ireturn                  |
                                 |
   15:  iload_0     <------------+
   16:  iconst_2
   17:  if_icmpne     23  -------+
   20:  bipush  99   // 'c'      |
   22:  ireturn                  |
                                 |
   23:  iload_0     <------------+
   24:  iconst_3
   25:  if_icmpne     31  -------+
   28:  bipush  100  // 'd'      |
   30:  ireturn                  |
                                 |
   31:  bipush  32  <------------+
   33:  ireturn
}

Z obou výše vypsaných disassemblovaných bajtkódů je patrné, že se v obou případech neustále provádí porovnání hodnoty jediného parametru metody s konstantami 1, 2 a 3 (porovnání s nulou je „optimalizováno“, protože je proveden pouze test na nulovost operandu, nikoli porovnání) a na základě výsledku tohoto porovnání se buď podmíněným skokem ifne/if_icmpne přejde k testu další větve, nebo se naopak řízení přenese dovnitř aktuální větve, což vede až k příkazu ireturn. Předností tohoto přístupu je naprostá univerzálnost, protože je v příkazu if () možné zapsat libovolný typ podmínky; na druhou stranu je však tělo metody poměrně dlouhé – celých 34 bajtů – a navíc je kvůli jednotlivým testům běh metody docela pomalý, a to i při překladu do bajtkódu JIT překladačem. Je tedy zřejmé, že by bylo vhodnější použít poněkud odlišný přístup k celé problematice.

3. Programová konstrukce switch v Javě

Každého Javistu samozřejmě hned napadne, jakým způsobem lze předchozí dva demonstrační programy vylepšit: buď by se jednalo o použití tabulky či asociativního pole, nebo o zápis rozvětvení s využitím programové konstrukce switch. Tato řídicí struktura je v programovacím jazyku Java dostupná již od samého počátku, tj. od JDK 1.0, což je ale vlastně samozřejmé, neboť byla po mírných úpravách převzata z jazyků C a C++, které jsou ideovými předchůdci Javy. Ovšem původně se jednalo o řídicí strukturu, v níž bylo možné za klíčovým slovem switch použít pouze celočíselný výraz vyhodnocovaný na int a jednotlivé větve specifikované klíčovým slovem case mohly obsahovat pouze celočíselnou konstantu typu byte, short či int, nikoli však long, což je omezení dané strukturou bajtkódu! (viz další text). Kromě těchto tří datových typů bylo možné použít i znakový literál, který je v Javě taktéž považován za jinak zapsanou celočíselnou šestnáctibitovou konstantu typu char – i tento typ je v bajtkódu zpracováván jako celé číslo typu int.

Jen pro zajímavost si připomeňme, že i když je datový typ boolean taktéž interně zpracováván podobně, jako proměnné typu int, není výraz typu boolean v příkazu switch možné použít, což je ostatně jen dobře, protože by tato konstrukce byla naprosto monstrózní, o čemž se můžete sami přesvědčit:

class JavaMonstrosity {
 
    static char badSwitch(boolean b) {
        switch (b) {
            case true:  /* neco */ break;
            case false: /* neco */break;
        }
    }
 
}

Při překladu zdrojového kódu je programová konstrukce vytvořená s využitím klíčových slov switch, case, break a default přeložena do bajtkódu, v němž jsou použity instrukce tableswitch, popř. lookupswitch, s nimiž se setkáme i v následujících kapitolách.

Konkrétní výběr jedné z těchto instrukcí, jež se ve vygenerovaném bajtkódu skutečně použije, je proveden v závislosti na tom, která instrukce je pro daný příkaz switch vykonána efektivněji nebo která je reprezentována kratším bajtkódem (to záleží především na tom, jaké konstanty jsou uvedeny u jednotlivých větví case, jak si to ostatně ukážeme na demonstračních příkladech). V J2SE 5.0 byly možnosti řídicí konstrukce switch ve dvou směrech rozšířeny. Kromě primitivních datových typů byte, short, int a char byla přidána i podpora pro instance obalových tříd těchto typů, tj. pro instance tříd Character, Byte, Short a Integer . Tato podpora samozřejmě souvisí s autoboxingem a unboxingem, což jsou taktéž nové vlastnosti J2SE 5.0. Ovšem mnohem užitečnější bylo rozšíření příkazu switch o výčtový typ (enumeration – enum), díky čemuž bylo možné mnoho algoritmů zapsat čitelnějším a taktéž bezpečnějším způsobem, protože se z programů mohly odstranit typově nezabezpečené „magické konstanty“.

4. Struktura instrukce tableswitch

První instrukcí, která slouží k implementaci příkazu switch, je instrukce nazvaná tableswitch. Na rozdíl od všech instrukcí, které jsme si v tomto seriálu až doposud popsali, je instrukce tableswitch poměrně složitá a variabilní, už jen z toho důvodu, že je její délka proměnná. Operační kód instrukce tableswitch má hodnotu 0×AA. Za operačním kódem mohou následovat až tři „výplňové bajty mající nulovou hodnotu (teoreticky je sice jejich hodnota libovolná, ale JVM provádí kontrolu, zda se skutečně jedná o nuly). Tyto bajty slouží k tomu, aby byly další údaje zarovnané na adresách dělitelných čtyřmi (tj. provádí se zarovnání na 32 bitů, a to vždy v rámci těla metody, nikoli v rámci celého bajtkódu!). Jde o první ukázku výjimečnosti instrukcí tableswitch a lookupswitch, protože žádné další instrukce virtuálního stroje Javy zarovnání nevyužívají ani nepožadují.

Za nula až třemi výplňovými bajty se nachází 32bitová hodnota představující offset skoku pro větev default, popř. offset první instrukce umístěné ZA příkazem switch v případě, že větev default není uvedena. Pozor: jedná se skutečně o offset, tj. o relativní adresu počítanou od pozice operačního kódu instrukce tableswitch. Offset musí být vždy větší než nula a navíc je z praktických důvodů délka metod omezena na 65536 bajtů, což znamená i omezení velikosti offsetu v reálných bajtkódech na šestnáctibitové kladné hodnoty. Dalšími údaji uvedenými u instrukce tableswitch jsou 32bitové hodnoty low a high představující nejmenší a největší hodnoty použité ve větvích case. Následuje sekvence 32bitových offsetů adres pro jednotlivé větve case; těchto offsetů je celkem high-low+1. Pokud se například v příkazu switch použijí větve s konstantami 10, 11 a 12, je hodnota low nastavena na 10, hodnota high nastavena na 12 a offsety jsou v tabulce uloženy celkem tři, protože 12–10+1=3:

1. operační kód
2. výplňové bajty
3. offset pro větev default
4. hodnota low (nejmenší použitá konstanta ve větvích case)
5. hodnota high (největší použitá konstanta ve větvích case)
6. offset pro větev #1
7. offset pro větev #2
8. offset pro větev #3
...
...
...

Instrukce tableswitch je použitelná pouze v těch případech, kdy se ve větvích case používají celočíselné konstanty tvořící nepřerušenou sekvenci. V tomto případě virtuální stroj Javy nejprve získá ze zásobníku operandů číselný operand, odečte od něj hodnotu low a získá tak index, který následně použije při přístupu do tabulky offsetů uloženou za operačním kódem instrukce tableswitch. Pokud je hodnota získaná ze zásobníku operandů menší než low nebo naopak větší než high, provede se skok na větev default. Důležitá je efektivita výpočtu adresy skoku, která je v tomto případě obecně větší, než při použití podmíněných skoků použitých v předchozích dvou příkladech a dokonce i větší, než je tomu u instrukce lookupswitch. Programátoři mohou tuto znalost využít ve svůj prospěch pro dosažení vyššího výkonu aplikací, protože v některých případech je výhodné doplnit do zdrojového textu „prázdné“ větve a docílit tak toho, že se využije instrukce tableswitch namísto delší a pomalejší instrukce lookupswitch.

5. Příklad využití instrukce tableswitch

Jak je z předchozího popisu zřejmé, je formát instrukce tableswitch skutečně poměrně složitý. Proto si teď ukážeme nejenom to, jakým způsobem je tato instrukce vygenerována v bajtkódu, ale taktéž její obsah získaný z hexa editoru, popřípadě nástrojem typu xxd:

class Test3 {
 
    static char simpleSwitch(int x) {
        switch (x) {
            case 10: return 'a';
            case 11: return 'b';
            case 12: return 'c';
            case 13: return 'd';
            case 14: return 'e';
            default: return ' ';
        }
    }
 
}

Bajtkód vygenerovaný překladačem javac obsahuje na začátku instrukci iload₀ zajišťující uložení hodnoty parametru metody na zásobník operandů. Druhou instrukcí je již popisovaná instrukce tableswitch se šesti skoky – pěti větvemi case a jednou větví default:

static char simpleSwitch(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //10 to 14
                10: 36;
                11: 39;
                12: 42;
                13: 45;
                14: 48;
                default: 51 }
 
   36:  bipush  97
   38:  ireturn
 
   39:  bipush  98
   41:  ireturn
 
   42:  bipush  99
   44:  ireturn
 
   45:  bipush  100
   47:  ireturn
 
   48:  bipush  101
   50:  ireturn
 
   51:  bipush  32
   53:  ireturn

6. Bajtkód instrukce tableswitch pod lupou hexa editoru

Nyní se podívejme na způsob zakódování binární podoby instrukce tableswitch v bajtkódu. Při průzkumu bajtkódu v hexa editoru lze snadno zjistit, že bajty tvořící tělo metody simpleSwitch začínají následující sekvencí hodnot:

1a aa 00 00 00 00 00 32 00 00 00 0a 00 00 00 0e
00 00 00 23 00 00 00 26 00 00 00 29 00 00 00 2c
00 00 00 2f .. .. .. .. .. .. .. .. .. .. .. ..

Poznámka: hexadecimální výpis obsahu bajtkódu zajistí příkaz xxd -g 1 test.class s případným přesměrováním výstupu do souboru. Popřípadě je možné soubor test.class otevřít v interním prohlížeči Midnight Commanderu a stlačit klávesu F4.

Na základě informací uvedených v předchozí kapitole je možné tuto sekvenci hodnot s trochou úsilí dekódovat. První bajt je operačním kódem instrukce iload₀, takže je pro nás v tuto chvíli nezajímavý. Ihned po něm následuje operační kód instrukce tableswitch, tj. hodnota 0×aa, za níž jsou uloženy dva výplňové bajty, které zarovnávají další hodnoty na 32 bitů. Poté můžeme v bajtkódu nalézt offset pro větev default, hodnoty low a high a konečně tabulku pěti hodnot, v nichž jsou uloženy offsety adres jednotlivých větví příkazu switch:

1a             // operační kód instrukce iload_0 - není součástí tableswitche!
 
aa             // operační kód instrukce tableswitch
00 00          // dvojice výplňových bajtů
00 00 00 32    // offset pro větev default je 0x32=50, reálná adresa je 51
00 00 00 0a    // hodnota low je nastavena na 0x0a = 10 desítkově
00 00 00 0e    // hodnota high je nastavena na 0x0e = 14 desítkově
00 00 00 23    // offset první větve je 0x23 = 35, reálná adresa je 36
00 00 00 26    // offset druhé větve je 0x26 = 38, reálná adresa je 39
00 00 00 29    // offset třetí větve je 0x29 = 41, reálná adresa je 42
00 00 00 2c    // offset čtvrté větve je 0x2c = 44, reálná adresa je 45
00 00 00 2f    // offset páté větve je 0x2f = 47, reálná adresa je 48

7. Struktura instrukce lookupswitch

Druhá instrukce používaná v bajtkódu pro implementaci příkazu switch je instrukce nazvaná lookupswitch. Struktura této instrukce se částečně podobá již popsané instrukci tableswitch, ovšem s tím rozdílem, že se namísto pole jednotlivých offsetů používá vyhledávací tabulka obsahující dvojici hodnota_větve_case:offset, takže je délka instrukce obecně větší, ovšem zato obecnější. Pojďme si tedy strukturu instrukce lookupswitch popsat podrobněji. Operační kód této instrukce je roven hodnotě 0×AB. Za operačním kódem může následovat nula až tři výplňové bajty (což již známe z předchozích kapitol). Po případných výplňových bajtech je uložen 32bitový offset pro větev default. Až doposud se tedy struktura instrukce lookupswitch podobala struktuře instrukce tableswitch (samozřejmě až na rozdílný operační kód).

Ovšem nyní již nastává změna, protože dalším údajem je 32bitová hodnota npairs, která obsahuje počet větví case (tento údaj nemusel být u instrukce tableswitch uveden, neboť ho bylo možné vypočítat z hodnot low a high, které však v lookupswitch nejsou použity). Dostáváme se již ke konci – za celočíselným údajem o počtu větví následuje npairs párů hodnota_větve_case:offset, přičemž oba prvky tohoto páru jsou reprezentovány 32bitovými hodnotami. Vzhledem k tomu, že údaj hodnota_větve_case může být libovolná konstanta typu int, znamená to, že se pomocí instrukce lookupswitch mohou realizovat prakticky libovolně konstruované příkazy switch:

1. operační kód
2. výplňové bajty
3. offset pro větev default
4. hodnota npairs
5. hodnota case + offset pro větev #1
6. hodnota case + offset pro větev #2
7. hodnota case + offset pro větev #3
8. hodnota case + offset pro větev #4
...
...
x. hodnota case + offset pro větev #npairs

8. Příklad využití instrukce lookupswitch

Při tvorbě demonstračního příkladu pro instrukci lookupswitch je nutné zajistit, aby konstanty použité ve větvích case netvořily souvislou řadu celých čísel, protože by překladač v tomto případě použil „optimalizovanou“ instrukci tableswitch:

class Test5 {
 
    static char simpleSwitch(int x) {
        switch (x) {
            case 0:    return 'a';
            case 10:   return 'b';
            case 64:   return 'c';
            case 99:   return 'd';
            case 6502: return 'e';
            default:   return ' ';
        }
    }
 
}

Bajtkód vygenerovaný překladačem javac obsahuje na začátku opět instrukci iload₀ zajišťující uložení hodnoty parametru metody na zásobník operandů. Druhou instrukcí je lookupswitch se šesti skoky – pěti větvemi case a jednou větví default:

static char simpleSwitch(int);
  Code:
   0:   iload_0
   1:   lookupswitch{ //5
        0:    52;
        10:   55;
        64:   58;
        99:   61;
        6502: 64;
        default: 67 }
   52:  bipush  97
   54:  ireturn
   55:  bipush  98
   57:  ireturn
   58:  bipush  99
   60:  ireturn
   61:  bipush  100
   63:  ireturn
   64:  bipush  101
   66:  ireturn
   67:  bipush  32
   69:  ireturn

Asi již tušíte, co bude následovat: podíváme se na způsob uložení binárního tvaru instrukce lookupswitch v bajtkódu. Ten vypadá následovně:

ab 00 00 00 00 00 42 00 00 00 05 00 00 00 00 00
00 00 33 00 00 00 0a 00 00 00 36 00 00 00 40 00
00 00 39 00 00 00 63 00 00 00 3c 00 00 19 66 00
00 00 3f

Tuto sekvenci bajtů lze již relativně snadno analyzovat:

aa                         // operační kód instrukce tableswitch
00 00                      // dvojice výplňových bajtů
00 00 00 42                // offset pro větvi default je 0x42 = 66, reálná adresa = 67
00 00 00 05                // hodnota npairs: počet párů hodnota_case:offset
00 00 00 00   00 00 00 33  // case 0:    - offset 0x33=51, reálná adresa = 52
00 00 00 0a   00 00 00 36  // case 10:   - offset 0x36=54, reálná adresa = 55
00 00 00 40   00 00 00 39  // case 64:   - offset 0x39=57, reálná adresa = 58
00 00 00 63   00 00 00 3c  // case 99:   - offset 0x3c=60, reálná adresa = 61
00 00 19 66   00 00 00 3f  // case 6502: - offset 0x3f=63, reálná adresa = 64