JVM의 LookupSwitch와 TableSwitch의 차이점은 무엇입니까?

JVM의 LookupSwitch와 TableSwitch의 차이점은 무엇입니까?

---

Java 바이트 코드에서 LookUpSwitch 및 TableSwitch를 이해하는 데 약간의 어려움이 있습니다.

내가 잘 이해하면 LookUpSwitch와 TableSwitch가 모두 switchJava 소스 의 설명에 해당 합니까? 하나의 JAVA 문이 2 개의 다른 바이트 코드를 생성하는 이유는 무엇입니까?

각각의 Jasmin 문서 :

• LookupSwitch
• 테이블 스위치

---

차이점은 lookupswitch는 키와 레이블이 있는 테이블을 사용 하지만 테이블 스위치는 레이블 만있는 테이블을 사용 한다는 것 입니다.

tableswitch를 수행 할 때 스택 상단의 int 값은 테이블에 대한 인덱스로 직접 사용되어 점프 대상을 잡고 즉시 점프를 수행합니다. 전체 조회 + 점프 프로세스는 O (1) 작업 이며 이는 매우 빠르다는 것을 의미합니다.

lookupswitch를 수행 할 때 스택 상단의 int 값은 일치 항목이 발견 될 때까지 테이블의 키와 비교 된 다음이 키 옆의 점프 대상이 점프를 수행하는 데 사용됩니다. 모든 X <Y에 대해 keyX <keyY가되도록 lookupswitch 테이블을 항상 정렬해야 하므로 전체 조회 + 점프 프로세스는 O (log n) 작업입니다.이진 검색 알고리즘을 사용하여 키를 검색하므로 일치 항목을 찾거나 일치하는 키가 없는지 확인하기 위해 가능한 모든 키와 int 값을 비교할 필요는 없습니다. O (log n)은 O (1)보다 다소 느리지 만 잘 알려진 많은 알고리즘이 O (log n)이고 일반적으로 빠른 것으로 간주되기 때문에 여전히 괜찮습니다. O (n) 또는 O (n * log n)조차도 여전히 꽤 좋은 알고리즘으로 간주됩니다 (느림 / 나쁜 알고리즘에는 O (n ^ 2), O (n ^ 3) 또는 더 나쁜 알고리즘이 있음).

사용할 명령 은 switch 문이 얼마나 간결한 지에 따라 컴파일러가 결정 합니다.

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

위의 스위치는 완벽하게 콤팩트하며 숫자 "구멍"이 없습니다. 컴파일러는 다음과 같은 테이블 스위치를 만듭니다.

 tableswitch 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

Jasmin 페이지의 의사 코드는이를 잘 설명합니다.

int val = pop();                // pop an int from the stack
if (val < low || val > high) {  // if its less than <low> or greater than <high>,
    pc += default;              // branch to default 
} else {                        // otherwise
    pc += table[val - low];     // branch to entry in table
}

이 코드는 그러한 테이블 스위치가 어떻게 작동하는지에 대해 매우 명확합니다. val이고 inputValue, low1 (스위치의 경우 낮은 값)이 될 것이고, high도 3 (스위치의 경우 최고 값)이 될 것이다.

약간의 구멍이 있어도 스위치는 컴팩트 할 수 있습니다.

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

위의 스위치는 "거의 콤팩트"하며 구멍이 하나뿐입니다. 컴파일러는 다음 명령어를 생성 할 수 있습니다.

 tableswitch 1 6
    OneLabel
    FakeTwoLabel
    ThreeLabel
    FourLabel
    FiveLabel
  default: DefaultLabel

  ; <...code left out...>

  FakeTwoLabel:
  DefaultLabel:
    ; default code

당신이 볼 수 있듯이, 컴파일러는 추가하는 2 가짜 케이스 , FakeTwoLabel. 2는 스위치의 실제 값이 아니기 때문에 FakeTwoLabel은 실제로 기본 케이스가있는 위치에서 코드 흐름을 변경하는 레이블입니다. 값 2는 실제로 기본 케이스를 실행해야하기 때문입니다.

So a switch doesn't have to be perfectly compact for the compiler to create a tableswitch, yet it should at least be pretty close to compactness. Now consider the following switch:

switch (inputValue) {
  case 1:    // ...
  case 10:   // ...
  case 100:  // ...
  case 1000: // ...
  default:   // ...
}

This switch is nowhere near compactness, it has more than hundred times more holes than values. One would call this a spare switch. The compiler would have to generate almost thousand fake cases to express this switch as a tableswitch. The result would be a huge table, blowing up the size of the class file dramatically. This is not practical. Instead it will generate a lookupswitch:

lookupswitch
    1       : Label1
    10      : Label10
    100     : Label100
    1000    : Label1000
    default : DefaultLabel

This table has only 5 entries, instead of over thousand ones. The table has 4 real values, O(log 4) is 2 (log is here log to the base of 2 BTW, not to the base of 10, since computer operate on binary numbers). That means it takes the VM at most two comparisons to find the label for the inputValue or to come to the conclusion, that the value is not in the table and thus the default value must be executed. Even if the table had 100 entries, it would take the VM at most 7 comparisons to find the correct label or decide to jump to the default label (and 7 comparisons is a lot less than 100 comparisons, don't you think?).

So it's nonsense that these two instructions are interchangeable or that the reason for two instructions has historical reasons. There are two instructions for two different kind of situations, one for switches with compact values (for maximum speed) and one for switches with spare values (not maximum speed, yet still good speed and very compact table representation regardless all the numeric holes).

---

How javac 1.8.0_45 decides what to compile switch to?

To decide when to use which, you could use the javac choice algorithm as basis.

We know that the source of javac is in the langtools repo.

Then we grep:

hg grep -i tableswitch

and the first result is langtools/src/share/classes/com/sun/tools/javac/jvm/Gen.java:

// Determine whether to issue a tableswitch or a lookupswitch
// instruction.
long table_space_cost = 4 + ((long) hi - lo + 1); // words
long table_time_cost = 3; // comparisons
long lookup_space_cost = 3 + 2 * (long) nlabels;
long lookup_time_cost = nlabels;
int opcode =
    nlabels > 0 &&
    table_space_cost + 3 * table_time_cost <=
    lookup_space_cost + 3 * lookup_time_cost
    ?
    tableswitch : lookupswitch;

Where:

• hi: maximum case value
• lo: minimum case value

So we conclude that it takes into consideration both the time and space complexity, with a weight of 3 for the time complexity.

TODO I don't understand why lookup_time_cost = nlabels and not log(nlabels), since a tableswitch could be done in O(log(n)) with binary search.

Bonus fact: C++ compilers also make an analogous choice between an O(1) jump table and O(long(n)) binary search: Advantage of switch over if-else statement

---

Java Virtual Machine Specification describe the difference. "The tableswitch instruction is used when the cases of the switch can be efficiently represented as indices into a table of target offsets." The specification describes the more details.

---

I suspect it is mostly historical, due to some specific binding of Java bytecode to underline machine code (e.g. Sun's own CPU).

The tableswitch is essentially a computed jump, where destination is taken from a lookup table. On a contrary lookupswitch requires comparison of each value, basically an iteration trough table elements until matching value is found.

Obviously those opcodes are interchangeable, but based on values, one or the other could be faster or more compact (e.g. compare set of keys with large gaps in between and a sequential set of keys).

참고URL : https://stackoverflow.com/questions/10287700/difference-between-jvms-lookupswitch-and-tableswitch