[C] switch와 점프 테이블
C/C++에서 코드를 짜봤다면, switch가 if-else보다 빠르다는 투의 소문을 종종 들어봤을 것이다.
이게 실제로 근거가 없는 것은 아니지만, 일반적인 응용프로그램 수준에서는 크게 의미가 없는 수준이긴 하다.
임베디드 수준으로 쥐어짜는 최적화가 필요할 때나 고려할만한 최적화 케이스다.
알아둬서 나쁠 것은 없지만 성능 때문에 switch를 쓴다는건 별로 의미없는 짓이다. 보통 switch 같은 다중분기문이 선택되는 이유는 성능보다는 직관성에 있다.
switch문
switch 같은 다중분기문은 if-else와 다르게 진행 방향이 직선적이고, 선후가 중요하지 않기 때문에 좀더 깔끔한 형태로 최적화가 될 수 있다.
그래서 분기의 갯수가 적을때는 큰 차이가 나지는 않지만, 분기가 매우 많은 상황에서는 보통 점프테이블을 통해 O(1) 이동을 사용하기 때문에 더 빠른 성능을 보여준다.
생성된 코드는 아래에서 한번 보겠다.
점프 테이블
점프 테이블, 혹은 branch table은 다중분기 최적화에 쓰이는 주요 기법 중 하나다.
보통 일종의 해시테이블이나 정적배열을 통해서, 조건과 실행 코드를 매칭시키는 것을 말한다.
https://thuc.space/posts/jump_table/
인덱싱으로 거의 바로 이동하다보니, 알고리즘적으로 O(1)을 보장해서 빠를 수 있다.
현대의 대표적인 C 컴파일러들은 case가 많은 switch 코드를 jump table로 바로 변환하곤 한다.
다만 case가 별로 없을 때는 if-else와 거의 비슷하게 뽑는다.
애초에 배열 기반으로 접근하는 간접 점프는 일반 점프보다 최적화가 덜 되기 때문에 아무때나 남발하면 더 느려지기 때문이다.
다중분기문에 대해서 jump table 코드를 생성하는건 C/C++에만 한정된 것은 아니고, Rust, Go, C#, Java 같은 대부분의 컴파일 언어들에 공통된 부분이다. 각 다중분기 조건이 단순한 정수 뿐이면서, case가 매우 많은 경우라면 jump table을 우선적으로 고려해서 최적화한다.
Python, Javascript 같은 인터프리터 환경의 언어들은 그 본질적인 한계 때문에 이러한 최적화 방법론을 사용하지는 못한다.
실습해보기 (GCC)
한번 C 코드를 직접 컴파일해서 결과를 보자. 내 환경은 amd64, linux, gcc다.
아래는 if-else를 사용한 코드다.
#include <stdio.h>
void if_else_example(int value)
{
if (value == 1)
{
printf("Value is 1\n");
}
else if (value == 2)
{
printf("Value is 2\n");
}
else if (value == 3)
{
printf("Value is 3\n");
}
else
{
printf("Value is something else\n");
}
}
int main()
{
int test_value = 2;
if_else_example(test_value);
return 0;
}gcc -O0 -o main main.c
./main
잘 실행된다. 나는 여기서 최적화를 하지 않기 위해 -O0를 줬는데, 사실 안줘도 차이는 없다.
gdb로 들어가서 까보면
우리가 기대한 일반적인 사고방식대로 어셈블리가 뽑혀있다.
+15줄에서 1과 비교해서 아니면 +38줄로 보내고, 맞다면 로직을 처리하고 +99로 이동해서 루프를 탈출한다.
그리고 +38줄에서는 2와 비교해서 똑같이 처리하고, +61줄에서는 3과 비교해서 처리한다.
그리 특별할 것은 없다.
switch도 빌드해보자.
#include <stdio.h>
void switch_example(int value)
{
switch (value)
{
case 1:
printf("Value is 1\n");
break;
case 2:
printf("Value is 2\n");
break;
case 3:
printf("Value is 3\n");
break;
default:
printf("Value is something else\n");
break;
}
}
int main()
{
int test_value = 2;
switch_example(test_value);
return 0;
}
이번엔 뭔가 코드가 많이 달라졌다.
해석하자면,
+15에서는 값이 3이면 3 처리 케이스로 코드를 점프시킨다.
+21에서는 값이 3보다 크면 default 처리 케이스로 점프시킨다.
+27에서는 값이 1이면 1 처리 케이스로 점프시키고
+33에서는 값이 2이면 2 처리 케이스로 점프시킨다.
+39에서는 나머지 케이스를 전부 핸들링하기 위해 default 처리 케이스로 점프시킨다.
이 정도다.
이건 if-else와 코드 생성 형태가 다르긴 하지만, 근본적으로는 단순한 비교->점프의 명령어 집합이 주르륵 나열된 것일 뿐인 포멀한 코드다.
그러니까, 이런 단순한 크기의 분기에 있어서는 jump table을 만들지는 않는 것이다.
점프테이블 유도해보기
이번에는 점프테이블을 생성하도록 유도해보자.
점프테이블이 유효한 동작임을 보장할 정도로 분기를 잔뜩 늘려보겠다.
500개다.
#include <stdio.h>
void switch_example(int value)
{
switch (value)
{
case 1:
printf("Value is 1\n");
break;
case 2:
printf("Value is 2\n");
break;
case 3:
printf("Value is 3\n");
break;
case 4:
printf("Value is 4\n");
break;
case 5:
printf("Value is 5\n");
break;
case 6:
printf("Value is 6\n");
break;
case 7:
printf("Value is 7\n");
break;
case 8:
printf("Value is 8\n");
break;
case 9:
printf("Value is 9\n");
break;
case 10:
printf("Value is 10\n");
break;
case 11:
printf("Value is 11\n");
break;
case 12:
printf("Value is 12\n");
break;
case 13:
printf("Value is 13\n");
break;
case 14:
printf("Value is 14\n");
break;
case 15:
printf("Value is 15\n");
break;
case 16:
printf("Value is 16\n");
break;
case 17:
printf("Value is 17\n");
break;
case 18:
printf("Value is 18\n");
break;
case 19:
printf("Value is 19\n");
break;
case 20:
printf("Value is 20\n");
break;
case 21:
printf("Value is 21\n");
break;
case 22:
printf("Value is 22\n");
break;
case 23:
printf("Value is 23\n");
break;
case 24:
printf("Value is 24\n");
break;
case 25:
printf("Value is 25\n");
break;
case 26:
printf("Value is 26\n");
break;
case 27:
printf("Value is 27\n");
break;
case 28:
printf("Value is 28\n");
break;
case 29:
printf("Value is 29\n");
break;
case 30:
printf("Value is 30\n");
break;
case 31:
printf("Value is 31\n");
break;
case 32:
printf("Value is 32\n");
break;
case 33:
printf("Value is 33\n");
break;
case 34:
printf("Value is 34\n");
break;
case 35:
printf("Value is 35\n");
break;
case 36:
printf("Value is 36\n");
break;
case 37:
printf("Value is 37\n");
break;
...
코드를 생성하는 코드를 짜서 돌렸다. 저 코드에서는 case를 좀 잔뜩 넣긴 했는데, case가 10개만 넘어서 몇십개 단위만 되어도 점프테이블 유도가 되는 것 같더라.
그리고 -O3 옵션을 줘서 적극적인 최적화를 하도록 했다.
이번엔 뭔가 좀 달라졌다.
지금 저 코드처럼 notrack jmp가 있다면 점프테이블 최적화를 적용했다고 볼 수 있다.
하나씩 까보자.
+10줄에서는 499보다 크면 디폴트 레이블로 점프시킨다. 이건 기존과 다르지 않다.
+16줄에서는 기준점이 되는 주소를 rdx 레지스터에 올린다.
+25줄에서는 rax 레지스터에 rdx + rdi(여기서는 입력값 2) * 4의 값을 저장한다. 아마 4를 곱해서 더하는 것이 정수값을 주소 간격으로 치환하기 위한 작업인 것 같다. 기준이 4인건 32비트라서일 것이다.
+29줄에서는 rax 레지스터에 주소값(rdx)을 더한다.
+32줄. 이게 핵심이다. notrack jmp 인스트럭션으로 rax에 저장된 주소값으로 점프한다. 이 순간이 점프테이블의 이동이다.
이처럼, 점프테이블 생성 코드는 이전의 어셈블리 코드들이 조건을 하나하나 체크하면서 내려갔던 것과 다르게 덧셈 연산과 간접 점프만으로 한번에 이동하는 구조를 갖는다.
notrack jmp 자체가 좀 느리긴 한데, case가 충분히 많은 경우에는 case를 다 도는 것보다는 빠르다.
점프테이블의 Soft 구현 (dispatch table)
일반적으로 이런건 컴파일러의 판단에 맡기는게 지혜로운 행동이지만, 드물게는 직접 최적화를 강제하고 싶을 수도 있다.
그냥 간단하게 구현하는 것은 그다지 어렵지는 않다.
배열 하나 깔아서, case 동작을 각각 구현한 함수의 주소를 집어넣으면 된다.
#include <stdio.h>
void _1()
{
printf("Value is 1\n");
}
void _2()
{
printf("Value is 2\n");
}
void _3()
{
printf("Value is 3\n");
}
void _4()
{
printf("Value is 4\n");
}
const void (*function_array[4])() = {_1, _2, _3, _4};
void default_()
{
printf("Value is something else\n");
}
void switch_example(int value)
{
if (value >= 1 && value <= 4)
{
function_array[value - 1]();
}
else
{
default_();
}
}
int main()
{
int test_value = 2;
switch_example(test_value);
return 0;
}
그럼 거의 비슷한 형태로 코드가 형성되고, 동작도 잘 된다.
이러한 구현 방법론을 dispatch table이라고 부르곤 한다.
이외에도 컴파일러 비표준 확장을 사용하는 방법이나 다른 트리키한 방법들이 있긴 하지만, 가장 잘 호환되고 표준적인 방법은 이거인 것 같다.
참조
https://stackoverflow.com/questions/45068614/is-it-faster-in-c-to-use-a-written-jump-table-or-switch-statement
https://thuc.space/posts/jump_table/
https://stackoverflow.com/questions/48017/what-is-a-jump-table
https://www.cipht.net/2017/10/03/are-jump-tables-always-fastest.html
https://forum.pjrc.com/index.php?threads/gcc-switch-when-does-gcc-create-a-jumptable.43327/
https://en.wikipedia.org/wiki/Branch_table#cite_note-1