[Java] Compiling Switches : tableswitch 와 lookupswitch

지난 포스팅에서는 if와 switch의 실제 동작 차이를 비교해보며 switch가 LOOKUPSWITCH 로 변경되는것을 확인해보았습니다.

if, switch 누가 더 빠를까?

 

하지만 실제로는 자바 컴파일러가 상황에 따라 TABLESWITCH, LOOKUPSWITCH 둘 중 효율적이라 생각하는 방식으로 switch의 컴파일을 사용합니다.

TABLESWITCH

tableswitch는 switch의 조건 값의 범위를 인덱싱하여 jump table을 구성하고, 해당하는 인덱스의 실행지점으로 바로 점프합니다.

[예제 자바코드]

int chooseNear(int i) {
    switch (i) {
        case 0:  return  0;
        case 1:  return  1;
        case 2:  return  2;
        default: return -1;
    }
}

[컴파일 코드]

case의 0 ~ 2 범위 내에 있는 값들( 0, 1, 2)을 인덱싱하고 해당하는 로직의 실행지점을 명시하여 jump table을 생성합니다.
범위를 벗어난 값은 default로 점프하여 로직이 실행되도록 합니다.

Method int chooseNear(int)
0   iload_1             // Push local variable 1 (argument i)
1   tableswitch 0 to 2: // Valid indices are 0 through 2
      0: 28             // If i is 0, continue at 28
      1: 30             // If i is 1, continue at 30
      2: 32             // If i is 2, continue at 32
      default:34        // Otherwise, continue at 34
28  iconst_0            // i was 0; push int constant 0...
29  ireturn             // ...and return it
30  iconst_1            // i was 1; push int constant 1...
31  ireturn             // ...and return it
32  iconst_2            // i was 2; push int constant 2...
33  ireturn             // ...and return it
34  iconst_m1           // otherwise push int constant -1...
35  ireturn             // ...and return it

    tableswitch 0 to 2: // Valid indices are 0 through 2
      0: 28             // If i is 0, continue at 28
      1: 30             // If i is 1, continue at 30
      2: 32             // If i is 2, continue at 32
      default:34        // Otherwise, continue at 34

jump table만 구성되어있으면 별도의 비교연산 없이 바로 실행지점을 이동할 수 있기때문에 굉장히 효율적이여보입니다.
하지만 case가 spare한 경우에는 공간낭비의 문제가 발생합니다.

아래와 예제에서 tableswitch 방식은 전체 범위를 인덱싱하기 때문에
실제로는 3개의 케이스 밖에 없지만(0,10, 100) 0~100까지의 모든 정수에 대해 인덱싱하게 되어 과도한 jump table 생성비용과 공간비용이 발생합니다.

int chooseNear(int i) {
    switch (i) {
        case 0:  return  0;
        case 10:  return  1;
        case 100:  return  2;
        default: return -1;
    }
}

    tableswitch 0 to 100: // Valid indices are 0 through 100
      0: 28             
      1: 30             
      2: 32             
      ...
      10:50
      ...
      100:150
      default:152        

LOOKUPSWITCH

case들이 sapre하여 tableswitch가 비효율적인 경우, 컴파일러는 lookupswitch 방식을 선택합니다.
lookupswich는 case 값만으로 테이블을 구성합니다.

[예제 자바코드]

int chooseFar(int i) {
    switch (i) {
        case -100: return -1;
        case 0:    return  0;
        case 100:  return  1;
        default:   return -1;
    }
}

[컴파일 코드]

1   lookupswitch 3:
         -100: 36
            0: 38
          100: 40
      default: 42

인덱스를 이용해 바로 찾아가는게 아니기 때문에 lookupswitch는 비교대상변수와 table에 구성된 key와의 비교연산이 필요합니다.

시간적 비용을 보완하고자 key들을 정렬하여 구성해놓고 바이너리 서치 알고리즘과 같은 것을 적용하여 선형 탐색 시간(O(n))보다는 빠른 시간을 보장합니다.

[참고]

docs oracle se11