if-else와 switch는 뭐가 다를까?
사실 최근 컴파일러에 와서는 차이가 없다.
설명은 20년 전 기준이라고 생각하자.
중요한 건 내부적으로 어떻게 컴파일러가 최적화 해주냐는 것이다
일단 들어온 값이 특정한 값을 리턴하는 함수를 작성해 보자.
아래와 같이 switch문을 작성 해보자.
int test(int n)
{
switch (n)
{
case 0:
return 5;
case 1: // fallthrough
case 2:
case 3:
return 10;
case 5: // fallthrough
case 7:
return 15;
default:
return 0;
}
}
C
복사
이 코드를 if문 처럼 케이스마다 하나하나 비교한다고 생각해보면 너무 비효율적이다.
그렇게 분기가 많이 생기면, CPU 파이프라인에서 그만큼 Stall이 생긴다.
분기예측으로 Stall을 상쇄할 순 있으나,
이런 류의 코드는 분기예측 확률이 높지 않을 가능성이 높을것이다.
굳이 비교할 필요가 없이 테이블을 만들어 한번에 해결할 수 있다.
C언어로 예시를 보자.
int test(int n)
{
const int LUT[8] = { 5, 10, 10, 10, 0, 15, 0, 15 };
if ((unsigned int)n > 7u)
{
return 0;
}
return LUT[n];
}
C
복사
배열 테이블을 만들어 미리 return값을 다 넣어두고,
n이 0-7 범위 밖인 경우를 처리한 뒤,
추가적인 분기 없이 한번에 return 해버린다.
(이걸 주로 LUT(LookUp-Table)라고 부른다)
이렇게 되면 분기가 한 번밖에 생기지 않는다.
그런데 실제로 컴파일러도 이렇게 최적화를 해준다
;Clang x86-64
test(int): # @test(int)
xor eax, eax
cmp edi, 7
ja .LBB0_2
movsxd rax, edi
mov eax, dword ptr [4*rax + .Lswitch.table.test(int)]
.LBB0_2:
ret
.Lswitch.table.test(int):
.long 5 # 0x5
.long 10 # 0xa
.long 10 # 0xa
.long 10 # 0xa
.long 0 # 0x0
.long 15 # 0xf
.long 0 # 0x0
.long 15 # 0xf
C
복사
보면 아까 c에서 LUT를 만든 것과 같이,
컴파일러도 테이블을 만든다.
테이블 범위 이외는 default로 0 반환.
테이블 범위 이내는 바로 테이블 값으로 바로 반환.
n이 0~7만 무조건 들어온다고 가정한다면
맨 앞의 cmp를 없애 더욱 최적화 시킬 수 있겠다.
C언어 코드를 바꿔보자.
#include <assert.h>
#define NDEBUG
int test(int n)
{
switch (n)
{
case 0:
return 5;
case 1: // fallthrough
case 2:
case 3:
return 10;
case 4: // fallthrough
case 6:
return 0;
case 5: // fallthrough
case 7:
return 15;
default:
__builtin_unreachable(); //GCC hint
// or __assume(0); //MSVC hint
// or assert(0);
}
}
C
복사
이러면 컴파일러는 0-7 이외 다른 값이 들어오지 않는다 가정하고
release 빌드에서 범위를 체크하는 cmp를 없앤다.
test(int): # @test(int)
movsxd rax, edi
lea rcx, [rip + .Lswitch.table.test(int)]
mov eax, dword ptr [rcx + 4*rax]
ret
.Lswitch.table.test(int):
.long 5 # 0x5
.long 10 # 0xa
.long 10 # 0xa
.long 10 # 0xa
.long 0 # 0x0
.long 15 # 0xf
.long 0 # 0x0
.long 15 # 0xf
C
복사
이렇게 분기를 아예 없애버려서 성능을 많이 올릴 수 있다.
사실 요즘엔 if-else 도 컴파일러가 알아서 결정해서 이 방식으로 최적화 해버린다.
그래도 내부 최적화가 어떻게 진행되는지 안다면,
위처럼 default 케이스를 제거하는 식으로 컴파일러에게 적극적인 성능향상 힌트를 제공할 수 있다.
+Jump table
물론 LUT를 값으로만 사용하는것이 아닌
주소로 사용하여 점프테이블로 사용할 수도 있다.
대충 이런식.
lea rbx, <jmp_table>
mov eax, [rbx + rcx * 8]
jmp [eax]
.jmp_table
.DQ 0x80000000 # <switch_case0>
.DQ 0x12345678 # <switch_case1>
.DQ 0x98763263 # <switch_case2>
Assembly
복사
