[MSVC] switch-case optimization

 

 

해당 내용은 Visual Studio의 msvc 컴파일러를 기준으로 작성한 글입니다.

( 본인이 사용하는 컴파일러가 해당 최적화를 진행하는 것은 컴파일러 문서를 참조하세요. )

 

 

1. 점프 테이블

 

swtich-case의 어셈블리 코드가 만들어 질 때, 컴파일러는 효율성을 높이기 위해, 여러 조건문을 비교하는 어셈블리를 대신하여 점프 테이블을 만들어서 활용합니다.

이를 통해 Swtich-case 문의 분기를 상수 시간 복잡도로 분기할 수 있습니다.

( 이는 case 값을 정렬하여 작성하였을 때를 기준으로 합니다. 예시를 들어 Case 1, Case 2, Case 3 ... ) 

 

using namespace std;
int main()
{
	
	int val = 0;

	std::cin >> val;


	switch(val)
	{
	case 1:
		cout << "1 value" << '\n';
		break;
	case 2:
		cout << "2 value " << '\n';
		break;
	case 3:
		cout << "3 value " << '\n';
		break;
	case 4:
		cout << "4 value " << '\n';
		break;
	case 5:
		cout << "5 value " << '\n';
		break;
	case 6:
		cout << "6 value " << '\n';
		break;
	default:
		cout << "NULL Value" << '\n';
	}
    
    return 0;
 }

 

이러한 코드의 어셈블리 코드를 확인하면, 다음과 같습니다.

 

MSVC 컴파일러, Release 32Bit

 

 

 

해당 어셈블리를 분석하면 다음과 같습니다.

 

 

eax,dword ptr [esp]  ; 스택에서 값을 가져와 eax 레지스터에 저장
00F4102F  dec           eax                   ; eax 값을 1 감소 (val - 1)
00F41030  cmp         eax,5                ; eax 값을 5와 비교		// 점프 테이블의 인덱스는 0부터 시작함
00F41033  ja          $LN9+7h (0F41066h)   ;    eax가 5보다 크면 기본 케이스로 점프
00F41035  jmp         dword ptr [eax*4+0F41090h]  ; eax*4를 점프 테이블의 시작 주소에 더한 후 해당 주소로 점프

 

 

- ja : 가장 마지막 인덱스인 5번과 비교하여 이보다 크다면, 점프 테이블이 아닌 기본 케이스로 점프합니다.

 

- jmp : 점프 테이블의 인덱스에 포함되는 Val 이라면, 해당 Val * 4(32bit 메모리 주소 크기) 바이트에 해당하는 값을 계산한 후 점프 테이블의 시작 주소인 [0F41090h] 에 더하여 점프합니다. 

 

 

 

의사 코드로 나타낸다면

void switch_example(int x) {
    void (*jumpTable[6])() = {func0, func1, func2, func3, func4, func5};

    if (x >= 0 && x < 6) {
        (*jumpTable[x])();
    } else {
        defaultFunc();
    }
}

 

이런 식으로 표현할 수 있습니다. 

 

 

 

2. 2개의 점프 테이블 

 

만약 case 에 대한 값을 정렬하지 않았을 경우에 컴파일러는 점프 테이블을 2개 만드는 방식을 이용하여 메모리를 절약합니다.

 

만약 이러한 식으로, 상당히 불편한 case 문을 작성한 코드가 있다고 가정 하였을 때...

 

using namespace std;
int main()
{
	
	int val = 0;

	std::cin >> val;


	switch(val)
	{
	case 1:
		cout << "1 value" << '\n';
		break;
	case 333:
		cout << "333 value " << '\n';
		break;
	case 200:
		cout << "200 value " << '\n';
		break;
	case 600:
		cout << "600 value " << '\n';
		break;
	case 800:
		cout << "800 value " << '\n';
		break;
	case 999:
		cout << "999 value " << '\n';
		break;
	default:
		cout << "NULL Value" << '\n';
	}
	
}

 

 

컴파일러는 해당 Switch-Case 문의 점프 테이블을 만들기 위해서 0부터 999개의 인덱스를 가지는 테이블을 만들지 않습니다.

만약 그렇게 된다면, 64비트 기준으로는 1000 * 8 ( 64bit 메모리 주소 크기 )에 해당하는 8000바이트의 메모리 공간을 통해 테이블을 만들어야 합니다.

( 리스트로 만든다면 임의 접근을 할 수 없으니 상수 시간 복잡도로 분기를 할 수 없습니다. )

 

 

우측이 실제 테이블, 좌측은 0~999개의 인덱스 번호만을 가지는 테이블

 

 

둘의 차이는, 우측은 실제 메모리 주소를 가지는 테이블입니다.

좌측은 0~부터 999개의 인덱스 번호를 가지고, 값으로는 메모리 주소가 아닌 실제 메모리 주소를 가지는 테이블의 

인덱스를 가르키는 테이블입니다.

 

이런 식으로 만들게 된다면, 8000바이트의 테이블을 대신하여 1000바이트의 배열을 통해 실제 case의 개수에

맞는 메모리 테이블만을 생성하여 인덱스를 통해 분기할 수 있습니다.

 

 

 

 

https://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

Something You May Not Know About the Switch Statement in C/C++