jamp table, switch case
2023. 11. 10. 14:59ㆍ카테고리 없음
jamp table은 제어권을 다른 특정 위치로 전송하는데 사용되는 추상 데이터 구조이다.
일반적인 경우, 구현이 더 쉽고 빠르게 만들기 위해 제한된 형식에서만 제공된다.
하지만, 모든 case문에 break문이 존재하는데, 이는 각 경우가 서로 독립적인 경우이다. 이러한 독립적인 경우에는 jump table의 전체 기능이 필요하지 않다.
이에, "제한된 jump table'은 효율성을 활용하지만, 각 '액션'이 다른 액션과 독립적일 때 사용된다. 즉, 각 경우가 서로 영향을 주지 않고 독립적으로 동작할 때 사용하여 코드의 효율성을 높일 수 있다.
해당 매핑은 보통 해쉬 테이블이 그 예시이며, jump table과 독립적으로 사용될 수 있다/
jump table의 복잡도는 다음과 같다.
보통은 O(K) 복잡도를 갖지만 최악의 경우 O(N)까지 갖는다.
그 이유는 jump table이 주로 키-값 매칭, 즉 해쉬 테이블로 사용되지만, 다양한 형태를 가질 수 있기 때문이다.
그렇기 때문에 무엇을 조회하는가, 어떻게 구현되어 있는가에 따라 달라질 수있다.
예를 들어, 데이터 구조가 균형 이진 트리라면, O(log n)일 것이다. 또한 해시 테이블의 복잡성은 사용하는 해시 함수와 충돌 처리 방식에 따라 달라진다.
다음은 직접 코드를 제작하여 컴파일 한 어셈블리어이다.
#include <iostream>
int main() {
int choice = 2;
switch (choice) {
case 1:
std::cout << "Choice 1\n";
break;
case 2:
std::cout << "Choice 2\n";
break;
case 3:
std::cout << "Choice 3\n";
break;
case 4:
std::cout << "Choice 3\n";
break;
case 5:
std::cout << "Choice 3\n";
break;
case 6:
std::cout << "Choice 3\n";
break;
case 7:
std::cout << "Choice 3\n";
break;
case 8:
std::cout << "Choice 3\n";
break;
case 9:
std::cout << "Choice 3\n";
break;
case 10:
std::cout << "Choice 3\n";
break;
default:
std::cout << "Invalid Choice\n";
break;
}
return 0;
}
main:
.LFB1559:
push rbp
.seh_pushreg rbp
mov rbp, rsp
.seh_setframe rbp, 0
sub rsp, 48
.seh_stackalloc 48
.seh_endprologue
call __main //c++ 프로그램이 시작될때 실행되는 초기화 코드
mov DWORD PTR -4[rbp], 2 //지역변수로 사용될 메모리 위치에 2를 저장
cmp DWORD PTR -4[rbp], 10 //2가 10보다 큰지 비교
ja .L2 // 만약 2가 10보다 크면 .L2로 점프
mov eax, DWORD PTR -4[rbp]
lea rdx, 0[0+rax*4]
lea rax, .L4[rip] //.L4의 주소를 rax에 로드
mov eax, DWORD PTR [rdx+rax]
cdqe
lea rdx, .L4[rip] //.L4의 주소를 rdx에 로드
add rax, rdx
jmp rax
.section .rdata,"dr"
.align 4
.L4: // jump table
.long .L2-.L4
.long .L13-.L4
.long .L12-.L4
.long .L11-.L4
.long .L10-.L4
.long .L9-.L4
.long .L8-.L4
.long .L7-.L4
.long .L6-.L4
.long .L5-.L4
.long .L3-.L4
.text
.L13: //각의 swich case문
lea rdx, .LC0[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L14
.L12: //각의 swich case문
lea rdx, .LC1[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L14
.L11: //각의 swich case문
lea rdx, .LC2[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L14
.L10: //각의 swich case문
lea rdx, .LC2[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L14
지금 ,.L4부분이 jump table이다. switch case문은 cmp와 jne 명령어를 각 조건문마다 사용하지 않고 jump table을 통해 특정 위치로 이동한다.
#include <iostream>
int main() {
int choice = 2;
if (choice ==1)
std::cout << "Choice 1\n";
else if (choice ==2)
std::cout << "Choice 2\n";
else if (choice ==3)
std::cout << "Choice 3\n";
else if (choice ==4)
std::cout << "Choice 4\n";
else if (choice ==5)
std::cout << "Choice 5\n";
else if (choice ==6)
std::cout << "Choice 6\n";
else if (choice ==7)
std::cout << "Choice 7\n";
else if (choice ==8)
std::cout << "Choice 8\n";
else if (choice ==9)
std::cout << "Choice 9\n";
else if (choice ==10)
std::cout << "Choice 10\n";
return 0;
}
하지만 if문을 사용한 경우 각 if 조건문 마다 cmp 명령어를 사용하여 O(n)의 복잡도를 갖는다.
.lcomm _ZStL8__ioinit,1,1
.def __main; .scl 2; .type 32; .endef
.LC0:
.ascii "Choice 1\12\0"
.LC1:
.ascii "Choice 2\12\0"
.LC2:
.ascii "Choice 3\12\0"
.LC3:
.ascii "Choice 4\12\0"
.LC4:
.ascii "Choice 5\12\0"
.LC5:
.ascii "Choice 6\12\0"
.LC6:
.ascii "Choice 7\12\0"
.LC7:
.ascii "Choice 8\12\0"
.LC8:
.ascii "Choice 9\12\0"
.LC9:
.ascii "Choice 10\12\0"
.text
.globl main
.def main; .scl 2; .type 32; .endef
.seh_proc main
main:
.LFB1559:
push rbp
.seh_pushreg rbp
mov rbp, rsp
.seh_setframe rbp, 0
sub rsp, 48
.seh_stackalloc 48
.seh_endprologue
call __main
mov DWORD PTR -4[rbp], 2
cmp DWORD PTR -4[rbp], 1
jne .L2
lea rdx, .LC0[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L2:
cmp DWORD PTR -4[rbp], 2
jne .L4
lea rdx, .LC1[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L4:
cmp DWORD PTR -4[rbp], 3
jne .L5
lea rdx, .LC2[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L5:
cmp DWORD PTR -4[rbp], 4
jne .L6
lea rdx, .LC3[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L6:
cmp DWORD PTR -4[rbp], 5
jne .L7
lea rdx, .LC4[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L7:
cmp DWORD PTR -4[rbp], 6
jne .L8
lea rdx, .LC5[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L8:
cmp DWORD PTR -4[rbp], 7
jne .L9
lea rdx, .LC6[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L9:
cmp DWORD PTR -4[rbp], 8
jne .L10
lea rdx, .LC7[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L10:
cmp DWORD PTR -4[rbp], 9
jne .L11
lea rdx, .LC8[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L3
.L11:
cmp DWORD PTR -4[rbp], 10
jne .L3
lea rdx, .LC9[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
.L3:
mov eax, 0
add rsp, 48
pop rbp
ret
.seh_endproc
.def __tcf_0; .scl 3; .type 32; .endef
.seh_proc __tcf_0
__tcf_0:
하지만 아래 코드의 어셈블리 코드에서는 jump table을 사용하지 않았다.
그 이유는 컴파일러가 최적화하여 je와 jne 명령어를 통해 각 case에 작접 점프하고 있기 때문이다.
main:
.LFB1559:
push rbp
.seh_pushreg rbp
mov rbp, rsp
.seh_setframe rbp, 0
sub rsp, 48
.seh_stackalloc 48
.seh_endprologue
call __main
mov DWORD PTR -4[rbp], 2
cmp DWORD PTR -4[rbp], 2
je .L2
cmp DWORD PTR -4[rbp], 3
je .L3
cmp DWORD PTR -4[rbp], 1
jne .L4
lea rdx, .LC0[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L5
.L2:
lea rdx, .LC1[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L5
.L3:
lea rdx, .LC2[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
jmp .L5
.L4:
lea rdx, .LC3[rip]
mov rcx, QWORD PTR .refptr._ZSt4cout[rip]
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
nop
.L5:
mov eax, 0
add rsp, 48
pop rbp
ret
.seh_endproc
.def __tcf_0; .scl 3; .type 32; .endef
.seh_proc __tcf_0
__tcf_0:
그렇게 때문에 많은 if 조건문을 사용할때 lookup table을 사용하면 좋다.
아래 예시를 보여주면서 설명하겠다.
#include <iostream>
typedef struct choice
{
char answerName[30];
} Ans
int main()
{
int choice = 2;
Ans tAns[3];
strcpy(tAns[0].answerName, "Choice 1\n");
strcpy(tAns[1].answerName, "Choice 2\n");
strcpy(tAns[2].answerName, "Choice 3\n");
printf("원하는 번호를 입력하세요: ");
scanf("%d", &Input );
if (Inpust <0 || Input >2)
{
puts("Invalid Choice\n");
}
printf("%s\n", tAns[Input].answerName);
return 0;
}
이러한 lookup table은 연산 속도와 가독성이 좋으며 추가하거나 삭제할때도 좋다는 장점이 존재한다.
단점은 고정된 작업만 가능하다는 것이다. 이에, switch case문과 혼용해서 사용한다고 한다.
그래서 보통 구조체보다는 포인터를 이용하여 정보를 가져온다고 한다.
#include <iostream>
typedef int(* PINT_DOUBLEINT)(int, int);
int One
int main()
{
/*미완성*/
}