C++에서의 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;
    }

위 코드의 특징은 case문을 정렬하지 않았고, 중간에 case4를 의도적으로 제거했다. switch문에 담긴 case는 총 6개이다. 디버그 모드로 실행하여 디스어셈블리를 해본 결과이다.

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

다음은 릴리즈 모드에서 실행하여 디스어셈블리를 한 결과이다.

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

switch-case문의 최적화에 대한 정확한 이론은 알 수 없으나, msvc의 경우 switch-case문의 case의 개수가 6개부터 점프테이블을 만들어준다.

다만 여기서 의문이 드는 점은, case 중간 중간을 의도적으로 비었음에도 불구하고 점프 테이블이 잘 만들어진다는 점이다. 즉, 점프 테이블이란 것이 일종의 배열일 것이다. case의 값과 인덱스를 동기화하고, 해당 인덱스에 저장된 값은 주 솟값을 가리키는 그런 배열 말이다. 그런데, 어떻게 중간에 비어도 잘 동작하는 것일까? 아무리 생각해도 떠오르지 않아서 검색을 해보니 다행히 좋은 아티클을 찾을 수 있었다.

요컨대, case가 중간 중간 비는 경우라면 점프 테이블을 2개 만들어서 활용한다는 것이다. 먼저 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로 반환한 매우 큰 값으로 변경되어 비교되고, 동일하게 처리될 것이다.

그러므로, 이 아티클의 내용대로라면, case의 최솟값과 최댓값 사이에 정수가 비어있지 않다면, 점프 테이블 하나를 이용하여 switch-case 문이 최적화될 것이다. 성능을 최대한 향상 시키고 싶다면, 하나의 점프 테이블을 이용하여 연산을 줄이는 것이 나으므로, case의 최솟값과 최댓값 사이의 정수를 비어 두지 않는 것이 좋을 것이다.

7 Likes

좋은 정보네요. switch 최적화 하면 생각나는 이불킥 에피소드하나…

2007년인가 8년인가에, 회사에서, JAVA vs C 런타임 속도에 대한 이야기를 하다가 재미로 내기를 했어요. 위키피디아에있는 버블소트(?) 인가 뭔가를 짜서 동일한 데이터셋으로 비교해서 누가 더 빠른가 로요.

제 옆자리 친구가 자바를 잡았고, 제가 C를 잡았는데… 그냥 나와있는 코드대로 했으면 이기고도 남았을텐데, 괞히 깝친다고, Duff’s device 구현했다가… 처참하게 발린 기억이 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

3 Likes

ㅋㅋㅋㅋ 으악

switch-case 정리하면서 생각해본 점은 “컴파일러의 최적화는 세계제일!!!” 뭐 이런것은 아니고… 오히려 다른 부분이 인상 깊었습니다.

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

위 내용들 다 "지식"으로써는 알고 있었는데, 실제 확인하고 체화한 것은 오늘이 될 것 같습니다.

2 Likes

아 저거 보니, 정말 케이스 많아지는경우는 if else 문보다 스위치로 짜는게 맞겠네요…

저는 1학년대는 스위치 케이스 짜는거 귀찮아서(그당시에는 자동완성이 안되는 비주얼 스튜디오를, 정확히 말하면 자동완성 되는줄 모르고) 스위치문 안쓰고 if else 문으로 도배했는데

요즘 스위치 써서 코딩하니 한결 깔끔하구 이쁘더군요, 거기에 최적화까지라니;;대박