개요
조건을 비교하는 경우 조건문 if - else if - else 문 (if문)과, switch case문(switch 문)을 사용한다.
switch case는 나눠서 작성하기 어려워 조건이 많은 경우 코드가 길어지는 단점이 있지만,
if문과 다르게 switch문은 성능 최적화의 여지가 있다.
switch문의 최적화
switch문은 if문과 다르게 조건이 일정한 범위의 값일 경우 switch문을 jump table 방식으로 구성한다.(컴파일러가 생성함)
위와 같이 연속적인 값의 경우 일반적인 조건문의 어셈블리와는 다른 어셈블리가 구성된다.
mov eax,dword ptr [a] -> a(조건에 사용되는 값)을 eax에 넣는다.
mov dword ptr [ebp-0Ch],eax
cmp dword ptr [ebp-0Ch],9 -> 9와 비교한다.
ja $LN19+0Fh (051118Bh) -> 9보다 크다면 분기한다. (051118B는 default가 시작하는 위치)
mov ecx,dword ptr [ebp-0Ch] -> a값을 ecx에 넣는다.
jmp dword ptr [ecx*4+5111A0h] -> jump table을 사용해 이동한다.
5111A0으로 가보면 조건에 따른 코드의 위치가 메모리마다 저장되어 있는 것을 볼 수 있다.
이는 배열처럼 구성되어 인덱스만으로 접근할 수 있다.
따라서 O(1)의 접근 속도로 분기할 수 있다.
if문의 경우 매번 조건을 비교하므로 O(n)이 걸리기 때문에 n이 크면 클 수록 성능이 좋아질 것이다.
jump table을 생성하는지 여러 방법으로 테스트
1. 경우의 수가 적은 경우
case 분기가 3개 이하로 내려가는 경우,
컴파일러는 jump table을 생성하는 대신 cmp je를 통해서 분기한다.
아마도 이게 더 효율적이라고 컴파일러가 판단한 듯 하다.
2. 순서를 건너뛰는 경우
순서를 조금 건너뛰는 경우에는 그대로 점프테이블을 만든다.
다만 중간 중간 비는 영역 (5,6,8,10)의 경우 코드를 빠져나가는 곳의 주소를 할당한다.
결론적으로 12이상이면 분기해서 벗어나고, 범위 내인 경우는 점프테이블을 참조하는 것을 볼 수 있다.
3. 순서를 섞은 경우
섞은 대로 테이블이 생성된다. (마치 case문을 정렬하고 jump table을 생성한 것과 비슷하다)
메모리의 주소값들을 살펴보면 알 수 있다.
4. 복잡하게
지금은 순서도 바꾸고 중간도 크게 비우는 등 여러 행동을 했다. 과연 어떻게 최적화 될까?
switch (a) {
009A1021 8B 45 F4 mov eax,dword ptr [a]
009A1024 89 45 F8 mov dword ptr [ebp-8],eax
009A1027 83 7D F8 20 cmp dword ptr [ebp-8],20h
009A102B 7F 26 jg wmain+43h (09A1053h)
009A102D 83 7D F8 20 cmp dword ptr [ebp-8],20h
009A1031 74 49 je wmain+6Ch (09A107Ch)
009A1033 8B 4D F8 mov ecx,dword ptr [ebp-8]
009A1036 83 C1 09 add ecx,9
009A1039 89 4D F8 mov dword ptr [ebp-8],ecx
009A103C 83 7D F8 10 cmp dword ptr [ebp-8],10h
009A1040 77 6E ja $LN11+7h (09A10B0h)
009A1042 8B 55 F8 mov edx,dword ptr [ebp-8]
009A1045 0F B6 82 CC 10 9A 00 movzx eax,byte ptr [edx+9A10CCh]
009A104C FF 24 85 B8 10 9A 00 jmp dword ptr [eax*4+9A10B8h]
009A1053 83 7D F8 30 cmp dword ptr [ebp-8],30h
009A1057 74 35 je wmain+7Eh (09A108Eh)
009A1059 83 7D F8 4B cmp dword ptr [ebp-8],4Bh
009A105D 74 26 je wmain+75h (09A1085h)
009A105F 81 7D F8 63 02 00 00 cmp dword ptr [ebp-8],263h
009A1066 74 2F je wmain+87h (09A1097h)
009A1068 EB 46 jmp $LN11+7h (09A10B0h)
case 0: a = 0; break;
switch문에서 case 0 사이의 어셈블리 코드이다.
해석해보자.
-> 먼저 조건에 해당하는 a의 값을 불러온다.
-> 그리고 이를 32와 비교한다.
-> 32보다 크다면 분기한다.(09A1053h)
-> 그리고 32와 같다면 분기한다.(09A107Ch)
-> 들어온 값에 9를 더한다.(switch 문 내의 최소값이 -9이므로 offset을 0으로 맞춰주기 위함)
-> 이를 16과 비교한다.(원래는 7)
-> 16보다 크다면 분기한다.(09A10B0h) (7보다 크면서 32보다 작은 case는 없으므로 switch문을 빠져나간다.)
-> edx+9A10CC 주소 안의 값을 eax로 불러온다.
9A10CC 메모리 안
우리가 지금 보고 있는 범위는 -9에서 7이다. offset 9를 더했으므로 0에서 16이다.
빈칸이 많은 넓은 범위를 모두 2번의 예시 처럼 빠져나가는 주소로 할당하는 것은 메모리 낭비이기 때문에
위와 같이 점프테이블의 간접 인덱스를 만들게 된다.
0(-9), 9(0), 10(1), 16(7) 번째 위치를 보면 00, 01, 02, 03 인것을 알 수 있다.
이를 보아 중간중간 채워진 04는 점프테이블에서 해당 범위를 빠져나가는 코드 위치를 가리키고 있을 것이다.
이제 점프테이블을 가지고 있는 9A10B8h을 보자
보다시피 점프테이블이 붙어있는 상태로 각각의 코드 위치를 가리키고 있음을 볼 수 있다.
남은 48, 75, 611은 je cmp를 통해서 분기하는 것도 확인할 수 있다.
아래는 전체 코드, 어셈블리이다.
switch (a) {
009A1021 8B 45 F4 mov eax,dword ptr [a]
009A1024 89 45 F8 mov dword ptr [ebp-8],eax
009A1027 83 7D F8 20 cmp dword ptr [ebp-8],20h
009A102B 7F 26 jg wmain+43h (09A1053h)
009A102D 83 7D F8 20 cmp dword ptr [ebp-8],20h
009A1031 74 49 je wmain+6Ch (09A107Ch)
009A1033 8B 4D F8 mov ecx,dword ptr [ebp-8]
009A1036 83 C1 09 add ecx,9
009A1039 89 4D F8 mov dword ptr [ebp-8],ecx
009A103C 83 7D F8 10 cmp dword ptr [ebp-8],10h
009A1040 77 6E ja $LN11+7h (09A10B0h)
009A1042 8B 55 F8 mov edx,dword ptr [ebp-8]
009A1045 0F B6 82 CC 10 9A 00 movzx eax,byte ptr [edx+9A10CCh]
009A104C FF 24 85 B8 10 9A 00 jmp dword ptr [eax*4+9A10B8h]
009A1053 83 7D F8 30 cmp dword ptr [ebp-8],30h
009A1057 74 35 je wmain+7Eh (09A108Eh)
009A1059 83 7D F8 4B cmp dword ptr [ebp-8],4Bh
009A105D 74 26 je wmain+75h (09A1085h)
009A105F 81 7D F8 63 02 00 00 cmp dword ptr [ebp-8],263h
009A1066 74 2F je wmain+87h (09A1097h)
009A1068 EB 46 jmp $LN11+7h (09A10B0h)
case 0: a = 0; break;
009A106A C7 45 F4 00 00 00 00 mov dword ptr [a],0
009A1071 EB 3D jmp $LN11+7h (09A10B0h)
case 1: a = 1; break;
009A1073 C7 45 F4 01 00 00 00 mov dword ptr [a],1
009A107A EB 34 jmp $LN11+7h (09A10B0h)
case 32: a = 32; break;
009A107C C7 45 F4 20 00 00 00 mov dword ptr [a],20h
009A1083 EB 2B jmp $LN11+7h (09A10B0h)
case 75: a = 75; break;
009A1085 C7 45 F4 4B 00 00 00 mov dword ptr [a],4Bh
009A108C EB 22 jmp $LN11+7h (09A10B0h)
case 48: a = 48; break;
009A108E C7 45 F4 30 00 00 00 mov dword ptr [a],30h
009A1095 EB 19 jmp $LN11+7h (09A10B0h)
case 611: a = 611; break;
009A1097 C7 45 F4 63 02 00 00 mov dword ptr [a],263h
009A109E EB 10 jmp $LN11+7h (09A10B0h)
case -9: a = -9; break;
009A10A0 C7 45 F4 F7 FF FF FF mov dword ptr [a],0FFFFFFF7h
009A10A7 EB 07 jmp $LN11+7h (09A10B0h)
case 7: a = 7; break;
009A10A9 C7 45 F4 07 00 00 00 mov dword ptr [a],7
}
결론
switch문을 만든 경우 컴파일러는 되도록이면 최적화가 반영되는 jump table을 만드려고 한다.
다만 수치가 꼬이면 간접 테이블을 만들거나, je cmp를 그대로 사용한다.
어떻게 만들어지는 지는 숫자 배치에 따라 컴파일러가 판단해 번역하기 때문에 직접 어셈블리 코드를 확인하는 것이 바람직 할 것이다.
'CS > 프밍 잡지식' 카테고리의 다른 글
| 컴퓨터의 시간측정 응용 - FixedUpdate (1) | 2025.07.03 |
|---|---|
| 함수 호출 시 일어나는 일 (0) | 2025.06.29 |
| 컴퓨터로 문자를 표현하는 법 (0) | 2024.12.18 |
