switch-case optimization

switch-case 어셈블리어

컴파일러가 switch-case문을 최적화시킨다는 것은 잘 알려진 사실이다. 최적화 옵션을 끄더라도, 최적화에 대한 힌트를 잘 주면 디버그 모드에서도 switch-case문에 점프 테이블을 만들어서 비교 횟수를 줄여준다. 비교를 줄임으로써, CPU의 파이프라인 기법에 좋은 영향을 줄 수 있다. 디스어셈블리를 쉽게 확인할 수 있는 비주얼 스튜디오를 이용하여 msvc 컴파일러를 이용하여 직접 확인해 보자. 확인을 위해 다음과 같은 코드를 사용하였다.

    switch (val)
    {
    case 2:
        val += 2;
        printf("val : %d\n", val);
        break;
    case 5:
        val += 5;
        printf("val : %d\n", val);
        break;
    case 7:
        val += 7;
        printf("val : %d\n", val);
        break;
    case 6:
        val += 6;
        printf("val : %d\n", val);
        break;
    case 1:
        val += 1;
        printf("val : %d\n", val);
        break;
    case 3:
        val += 3;
        printf("val : %d\n", val);
        break;
        break;
    default:
        printf("wrong state \n");
        break;
    }

위 코드의 특징은 다음과 같다.

• switch문에 담긴 case는 총 6개이다.
• case문을 오름차순으로 정렬하지 않았다.
• case문 중간에 case 4를 제거했다.

 

다음은 디버그 모드로 실행하여 디스어셈블리를 해본 결과이다.

점프테이블을 활용하기위하여 dec나 cmp, ja 명령어가 들어있는 것을 볼 수 있다.

점프 테이블을 활용하기 위해서 mov, dec, ja 명령어 등이 사용되고 있는 것을 알 수 있다. ja명령어의 경우 default문이나 switch문이 끝나는 곳으로 점프하기 위한 것이다. cmp로 6과 비교하는 것은 case에 인자로 오는 정수가 switch-case문의 가장 큰 정수보다 큰지 작은지 비교하기 위한 것이다. 다음은 릴리즈 모드에서 실행하여 디스어셈블리를 한 결과이다.

릴리즈 모드의 어셈블리는 훨씬간단하나 기본은 디버그 모드랑 같다.

디버그 모드에 비교하여 연산이 줄었다는 것을 알 수 있다. 대신, 핵심이 되는 cmp, ja 명령어 그리고 점프 테이블을 이용하기 위한 계산 및 jmp 명령어가 여전히 존재하는 것을 알 수 있다.

점프 테이블 구성

switch-case문의 최적화에 대한 정확한 이론은 알 수 없으나, msvc는 switch-case문의 case의 개수가 6개부터 점프 테이블을 만들어준 것을 확인했다. 의문이 드는 점은 case 중간중간을 의도적으로 비었음에도 불구하고 점프 테이블이 잘 만들어진다는 점이다. 추측컨대, 점프 테이블은 일종의 배열일 것이다. 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++

 

요약하면 case가 중간중간 비는 경우라면 점프 테이블을 2개 만들어서 활용한다는 것이다. 이렇게 하면 점프테이블 하나를 쓰는 것보다 메모리를 아낄 수 있게 된다. 예를 들어, 케이스의 가장 작은 수가 0이고 가장 큰 수가 999인데, 중간중간 많이 비어있는 경우를 생각해 보자. 이를 하나의 점프 테이블로 만들려면 1000 x 8(64비트 운영체제에서 주솟값은 8바이트니까)로 총 8000바이트가 필요하다.

 

점프 테이블을 2개로 만든다고 생각해보자. case에서 호출하는 함수의 가짓수가 10개 정도라면, 점프 테이블은 1000 * 1(unsigned char는 1바이트로 0~255까지 표현 가능)에 주솟값을 가리키는 점프 테이블 10 * 8로 총 1080 바이트를 쓰게 되는 것이다. 첫 번째 점프 테이블의 값은 두 번째 테이블의 인덱스를 가지는 것이다. 점프 테이블을 1개 쓰는 것보다 약 7,000바이트 아끼게 되는 것이다. 항상 점프 테이블을 2개 만드는 것은 아닌 것 같고, 내부 규칙으로 점프 테이블 하나 혹은 두 개 혹은 if else방식으로 치환할 것이다.

 

조금 더 자세히 보자. 아티클의 내용에 따르면, case를 처리하는 코드 블록의 시작점에 해당하는 주소를 저장한 테이블이 하나 있을 것이다. 이 테이블은 [0] = 0x0000, [1]= 0x0008... 이런 식이다. 테이블의 크기는 case의 개수와 같을 것이다. 다른 하나는 case의 가장 작은 값을 0번째 인덱스로 잡고, (가장 큰 값 - 가장 작은 값 + 1)이 테이블의 사이즈가 되는 테이블이다. 이 테이블의 인덱스는 case에 해당하는 정수에 대응하고, 값은 첫 번째 테이블의 인덱스를 따라간다. 즉, 두 번째 테이블의 인덱스를 통하여 얻은 값을 첫 번째 테이블의 인덱스로 써서 값을 얻는다면, case를 처리하는 코드 블록의 시작 주소를 얻을 수 있는 것이다.

 

두 개의 배열을 쓴다.

식으로 나타내보자. case를 처리하는 코드블럭의 시작점을 가진 테이블을 A, case를 인덱스와 대응하는 테이블을 B라고 고 하고, case에 들어온 숫자를 M, switch-case문에서 가장 작은 case를 N이라고 가정한다. 이럴 때, 처리할 주소를 얻을 수 있으려면 A[B[M-N]] 이런 느낌이다.

 

그런데, M이 너무 커서 B 테이블의 사이즈보다 커지면 점프 테이블의 범위를 벗어나게 된다. 그래서 아래와 같은 코드가 필요하다. 여기서는 "dec eax"지만, 가장 작은 case의 숫자가 1이 아니라면, "sub eax,가장 작은 숫자" 이렇게 될 것이다. 그리고 이 값을 "case에서 가장 큰 값 -1"(코드에서는 7-1)과 비교하는 것이다. 이렇게 하면, M이 너무 큰 경우를 거를 수 있다. 마찬가지로 너무 작은 값... 예를 들어 음수 값이 들어오고 case에 음수 값이 없다면, 해당 음수 값은 unsigned int로 반환한 매우 큰 값으로 변경되어 비교되고, 동일하게 처리될 것이다.

점프 테이블에 들어오지 않는다면 default나 switch-case문이 끝나는 곳으로 점프한다.

그러므로, 이 아티클의 내용대로라면, case의 최솟값과 최댓값 사이에 정수가 비어있지 않다면, 점프 테이블 하나를 이용하여 switch-case 문이 최적화될 것이다. 점프 테이블을 두 개 쓰는 게 오히려 메모리를 많이 차지할 수도 있고 점프 한 번을 줄이면 속도에 이득이 있기 때문이다. 즉, 성능을 최대한 향상하고 싶다면, 하나의 점프 테이블을 이용하여 연산을 줄이는 것이 나으므로, case의 최솟값과 최댓값 사이의 정수를 비어 두지 않는 것이 좋을 것이다.

 

점프 테이블을 한 번만 쓸 것이라는 내 고정관념을 버리고 2개를 써서 매우 간단하면서도 효율적인 구현을 한 것이 인상 깊었다. 그리고, 특정 범위 안에 데이터가 있는지 비교할 때, 비교를 2번 하는 것이 아니라, 1번으로도 가능한 것도 재밌었다. 컴파일러의 최적화 옵션이 코드를 어셈블리로 만들 때, 상상 이상의 영향을 끼치는 것을 볼 수 있었다. switch-case문에서 속도를 신경 쓴다면, case의 최솟값과 최댓값 사이를 모두 채워줘야 한다.