[JAVA] Switch가 If 보다 빠른 이유 (lookupswitch와 tableswitch의 분기 조건)
일반적으로 Java에서
switch문은 if문 보다 빠르다
그 이유에 대해 차근차근 알아보자
1. If와 Switch의 차이
우선 Switch 와 If문의 컴파일시 bytecode차이를 분석해보자.
우선 If 와 Switch는 모두 문맥상 같은 역할을 하고있도록 구성하였다.
먼저 If를 살펴본다.
// IfExample.java
public class IfExample {
public int test(int i) {
if (i == 1) return 6;
if (i == 2) return 7;
return 11;
}
}
// IfExample.class
Compiled from "IfExample.java"
public class IfExample {
public IfExample();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public int test(int);
Code:
0: iload_1
1: iconst_1
2: if_icmpne 8 // if (i != 1) goto 8
5: bipush 6 // return 6
7: ireturn
8: iload_1
9: iconst_2
10: if_icmpne 16 // if (i != 2) goto 16
13: bipush 7 // return 7
15: ireturn
16: bipush 11 // 그외 경우 return 11
18: ireturn
}예상한대로 If는 모든 경우의 수를 하나씩 확인한 후 반환한다.
다음은 Switch를 살펴본다.
// SwitchExample.java
public class SwitchExample {
public int test(int i) {
switch (i) {
case 1:
return 6;
case 2:
return 7;
default:
return 11;
}
}
}// SwitchExample.class
Compiled from "SwitchExample.java"
public class SwitchExample {
public SwitchExample();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public int test(int);
Code:
0: iload_1
1: lookupswitch { // 2
1: 28 // if (i==1) goto 28
2: 31 // if (i==2) goto 31
default: 34 // 그외의 경우 goto 34
}
28: bipush 6 // return 6
30: ireturn
31: bipush 7 // return 7
33: ireturn
34: bipush 11 // return 11
36: ireturn
}무엇인가 If문과 다른 부분이 보이는가?
If는 매 분기별로 JVM 명령어를 한줄씩 읽어 나가고
Switch는 모든 분기를 JVM 명령어 하나로 처리한다.
그러므로 해당 Jump Table을 만드는 초기 비용을 제외하면
Switch문이 별도의 분기 없이 바로 탐색이 가능하다
그렇지만 실제로 bytecode로 변환된 코드에는 두가지 Switch가 존재한다.
아래에서 해당 부분을 확인해보자.
2. Switch의 두가지 종류 LookupSwitch, TableSwitch
그러나 Switch를 bytecode로 변환해보면 경우에 따라 다르게 변환이된다.
아까와 같은 코드에 case 분기를 하나 더 추가시키고 컴파일해본다.
// SwitchExample_2.java
public class SwitchExample_2 {
public int test(int i) {
switch (i) {
case 1:
return 6;
case 2:
return 7;
case 3:
return 8;
default:
return 11;
}
}
}// SwitchExample_2.class
Compiled from "SwitchExample_2.java"
public class SwitchExample_2 {
public SwitchExample_2();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public int test(int);
Code:
0: iload_1
1: tableswitch { // 1 to 3
1: 28 // if(i==1) goto 28
2: 31 // if(i==2) goto 31
3: 34 // if(i==3) goto 34
default: 37 // 그 외에 goto 37
}
28: bipush 6 // return 6
30: ireturn
31: bipush 7 // return 7
33: ireturn
34: bipush 8 // return 8
36: ireturn
37: bipush 11 // return 11
39: ireturn
}차이점을 느낄 수 있는가?
기존에는 분기가 lookupswitch로 이루어졌지만
하나가 더 추가되었을 경우 tableswitch라는 명령어로 변경되었다.
Oracle Java 22 문서에는 이와 같이 적혀있다.
The tableswitch instruction is used when the cases of the switch can be efficiently represented as indices into a table of target offsets.
tableswitch는 offset 테이블로 효율적으로 표현될 수 있을때 사용되어집니다.
이말은
특정 경우에는 lookupswitch를
특정 경우에는 tableswitch를
사용한다.
그렇다면 실제로 어떤 기준으로 나뉘어지는 것인가?
해당 부분은 OpenJDK 소스코드 에서 확인해볼 수 있다.
// jdk/src/jdk.compiler/share/classes/com/sun/tools/javac/jvm/Gen.java
private void handleSwitch(JCTree swtch, JCExpression selector, List<JCCase> cases,boolean patternSwitch) {
...
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;
...
}위의 표를 정리해보자면 아래와 같다.
| Opcode | Space Cost | Time Cost |
| tableswitch | 4 + ( hi - lo + 1 ) | 3 |
| lookupswitch | 3 + 2 * nlabels | nlabels |
lo = key들의 최소 값
hi = key들의 최대 값
nlabels = 각 스위치 수
그리고 Switch의 $$Space Cost+Time Cost*3$$중 작은 값으로 선택되어진다.
간단하게 요약하자면
tableswitch는 해당 값이 최소와 최대값 사이에 있는가를 따지고
lookupswitch는 해당 값이 일치 하는지를 모두 확인해본다.
아래와 같은 예시로 확인해보자.
// SwitchExample_3.java
public class SwitchExample_3 {
public int test(int i) {
switch (i) {
case 1:
return 6;
case 2:
return 7;
case 4:
return 5;
case 6:
return 6;
default:
return 11;
}
}
}$$ \begin{align} & lo = 1 \\& hi = 6 \\& nlabels = 4 \\& tableswitch = ( 4+(6-1+1) ) +3 * 3 = 19 \\& lookupswitch = ( 3+2*4 ) + 3 * 4 = 23 \end{align} $$
tableswitch는 lookupswitch보다 작으니 tableswitch로 선택되어진다.
또한, 해당 switch의 필요하지않은 key에는 default값이 들어가게된다.
// SwitchExample_3.class
Compiled from "SwitchExample_3.java"
public class SwitchExample_3 {
public SwitchExample_3();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public int test(int);
Code:
0: iload_1
1: tableswitch { // 1 to 6
1: 40 // if (i==1) goto 40
2: 43 // if (i==2) goto 43
3: 52 // 그외 goto 52
4: 46 // if (i==4) goto 46
5: 52 // 그외 goto 52
6: 49 // if (i==6) goto 49
default: 52 // 그외 goto 52
}
40: bipush 6 // return 6
42: ireturn
43: bipush 7 // return 7
45: ireturn
46: bipush 8 // return 8
48: ireturn
49: bipush 9 // return 9
51: ireturn
52: bipush 11 // return 11
54: ireturn
}놀랍게도 3, 5인 경우에는 default값이 들어가 해결되었다.
실질적으로 시간 효율성을 위해 공간 효율성을 포기한거 같다.
그렇다면 정수형이 아닌 문자열같은 경우에는 어떻게 작동하는가?
아래에서 해당 부분을 확인해보자.
3. 문자열에 대한 Switch 작동 방식
문자열에 대한 처리를 보면 이해가 된다.
// SwitchExample_String.java
...
switch (i) {
case "ga":
return 6;
case "na":
return 7;
case "da":
return 8;
default:
return 11;
}
...원본 문자열들은 HashCode로 변환된 후, 해당 값들을 기준으로 switch가 진행된다.
// SwitchExample_String.java
...
byte tmp = -1;
switch (tmp.hashCode()) {
case 3290:
if (tmp.equals("ga")){
tmp = 0;
} else if (tmp.equals("da")){
tmp = 2; // 만약 hash가 충돌 날경우
}
break;
case 3507:
if (tmp.eqauls("na")){
tmp = 1;
}
break;
}
switch(tmp){
case 0:
return 6;
case 1:
return 7;
case 2:
return 8;
default:
return 11;
}
...
소스코드 : https://github.com/AnOldStory/blogcode/tree/main/java_if_switch
참고 자료 :
Oracle JVM docs : https://docs.oracle.com/javase/specs/jvms/se22/html/jvms-3.html#jvms-3.10
openjdk 22 : https://github.com/openjdk/jdk/blob/jdk-22%2B36/src/jdk.compiler/share/classes/com/sun/tools/javac/jvm/Gen.java#L1331C45-L1331C56