티스토리 뷰
들어가며
C언어에서 조건문에는 if문, switch문이 있다. 논리적으로 둘은 치환 가능하다. 따라서 무엇을 선택할지에 대해서, 프로그래머의 단순한 "취향차이"로 치부하는 경우가 많다.
하지만, switch문은 컴파일러에 의해 최적화가 적용될 여지가 있다.
컴파일러의 최적화
규칙적인 조건이 많다면, if문이 아닌 switch문으로 작성하는 것이 좋다.
어셈블리어로 변환되는 것을 확인해 보자.
개발환경
- Apple M1 Pro
- MacOS Sonoma 14.3
- C89
- clang
규칙적인 조건의 예시
if_in_regular.c
#include <stdio.h>
void if_in_regular(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 if (value == 4) {
printf("Value is 4\n");
} else if (value == 5) {
printf("Value is 5\n");
} else {
printf("Value is out of range\n");
}
}
switch_in_regular.c
#include <stdio.h>
void switch_in_regular(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;
default:
printf("Value is out of range\n");
}
}
clang -S -o if_in_regular.s if_in_regular.c
clang -S -o switch_in_regular.s switch_in_regular.c
if_in_regular.s
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 14, 0
.globl _if_in_regular ; -- Begin function if_in_regular
.p2align 2
_if_in_regular: ; @if_in_regular
.cfi_startproc
; %bb.0:
sub sp, sp, #32
.cfi_def_cfa_offset 32
stp x29, x30, [sp, #16] ; 16-byte Folded Spill
add x29, sp, #16
.cfi_def_cfa w29, 16
.cfi_offset w30, -8
.cfi_offset w29, -16
stur w0, [x29, #-4]
ldur w8, [x29, #-4]
subs w8, w8, #1
cset w8, ne
tbnz w8, #0, LBB0_2
b LBB0_1
LBB0_1:
adrp x0, l_.str@PAGE
add x0, x0, l_.str@PAGEOFF
bl _printf
b LBB0_15
LBB0_2:
ldur w8, [x29, #-4]
subs w8, w8, #2
cset w8, ne
tbnz w8, #0, LBB0_4
b LBB0_3
LBB0_3:
adrp x0, l_.str.1@PAGE
add x0, x0, l_.str.1@PAGEOFF
bl _printf
b LBB0_14
LBB0_4:
ldur w8, [x29, #-4]
subs w8, w8, #3
cset w8, ne
tbnz w8, #0, LBB0_6
b LBB0_5
LBB0_5:
adrp x0, l_.str.2@PAGE
add x0, x0, l_.str.2@PAGEOFF
bl _printf
b LBB0_13
LBB0_6:
ldur w8, [x29, #-4]
subs w8, w8, #4
cset w8, ne
tbnz w8, #0, LBB0_8
b LBB0_7
LBB0_7:
adrp x0, l_.str.3@PAGE
add x0, x0, l_.str.3@PAGEOFF
bl _printf
b LBB0_12
LBB0_8:
ldur w8, [x29, #-4]
subs w8, w8, #5
cset w8, ne
tbnz w8, #0, LBB0_10
b LBB0_9
LBB0_9:
adrp x0, l_.str.4@PAGE
add x0, x0, l_.str.4@PAGEOFF
bl _printf
b LBB0_11
LBB0_10:
adrp x0, l_.str.5@PAGE
add x0, x0, l_.str.5@PAGEOFF
bl _printf
b LBB0_11
LBB0_11:
b LBB0_12
LBB0_12:
b LBB0_13
LBB0_13:
b LBB0_14
LBB0_14:
b LBB0_15
LBB0_15:
ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
add sp, sp, #32
ret
.cfi_endproc
; -- End function
.section __TEXT,__cstring,cstring_literals
l_.str: ; @.str
.asciz "Value is 1\n"
l_.str.1: ; @.str.1
.asciz "Value is 2\n"
l_.str.2: ; @.str.2
.asciz "Value is 3\n"
l_.str.3: ; @.str.3
.asciz "Value is 4\n"
l_.str.4: ; @.str.4
.asciz "Value is 5\n"
l_.str.5: ; @.str.5
.asciz "Value is out of range\n"
.subsections_via_symbols
switch_in_regular.s
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 14, 0
.globl _switch_in_regular ; -- Begin function switch_in_regular
.p2align 2
_switch_in_regular: ; @switch_in_regular
.cfi_startproc
; %bb.0:
sub sp, sp, #32
.cfi_def_cfa_offset 32
stp x29, x30, [sp, #16] ; 16-byte Folded Spill
add x29, sp, #16
.cfi_def_cfa w29, 16
.cfi_offset w30, -8
.cfi_offset w29, -16
stur w0, [x29, #-4]
ldur w8, [x29, #-4]
subs w8, w8, #1
mov w8, w8
; kill: def $x8 killed $w8
str x8, [sp] ; 8-byte Folded Spill
subs x8, x8, #4
cset w8, hi
tbnz w8, #0, LBB0_7
; %bb.1:
ldr x11, [sp] ; 8-byte Folded Reload
adrp x10, LJTI0_0@PAGE
add x10, x10, LJTI0_0@PAGEOFF
Ltmp0:
adr x8, Ltmp0
ldrsw x9, [x10, x11, lsl #2]
add x8, x8, x9
br x8
LBB0_2:
adrp x0, l_.str@PAGE
add x0, x0, l_.str@PAGEOFF
bl _printf
b LBB0_8
LBB0_3:
adrp x0, l_.str.1@PAGE
add x0, x0, l_.str.1@PAGEOFF
bl _printf
b LBB0_8
LBB0_4:
adrp x0, l_.str.2@PAGE
add x0, x0, l_.str.2@PAGEOFF
bl _printf
b LBB0_8
LBB0_5:
adrp x0, l_.str.3@PAGE
add x0, x0, l_.str.3@PAGEOFF
bl _printf
b LBB0_8
LBB0_6:
adrp x0, l_.str.4@PAGE
add x0, x0, l_.str.4@PAGEOFF
bl _printf
b LBB0_8
LBB0_7:
adrp x0, l_.str.5@PAGE
add x0, x0, l_.str.5@PAGEOFF
bl _printf
b LBB0_8
LBB0_8:
ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
add sp, sp, #32
ret
.cfi_endproc
.section __TEXT,__const
.p2align 2, 0x0
LJTI0_0:
.long LBB0_2-Ltmp0
.long LBB0_3-Ltmp0
.long LBB0_4-Ltmp0
.long LBB0_5-Ltmp0
.long LBB0_6-Ltmp0
; -- End function
.section __TEXT,__cstring,cstring_literals
l_.str: ; @.str
.asciz "Value is 1\n"
l_.str.1: ; @.str.1
.asciz "Value is 2\n"
l_.str.2: ; @.str.2
.asciz "Value is 3\n"
l_.str.3: ; @.str.3
.asciz "Value is 4\n"
l_.str.4: ; @.str.4
.asciz "Value is 5\n"
l_.str.5: ; @.str.5
.asciz "Value is out of range\n"
.subsections_via_symbols
어셈블리어 분석
if_in_regular.s
(라인 15 ~ 라인 20) : 첫 번째 조건 검사
stur w0, [x29, #-4]
ldur w8, [x29, #-4]
subs w8, w8, #1
cset w8, ne
tbnz w8, #0, LBB0_2
b LBB0_1
- stur w0, [x29, #-4]: 입력 값 w0를 스택에 저장한다.
- ldur w8, [x29, #-4]: 스택에서 값을 w8 레지스터로 로드한다.
- subs w8, w8, #1: 값을 1과 비교합니다. 결과가 0이 되면 w0이 1 임을 의미한다.
- cset w8, ne: 비교 결과가 같지 않으면 w8을 1로 설정한다.
- ✅ tbnz w8, #0, LBB0_2: w8이 0이 아니면(w0이 1이 아니면) LBB0_2로 분기한다.
- ✅ b LBB0_1: w0이 1인 경우 LBB0_1으로 분기합니다.
맨 아래 두 줄이 핵심이다!
(라인 21 ~ 라인 25) : LBB0_1 ; 조건이 참일 경우 출력
LBB0_1:
adrp x0, l_.str@PAGE
add x0, x0, l_.str@PAGEOFF
bl _printf
b LBB0_15
다음 블록들도 같은 방식으로 진행되고 있다.
(라인 26 ~ 라인 31): LBB0_2
LBB0_2:
ldur w8, [x29, #-4]
subs w8, w8, #2
cset w8, ne
tbnz w8, #0, LBB0_4
b LBB0_3
결국, 규칙적인 상황이라도 다음 분기로 넘어가는 과정을 모두 수행하고 있다.
switch_in_regular
(라인 70 ~ 라인 75): 분기 테이블 생성
LJTI0_0:
.long LBB0_2-Ltmp0
.long LBB0_3-Ltmp0
.long LBB0_4-Ltmp0
.long LBB0_5-Ltmp0
.long LBB0_6-Ltmp0- LJTI0_0:
- LJTI0_0 레이블은 분기 테이블의 시작을 나타낸다.
- 이 레이블 아래에 각 case에 해당하는 코드 레이블로부터의 오프셋(offset) 값을 나타내는 .long 지시자가 있다.
- .long LBB0_2-Ltmp0:
- 각 .long 지시자는 해당 case 레이블 (LBB0_2, LBB0_3, ...)로 점프할 수 있는 주소 계산을 나타낸다.
- 예를 들어, LBB0_2 레이블로 점프할 때의 주소를 계산합니다. Ltmp0 레이블에서 LBB0_2까지의 오프셋을 계산하여 저장한다.
(라인 25 ~ 라인 27): 초기 세팅
ldr x11, [sp] ; 8-byte Folded Reload
adrp x10, LJTI0_0@PAGE
add x10, x10, LJTI0_0@PAGEOFF
- ldr x11, [sp]:
- 스택에서 값을 x11 레지스터에 로드한다.
- 이 값은 switch 문의 조건 변수의 값이다.
- adrp x10, LJTI0_0@PAGE, add x10, x10, LJTI0_0@PAGEOFF:
- LJTI0_0라는 레이블의 주소를 계산하여 x10에 저장한다.
- LJTI0_0은 분기 테이블을 나타내는 데이터 영역이다.
(라인 28 ~ 라인 32): 점프할 분기 계산
Ltmp0:
adr x8, Ltmp0
ldrsw x9, [x10, x11, lsl #2]
add x8, x8, x9
br x8
- adr x8, Ltmp0:
- 현재 위치의 주소를 x8 레지스터에 저장한다.
- 이 위치는 분기 테이블의 시작 주소로 사용된다.
- ldrsw x9, [x10, x11, lsl #2]:
- x11의 값에 따라 분기할 오프셋을 x10에서 읽어온다.
- x11은 switch 문의 조건 변수이다.
- lsl #2는 x11을 4배로 크기를 증가시켜 오프셋을 계산한다.
- 따라서 x9에는 오프셋에 해당하는 값을 가져온다.
- add x8, x8, x9:
- x8에 Ltmp0의 주소에 x9를 더하여 실제 점프할 주소를 계산한다.
- x9는 ldrsw 명령으로 읽어온 오프셋 값이다.
- ✅ br x8:
- x8에 저장된 주소로 점프한다.
- 이 주소는 switch 문의 각 case 레이블에서 출력 코드로 점프할 위치다.
분기 테이블은 각 case의 코드 주소를 배열 형태로 저장하고, 조건 변수의 값에 따라 이 주소로 점프하여 실행한다.
예를 들어, 조건 변수의 값이 0일 때는 첫 번째 case의 주소로 점프하고, 1일 때는 두 번째 case의 주소로 점프하는 식이다.
만약, 불규칙한 상황이라면?
if_in_irregular.c
#include <stdio.h>
void if_in_irregular(int value) {
if (value == 1) {
printf("Value is 1\n");
} else if (value == 3) {
printf("Value is 3\n");
} else if (value == 5) {
printf("Value is 5\n");
} else {
printf("Value is out of range\n");
}
}
switch_in_irregular.c
#include <stdio.h>
void switch_in_irregular(int value) {
switch (value) {
case 1:
printf("Value is 1\n");
break;
case 3:
printf("Value is 3\n");
break;
case 5:
printf("Value is 5\n");
break;
default:
printf("Value is out of range\n");
}
}
clang -S -o if_in_irregular.s if_in_irregular.c
clang -S -o switch_in_irregular.s switch_in_irregular.c
if_in_irregular.s
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 14, 0
.globl _if_in_irregular ; -- Begin function if_in_irregular
.p2align 2
_if_in_irregular: ; @if_in_irregular
.cfi_startproc
; %bb.0:
sub sp, sp, #32
.cfi_def_cfa_offset 32
stp x29, x30, [sp, #16] ; 16-byte Folded Spill
add x29, sp, #16
.cfi_def_cfa w29, 16
.cfi_offset w30, -8
.cfi_offset w29, -16
stur w0, [x29, #-4]
ldur w8, [x29, #-4]
subs w8, w8, #1
cset w8, ne
tbnz w8, #0, LBB0_2
b LBB0_1
LBB0_1:
adrp x0, l_.str@PAGE
add x0, x0, l_.str@PAGEOFF
bl _printf
b LBB0_9
LBB0_2:
ldur w8, [x29, #-4]
subs w8, w8, #3
cset w8, ne
tbnz w8, #0, LBB0_4
b LBB0_3
LBB0_3:
adrp x0, l_.str.1@PAGE
add x0, x0, l_.str.1@PAGEOFF
bl _printf
b LBB0_8
LBB0_4:
ldur w8, [x29, #-4]
subs w8, w8, #5
cset w8, ne
tbnz w8, #0, LBB0_6
b LBB0_5
LBB0_5:
adrp x0, l_.str.2@PAGE
add x0, x0, l_.str.2@PAGEOFF
bl _printf
b LBB0_7
LBB0_6:
adrp x0, l_.str.3@PAGE
add x0, x0, l_.str.3@PAGEOFF
bl _printf
b LBB0_7
LBB0_7:
b LBB0_8
LBB0_8:
b LBB0_9
LBB0_9:
ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
add sp, sp, #32
ret
.cfi_endproc
; -- End function
.section __TEXT,__cstring,cstring_literals
l_.str: ; @.str
.asciz "Value is 1\n"
l_.str.1: ; @.str.1
.asciz "Value is 3\n"
l_.str.2: ; @.str.2
.asciz "Value is 5\n"
l_.str.3: ; @.str.3
.asciz "Value is out of range\n"
.subsections_via_symbols
switch_in_irregular.s
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 14, 0
.globl _switch_in_irregular ; -- Begin function switch_in_irregular
.p2align 2
_switch_in_irregular: ; @switch_in_irregular
.cfi_startproc
; %bb.0:
sub sp, sp, #32
.cfi_def_cfa_offset 32
stp x29, x30, [sp, #16] ; 16-byte Folded Spill
add x29, sp, #16
.cfi_def_cfa w29, 16
.cfi_offset w30, -8
.cfi_offset w29, -16
stur w0, [x29, #-4]
ldur w8, [x29, #-4]
str w8, [sp, #8] ; 4-byte Folded Spill
subs w8, w8, #1
cset w8, eq
tbnz w8, #0, LBB0_3
b LBB0_1
LBB0_1:
ldr w8, [sp, #8] ; 4-byte Folded Reload
subs w8, w8, #3
cset w8, eq
tbnz w8, #0, LBB0_4
b LBB0_2
LBB0_2:
ldr w8, [sp, #8] ; 4-byte Folded Reload
subs w8, w8, #5
cset w8, eq
tbnz w8, #0, LBB0_5
b LBB0_6
LBB0_3:
adrp x0, l_.str@PAGE
add x0, x0, l_.str@PAGEOFF
bl _printf
b LBB0_7
LBB0_4:
adrp x0, l_.str.1@PAGE
add x0, x0, l_.str.1@PAGEOFF
bl _printf
b LBB0_7
LBB0_5:
adrp x0, l_.str.2@PAGE
add x0, x0, l_.str.2@PAGEOFF
bl _printf
b LBB0_7
LBB0_6:
adrp x0, l_.str.3@PAGE
add x0, x0, l_.str.3@PAGEOFF
bl _printf
b LBB0_7
LBB0_7:
ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
add sp, sp, #32
ret
.cfi_endproc
; -- End function
.section __TEXT,__cstring,cstring_literals
l_.str: ; @.str
.asciz "Value is 1\n"
l_.str.1: ; @.str.1
.asciz "Value is 3\n"
l_.str.2: ; @.str.2
.asciz "Value is 5\n"
l_.str.3: ; @.str.3
.asciz "Value is out of range\n"
.subsections_via_symbols
어셈블리어 분석
불규칙한 상황에서 if문, switch문은 최적화가 발생하지 않는다. 두 코드 덩어리 모두 if_in_regular.s (규칙적 상황에서의 if문 동작)에서처럼 진행한다.
정리
규칙적인 상황에서 컴파일러는 switch 문을 최적화한다.
이에 따른 장점과 단점을 생각해 보자.
- 장점
- 실행 속도가 향상
- 단점
- 분기 테이블의 크기와 메모리 사용량이 비례
당연하게도, 일반적으로 단점보다는 장점으로 얻는 게 많기에, 컴파일러에서 최적화하는 것이겠다.
또한, 일반적인 최적화이므로 C언어 뿐 아니라 대부분의 상용 언어들에는 적용되어 있을 것이라 추측한다.
cf) OpenJDK(11버전) 의 JVM (hotspot) 소스코드 분석
cf) OpenJDK 프로젝트의 JVM인 hotspot에서 switch문에 대해 점프테이블을 생성하는 기능이 있는 것으로 보아 맞을 것이다.
jdk/src/hotspot/share/opto/parse2.cpp at 4ec1ae109710aa150e27acf5706475d335c4655c · openjdk/jdk
JDK main-line development https://openjdk.org/projects/jdk - openjdk/jdk
github.com
Parse::create_jump_tables 함수에서 "조건문이 연속된 정수 범위를 갖고, 점프 테이블이 적절한 크기와 희소성을 가질 때 점프 테이블을 생성"하는 부분은 함수 내 여러 조건들로 확인할 수 있다. (라인 797 ~ 라인 820)
1. 조건문이 연속된 정수 범위를 갖는지 확인 (라인 797 ~ 라인 799)
// Find the total number of cases and ranges
int64_t num_cases = ((int64_t)hi->hi()) - ((int64_t)lo->lo()) + 1;
int num_range = hi - lo + 1;- num_cases 변수는 조건문의 전체 케이스 수를 계산한다. hi->hi()와 lo->lo()는 각각 switch 문의 상한과 하한을 나타낸다. 이 계산을 통해 조건문이 연속된 정수 범위를 갖는지 확인할 수 있다.
2. 점프 테이블의 적절한 크기 확인 (라인 801 ~ 라인 803)
// Don't create table if: too large, too small, or too sparse.
if (num_cases > MaxJumpTableSize)
return false;3. 점프 테이블의 희소성 확인 (라인 819 ~ 라인 820)
if (num_cases > (MaxJumpTableSparseness * num_range))
return false;4. 점프 테이블의 최소 크기 확인 (라인 801 ~ 라인 818)
if (UseSwitchProfiling) {
// MinJumpTableSize is set so with a well balanced binary tree,
// when the number of ranges is MinJumpTableSize, it's cheaper to
// go through a JumpNode that a tree of IfNodes. Average cost of a
// tree of IfNodes with MinJumpTableSize is
// log2f(MinJumpTableSize) comparisons. So if the cost computed
// from profile data is less than log2f(MinJumpTableSize) then
// going with the binary search is cheaper.
if (cost < log2f(MinJumpTableSize)) {
return false;
}
} else {
if (num_cases < MinJumpTableSize)
return false;
}
5. 전체 코드에서 조건 확인 부분
코드 전체적으로 정리하면:
- num_cases가 MaxJumpTableSize를 초과하지 않는지 확인
- num_cases가 MaxJumpTableSparseness * num_range를 초과하지 않는지 확인
- num_cases가 MinJumpTableSize보다 큰지 또는 프로파일링 데이터에 기반하여 적절한 크기인지 확인
"규칙적인"의 상황이란?
"규칙적인"의 상황을 정량적으로 정리해 보자. 연속된 정수를 의미한다고 정리하자.
당연하게도, 문자(아스키코드)와 enum 은 정수로 해석되므로 마찬가지일 것이다.
언제 switch문 쓰고, 언제 if문을 쓸까?
그러면 "무조건 switch문으로 쓰는게 좋은 거 아닐까?"라고 생각이 들었다.
if문보다 성능이 같거나 더 나은 거니깐?! ㅎㅎ
점프테이블로 인한 성능의 향상폭을 정량적으로 구하지 않았지만,
조건의 집합이 커질수록 유리할 것일 것이다. (이 또한 어느 정도라는 규모는 실험해보지 않았음)
따라서 "검사해야할 조건이 많아지고, 그 조건들이 연속된 정수인 상황이라면 switch 문을 쓰자"로 정리 할 수 있겠다
포프TV
유튜브 포프TV에서 아래와 같이 다루고 있다
실무에서 겪은 이야기를 해준다
https://www.youtube.com/watch?v=1Qg-dIh2qGQ
'최적화' 카테고리의 다른 글
| [C언어] 변수는 초기화 시점에 실제 명령어가 작성된다 (0) | 2024.05.21 |
|---|
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- S4
- pocu
- Java
- Spring MVC
- PS
- condition variable
- generic swap
- core c++
- 엔티티 설계 주의점
- sleep lock
- 백준
- servlet
- JPA
- tree
- generic sort
- 이진탐색
- CPU
- OOP
- 개발 공부 자료
- S1
- Memory
- tomcat11
- 객체 변조 방어
- 연관관계 편의 메서드
- 톰캣11
- reader-writer lock
- thread
- Dispatcher Servlet
- C
- 논문추천
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |
글 보관함