if vs switch, 성능 / 메모리 사용량 비교
사실 실제 코드에서 if와 switch가 중에 뭐가 더 빠른지를 알기는 매우 어렵다. if와 switch를 사용했을 때, 아래 사항을 고려해야 하기 때문이다.
- if나 switch를 사용했을 때 CPU 명령어가 각각 어떻게 구성되는지
- 예를 들어 if나 switch가 5군데로 분기한다면 어디로 분기하는 경우가 많은지
- CPU마다 분기 예측 방법 / 성능이 다른데 if나 switch를 사용했을 때 분기 예측 성공 / 실패가 어떻게 되는지
void test_if(int param)
{
if(param == 0)
func1();
else if(param == 1)
func2();
else if(param == 2)
func3();
else if(param == 3)
func4();
else if(param == 4)
func5();
}
void test_switch(int param) // 위 if 예제에 대응하는 switch의 CPU 명령어 동작을 표현
{
(jump table address) + (param * 4) 에 있는 주소에 있는 값으로 jump
}
ex. jump table
CPU 명령어 주소 CPU 명령어
10000000: 00000028 (28번지에 func1 호출 CPU 명령어가 있음)
10000004: 0000002c (2c번지에 func2 호출 CPU 명령어가 있음)
10000008: 00000030 (30번지에 func3 호출 CPU 명령어가 있음)
1000000c: 00000020 (20번지에 func4 호출 CPU 명령어가 있음)
10000010: 00000024 (24번지에 func5 호출 CPU 명령어가 있음)
먼저 if와 switch의 동작이 어떻게 다른지 보자. if의 CPU 동작은 c언어 표현과 같다. 하지만 switch는 jump table을 만들어서 해당 table의 주소로 jump 하는 방법을 쓴다.
위 예제에서 param이 1인 경우를 예로 들면, 0x10000000(jump table address) + 1(param) * 4 = 0x10000004의 값인 0x2c로 jump 한다. 0x2c에는 func2 함수를 호출하는 명령어가 있어서 func2 함수를 호출한다.
if는 비교를 할 때마다 수행하는 CPU 명령어 추가되고 switch는 jump table의 주소를 계산해서 해당 table의 값으로 jump 하므로 수행하는 명령어 수가 같다. 하지만 jump 할 주소를 계산하는 등의 동작을 하기 위해서 여러 개의 명령어를 수행해서 if문을 한 번만 수행할 때는 if문이 더 빠르고 if문을 여러 번 수행하는 경우에는 switch가 더 빠르다.
글 아래 부분의 성능 계산한 결과를 보면 대략 5개까지 비교하는 경우라면 if가 빠르고 대략 6개 이상 비교하는 경우에는 switch가 빠를 것 같다. 하지만 위에서 언급했듯이 어디로 분기하는 경우가 많은지, 분기 예측 성공 / 실패가 어떻게 되는지 등에 따라 속도는 달라지기 때문에, 성능 때문에 if와 switch 중에 선택을 해야하는 경우라면 실제 상황에서 성능 측적을 해서 결정해야 한다.
여기까지 간략히 if와 switch의 성능에 대해서 살펴봤고 아래 내용은 많이 복잡해서 자세히 알고 싶은 경우에만 보면 될 것 같다.
👇
switch는 if와 다르게 jump table을 사용한다. if와 switch 중에 뭐가 더 빠를까? 성능이 매우 중요한 경우라면, 어느 경우에 if를 쓰고 어느 경우에 switch를 써야 할까? if와 switch의 성능과 메모리 사용량을 비교해보자.
* 성능 / 메모리 사용량 비교 방법 : C 코드를 컴파일하여 생성된 RISC-V 어셈블리(assembly) 코드로 비교
포스팅 ▶ 테스트 조건 및 성능 / 메모리 사용량 비교 방법
포스팅 ▶ RISC-V 어셈블리 명령어 설명
if vs switch, 4 군데로 분기하는 경우
<C 코드>
void test_if(int param)
{
if(param == 0)
func1();
else if(param == 1)
func2();
else if(param == 2)
func3();
else if(param == 3)
func4();
}
void test_switch(int param)
{
switch (param)
{
case 0:
func1();
break;
case 1:
func2();
break;
case 2:
func3();
break;
case 3:
func4();
break;
}
}
<어셈블리 코드>
00000000 <test_if>:
0: 02050063 beqz a0,20 <test_if+0x20>
4: 00100793 li a5,1
8: 02f50063 beq a0,a5,28 <test_if+0x28>
c: 00200793 li a5,2
10: 00f50a63 beq a0,a5,24 <test_if+0x24>
14: 00300793 li a5,3
18: 00f50a63 beq a0,a5,2c <test_if+0x2c>
1c: 00008067 ret
20: 7e11f06f j 20000 <func1>
24: 7e51f06f j 20008 <func3>
28: 7dd1f06f j 20004 <func2>
2c: 7e11f06f j 2000c <func4>
00000000 <test_switch>:
0: 00200793 li a5,2
4: 02f50663 beq a0,a5,30 <test_switch+0x30>
8: 00a7ca63 blt a5,a0,1c <test_switch+0x1c>
c: 02050063 beqz a0,2c <test_switch+0x2c>
10: 00100793 li a5,1
14: 02f51063 bne a0,a5,34 <test_switch+0x34>
18: 7ed1f06f j 20004 <func2>
1c: 00300793 li a5,3
20: 00f51463 bne a0,a5,28 <test_switch+0x28>
24: 7e91f06f j 2000c <func4>
28: 00008067 ret
2c: 7d51f06f j 20000 <func1>
30: 7d91f06f j 20008 <func3>
34: 00008067 ret4군데로 분기하는 경우에는 switch도 jump table을 사용하지 않았다. 다만 if와 switch의 어셈블리 코드가 다른데, 이 부분은 어느 컴파일러를 썼는지, 컴파일러 옵션은 어떻게 되는지 등 최적화에 따라 달라질 수 있는 부분이라서 따로 설명은 하지 않겠다. switch가 jump table을 사용한 경우를 if와 아래에서 비교하겠다.
if vs switch, 5 군데로 분기하는 경우
<C 코드>
void test_if(int param)
{
if(param == 0)
func1();
else if(param == 1)
func2();
else if(param == 2)
func3();
else if(param == 3)
func4();
else if(param == 4)
func5();
}
void test_switch(int param)
{
switch (param)
{
case 0:
func1();
break;
case 1:
func2();
break;
case 2:
func3();
break;
case 3:
func4();
break;
case 4:
func5();
break;
}
}
<어셈블리 코드>
- if
00000000 <test_if>: 0: 02050463 beqz a0,28 <test_if+0x28> # if(param==0),28번지로 분기 4: 00100793 li a5,1 8: 02f50463 beq a0,a5,30 <test_if+0x30> # if(param==1),30번지로 분기 c: 00200793 li a5,2 10: 00f50e63 beq a0,a5,2c <test_if+0x2c> # if(param==2),2c번지로 분기 14: 00300793 li a5,3 18: 00f50e63 beq a0,a5,34 <test_if+0x34> # if(param==3),34번지로 분기 1c: 00400793 li a5,4 20: 00f50c63 beq a0,a5,38 <test_if+0x38> # if(param==4),38번지로 분기 24: 00008067 ret # param이 0~4가 아닌 경우에 함수 종료 28: 7d91f06f j 20000 <func1> # func1 함수 호출 2c: 7dd1f06f j 20008 <func3> 30: 7d51f06f j 20004 <func2> 34: 7d91f06f j 2000c <func4> 38: 7d91f06f j 20010 <func5>
- switch
00000000 <test_switch>: 0: 00400793 li a5,4 4: 02a7e863 bltu a5,a0,34 <test_switch+0x34> # if(param>4),34번지로 분기 # switch의 jump table이 1000_0000번지에 위치한다. # jump table의 값인 [1000_0000번지+(param*4)] 위치의 값으로 분기한다. 8: 100007b7 lui a5,0x10000 # a5 = 1000_0000 c: 00078793 mv a5,a5 # a5 = a5 -> 변경 내역 없음(컴파일러 최적화 부족) 10: 00251513 slli a0,a0,0x2 # a0 = param * 4 14: 00f50533 add a0,a0,a5 # a0 = 1000_0000 + (param * 4) 18: 00052783 lw a5,0(a0) # a5 = a0가 가리키는 값 1c: 00078067 jr a5 # 10000000 <main+0xffdffd8> // a5 값으로 분기 20: 7ed1f06f j 2000c <func4> # func4 함수 호출 24: 7ed1f06f j 20010 <func5> 28: 7d91f06f j 20000 <func1> 2c: 7d91f06f j 20004 <func2> 30: 7d91f06f j 20008 <func3> 34: 00008067 ret # 함수 종료 # switch의 jump table 10000000 <.test_data>: 10000000: 00000028 # jump table의 entry이며 28번지의 명령어 -> j 20000 <func1> 10000004: 0000002c -> j 20004 <func2> 10000008: 00000030 -> j 20008 <func3> 1000000c: 00000020 -> j 2000c <func4> 10000010: 00000024 -> j 20010 <func5>
위의 어셈블리 코드를 보면 if는 한 번 비교할 때마다 conditional branch를 사용하기 때문에 if 문 비교가 늘어날 때마다 conditional branch가 추가로 사용된다. 반면에 switch는 jump table을 사용하기 때문에 indirect jump 한 번으로 분기를 한다.
[switch 8번지~1c번지 부분] 하지만 param에 따라 jump table의 값으로 분기하기 위한 명령어가 여러 개 필요하다.
[switch 0번지, 4번지 부분] 또한 jump table에 존재하지 경우(param이 0~4가 아닌 경우)를 먼저 처리해야 한다. param이 0~4가 아니라면 먼저 처리해서 효과적이겠지만 param이 0~4인 경우에는 그만큼 느려진다.
여기서는 분기 예측 성공 시에는 penalty가 없고 실패 시에는 penalty가 3 cycle이라고 가정하고 계산하겠다. 제어 해저드와 분기 예측이 궁금하면 아래 포스팅을 참고하자.
포스팅 ▶ real CPU로 보는 분기 예측(branch prediction) - BHT, BTB, RAS
성능
차례대로 func1, func2, func3, func4, func5, 아무 함수도 타지 않는 경우가 반복되는 패턴
먼저 아래에서 나오는 표에 대해서 설명한다.
- 8: 02f50463 beq a0,a5,30
[program flow(PC)]는 프로그램 수행 번지를 나타낸다. 위의 어셈블리 코드 예제의 빨간 글자인 8번지가 프로그램 수행 번지이다. - [program flow(PC)]에서 빨간 글자로 표시한 부분은 분기 예측이 실패한 경우이다. 분기 예측이 실패한 경우에는 위에서 언급한대로 3 clock이 더 소모된다고 가정했다.
- 30: 7d91f06f j 20008 <func3>
가령 test_if 함수나 test_switch 함수의 마지막에 위와 같이 j 명령어로 func3 함수를 호출하면, test_switch 함수에서 함수 종료 명령어인 ret를 따로 호출하지 않고 func3 함수가 종료되면서 test_switch 함수도 동시에 종료된다. - 소요 clock을 계산할 때는 모든 명령어가 1cycle이라고 가정했다.
- [program flow(PC)]에는 해당 번지를 기재했지만, test_if / test_switch 함수의 마지막에 수행되는 ret / j 명령어는 공통된 부분이기 때문에 소요 clock 계산에서 제외했다.
<if>
| 차례 | program flow(PC) | 소요 clock | 합계 |
|---|---|---|---|
| 1 | 0 28(func1) | 4 | 64 |
| 2 | 0 4 8 30(func2) | 9 | |
| 3 | 0 4 8 c 10 2c(func3) | 11 | |
| 4 | 0 4 8 c 10 14 18 34(func4) | 13 | |
| 5 | 0 4 8 c 10 14 18 1c 20 38(func5) | 15 | |
| 6 | 0 4 8 c 10 14 18 1c 20 24(ret) | 12 |
if문에서 수행하는 conditional branch는 분기하거나 분기하지 않는 2가지 경우만 있다. 0번지의 conditional branch(beqz)를 보면 28번지로 분기하거나 분기를 하지 않고 4번지로 이동한다. 여기서의 분기 예측기는 해당 conditional branch의 바로 직전의 분기 여부를 기억하고 있어서 다음에 해당 conditional branch를 수행하면 그대로 예측한다고 가정한다. 가령, 0번지 conditional branch의 직전 분기 여부가 분기하지 않고 4번지로 이동한 경우라면 다음에 0번지 conditional branch를 다시 수행하면 분기하지 않고 4번지로 이동하는 것으로 분기 예측한다.
- 차례 1
차례 1~6이 계속 반복되는 패턴이므로, 차례 6에서 0번지 분기문에서 4번지로 이동했는데, 차례 1에서 0번지에서 4번지가 아닌 28번지로 이동했으므로 분기 예측이 실패했다.
- 차례 2
차례 1에서 0번지 분기문에서 28번지로 이동했는데, 차례 2에서 0번지에서 28번지가 아닌 4번지로 이동했으므로 분기 예측이 실패했다. 그리고 차례 6에서 8번지 분기문에서 c번지로 이동했는데, 차례 2에서 8번지에서 c번지가 아닌 30번지로 이동했으므로 분기 예측이 실패했다.
- 차례 3
차례 2에서 0번지 분기문에서 4번지로 이동했는데, 차례 3에서 0번지에서 4번지로 이동했으므로 분기 예측이 성공했다. 그리고 차례 2에서 8번지 분기문에서 30번지로 이동했는데, 차례 3에서 8번지에서 c번지로 이동했으므로 분기 예측이 실패했다. 그리고 차례 6에서 10번지 분기문에서 14번지로 이동했는데, 차례 3에서 10번지에서 14번지가 아닌 2c번지로 이동했기 때문에 분기 예측이 실패했다.
- 나머지 차례의 경우도 마찬가지 방식으로 분기 예측이 동작한다.
<switch>
| 차례 | program flow(PC) | 소요 clock | 합계 |
|---|---|---|---|
| 1 | 0 4 8 10 14 18 1c 28(func1) | 13 | 59 |
| 2 | 0 4 8 10 14 18 1c 2c(func2) | 10 | |
| 3 | 0 4 8 10 14 18 1c 30(func3) | 10 | |
| 4 | 0 4 8 10 14 18 1c 20(func4) | 10 | |
| 5 | 0 4 8 10 14 18 1c 24(func5) | 10 | |
| 6 | 0 4 34(ret) | 6 |
switch의 c번지는 주석에 기재한 것처럼 컴파일러 최적화가 부족하여 아무 변화도 없는 명령어를 수행했기 때문에, 위의 [program flow(PC)]에서 빼는 게 공정하다고 생각해서 제거했고 [소요 clock]에도 계산하지 않았다.
switch의 jump table에서 사용하는 분기 명령어인 indirect jump는 [register의 값 + offset]의 위치로 분기한다. conditional branch는 분기하거나 분기하지 않는 2가지 경우만 있는데, indirect jump는 분기하는 주소가 5가지가 될 수도 있고, 100가지가 될 수도 있다. 여기서의 분기 예측기는 해당 indirect jump의 바로 직전의 분기 주소를 기억하고 있어서 다음에 해당 indirect jump를 수행하면 해당 주소로 분기하는 것으로 예측한다고 가정한다. 가령, 1c번지 indirect jump의 직전 분기 주소가 20000번지라면 다음에 1c번지를 다시 수행하면 20000번지로 분기하는 것으로 분기 예측한다.
- 차례 1
차례 6에서 4번지 conditional branch에서 34번지로 이동했는데, 차례 1에서 4번지에서 34번지가 아닌 8번지로 이동했으므로 분기 예측이 실패했다. 그리고 차례 5에서 1c번지 indirect jump에서 24번지로 이동했는데, 차례 1에서 1c번지에서 24번지가 아닌 28번지로 이동했으므로 분기 예측이 실패했다.
- 차례 2
차례 1에서 4번지 conditional branch에서 8번지로 이동했는데, 차례 2에서 4번지에서 8번지로 이동했으므로 분기 예측이 성공했다. 그리고 차례 1에서 1c번지 indirect jump에서 28번지로 이동했는데, 차례 2에서 1c번지에서 28번지가 아닌 2c번지로 이동했으므로 분기 예측이 실패했다.
- 나머지 차례의 경우도 마찬가지로 분기 예측이 동작한다.
| 차례 | if 소요 clock |
switch 소요 clock |
|---|---|---|
| 1(func1) | 4 | 13 |
| 2(func2) | 9 | 10 |
| 3(func3) | 11 | 10 |
| 4(func4) | 13 | 10 |
| 5(func5) | 15 | 10 |
| 6(ret) | 12 | 6 |
| 합계 | 64 | 59 |
위에서 언급한 이유로 func1, func2 타는 경우는 if문이 빨랐지만 나머지는 switch가 빨랐다. 그리고 합계를 보면 switch가 조금 더 빨랐다.
아래의 다른 패턴은 결과가 어떤지 보자.
차례대로 func1 5회, func2 5회, func3 5회, func4 5회, func5 5회, 아무 함수도 타지 않는 경우 5회가 반복되는 패턴
<if>
| 차례 | program flow(PC) | 소요 clock | 합계 | 총합계 |
|---|---|---|---|---|
| 1 2 3 4 5 | 0 28(func1) 0 28 0 28 0 28 0 28 | 4 1 1 1 1 | 8 | 200 |
| 6 7 8 9 10 | 0 4 8 30(func2) 0 4 8 30 0 4 8 30 0 4 8 30 0 4 8 30 | 9 3 3 3 3 | 21 | |
| 11 12 13 14 15 | 0 4 8 c 10 2c(func3) 0 4 8 c 10 2c 0 4 8 c 10 2c 0 4 8 c 10 2c 0 4 8 c 10 2c | 11 5 5 5 5 | 31 | |
| 16 17 18 19 20 | 0 4 8 c 10 14 18 34(func4) 0 4 8 c 10 14 18 34 0 4 8 c 10 14 18 34 0 4 8 c 10 14 18 34 0 4 8 c 10 14 18 34 | 13 7 7 7 7 | 41 | |
| 21 22 23 24 25 | 0 4 8 c 10 14 18 1c 20 38(func5) 0 4 8 c 10 14 18 1c 20 38 0 4 8 c 10 14 18 1c 20 38 0 4 8 c 10 14 18 1c 20 38 0 4 8 c 10 14 18 1c 20 38 | 15 9 9 9 9 | 51 | |
| 26 27 28 29 30 | 0 4 8 c 10 14 18 1c 20 24(ret) 0 4 8 c 10 14 18 1c 20 24 0 4 8 c 10 14 18 1c 20 24 0 4 8 c 10 14 18 1c 20 24 0 4 8 c 10 14 18 1c 20 24 | 12 9 9 9 9 | 48 |
<switch>
| 차례 | program flow(PC) | 소요 clock | 합계 | 총합계 |
|---|---|---|---|---|
1 2 3 4 5 | 0 4 8 10 14 18 1c 28(func1) 0 4 8 10 14 18 1c 28 0 4 8 10 14 18 1c 28 0 4 8 10 14 18 1c 28 0 4 8 10 14 18 1c 28 | 13 7 7 7 7 | 41 | 206 |
6 7 8 9 10 | 0 4 8 10 14 18 1c 2c(func2) 0 4 8 10 14 18 1c 2c 0 4 8 10 14 18 1c 2c 0 4 8 10 14 18 1c 2c 0 4 8 10 14 18 1c 2c | 10 7 7 7 7 | 38 | |
11 12 13 14 15 | 0 4 8 10 14 18 1c 30(func3) 0 4 8 10 14 18 1c 30 0 4 8 10 14 18 1c 30 0 4 8 10 14 18 1c 30 0 4 8 10 14 18 1c 30 | 10 7 7 7 7 | 38 | |
16 17 18 19 20 | 0 4 8 10 14 18 1c 20(func4) 0 4 8 10 14 18 1c 20 0 4 8 10 14 18 1c 20 0 4 8 10 14 18 1c 20 0 4 8 10 14 18 1c 20 | 10 7 7 7 7 | 38 | |
21 22 23 24 25 | 0 4 8 10 14 18 1c 24(func5) 0 4 8 10 14 18 1c 24 0 4 8 10 14 18 1c 24 0 4 8 10 14 18 1c 24 0 4 8 10 14 18 1c 24 | 10 7 7 7 7 | 38 | |
26 27 28 29 30 | 0 4 34(ret) 0 4 34 0 4 34 0 4 34 0 4 34 | 5 2 2 2 2 | 13 |
같은 program flow를 타도 분기 예측 성공 / 실패에 따라 소요 clock이 달라지기 때문에 패턴에 따라 결과도 달라진다.
| 차례 | if 소요 clock | switch 소요 clock |
|---|---|---|
| 1~5(func1) | 8 | 41 |
| 6~10(func2) | 21 | 38 |
| 11~15(func3) | 31 | 38 |
| 16~20(func4) | 41 | 38 |
| 20~25(func5) | 51 | 38 |
| 26~30(ret) | 48 | 13 |
| 합계 | 200 | 206 |
세 번째 비교까지는 if문이 빨랐지만 네 번째 비교부터는 switch가 빨랐다. 그리고 합계를 보면 if가 조금 더 빨랐다.
결과 분석
위에서의 두 가지 패턴을 보면, 첫 번째 패턴은 func1, func2 타는 경우는 if가 빠르고 나머지는 switch가 빨랐다. 두 번째 패턴은 func1 번째 비교까지는 if가 속도가 빠르고 3~나머지 번째 비교는 switch가 속도가 빨랐다. 그리고 전체 속도를 비교하면, 조금 차이지만 첫 번째 패턴은 switch가 빠르고 두 번째 패턴은 if가 빨랐다. 분기 예측 성공 / 실패가 패턴에 따라 다른 결과가 나오기 때문에 func1, fucn2, func3, func4, func5, 아무 함수도 타지 않는 경우가 두 패턴 다 1:1:1:1:1:1로 타는 비율이 같았지만, 패턴에 따라 조금 다른 결과가 나왔다.
if 기준으로 초반 비교일수록 상대적으로 if가 더 빠르고 후반 비교일수록 상대적으로 switch 더 빠르다. 위의 두 가지 패턴 중에서 첫 번째 패턴은 2번째 비교까지는 if가 빠르고 나머지는 switch가 빨랐고, 두번째 패턴은 3번째 비교까지는 if가 빠르고 나머지는 switch가 빨랐다.
그렇다면 성능이 매우 중요한 경우라면, 어느 경우에 if를 쓰고 어느 경우에 switch를 써야 할까? switch는 case 인자가 0, 1, 2, 3, 4 처럼 연속인 경우에는 jump table 이 사용 가능하지만 0, 10, 15, 100 처럼 연속이 아닌 경우에는 jump table을 사용이 어려우므로 case 인자가 연속인 경우만 생각해보자.
위의 결과를 보면 패턴에 따라 다를 수 있지만, 일반적으로 1, 2 번째 비교가 많으면 if를 사용하고 4~나머지 번째 비교가 많으면 switch를 사용하면 될 것이다. 가령 10 군데로 분기하는 경우라면, 균등하게 탄다면 switch가 빠를 것이다. 하지만 if의 1~2 번째 비교문을 90% 타고 10%는 나머지 비교문을 균등하게 탄다면 if가 빠를 것이다.
real CPU에서 if와 switch 중에 어느 걸 써야 할까? 보통은 가독성이 좋은 걸 선택하면 된다. 다만 성능 path라서 조금이라도 빨라야 하는 부분이라면 둘 중에 빠른 걸 써야 한다. 그렇다면 어느 게 빠른지 어떻게 계산할까? 위의 예제에서는 CPU architecture(분기 예측 등) 동작을 임의로 가정해서 정확한 계산이 가능했지만 보통 CPU architecture(분기 예측 등)의 모든 동작이 투명하게 다 공개되지 않기 때문에 정확한 계산은 어렵다. 또한 분기 예측으로 인해 분기를 타는 패턴마다 성능도 다르기 때문에 실제의 패턴으로 성능 측정을 해서 어느 게 더 빠른지 확인해야 한다. 결국 성능을 측정해야 하지만 그래도 if와 switch의 동작을 대략 알면 성능 최적화 시에 효율적으로 할 수 있을 것이다.
메모리 사용량
따로 data 영역으로 잡힌 게 없기 때문에 메모리 사용량은 code 크기만 비교했다.
switch는 jump table까지 포함해서 code 크기를 계산했다. code 크기는 명령어 하나가 4byte이고 jump table entry 하나가 4byte다.
| code 크기 (byte) |
|
|---|---|
| if | 60 |
| switch | 76 |
code 크기는 switch가 if 보다 크다.
1c: 00400793 li a5,4
20: 00f50c63 beq a0,a5,38 <test_if+0x38> # if(param==4),38번지로 분기
코드를 보면 비교가 하나 추가될 때마다 if는 위와 같이 li, beq 명령어가 추가돼서 8byte가 추가되고,
10000010: 00000024 -> j 20010 <func5>
switch는 위와 같이 jump table entry 하나가 추가돼서 4byte가 추가된다.
비교가 하나 추가될 때마다 if가 switch 대비 4byte 더 증가하기 때문에 비교가 4개 추가되면 16byte가 더 증가해서 if와 switch의 code 크기가 같아진다. 즉, 9 군데로 분기하는 경우에는 if와 switch의 code 크기가 같고 10 군데 이상부터는 switch가 더 작다.
정리
switch가 jump table을 사용한 경우만 비교해보자.
성능
if 기준으로 초반 비교일수록 상대적으로 if가 더 빠르고 후반 비교일수록 상대적으로 switch 더 빠르다. 분기 예측으로 인해 분기 타는 패턴에 따라 달라질 수 있지만, 위의 두 가지 패턴에서는 2번째 비교까지는 if가 빠르고, 3번째 비교는 한번은 if가 빠르고 한번은 switch가 빨랐고, 4번째 비교부터는 switch가 빨랐다.
위의 예제에서는 CPU architecture(분기 예측 등) 동작을 임의로 가정해서 정확한 계산이 가능했지만, real CPU는 보통 CPU architecture(분기 예측 등)의 모든 동작이 투명하게 다 공개되지 않기 때문에 정확한 계산은 어렵다. real CPU에서 성능이 매우 중요해서 if와 switch 중에 더 빠른 걸 선택해야 하는 상황이라면 분기 예측으로 인해 분기 패턴에 따라 성능이 달라지기 때문에 실제의 패턴으로 성능을 측정해서 어느 게 더 빠른지 확인해야 한다. 결국 성능을 측정해야 하지만 그래도 if와 switch의 동작을 대략 알면 성능 최적화 시에 효율적으로 할 수 있을 것이다.
code 크기
비교가 추가될 때마다 if는 8byte, switch는 4byte씩 code 크기 증가해서 9 군데로 분기하는 경우에는 code 크기가 같았고, 분기를 9 군데보다 적게 하면 if가 작고, 분기를 9 군데보다 많이 하면 switch가 작다.
* Feedback은 언제나 환영합니다.
Comments
Post a Comment