Über JVM Switch, wusstet ihr das?

switch

#1

Ich liebe java. Keine andere Sprache hat mir das Informatk-Leben so vereinfacht wie diese.
Nun entwickele ich eine JVM in Java.
Dabei habe ich eine tolle Sache herausgefunden:
Damit switch-Anweisungen schnell ablaufen (O(1)) müssen sie dicht programmiert sein.

switch (inputValue) {
 case 1: // ...
 case 2: // ... 
case 3: // ... 
default: // ... }


switch (inputValue) { 
case 42: // ... 
case 95: // ...
 case 124: // ... 
default: // ... }

Die erste läuft in O(1) ab also direkter Sprung, während die zweite in O(n) ausgeführt wird.

Habt ihr das gewusst?
Jetzt ist das entscheidende Element meiner JVM auch eine switch Anweisung: ich verwende sie um zwischen all den op-codes des bytecodes zu selektieren.
Wenn ich diese nun nicht dicht mache, wird sie wohl hunderte male langsamer arbeiten.

Daa Ziel ist, diese jvm in sich selbst ausführen zu lassen (rein aus pädagogischen Gründen)

Dieses Video finde ich dabei toll:


#2

Tatsächlich “wusste” ich das nicht. Ich bin sicher damals, als ich mir das Class FileFormat und ByteCode & Co genauer angesehen habe, mal über tableswitch vs. lookupswitch gestolpert, aber “auf dem Schirm” hatte ich das nicht.

Ein bißchen was dazu steht hier:

tl;dr ist: Wenn die cases “dicht gepackt” sind, wird ein lookup verwendet. Andernfalls eine “Suche”. Die muss aber nicht O(n) sein, sondern geht auch in O(logn).

(Ob es einen Unterschied macht, ob man

  case 1:    // ...
  case 10:   // ...
  case 100:  // ...

oder

  case 10:   // ...
  case 1:    // ...
  case 100:  // ...

schreibt, und (wichtig: ) ob es dann eine Rolle spielt, ob es dort ein “fall-through” gibt, oder jeweils ein break kommt, müßte man sich mal genauer ansehen).

Aber wie so oft: Der Unterschied zwischen Theorie und Praxis ist in der Praxis größer als in der Theorie. Oder kleiner. Wenn man folgendes Programm hat…

public class SwitchComplexity
{
    public static void main(String[] args)
    {
        int values[] = { 1, 2, 3, 42, 95, 124 };

        int bh0 = 0;
        int bh1 = 0;
        for (int i = 0; i < values.length * 10000; i++)
        {
            int index = i % values.length;
            bh0 += switchDense(values[index]);
            bh1 += switchSparse(values[index]);
        }
        System.out.println(bh0+" "+bh1);
    }

    static int switchDense(int inputValue)
    {
        switch (inputValue)
        {
            case 1:
                return 12;
            case 2:
                return 34;
            case 3:
                return 56;
            default:
                return 78;
        }
    }

    static int switchSparse(int inputValue)
    {
        switch (inputValue)
        {
            case 42:
                return 12;
            case 95:
                return 34;
            case 124:
                return 56;
            default:
                return 78;
        }
    }
}

und das dann compiliert und sich mit javap -c SwitchComplexity den bytecode ansieht, sieht man:

  static int switchDense(int);
    Code:
       0: iload_0
       1: tableswitch   { // 1 to 3
                     1: 28
                     2: 31
                     3: 34
               default: 37
          }
      28: bipush        12
      30: ireturn
      31: bipush        34
      33: ireturn
      34: bipush        56
      36: ireturn
      37: bipush        78
      39: ireturn

  static int switchSparse(int);
    Code:
       0: iload_0
       1: lookupswitch  { // 3
                    42: 36
                    95: 39
                   124: 42
               default: 45
          }
      36: bipush        12
      38: ireturn
      39: bipush        34
      41: ireturn
      42: bipush        56
      44: ireturn
      45: bipush        78
      47: ireturn

Ja, es macht einen Unterschied: Einmal steht da tableswitch und einmal lookupswitch.

Wenn man das ganze dann aber mal mit java -server -XX:+UnlockDiagnosticVMOptions -XX:+TraceClassLoading -XX:+LogCompilation -XX:+PrintAssembly -XX:+PrintInlining SwitchComplexity in einer Hotspot-Disassembler-JVM laufen läßt, und sich das Endergebnis der beiden Methoden ansieht, kommt das hier raus:

Decoding compiled method 0x00000000028d2650:
Code:
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x00000000245104d0} &apos;switchDense&apos; &apos;(I)I&apos; in &apos;SwitchComplexity&apos;
  # parm0:    rdx       = int
  #           [sp+0x40]  (sp of caller)
  0x00000000028d27a0: mov    %eax,-0x6000(%rsp)
  0x00000000028d27a7: push   %rbp
  0x00000000028d27a8: sub    $0x30,%rsp
  0x00000000028d27ac: movabs $0x24510780,%rax
  0x00000000028d27b6: mov    0x8(%rax),%esi
  0x00000000028d27b9: add    $0x8,%esi
  0x00000000028d27bc: mov    %esi,0x8(%rax)
  0x00000000028d27bf: movabs $0x245104c8,%rax   ;   {metadata({method} {0x00000000245104d0} &apos;switchDense&apos; &apos;(I)I&apos; in &apos;SwitchComplexity&apos;)}
  0x00000000028d27c9: and    $0x3ff8,%esi
  0x00000000028d27cf: cmp    $0x0,%esi
  0x00000000028d27d2: je     0x00000000028d2837  ;*iload_0
            ; - SwitchComplexity::switchDense@0 (line 20)

  0x00000000028d27d8: cmp    $0x1,%edx
  0x00000000028d27db: je     0x00000000028d2826
  0x00000000028d27e1: cmp    $0x2,%edx
  0x00000000028d27e4: je     0x00000000028d2815
  0x00000000028d27ea: cmp    $0x3,%edx
  0x00000000028d27ed: je     0x00000000028d2804  ;*tableswitch
            ; - SwitchComplexity::switchDense@1 (line 20)

  0x00000000028d27f3: mov    $0x4e,%eax
  0x00000000028d27f8: add    $0x30,%rsp
  0x00000000028d27fc: pop    %rbp
  0x00000000028d27fd: test   %eax,-0x1be2703(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2803: retq                      ;*ireturn
            ; - SwitchComplexity::switchDense@39 (line 29)

  0x00000000028d2804: mov    $0x38,%eax
  0x00000000028d2809: add    $0x30,%rsp
  0x00000000028d280d: pop    %rbp
  0x00000000028d280e: test   %eax,-0x1be2714(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2814: retq                      ;*ireturn
            ; - SwitchComplexity::switchDense@36 (line 27)

  0x00000000028d2815: mov    $0x22,%eax
  0x00000000028d281a: add    $0x30,%rsp
  0x00000000028d281e: pop    %rbp
  0x00000000028d281f: test   %eax,-0x1be2725(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2825: retq                      ;*ireturn
            ; - SwitchComplexity::switchDense@33 (line 25)

  0x00000000028d2826: mov    $0xc,%eax
  0x00000000028d282b: add    $0x30,%rsp
  0x00000000028d282f: pop    %rbp
  0x00000000028d2830: test   %eax,-0x1be2736(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2836: retq   
  0x00000000028d2837: mov    %rax,0x8(%rsp)
  0x00000000028d283c: movq   $0xffffffffffffffff,(%rsp)
  0x00000000028d2844: callq  0x00000000028bf1a0  ; OopMap{off=169}
            ;*synchronization entry
            ; - SwitchComplexity::switchDense@-1 (line 20)
            ;   {runtime_call}
  0x00000000028d2849: jmp    0x00000000028d27d8
  0x00000000028d284b: nop
  0x00000000028d284c: nop
  0x00000000028d284d: mov    0x2a8(%r15),%rax
  0x00000000028d2854: movabs $0x0,%r10
  0x00000000028d285e: mov    %r10,0x2a8(%r15)
  0x00000000028d2865: movabs $0x0,%r10
  0x00000000028d286f: mov    %r10,0x2b0(%r15)
  0x00000000028d2876: add    $0x30,%rsp
  0x00000000028d287a: pop    %rbp
  0x00000000028d287b: jmpq   0x000000000282c6e0  ;   {runtime_call}
[Exception Handler]
[Stub Code]
  0x00000000028d2880: callq  0x00000000028bc960  ;   {no_reloc}
  0x00000000028d2885: mov    %rsp,-0x28(%rsp)
  0x00000000028d288a: sub    $0x80,%rsp
  0x00000000028d2891: mov    %rax,0x78(%rsp)
  0x00000000028d2896: mov    %rcx,0x70(%rsp)
  0x00000000028d289b: mov    %rdx,0x68(%rsp)
  0x00000000028d28a0: mov    %rbx,0x60(%rsp)
  0x00000000028d28a5: mov    %rbp,0x50(%rsp)
  0x00000000028d28aa: mov    %rsi,0x48(%rsp)
  0x00000000028d28af: mov    %rdi,0x40(%rsp)
  0x00000000028d28b4: mov    %r8,0x38(%rsp)
  0x00000000028d28b9: mov    %r9,0x30(%rsp)
  0x00000000028d28be: mov    %r10,0x28(%rsp)
  0x00000000028d28c3: mov    %r11,0x20(%rsp)
  0x00000000028d28c8: mov    %r12,0x18(%rsp)
  0x00000000028d28cd: mov    %r13,0x10(%rsp)
  0x00000000028d28d2: mov    %r14,0x8(%rsp)
  0x00000000028d28d7: mov    %r15,(%rsp)
  0x00000000028d28db: movabs $0x619e8e30,%rcx   ;   {external_word}
  0x00000000028d28e5: movabs $0x28d2885,%rdx    ;   {internal_word}
  0x00000000028d28ef: mov    %rsp,%r8
  0x00000000028d28f2: and    $0xfffffffffffffff0,%rsp
  0x00000000028d28f6: callq  0x00000000616a3d40  ;   {runtime_call}
  0x00000000028d28fb: hlt    
[Deopt Handler Code]
  0x00000000028d28fc: movabs $0x28d28fc,%r10    ;   {section_word}
  0x00000000028d2906: push   %r10
  0x00000000028d2908: jmpq   0x0000000002807200  ;   {runtime_call}
  0x00000000028d290d: hlt    
  0x00000000028d290e: hlt    
  0x00000000028d290f: hlt    

und

Decoding compiled method 0x00000000028d2a10:
Code:
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x00000000245105b0} &apos;switchSparse&apos; &apos;(I)I&apos; in &apos;SwitchComplexity&apos;
  # parm0:    rdx       = int
  #           [sp+0x40]  (sp of caller)
  0x00000000028d2b60: mov    %eax,-0x6000(%rsp)
  0x00000000028d2b67: push   %rbp
  0x00000000028d2b68: sub    $0x30,%rsp
  0x00000000028d2b6c: movabs $0x245107a0,%rax
  0x00000000028d2b76: mov    0x8(%rax),%esi
  0x00000000028d2b79: add    $0x8,%esi
  0x00000000028d2b7c: mov    %esi,0x8(%rax)
  0x00000000028d2b7f: movabs $0x245105a8,%rax   ;   {metadata({method} {0x00000000245105b0} &apos;switchSparse&apos; &apos;(I)I&apos; in &apos;SwitchComplexity&apos;)}
  0x00000000028d2b89: and    $0x3ff8,%esi
  0x00000000028d2b8f: cmp    $0x0,%esi
  0x00000000028d2b92: je     0x00000000028d2bf7  ;*iload_0
            ; - SwitchComplexity::switchSparse@0 (line 35)

  0x00000000028d2b98: cmp    $0x2a,%edx
  0x00000000028d2b9b: je     0x00000000028d2be6
  0x00000000028d2ba1: cmp    $0x5f,%edx
  0x00000000028d2ba4: je     0x00000000028d2bd5
  0x00000000028d2baa: cmp    $0x7c,%edx
  0x00000000028d2bad: je     0x00000000028d2bc4  ;*lookupswitch
            ; - SwitchComplexity::switchSparse@1 (line 35)

  0x00000000028d2bb3: mov    $0x4e,%eax
  0x00000000028d2bb8: add    $0x30,%rsp
  0x00000000028d2bbc: pop    %rbp
  0x00000000028d2bbd: test   %eax,-0x1be2ac3(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2bc3: retq                      ;*ireturn
            ; - SwitchComplexity::switchSparse@47 (line 44)

  0x00000000028d2bc4: mov    $0x38,%eax
  0x00000000028d2bc9: add    $0x30,%rsp
  0x00000000028d2bcd: pop    %rbp
  0x00000000028d2bce: test   %eax,-0x1be2ad4(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2bd4: retq                      ;*ireturn
            ; - SwitchComplexity::switchSparse@44 (line 42)

  0x00000000028d2bd5: mov    $0x22,%eax
  0x00000000028d2bda: add    $0x30,%rsp
  0x00000000028d2bde: pop    %rbp
  0x00000000028d2bdf: test   %eax,-0x1be2ae5(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2be5: retq                      ;*ireturn
            ; - SwitchComplexity::switchSparse@41 (line 40)

  0x00000000028d2be6: mov    $0xc,%eax
  0x00000000028d2beb: add    $0x30,%rsp
  0x00000000028d2bef: pop    %rbp
  0x00000000028d2bf0: test   %eax,-0x1be2af6(%rip)        # 0x0000000000cf0100
            ;   {poll_return}
  0x00000000028d2bf6: retq   
  0x00000000028d2bf7: mov    %rax,0x8(%rsp)
  0x00000000028d2bfc: movq   $0xffffffffffffffff,(%rsp)
  0x00000000028d2c04: callq  0x00000000028bf1a0  ; OopMap{off=169}
            ;*synchronization entry
            ; - SwitchComplexity::switchSparse@-1 (line 35)
            ;   {runtime_call}
  0x00000000028d2c09: jmp    0x00000000028d2b98
  0x00000000028d2c0b: nop
  0x00000000028d2c0c: nop
  0x00000000028d2c0d: mov    0x2a8(%r15),%rax
  0x00000000028d2c14: movabs $0x0,%r10
  0x00000000028d2c1e: mov    %r10,0x2a8(%r15)
  0x00000000028d2c25: movabs $0x0,%r10
  0x00000000028d2c2f: mov    %r10,0x2b0(%r15)
  0x00000000028d2c36: add    $0x30,%rsp
  0x00000000028d2c3a: pop    %rbp
  0x00000000028d2c3b: jmpq   0x000000000282c6e0  ;   {runtime_call}
[Exception Handler]
[Stub Code]
  0x00000000028d2c40: callq  0x00000000028bc960  ;   {no_reloc}
  0x00000000028d2c45: mov    %rsp,-0x28(%rsp)
  0x00000000028d2c4a: sub    $0x80,%rsp
  0x00000000028d2c51: mov    %rax,0x78(%rsp)
  0x00000000028d2c56: mov    %rcx,0x70(%rsp)
  0x00000000028d2c5b: mov    %rdx,0x68(%rsp)
  0x00000000028d2c60: mov    %rbx,0x60(%rsp)
  0x00000000028d2c65: mov    %rbp,0x50(%rsp)
  0x00000000028d2c6a: mov    %rsi,0x48(%rsp)
  0x00000000028d2c6f: mov    %rdi,0x40(%rsp)
  0x00000000028d2c74: mov    %r8,0x38(%rsp)
  0x00000000028d2c79: mov    %r9,0x30(%rsp)
  0x00000000028d2c7e: mov    %r10,0x28(%rsp)
  0x00000000028d2c83: mov    %r11,0x20(%rsp)
  0x00000000028d2c88: mov    %r12,0x18(%rsp)
  0x00000000028d2c8d: mov    %r13,0x10(%rsp)
  0x00000000028d2c92: mov    %r14,0x8(%rsp)
  0x00000000028d2c97: mov    %r15,(%rsp)
  0x00000000028d2c9b: movabs $0x619e8e30,%rcx   ;   {external_word}
  0x00000000028d2ca5: movabs $0x28d2c45,%rdx    ;   {internal_word}
  0x00000000028d2caf: mov    %rsp,%r8
  0x00000000028d2cb2: and    $0xfffffffffffffff0,%rsp
  0x00000000028d2cb6: callq  0x00000000616a3d40  ;   {runtime_call}
  0x00000000028d2cbb: hlt    
[Deopt Handler Code]
  0x00000000028d2cbc: movabs $0x28d2cbc,%r10    ;   {section_word}
  0x00000000028d2cc6: push   %r10
  0x00000000028d2cc8: jmpq   0x0000000002807200  ;   {runtime_call}
  0x00000000028d2ccd: hlt    
  0x00000000028d2cce: hlt    
  0x00000000028d2ccf: hlt    

und siehe da: Der Assemblercode ist letztendlich derselbe. Auf den Justin ist halt Verlaß :sunglasses:

(Zumindest in diesem trvialen Fall. Es gibt vielleicht einen Punkt oder eine Konstellation, wo er das nicht mehr macht. Vielleicht wenn es mehr cases gibt, oder dort mehr steht als ein return, und er da dann eher mit Method inlining & Co zu kämpfen hat. Aber letztendlich sehe ich keinen Grund, warum es am Ende nicht auf einen echten Sprung rauslaufen sollte: Im x86 kann er ja beliebig rumhüpfen…)

Die JavaZone-Videos sind manhmal recht unterhaltsam :smiley:


#3

Vielen Dank für die unglaublich ausführliche Antwort.
Wenn ihr Interesse habt hier kann man meine JVM unter Android testen:

Es funktionieren einfache Algorithmen, aber wie gesagt sie wird bald fähig sein, sich selbst auszuführen.

Hier ist der Quellcode (Sieht noch wie eine Chaotische Baustelle aus):

Diese JVM versucht nach Möglichkeit die Klassen der JVM auf der sie läuft zu benutzen. Ich habe versucht die System-Klasse in ihr zu laden, aber das war doch ein ziemlich komplizierter Vorgang wie hier beschrieben:

Es kommt noch die Möglichkeit den Quellcode einzubinden, so dass man den schön debuggen kann. Das finde ich einfach nur geil.


#4

Hab’ mal kurz über den Code gebrowst. Ja, ist wohl noch einiges zu tun :wink:

Wenn man ein bißchen websucht, findet man zwar https://github.com/beehive-lab/Maxine-VM , aber irgendwas kleines, kompaktes, pragmatisches, just for the sake of it, wäre schon ganz interessant. Sowas wie https://github.com/zxh0/jvm.go oder https://github.com/lihaoyi/Metascala könnte “inspirierend” sein, aber wenn schon Java, dann doch bitte Java :smiley:

BTW, ein kleiner Pointer: